Bevezetés az operációs rendszerekbe

Szia Habr! Szeretném figyelmébe ajánlani egy véleményem szerint érdekes irodalom - az OSTEP - cikk-fordításait. Ez az anyag meglehetősen mélyen tárgyalja a unix-szerű operációs rendszerek munkáját, nevezetesen a folyamatokkal, különféle ütemezőkkel, memóriával és más hasonló összetevőkkel való munkát, amelyek egy modern operációs rendszert alkotnak. Az összes anyag eredetijét itt tekintheti meg itt. Kérem, vegye figyelembe, hogy a fordítás szakszerűtlenül (elég szabadon) készült, de remélem, megtartottam az általános jelentést.

A témában végzett labormunkák itt találhatók:

Egyéb alkatrészek:

Megnézheted a csatornámat is a címen távirat =)

Tervezés: Többszintű visszajelzési sor

Ebben az előadásban az egyik leghíresebb megközelítés kidolgozásának problémáiról lesz szó
tervezés, amelyet ún Többszintű visszajelzési sor (MLFQ). Az MLFQ ütemezőt először 1962-ben Fernando J. Corbató írta le az ún.
Kompatibilis időmegosztási rendszer (CTSS). Ezek a munkák (beleértve a későbbi munkákat is
Multics) ezt követően Turing-díjra jelölték. Az ütemező az volt
ezt követően továbbfejlesztették és elnyerték azt a megjelenést, amely már megtalálható
néhány modern rendszer.

Az MLFQ algoritmus 2 alapvető átfedő problémát próbál megoldani.
Először, igyekszik optimalizálni az átfutási időt, amit – ahogy az előző előadásban is tárgyaltuk – a sor élén induló módszerrel optimalizálunk.
rövid feladatok. Az operációs rendszer azonban nem tudja, hogy ez vagy az a folyamat meddig fut, és ez
SJF, STCF algoritmusok működéséhez szükséges ismeretek. Másodszor, MLFQ próbálkozik
tegye a rendszert reagálóvá a felhasználók számára (például azok számára, akik ülnek és
a képernyőt bámulva a feladat befejezésére várva), és így minimalizálja az időt
válasz. Sajnos az olyan algoritmusok, mint az RR, csökkentik a válaszidőt, de
rossz hatással vannak az átfutási idő mutatójára. Ezért a problémánk: Hogyan tervezzünk
ütemező, amely megfelel a követelményeinknek, és ugyanakkor semmit sem tud róla
a folyamat természete általában? Hogyan tanulhatja meg az ütemező a feladatok jellemzőit,
amelyet elindít, és ezáltal jobb ütemezési döntéseket hoz?

A probléma lényege: Hogyan tervezzük meg a feladatok kitűzését tökéletes tudás nélkül?
Hogyan tervezzünk olyan ütemezőt, amely egyidejűleg minimalizálja a válaszidőt
interaktív feladatokhoz, és egyben minimálisra csökkenti az átfutási időt anélkül, hogy tudná
a feladat-végrehajtási idő ismerete?

Megjegyzés: tanulni a korábbi eseményekből

Az MLFQ-sor kiváló példa egy olyan rendszerre, amelyre betanították
múltbeli események a jövő előrejelzésére. Az ilyen megközelítések gyakran
megtalálható az operációs rendszerben (és a számítástechnika sok más ágában, beleértve az ágakat is
hardveres előrejelzések és gyorsítótárazási algoritmusok). Hasonló túrák
akkor vált ki, ha a feladatoknak viselkedési fázisai vannak, és így előre láthatóak.
Ezzel a technikával azonban óvatosnak kell lenni, mert az előrejelzések nagyon egyszerűek.
tévesnek bizonyulhat, és a rendszert rosszabb döntések meghozatalához vezetheti
egyáltalán tudás nélkül lenne.

MLFQ: Alapvető szabályok

Tekintsük az MLFQ algoritmus alapvető szabályait. És bár ennek az algoritmusnak a megvalósításai
több van, az alapvető megközelítések hasonlóak.
Az általunk figyelembe vett megvalósítás során az MLFQ-nak több lesz
külön várólisták, amelyek mindegyikének más-más prioritása lesz. Bármikor,
a végrehajtásra kész feladat ugyanabban a sorban van. Az MLFQ prioritásokat használ,
eldönteni, hogy melyik feladatot fussanak végrehajtásra, azaz. feladat magasabb
prioritás (egy feladat a legmagasabb prioritású sorból) indul el először
sorban.
Természetesen egy adott sorban több feladat is lehet, tehát
így ugyanaz lesz az elsőbbségük. Ebben az esetben a mechanizmust használják
RR az indítási tervezés ezen feladatok között.
Így az MLFQ két alapvető szabályához jutunk el:

