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 =)

Bevezetés az ütemezőbe

A probléma lényege: Hogyan készítsünk ütemező házirendet
Hogyan kell megtervezni az alapul szolgáló ütemező házirend-kereteket? Mik legyenek a legfontosabb feltételezések? Milyen mutatók fontosak? Milyen alapvető technikákat használtak a korai számítástechnikai rendszerekben?

Munkaterhelési feltételezések

A lehetséges irányelvek megvitatása előtt először tegyünk néhány egyszerűsítő kitérőt a rendszerben futó folyamatokról, amelyeket összefoglaló ún. munkaterhelés. A munkaterhelés meghatározása az építési szabályzatok kritikus része, és minél többet tud a terhelésről, annál jobb házirendet írhat.

Tegyük fel a következő feltevéseket a rendszerben futó, néha ún munkahelyek (feladatok). Szinte ezek a feltételezések nem reálisak, de szükségesek a gondolkodás fejlődéséhez.

Minden feladat ugyanannyi ideig fut,
Minden feladatot egyszerre állítunk be,
A kijelölt feladat a befejezésig működik,
Minden feladat csak CPU-t használ,
Az egyes feladatok futási ideje ismert.

Ütemező metrikák

A terhelésre vonatkozó néhány feltételezés mellett egy másik eszközre van szükség a különböző ütemezési szabályzatok összehasonlításához: az ütemező metrikáira. A mérőszám csak valami mértékegysége. Számos mérőszám használható az ütemezők összehasonlítására.

Például egy mérőszámot fogunk használni, melynek neve átfutási idő (átfutási idő). A feladat átfutási ideje a feladat befejezési ideje és a rendszerbe való beérkezési idő közötti különbség.

Tturnaround=Tbefejezés–Tarrival

Mivel azt feltételeztük, hogy minden feladat egyszerre érkezett, akkor Ta=0 és így Tt=Tc. Ez az érték természetesen változik, ha megváltoztatjuk a fenti feltevéseket.

Egy másik mérőszám - méltányosság (tisztesség, őszinteség). A termelékenység és a méltányosság gyakran ellentétes jellemzők a tervezésben. Például az ütemező optimalizálhatja a teljesítményt, de annak az árán, hogy megvárja, amíg más feladatok futnak, így csökkentve a méltányosságot.

FIRST IN FIRST OUT (FIFO)

A legalapvetőbb algoritmus, amit megvalósíthatunk, a FIFO ill első beérkezés, első kiszolgálás. Ennek az algoritmusnak több előnye is van: nagyon könnyen megvalósítható, és minden feltételezésünknek megfelel, és elég jól végzi a munkáját.

Nézzünk egy egyszerű példát. Tegyük fel, hogy egyszerre 3 feladatot tűztek ki. De tegyük fel, hogy az A feladat valamivel korábban érkezett meg, mint az összes többi, tehát korábban jelenik meg a végrehajtási listában, mint a többi, csakúgy, mint B a C-hez képest. Tegyük fel, hogy mindegyik 10 másodpercig lesz végrehajtva. Ebben az esetben mennyi lesz az átlagos idő ezen feladatok elvégzésére?

A -10+20+30 értékeket megszámolva és 3-mal osztva 20 másodpercnek megfelelő átlagos programvégrehajtási időt kapunk.
Most próbáljunk meg változtatni a feltételezéseinken. Konkrétan az 1. feltevés, így többé nem fogjuk azt feltételezni, hogy minden feladat végrehajtása ugyanannyi időt vesz igénybe. Hogyan fog teljesíteni ezúttal a FIFO?

Mint kiderült, a különböző feladat-végrehajtási idők rendkívül negatív hatással vannak a FIFO algoritmus termelékenységére. Tételezzük fel, hogy az A feladat végrehajtása 100 másodpercet vesz igénybe, míg B és C továbbra is 10 másodpercet vesz igénybe.

Amint az ábrán látható, a rendszer átlagos ideje (100+110+120)/3=110 lesz. Ezt a hatást ún konvoj hatás, amikor egy erőforrás néhány rövid távú fogyasztója sorban áll egy erős fogyasztó után. Olyan ez, mint a sorban állás az élelmiszerboltban, amikor egy vevő áll előtted teli kosárral. A probléma legjobb megoldása az, ha megpróbálja lecserélni a pénztárgépet, vagy lazítani és mélyeket lélegezni.

Először a legrövidebb munka

Meg lehet valahogy oldani egy hasonló helyzetet nehézsúlyú folyamatokkal? Biztosan. A tervezés egy másik fajtája az únElőször a legrövidebb munka (SJF). Algoritmusa is meglehetősen primitív - ahogy a neve is sugallja, a legrövidebb feladatok indulnak el először, egymás után.

Ebben a példában ugyanazon folyamatok futtatásának eredménye a program átlagos átfutási idejének javulása lesz, és egyenlő lesz 50 helyett 110, ami majdnem 2-szer jobb.