1. szabály: Ha prioritás(A) > Prioritás(B), akkor az A feladat fut (B nem)
2. szabály: Ha prioritás(A) = prioritás(B), az A&B az RR használatával indul

A fentiek alapján az MLFQ tervezésének kulcselemei a következők
prioritások. Ahelyett, hogy mindegyiknek fix prioritást adna
feladat esetén az MLFQ a megfigyelt viselkedéstől függően megváltoztatja a prioritását.
Például, ha egy feladat folyamatosan kilép a CPU-n, miközben a billentyűzet bevitelére vár,
Az MLFQ magasan tartja a folyamat prioritását, mert így
Az interaktív folyamatnak működnie kell. Ha éppen ellenkezőleg, a feladat folyamatosan és
hosszú ideig CPU-igényes, az MLFQ leminősíti
prioritás. Így az MLFQ a folyamatok viselkedését fogja vizsgálni futásuk idején.
és használati magatartásokat.
Rajzoljunk példát arra, hogyan nézhetnek ki a sorok valamikor
idő és akkor valami ilyesmit kapsz:

Ebben a sémában 2 A és B folyamat van a legmagasabb prioritású sorban. Folyamat
C valahol a közepén, a D folyamat pedig a sor legvégén van. A fentiek szerint
Az MLFQ algoritmus leírásainál az ütemező csak a legmagasabb értékkel hajtja végre a feladatokat
RR szerinti elsőbbség, és a C, D feladatok munka nélkül maradnak.
Természetesen egy statikus pillanatkép nem ad teljes képet az MLFQ működéséről.
Fontos megérteni, hogy a kép hogyan változik az idő múlásával.

1. kísérlet: A prioritás megváltoztatása

Ezen a ponton el kell döntenie, hogy az MLFQ hogyan módosítja a prioritási szintet
feladat (és így a feladat pozíciója a sorban) életciklusa során. Mert
ebből szem előtt kell tartania a munkafolyamatot: egy bizonyos összeget
interaktív feladatok rövid futási idővel (és így gyakori kiadással
CPU) és számos hosszú feladat, amelyek teljes munkaidejükben a CPU-t használják, miközben
az ilyen feladatok válaszideje nem fontos. És így megteheti az első kísérletet
implementálja az MLFQ algoritmust a következő szabályokkal:

3. szabály: Amikor egy feladat belép a rendszerbe, akkor a legmagasabb értékkel rendelkező sorba kerül
kiemelten fontos.
4a szabály: Ha egy feladat a teljes időablakot használja, akkor azt
a prioritás csökken.
4b szabály: Ha egy Task felszabadítja a CPU-t az időablak lejárta előtt, akkor azt
ugyanazzal a prioritással marad.

1. példa: Egyetlen hosszan futó feladat

Amint ebben a példában látható, a felvételi feladat a legmagasabb értékkel van beállítva
kiemelten fontos. 10 ms-os időablak után a folyamat prioritása alacsonyabb lesz.
ütemező. A következő időablak után a feladat végül visszaminősítésre kerül
legalacsonyabb prioritású a rendszerben, ahol marad.

2. példa: Felvett egy rövid feladatot

Most lássunk egy példát arra, hogy az MLFQ hogyan próbálja megközelíteni az SJF-et. Abban
például két feladat: A, ami egy hosszan futó feladat folyamatosan
CPU és B elfoglalása, ami egy rövid interaktív feladat. Tegyük fel
hogy A már egy ideje futott, mire a B feladat megérkezett.

Ez a grafikon a forgatókönyv eredményeit mutatja. Az A feladat, mint minden feladat,
a CPU használata a legalján volt. A B feladat T=100 időpontban érkezik és meg fog
a legmagasabb prioritású sorba kerül. Mivel a működési idő rövid,
az utolsó sor elérése előtt befejeződik.

Ebből a példából meg kell értenie az algoritmus fő célját: mivel az algoritmus nem
tud egy hosszú vagy egy rövid feladatot, akkor mindenekelőtt azt feltételezi, hogy a feladat
rövid, és a legmagasabb prioritást adja neki. Ha ez tényleg rövid feladat, akkor
gyorsan végrehajtja, különben ha hosszú feladatról van szó, lassan halad
prioritás le, és hamarosan bebizonyítja, hogy ő valóban egy hosszú feladat, hogy nem
választ igényel.

3. példa: Mi a helyzet az I/O-val?

Most nézzünk egy I/O példát. A 4b szabályban foglaltak szerint
ha egy folyamat felszabadítja a processzort anélkül, hogy teljesen felhasználta volna a processzor idejét,
akkor ugyanazon a prioritási szinten marad. Ennek a szabálynak a célja meglehetősen egyszerű.
- ha az interaktív munka sok I/O-t hajt végre, például vár
a felhasználói billentyűleütésektől vagy az egértől, egy ilyen feladat felszabadítja a processzort
a kijelölt ablak előtt. Nem szeretnénk kihagyni egy ilyen kiemelt feladatot,
és így ugyanazon a szinten marad.

Ez a példa bemutatja, hogyan működne az algoritmus ilyen folyamatokkal - interaktív B feladat, amelynek csak 1 ms-ig van szüksége a CPU-ra a végrehajtás előtt
I/O folyamat és egy hosszú A feladat, amely folyamatosan a CPU-t használja.
Az MLFQ továbbra is a B folyamatot tartja a legmagasabb prioritáson
engedje el a CPU-t. Ha B egy interaktív feladat, akkor az algoritmus ebben az esetben elérte
célja az interaktív feladatok gyors elindítása.

Problémák a jelenlegi MLFQ algoritmussal

Az előző példákban elkészítettük az MLFQ alapverzióját. És úgy tűnik, hogy ő
jól és tisztességesen végzi a dolgát, igazságosan elosztva a CPU-időt között
hosszú feladatokat, és lehetővé teszi a rövid vagy erősen hozzáférhető feladatokat
I/O-ra a gyors feldolgozás érdekében. Sajnos ez a megközelítés több dolgot is tartalmaz
komoly problémákat.
Először, az éhség problémája: ha a rendszerben sok interaktív lesz
feladatokat, akkor az összes CPU-időt elfogyasztják, így egyetlen hosszú időt sem
a feladat nem kap lehetőséget a végrehajtásra (éheznek).

Másodszor, az okos felhasználók megírhatnák a programjaikat úgy, hogy
becsapja az ütemezőt. A megtévesztés abban rejlik, ha valamit azért teszünk, hogy erőltessenek
ütemezőt, hogy több CPU-időt biztosítson a folyamatnak. Az algoritmus, hogy
A fent leírtak meglehetősen érzékenyek az ilyen támadásokra: az időablak előtt gyakorlatilag
vége, végre kell hajtania egy I / O műveletet (egyeseknél, függetlenül attól, hogy melyik fájl)
és így felszabadítja a CPU-t. Az ilyen viselkedés lehetővé teszi, hogy ugyanazon maradjon
maga a sor, és ismét nagyobb százalékban kapja meg a CPU-időt. Ha kész
ez helyes (például futtassa az ablakidő 99%-át a CPU felszabadítása előtt),
egy ilyen feladat egyszerűen monopolizálhatja a processzort.

Végül egy program idővel megváltoztathatja viselkedését. Azok a feladatok
amelyek a CPU-t használták, interaktívvá válhatnak. Példánkban hasonló
feladatokat az ütemező nem fogja megfelelően kezelni, ahogy azt mások tennék
(eredeti) interaktív feladatok.

Kérdés a közönséghez: milyen támadások érhetik az ütemezőt a modern világban?

2. kísérlet: Növelje a prioritást

Próbáljunk meg változtatni a szabályokon, és nézzük meg, elkerülhetjük-e a problémákat
éhezés. Mit tehetünk annak érdekében, hogy ez összefüggjön
A CPU-feladatok megkapják az idejüket (még ha nem is sokáig).
A probléma egyszerű megoldásaként rendszeresen javasolhat
növelje az összes ilyen feladat prioritását a rendszerben. Számos módja van
ennek eléréséhez próbáljunk meg valami egyszerű példát megvalósítani: a fordítást
minden feladat egyszerre a legmagasabb prioritású, ezért az új szabály:

Rule5: Bizonyos S időszak után helyezze át a rendszerben lévő összes feladatot a legmagasabb sorba.