Így arra az adott feltételezésre, hogy minden feladat egyszerre érkezik, az SJF algoritmus tűnik a legoptimálisabb algoritmusnak. Feltételezéseink azonban továbbra sem tűnnek reálisnak. Ezúttal megváltoztatjuk a 2. feltevést, és ezúttal elképzeljük, hogy a feladatok bármikor jelen lehetnek, és nem egyszerre. Milyen problémákhoz vezethet ez?

Képzeljük el, hogy az A (100c) feladat érkezik először, és elkezdődik a végrehajtás. t=10-nél megérkeznek a B és C feladatok, amelyek mindegyike 10 másodpercet vesz igénybe. Tehát az átlagos végrehajtási idő (100+(110-10)+(120-10))3 = 103. Mit tehetne az ütemező ennek javítására?

Először a legrövidebb befejezési idő (STCF)

A helyzet javítása érdekében figyelmen kívül hagyjuk azt a 3. feltevést, hogy a program elindult és a befejezésig fut. Ezen kívül szükségünk lesz hardveres támogatásra, és ahogy sejtheti, használni is fogjuk időzítő futó feladat megszakítására és kontextusváltás. Így az ütemező a B, C feladatok érkezésének pillanatában tehet valamit - leállítja az A feladat végrehajtását, és feldolgozásba helyezi a B és C feladatokat, és azok befejeződése után folytathatja az A folyamat végrehajtását. Az ilyen ütemezőt ún. STCFvagy Megelőző munka az első.

Ennek a tervezőnek az eredménye a következő lesz: ((120-0)+(20-10)+(30-10))/3=50. Így egy ilyen ütemező még optimálisabbá válik feladataink számára.

Metrikus válaszidő

Így, ha ismerjük a feladatok futási idejét és azt, hogy ezek a feladatok csak CPU-t használnak, az STCF lesz a legjobb megoldás. És valamikor a korai időkben ezek az algoritmusok egészen jól működtek. A felhasználó azonban ideje nagy részét a terminálon tölti, és produktív interaktív élményt vár. Így született meg egy új mérőszám - válaszidő (válasz).

A válaszidő kiszámítása a következőképpen történik:

Tresponse=Tfirstrun-Tarrival

Így az előző példában a válaszidő a következő lesz: A=0, B=0, C=10 (abg=3,33).

És kiderül, hogy az STCF algoritmus nem olyan jó olyan helyzetben, amikor 3 feladat érkezik egyszerre - meg kell várnia, amíg a kis feladatok teljesen elkészülnek. Tehát az algoritmus jó az átfutási idő mérőszámához, de rossz az interaktivitás mérőszámához. Képzelje el, ha egy terminálnál ülve próbál karaktereket beírni egy szerkesztőbe, és több mint 10 másodpercet kellene várnia, mert valami más feladat veszi igénybe a CPU-t. Nem túl kellemes.

Tehát egy másik problémával kell szembenéznünk – hogyan építhetünk fel olyan ütemezőt, amely érzékeny a válaszidőre?

Round Robin

A probléma megoldására algoritmust fejlesztettek ki Round Robin (RR). Az alapötlet meglehetősen egyszerű: a feladatok befejezéséig történő futtatása helyett a feladatot egy bizonyos ideig futtatjuk (úgynevezett időszelet), majd átváltunk egy másik feladatra a sorból. Az algoritmus addig ismétli a munkáját, amíg minden feladatot el nem végez. Ebben az esetben a program futási idejének többszörösének kell lennie annak az időnek, amely után az időzítő megszakítja a folyamatot. Például, ha egy időzítő megszakít egy folyamatot minden x=10 ms-ban, akkor a folyamat-végrehajtási ablak méretének 10 többszörösének kell lennie, és 10,20 vagy x*10-nek kell lennie.

Nézzünk egy példát: Az ABC feladatok egyszerre érkeznek a rendszerbe, és mindegyik 5 másodpercig akar futni. Az SJF algoritmus minden feladatot a befejezésig befejez, mielőtt újabbat kezdene. Ezzel szemben az RR algoritmus egy indítóablak = 1s a következőképpen megy végig a feladatokon (4.3. ábra):