Új szabályunk egyszerre két problémát old meg. Először is a folyamatok
garantáltan nem éhezik: a legmagasabb sorban lévő feladatok megoszlanak
processzoridőt az RR algoritmus szerint, és így minden folyamat megkapja
processzoridő. Másodszor, ha valamilyen folyamat, amely korábban használt
csak a processzor válik interaktívvá, az marad a legmagasabb sorban
prioritást, miután egyszer kapott a legmagasabb prioritásra.
Nézzünk egy példát. Ebben a forgatókönyvben fontoljon meg egyetlen folyamatot

CPU és két interaktív, rövid folyamat. Az ábra bal oldalán az ábra a prioritásnövelés nélküli viselkedést mutatja, így a hosszan futó feladat éhezni kezd, miután két interaktív feladat érkezik a rendszerbe. A jobb oldali ábrán 50 ms-onként prioritásnövekedés történik, így garantáltan minden folyamat megkapja a processzoridőt, és rendszeresen elindul. Ebben az esetben az 50 ms-t vesszük példaként, a valóságban ez a szám valamivel magasabb.
Nyilvánvaló, hogy az S periodikus emelkedési idő összeadása oda vezet
logikus kérdés: milyen értéket kell beállítani? Az egyik jól megérdemelt
A rendszermérnökök John Outterhout voo-doo néven hivatkozott hasonló mennyiségekre a rendszerekben
állandó, mivel valamilyen módon fekete mágiát igényeltek a helyes használathoz
kitettség. És sajnos az S-nek ilyen íze van. Ha beállítod az értéket is
nagy - hosszú feladatok kiéheznek. És ha túl alacsonyra állítod,
Az interaktív feladatok nem kapnak megfelelő CPU-időt.

3. kísérlet: Jobb könyvelés

Most még egy problémát kell megoldanunk: hogyan ne
megengedjük, hogy átverjük az ütemezőnket? Ennek a lehetőségnek a bűnösei azok
4a, 4b szabályok, amelyek lehetővé teszik, hogy egy job megtartsa prioritását a processzor felszabadításával
a megadott idő lejárta előtt. Hogyan kezeljük?
A megoldás ebben az esetben az egyes CPU-idő jobb elszámolása tekinthető
MLFQ szint. Ahelyett, hogy elfelejtené a program által használt időt
processzort a kijelölt intervallumra, vegye figyelembe és mentse el. Után
a folyamat elhasználta a rászabott idejét, le kell lépni a következőre
prioritási szint. Most már nem számít, hogy a folyamat hogyan fogja felhasználni idejét – hogyan
folyamatosan számít a processzoron vagy híváskészletként. És így,
a 4. szabályt a következőképpen kell átírni:

Rule4: Miután egy feladat felhasználta az aktuális sorban lefoglalt idejét (függetlenül attól, hogy hányszor szabadította fel a CPU-t), az ilyen feladat prioritása csökken (lefelé mozog a sorban).

Nézzünk egy példát:
»

Az ábra azt mutatja, hogy mi történik, ha megpróbálja becsapni az ütemezőt
ha az előző 4a szabály szerint lenne, akkor a 4b eredmény lenne a bal oldalon. Újjal
a szabály az, hogy az eredmény a jobb oldalon van. A védelem előtt bármely folyamat meghívhatja az I/O-t a befejezés előtt és
így uralják a CPU-t a védelem engedélyezése után, a viselkedéstől függetlenül
I/O, továbbra is le fog állni a sorban, és így nem tud tisztességtelenül
átveszi a CPU erőforrásait.

Az MLFQ és egyéb problémák javítása

A fenti fejlesztésekkel új problémák merülnek fel: az egyik fő
kérdések - hogyan lehet paraméterezni egy ilyen ütemezőt? Azok. Mennyi legyen
sorok? Mekkora legyen a programablak a sorban? Hogyan
programot gyakran prioritásként kell kezelni, hogy elkerüljük az éhezést és
figyelembe venni a program viselkedésében bekövetkezett változást? Ezekre a kérdésekre nincs egyszerű megoldás
válasz, és csak kísérletek a terhelésekkel és az azt követő konfigurációval
Az ütemező kielégítő egyensúlyhoz vezethet.

Például a legtöbb MLFQ-megvalósítás lehetővé teszi különböző hozzárendeléseket
idősávok a különböző sorokhoz. A magas prioritású sorok általában
rövid időközönként. Ezek a sorok interaktív feladatokból állnak,
amelyek közötti váltás meglehetősen érzékeny, és 10 vagy kevesebb ideig tarthat
Kisasszony. Ezzel szemben az alacsony prioritású várólisták hosszú ideig futó feladatokból állnak, amelyek használnak
CPU. És ebben az esetben a hosszú időintervallumok nagyon jól illeszkednek (100 ms).

Ebben a példában 2 feladat működik a 20-as magas prioritású sorban
ms 10 ms-os ablakokra osztva. 40 ms a középső sorban (20 ms ablak) és az alacsony prioritású sorban
A várakozási időablak 40 ms lett, ahol a feladatok befejezték a munkájukat.

Az MLFQ megvalósítása a Solaris operációs rendszerben az időmegosztásos ütemezők egy osztálya.
Az ütemező táblázatokat biztosít, amelyek pontosan meghatározzák, hogyan kell
változtassa meg a folyamat prioritását az élettartama során, mekkora legyen a méret
kiosztandó ablakot és azt, hogy milyen gyakran kell emelni a feladat prioritásait. Adminisztrátor
rendszer kölcsönhatásba léphet ezzel a táblával, és az ütemezőt viselkedésre készteti
eltérően. Alapértelmezés szerint ebben a táblában 60 sor van, fokozatos növekedéssel
ablakméret 20 ms-tól (magas prioritás) több száz ms-ig (legalacsonyabb prioritás), és
az összes feladat másodpercenkénti egyszeri növelésével is.

Más MLFQ-ütemezők nem használnak táblát vagy semmilyen konkrétat
az ebben a fejezetben leírt szabályok, éppen ellenkezőleg, a prioritásokat a segítségével számítják ki
matematikai képletek. Például a FreeBSD ütemezője a következő képletet használja
az aktuális feladatprioritás kiszámítása az alapján, hogy mennyi a folyamat
használta a CPU-t. Ráadásul a CPU-használat idővel romlik, és így
Így a prioritás növelése némileg eltér a fent leírtaktól. Ez igaz
roncsolási algoritmusoknak nevezzük. A 7.1-es verziótól kezdve a FreeBSD az ULE ütemezőt használja.

Végül sok tervező más funkciókkal is rendelkezik. Például néhány
az ütemezők magasabb szinteket tartanak fenn az operációs rendszer működéséhez és így
Így egyetlen felhasználói folyamat sem kaphatja meg a legmagasabb prioritást
rendszer. Egyes rendszerek lehetővé teszik, hogy tanácsot adjon a segítséghez
az ütemező a helyes prioritás meghatározásához. Például a parancs használatával szép
növelheti vagy csökkentheti egy feladat prioritását, és így növelheti vagy csökkentheti
csökkenti a program esélyét a CPU-időre.

MLFQ: Összegzés

Leírtunk egy MLFQ nevű tervezési megközelítést. Neve
működési elvben levonható - több sora van és visszacsatolást használ
feladat fontossági sorrendbe állításához.
A szabályok végleges formája a következő lesz:

Rule1: Ha prioritás(A) > Prioritás(B), akkor az A feladat fut (B nem)
Rule2: Ha prioritás(A) = prioritás(B), az A&B az RR használatával indul
Rule3: Amikor egy feladat belép a rendszerbe, a legmagasabb prioritású sorba kerül.
Rule4: Miután egy feladat felhasználta az aktuális sorban lefoglalt idejét (függetlenül attól, hogy hányszor szabadította fel a CPU-t), az ilyen feladat prioritása csökken (lefelé mozog a sorban).
Rule5: Bizonyos S időszak után helyezze át a rendszerben lévő összes feladatot a legmagasabb sorba.

Az MLFQ a következő ok miatt érdekes - ahelyett, hogy tudást igényelne
A feladat jellegétől függően az algoritmus megtanulja a feladat múltbeli viselkedését és halmazait
ennek megfelelően prioritásokat. Így megpróbál egyszerre két széken ülni - hogy kisebb feladatokat (SJF, STCF) érjen el, és őszintén fusson hosszú feladatokat,
CPU-betöltési feladatok. Ezért számos rendszer, beleértve a BSD-t és származékait,
A Solaris, a Windows és a Mac valamilyen algoritmust használ ütemezőként
MLFQ mint kiindulópont.

További anyagok:

Forrás: will.com

Operációs rendszerek: Három Easy Pieces. 5. rész: Tervezés: Többszintű visszajelzési sor (fordítás)