(Újra SJF (rossz válaszidő)

(Round Robin (Jó válaszidő)

Az átlagos válaszidő az RR algoritmusnál (0+1+2)/3=1, míg az SJF-nél (0+5+10)/3=5.

Logikus az a feltételezés, hogy az időablak nagyon fontos paraméter az RR számára, minél kisebb, annál nagyobb a válaszidő. Nem szabad azonban túl kicsire tenni, mivel a kontextusváltási idő is szerepet játszik az általános teljesítményben. Így a végrehajtási ablak idejét az operációs rendszer tervezője határozza meg, és az attól függ, hogy milyen feladatokat terveznek benne végrehajtani. A kontextusváltás nem az egyetlen szolgáltatási művelet, amely időt veszít – a futó program sok más dolgot is működtet, például különféle gyorsítótárakat, és minden váltásnál el kell menteni és vissza kell állítani ezt a környezetet, ami szintén sok időt vesz igénybe. idő.

Az RR nagyszerű ütemező, ha csak a válaszidő mérőszámáról beszélünk. De hogyan fog viselkedni a feladat átfutási idejének mutatója ezzel az algoritmussal? Tekintsük a fenti példát, amikor A, B, C működési ideje = 5s és egyszerre érkezik. Az A feladat 13-kor, a B 14-kor, a C 15-kor ér véget, és az átlagos átfutási idő 14 másodperc lesz. Így az RR a legrosszabb algoritmus a forgalmi mérőszámhoz.

Általánosabban fogalmazva, bármely RR-típusú algoritmus tisztességes: egyenlően osztja el a CPU-időt az összes folyamat között. Így ezek a mutatók folyamatosan ütköznek egymással.

Így számos ellentétes algoritmusunk van, ugyanakkor még mindig több feltételezés maradt - hogy a feladat ideje ismert, és a feladat csak a CPU-t használja.

Keverés I/O-val

Először is távolítsuk el a 4. feltevést, amely szerint a folyamat csak a CPU-t használja; természetesen ez nem így van, és a folyamatok hozzáférhetnek más berendezésekhez.

Abban a pillanatban, amikor bármely folyamat I/O műveletet kér, a folyamat blokkolt állapotba kerül, és várja az I/O befejezését. Ha I/O-t küld a merevlemezre, akkor egy ilyen művelet akár több ms-ig vagy tovább is tarthat, és a processzor ebben a pillanatban tétlen lesz. Ez idő alatt az ütemező bármilyen más folyamattal lefoglalhatja a processzort. A következő döntést az ütemezőnek kell meghoznia, hogy mikor fejezi be a folyamat az I/O-t. Amikor ez megtörténik, megszakítás történik, és az operációs rendszer kész állapotba helyezi az I/O-t hívó folyamatot.

Nézzünk egy példát több feladatra. Mindegyikhez 50 ms CPU-idő szükséges. Az első azonban 10 ms-onként hozzáfér az I/O-hoz (ami szintén 10 ms-onként kerül végrehajtásra). A B processz pedig egyszerűen egy 50 ms-os processzort használ I/O nélkül.

Ebben a példában az STCF ütemezőt fogjuk használni. Hogyan fog viselkedni az ütemező, ha olyan folyamat indul el rajta, mint az A? A következőt fogja tenni: először teljesen kidolgozza az A, majd a B folyamatot.

A probléma megoldásának hagyományos megközelítése az, hogy az A folyamat minden 10 ms-os részfeladatát külön feladatként kezeljük. Így az STJF algoritmussal kiindulva kézenfekvő a választás egy 50 ms-os és egy 10 ms-os feladat között. Ezután, amikor az A részfeladat befejeződött, elindul a B folyamat és az I/O. Az I/O befejezése után szokás lesz a 10 ms-os A folyamat újraindítása a B helyett. Így lehetséges az átfedés megvalósítása, ahol a CPU-t egy másik folyamat használja, miközben az első a I/O. Ennek eredményeként a rendszer jobban kihasználható - abban a pillanatban, amikor az interaktív folyamatok I/O-ra várnak, más folyamatok is végrehajthatók a processzoron.

Az Oracle nincs többé

Most próbáljunk megszabadulni attól a feltételezéstől, hogy a feladat futási ideje ismert. Általában ez a legrosszabb és legirreálisabb feltevés az egész listán. Valójában az átlagos rendes operációs rendszerben maga az operációs rendszer általában nagyon keveset tud a feladatok végrehajtási idejéről, tehát hogyan építhet fel ütemezőt anélkül, hogy tudná, mennyi ideig tart a feladat végrehajtása? Talán használhatunk néhány RR-elvet a probléma megoldására?

Teljes

Megnéztük a feladatütemezés alapötleteit, és megvizsgáltunk 2 ütemező családot. Az első a legrövidebb feladatot indítja el először, és ezzel megnöveli az átfutási időt, míg a második egyformán szakad az összes feladat között, növelve a válaszidőt. Mindkét algoritmus rossz, ahol a másik család algoritmusai jók. Azt is megvizsgáltuk, hogy a CPU és az I/O párhuzamos használata hogyan javíthatja a teljesítményt, de ez nem oldotta meg a problémát az operációs rendszer tisztánlátásával. A következő leckében pedig egy olyan tervezőt fogunk megvizsgálni, amely a közvetlen múltba tekint, és megpróbálja megjósolni a jövőt. És ezt többszintű visszajelzési sornak hívják.

Forrás: will.com

Operációs rendszerek: Három Easy Pieces. 4. rész: Bevezetés az ütemezőbe (fordítás)