Ugrás a tartalomhoz

Operációs rendszerek mérnöki megközelítésben

Benyó Balázs, Fék Márk, Kiss István, Kóczy Annamária, Kondorosi Károly, Mészáros Tamás, Román Gyula, Szeberényi Imre, Sziray József

Panem Kiadó

3.3. Folyamatkezelés

3.3. Folyamatkezelés

A 2. fejezetben tárgyalt folyamatmodell feltételezte, hogy minden folyamat a saját különálló processzorán fut. A multiprogramozott rendszerekben azonban egyetlen processzor több folyamatot futtat. A következőkben azzal foglalkozunk, hogy hogyan teszi mindezt.

3.3.1. A folyamatmodell leképezése a fizikai eszközökre

A folyamatmodell feltételezte, hogy a rendszer minden folyamata saját processzoron fut, és saját memóriája van. A multiprogramozott rendszerben egyetlen fizikai processzoron és egyetlen, lineárisan címezhető fizikai memóriában kell megvalósítani a folyamatok működtetését. A modell leképezésének legfontosabb kérdéseit tárgyaljuk a következőkben.

3.3.1.1. A működés alapjai

A folyamat megismert modellje mind multiprogramozott, mind multipro­cesszáló rendszerekben használható. A folyamatok kezelésével kapcsolatos feladatok természetesen különbözőek a két rendszertípus esetén, hiszen a modell megvalósítása a különböző rendszerarchitektúrákon egymástól lényegesen különböző problémákat vet fel. Általában igaz, hogy a multiprocesszáló rendszerekben a folyamatok száma meghaladja a processzorok számát, emiatt ilyenkor is megoldandó az egyes processzorok multiprogramozott működtetése (és emellett természetesen a processzorok együttműködésével kapcsolatos feladatok is). A folyamatok kezelésének alapvető kérdéseit a következőkben multiprogramozott esetre tárgyaljuk, a multiprocesszálás esetére csak utalunk, illetve egyes kérdéseinek külön fejezetet szánunk.

Egy multiprogramozott operációs rendszer minden időpillanatban folyamatok egy csoportjának végrehajtásával foglalkozik, amelyeket egyetlen fizikai processzoron futtat. A multiprogramozás foka a rendszerben egy adott pillanatban jelenlévő – tehát megkezdett, de még be nem fejezett – folyamatok száma.

Az operációs rendszer egyik alapvető feladata az erőforrás-gazdálkodás és –kiosztás. A két alapvető erőforrás a processzor (CPU) és a memória. Ezek kiosztása még együttműködő folyamatok esetén is általában a versengés elvén történik, hiszen a folyamatok kódjában rendszerint nem jelenik meg külön utasítás ezek lefoglalására, illetve felszabadítására.

Amikor egy folyamat létrejön a rendszerben, létrejön számára egy logikai memória és egy logikai processzor, amelyekhez fizikai megfelelőket kell rendelni.

A logikai memória létrehozása a fizikai rendszer tekintetében azt jelenti, hogy a folyamat megkapja a fizikai tár egy részét, ahova a kódja és változói (vagy legalább is azok egy futáshoz éppen szükséges része) megfelelő kezdőértékekkel betöltődnek. Elvileg a logikai memóriához a háttértár valamely területe is hozzárendelhető, az éppen futó folyamat végrehajtandó utasításának azonban mindenképpen a memóriában kell lennie (hiszen a háttértárról való betöltés a processzorsebességhez képest rendkívül lassú). A processzorért emiatt csak azok a folyamatok versenyezhetnek, amelyek következő végrehajtandó kódrésze a memóriában van.

A logikai processzorok látszólag párhuzamosan működnek. Valójában az egyetlen fizikai processzor egyidejűleg egyetlen folyamat utasításait tudja végrehajtani. Ha a fizikai processzor elég gyakran átkapcsol egy folyamat egy részletének végrehajtása után egy másik folyamatra úgy, hogy mindegyik elég gyakran jusson szóhoz, akkor egy durvább időléptékben a folyamatok futása párhuzamosnak látszik. A dolgot úgy is felfoghatjuk, hogy a rendszer legfontosabb egyedi erőforrása a fizikai processzor, amelyet egyidejűleg egyetlen folyamat használhat, és amelyhez tartozik egy várakozási sor, ahol a többi, processzorra váró folyamat tartózkodik. A processzor felszabadulásakor az operációs rendszer választja ki valamilyen algoritmussal a sorban várakozók közül azt a folyamatot, amelyik a következő időszakra megkapja a processzort (CPU-ütemezés).

A folyamatok tipikus szerkezete olyan, hogy egy processzor által végrehajtott utasítássorozatot – processzorlöket (CPU-burst) – egy B/K-művelet – be-/kiviteli löket (I/O-burst) – követ, és ez a két fázis ismétlődik ciklikusan. A be-/kiviteli művelet végrehajtása a megszakításos, vagy DMA jellegű szervezés miatt gyakorlatilag csak a perifériát (és időszakosan a be/kivitelben résztvevő vezérlő egységeket és adatutakat) köti le és nem veszi igénybe a CPU-t. Egy folyamat be-/kiviteli műveleteinek végrehajtása közben a CPU így más folyamat futtatásával foglalkozhat. Ekkor természetesen lehetséges, hogy a működő perifériára egy közben futó folyamat újabb be/kiviteli műveletet kezdeményez, és ez többször is ismétlődhet. Tehát a perifériákért is versenyeznek a folyamatok, azokat is egyedi erőforrásoknak kell tekinteni, a rájuk várakozó folyamatokat sorba kell állítani, ütemezni kell stb. Amikor egy be/kiviteli művelet befejeződött, a műveletet kezdeményező folyamat ismét a CPU-ért versenyez, hogy következő processzorlökete végrehajtódhasson.

A rendszer folyamatai különbözhetnek abban a tekintetben, hogy futásuk során milyen arányban használják a CPU-t és a B/K-eszközöket. Vannak folyamatok, amelyeket intenzív CPU-használat, és mérsékelt B/K-igény jellemez. Ilyenek például a numerikus közelítő módszerekkel dolgozó egyenletmegoldások, és minden olyan program, amelyik sok számítást végez viszonylag kevés adattal. Más folyamatok alig használnak CPU-t, de annál intenzívebb a B/K-tevékenységük. Ilyenek például a formátum-átalakítást végző konverziós programok. A CPU-használat és B/K-használat aránya alapján megkülönböztetünk CPU-intenzív, illetve B/K-intenzív folyamatokat. Az erőforrások jó kihasználásának feltétele, hogy egy adott időszakban a CPU-intenzív folyamatok és a B/K-intenzív folyamatok száma kiegyenlített legyen a rendszerben.

Az operációs rendszer az elvégzendő feladatok végrehajtását valamilyen szempontból optimalizálni igyekszik. Ez lehet például kötegelt feldolgozás esetén az áteresztőképesség, vagy a processzor-kihasználás maximalizálása, egy feladat átlagos átfutási idejének minimalizálása stb., interaktív rendszerek esetén az átlagos válaszidő minimalizálása, valósidejű rendszerek esetén a határidő-mulasztások minimalizálása, és még sok más jellemző. A megfogalmazott célokhoz igazítják azokat az algoritmusokat, amelyek döntenek új folyamatok beengedéséről a rendszerbe (új job indulása, új felhasználó belépése), a multiprogramozás fokának változtatásáról (növelés vagy csökkentés), az egyes folyamatoknak kiosztott memóriaterület méretéről, és amelyek ütemezik az erőforrásokat.

Az operációs rendszer folyamatkezelését két modellel szemléltetjük. Az egyik egy tömegkiszolgálási modell, az ún. sorállási modell (grafikus ábrázolása a sorállási diagram), amelyik a folyamatok erőforrás-használatára koncentrál, a másik egy állapotmodell (grafikus ábrázolása az állapotdiagram), amelyik a folyamatok végrehajtásának menetére koncentrál.

3.3.1.2. Sorállási modell

A sorállási modell korlátos erőforráskészletért versengő folyamatok rendszerének elemzésére alkalmas. A modell a sorállási diagramon szemléltethető. A modell addig áttekinthető, amíg azoknak az erőforrásoknak a használatát szemléltetjük vele, amelyeket a folyamatok szekvenciálisan használnak, azaz elengedik a birtokolt erőforrást, mielőtt újat igényelnének.

Az operációs rendszerek tipikus sorállási diagramját a 3.4. ábra mutatja. A diagram a processzorlöket, B/K-löket ciklikusságot szemlélteti azzal a feltételezéssel (ami normális működés esetén általában teljesül), hogy a folyamatoknak közben folyamatosan elegendő memória áll rendelkezésükre.

3.4. ábra. ábra - Sorállási diagram

Sorállási diagram


Az erőforrásokat körök, a várakozási sorokat téglalapok jelölik. A rendszer működését a folyamatok irányított élek mentén történő vándorlása szemlélteti. Az új, induló folyamatok processzorlökettel kezdődnek, ezért a CPU várakozási sorába lépnek be. Normál befejeződés esetén ugyancsak processzorlöketből lépnek ki. Közben a be-/kiviteli műveleteiktől függően kerülnek át a különböző perifériák várakozási soraiba, illetve lesznek a perifériák használói. Egy be-/kiviteli löket után ismét a CPU várakozási sorába kerülnek vissza.

A modell számításokra is alkalmas változata valószínűségi változókat és eloszlásfüggvényeket használ a terhelés (a folyamatok rendszerbe történő belépésének időbeli gyakorisága) és a kiszolgálás (az erőforrások birtoklásának időszükséglete) jellemzésére. A valószínűségi modell kiértékelése alapján adott struktúrára, adott terhelési és kiszolgálási paraméterek mellett számíthatók a rendszer fontos működési jellemzőinek (például átfutási idő, várakozási idő, sorhosszúság) várható értékei, illetve egyéb valószínűségi jellemzői.

A diagramon jól azonosíthatók az ütemezési pontok, amelyek tipikusan a várakozási sorok kimenetén helyezkednek el. Kivétel a rendszerbe való bejutást szabályozó ún. hosszú távú ütemező, amelyik tipikusan a kötegelt feldolgozást végző rendszerekben van jelen, és új jobok végrehajtásának megkezdéséről (új folyamatok indításáról) dönt. Az elvégzésre váró munkák közül a választás szempontja, hogy a rendszerben a CPU-intenzív és B/K-intenzív folyamatok aránya optimális legyen (optimális job-mix fenntartása). Jó tehát, ha a rendszernek van előzetes információja egy-egy munka CPU-, illetve B/K-igényéről.

Kitüntetett szerepe van a CPU-ütemezőnek, amit általában rövid távú ütemezőnek hívnak, és amelynek algoritmusait külön fejezetben tárgyaljuk. (A rövid, illetve hosszú távú elnevezés a futási gyakoriságra utal. A hosszú távú ütemező általában akkor fut le, amikor egy job végrehajtása befejeződik. A rövid távú ütemező pedig biztosan lefut, amikor egy processzorlöket befejeződik. A két gyakoriság között több nagyságrend különbség van). A perifériák ütemezése a leggyakrabban érkezési sorrendben (FIFO) történik. Kivétel például a mágneslemez, amelynek hatékony ütemezésével ugyancsak foglalkozunk a későbbiekben.

Néhány rendszerben működik középtávú ütemező is, amelynek egyik szerepe a multiprogramozás fokának változtatása jellegzetesen azokban a helyzetekben, amikor a memória válik a rendszer szűk keresztmetszetévé, illetve ez a helyzet megszűnik. A középtávú ütemező – észlelve a memóriaszűkét – egyes folyamatokat felfüggeszt, memóriaterületüket háttértárra menti és felszabadítja, átmenetileg kivonja őket az erőforrásokért folytatott versengésből. A felfüggesztett folyamatok memóriaterületét a többi folyamat használhatja. Később, ha a terhelés csökken, a felfüggesztett folyamatok visszatölthetők és folytathatják működésüket. A felfüggesztendő, illetve visszatöltendő folyamatok kiválasztásának szempontja is a CPU-intenzív és B/K-intenzív folyamatok kiegyensúlyozása lehet, ami már nemcsak előzetes információkra, hanem a folyamatok korábbi viselkedésére is alapozhat. A középtávú ütemező akkor is felfüggeszthet folyamatot, ha az várhatóan igen hosszú várakozásra kényszerül. A középtávú ütemező helye nem mutatható meg a diagramon, mert a memória használata és a memóriaigény növekedése más erőforrások (CPU) használata közben lép fel, az erőforrás-használat nem szekvenciális, ezért a modell ennek leírására ebben a formában nem alkalmas.

3.3.1.3. Állapotmodell

Egy folyamat végrehajtásának dinamikáját a multiprogramozott rendszerekben egy hozzárendelt állapotjelzővel és az állapotátmeneti gráffal írhatjuk le.

Az állapotátmeneti gráf legegyszerűbb változatát a 3.5. ábra mutatja be.

3.5. ábra. ábra - Multiprocesszoros rendszerek logikai tömbvázlata

Multiprocesszoros rendszerek logikai tömbvázlata


Futásra kész (ready) állapotban vannak azok a folyamatok, amelyeknek következő műveletét a CPU bármikor végrehajthatná. Másszóval a CPU-n kívül minden más erőforrást birtokolnak, amire működésük adott szakaszában szükségük van.

Futó (running) állapotban egy multiprogramozott rendszerben egyidejűleg egyetlen folyamat lehet, amelyiknek az aktuális műveletét a CPU éppen végrehajtja.

Várakozó (waiting, blocked) állapotban vannak azok a folyamatok, amelyek nem tudják használni a CPU-t, mert valamilyen feltétel teljesülésére várakoznak. Ilyen feltétel lehet például egy általuk kezdeményezett be-/kiviteli művelet befejeződése, együttműködő folyamatok esetén valamilyen szinkro­ni­zációs vagy kommunikációs művelet végrehajtódása.

Állapotátmenetek

Amikor a folyamat létrejön, megkapja a fizikai memória egy területét, ahova betöltődik a kódja, vagy legalább is annak az induláshoz szükséges része, létrejönnek a változói, esetleg más erőforrásokat, indítási paramétereket kaphat. Az operációs rendszer nyilvántartásba veszi, és futásra kész állapotba állítja, hogy végrehajtása megkezdőzhessen.

Futásra kész => futó állapotátmenet történik, amikor az operációs rendszer CPU-ütemezője kiválasztja a folyamatot végrehajtásra. Új futó folyamat kiválasztása mindenképpen szükséges, ha az előző folyamat befejezte működését, vagy várakozó állapotba került, hiszen ilyenkor a CPU felszabadul.

Futó => futásra kész állapotátmenet két ok miatt fordul elő.

  • Az operációs rendszer elveszi a processzort a folyamattól (preemptív ütemezés). Amikor a CPU-ütemező nem érkezési sorrendben hajtja végre a futásra kész folyamatokat, hanem például prioritás szerinti sorrendben, akkor előfordulhat, hogy egy folyamat futása közben egy nála magasabb prioritású másik folyamat átlép várakozó állapotból futásra kész állapotba. Ha a prioritás azonnali érvényesítése fontosabb szempont, mint egyszerűen a CPU munkában tartása, akkor a futó folyamatot meg kell szakítani, vissza kell léptetni futásra kész állapotba, és a magasabb prioritású folyamatot kell futásra kiválasztani.

  • A folyamat lemond a processzorról (újraütemezést kér). Együttműködő folyamatok kooperatív viselkedésének egyik formája, hogy nem­preemptív ütemezés esetén egy folyamat hosszú processzorlöketek közben, meghatározott pontokon lehetőséget ad más folyamatok futására.

Futó => várakozó állapotátmenet akkor következik be, ha a folyamat olyan műveletet indított, amelynek végrehajtása várhatóan hosszabb (más folyamat futtatására kihasználható idejű) CPU-tétlenséget okozna. Ilyenek a be-/kiviteli műveletek, az erőforrás-foglalások, ha az erőforrás foglalt, a szemaforra kiadott várakozások, ha a szemafor tilosat jelez, az üzenetfogadások, ha az üzenet még nem érkezett meg stb.

Várakozó => futásra kész állapotátmenet történik, ha a folyamat által várt esemény bekövetkezik (például az elindított be/kivitel befejeződik, az erőforrás felszabadul, a szemaforra jelzés érkezik, az üzenet megérkezik stb.).

A folyamatok működésüket akkor fejezik be, amikor utolsó utasításuk végrehajtódik. Ez normális esetben egy olyan rendszerhívás (például exit), aminek hatására az operációs rendszer felszabadítja a folyamat erőforrásait és törli a folyamatot a nyilvántartásából, esetleg információt ad a folyamat szülőjének a futás eredményéről.

A bemutatott állapotmodell csak a legalapvetőbb eseteket tartalmazza. A gyakorlatban az operációs rendszerek általában bonyolultabbak. Alkalmazzák például a felfüggesztést, ami a folyamat működésének időleges szüneteltetését jelenti, miközben memóriaterülete felszabadul, vagy a folyamat „kilövésének” lehetőségét (végleges eltávolítását általában rendellenes működés miatt), illetve több más várakozó állapotot is bevezetnek. A felfüggesztett állapotokkal kiegészített állapotátmeneti diagram egy változatát mutatja a 3.6. ábra.

Látható, hogy a rendszer várakozó, vagy legfeljebb futásra kész folyamatokat függeszt fel, és a felfüggesztett folyamatokat is áthelyezi felfüggesztve futásra kész állapotba a várt esemény bekövetkezésekor.

3.6. ábra. ábra - Felfüggesztett állapotokat kiegészített állapotmeneti diagram

Felfüggesztett állapotokat kiegészített állapotmeneti diagram


3.3.1.4. Egy megvalósítási séma

A következőkben egy logikai sémát mutatunk be. A legtöbb operációs rendszerben ehhez hasonló megoldásokat találunk, bár a konkrét részletekben jelentős eltérések lehetnek.

Az operációs rendszer a folyamatok kezeléséhez szükséges információkat egy speciális adatszerkezetben, a folyamatleíróban (PCB: Process Control Block) tárolja.

A folyamatleíró tartalma:

  • a folyamat azonosítója,

  • a folyamat állapota,

  • a folyamat szülőjének és gyerekeinek azonosítója,

  • a folyamathoz tartozó összes tárterület leírása, mutatók, illetve a virtuális tárkezeléshez szükséges összes adat (címtranszformációs táblák, lemez blokkok leírása stb.),

  • a folyamat által használt egyéb erőforrások leírása (például a nyitott állományok leírása),

  • a regiszterek tartalma,

  • várakozó folyamatoknál a várt esemény leírása,

  • ütemezéshez szükséges információk (prioritás, várakozási idő),

  • számlázási információk és egyéb statisztikák.

A sorállási modellt az operációs rendszer tipikusan a folyamatleírók láncolt listákra fűzésével valósítja meg (3.7. ábra).

3.7. ábra. ábra - Folyamatleírok láncolása

Folyamatleírok láncolása


A 3.7. ábrán a P4 folyamat fut, a P1, P3. P5. és P7. folyamat futásra kész, az 1. periféria szabad, az n. periféria a P2 folyamat által kezdeményezett be-/kiviteli műveletet hajtja végre (a perifériák érkezési sorrendben szolgálják ki a folyamatokat, ezért nincs külön mutató arra, hogy melyik folyamat műveletét hajtja végre éppen a periféria), de már a P6 folyamat is kiadott rá műveletet. A P2 és P6 folyamat várakozó. A be-/kiviteli műveletek paramétereinek tárolására a rendszer be-/kiviteli leírókat (IOCB, Input-Output Control Block) használ. Az IOCB tartalmazza a művelet kijelölését (például olvasás, írás), a tárterület címét, ahova, vagy ahonnan a B/K-művelet végrehajtandó, szükség esetén a B/K készülékre vonatkozó egyéb adatokat (például mágneslemez egység szektorcíme), az átviendő adatmennyiséget, állapotjelzőket stb., azaz a művelet végrehajtásához szükséges valamennyi adatot. Az IOCB-k a B/K-műveletet kezdeményező folyamat PCB-jére fűződnek fel, így az elindított B/K-műveletek és az azokra várakozó folyamatok összetartozásának nyilvántartása is megoldott.

A perifériák mellett hasonló várakozási sorok szervezhetők szemaforokra, logikai erőforrásokra és más szinkronizációs, kommunikációs objektumokra.

Látható, hogy a bemutatott megoldásban a folyamat állapotát a PCB-ben tárolt állapotjelző mellett az is jellemzi, hogy a hozzá tartozó PCB éppen melyik sorban található.

Amikor a rendszer átkapcsol egy másik folyamat futtatására, a futó folyamat teljes állapotterét menteni kell, hogy a végrehajtás folytatható legyen (logikai memória, logikai processzor), továbbá az új futó folyamat utoljára elmentett állapotterét kell elővenni és visszaállítani, hogy annak végrehajtása folytatódjon. Ezt a műveletet környezetváltásnak (context switching) nevezik. Tekintve, hogy a memóriát a folyamat tartósan birtokolja, a me­mó­ria­kép megőrződik a folyamat várakozó állapotában is, így csak a logikai processzor átkapcsolása szükséges. Ez egyrészt a fizikai processzor regiszterei­nek, másrészt az operációs rendszer belső változóinak (rendszertáblázatok, memóriakezelési információk, periféria hozzárendelések stb.) elmentését, és az új folyamatnak megfelelő beállítását jelenti. A mentés a PCB-ben fenntartott megfelelő területre történik.

A be-/kiviteli műveletek végrehajtásának menete a következő:

  • a folyamat (általában rendszerhívások segítségével) kitölt egy IOCB-t, amiben megadja a művelet paramétereit,

  • B/K rendszerhívást hajt végre az IOCB paraméterként történő átadásával,

  • az operációs rendszer

    • hozzáláncolja az IOCB-t a folyamat PCB-jéhez,

    • a folyamat PCB-jét befűzi a periféria sorába,

    • ha a sor üres volt, az IOCB paramétereivel indítási parancsot ad a perifériának,

    • a folyamatot várakozó állapotba helyezi,

    • CPU-ütemezést hajt végre, azaz kiválasztja a következő futó folyamatot és környezetet vált,

    • visszatér (a visszatérés a környezetváltás miatt az új folyamatra történik).

A CPU és a perifériák párhuzamosan működnek. Az átvitelek végét megszakítások jelzik, amelyeket az operációs rendszer kezel (a megszakítások kiszolgáló programjait hardverütemezésű rendszerfolyamatoknak tekinthetjük).

Egy be-/kiviteli megszakítás kezelésekor az operációs rendszer:

  • az átvitel helyes vagy hibás eredményére utaló jelzést ír a periféria várakozási sorának elején álló PCB-hez láncolt IOCB-be,

  • a sor elején álló PCB-t kifűzi a sorból, átteszi a futásra kész sorba, a PCB-ben a folyamat állapotjelzőjét futásra kész-re állítja,

  • ha van még várakozó folyamat a periféria sorában, a következő IOCB pa­ramétereivel indítási parancsot ad a perifériának,

  • ha a CPU-ütemezés preemptív, CPU-ütemezést hajt végre,

  • visszatér.

Ezzel a szervezéssel a B/K-rendszerhívást kiadó folyamatnak a rendszerhívást követő utasítása akkor hajtódik végre, amikor az átvitel már befejeződött, és a CPU-ütemező őt választotta ki futásra.

3.3.1.5. Tétlen ciklusok kiküszöbölése

A szinkronizációs és kommunikációs műveletek ugyancsak okozhatják a folyamatok várakozását. A szemafor P(s) műveletének korábban (a 2.2.5.3. pontban) bemutatott definíciós programja:

while s<1 do skip;

s:=s-1;

Ez a program az oszthatatlanság mellett még azzal a feltételezéssel is él, hogy minden folyamatot külön processzor hajt végre, amelynek nincs más dolga, mint ciklikusan tesztelni a szemaforváltozót, amíg csak szabadnak nem találja. Multiprogramozott rendszerben ezek a tétlen ciklusok – az ún. foglalva várakozás (busy waiting) – használhatatlanok (gyakorlatilag még multiprocesszoros esetben is azok, ezért nevezzük a programot csupán definíciós programnak), hiszen a ciklikus tesztelés feleslegesen kötné le a processzort és a memóriát.

A szemaforkezelést ezért az operációs rendszer hatáskörébe kell utalni P és V rendszerhívásokkal, amelyek megvalósítása például a következő lehet.

Feltételezzük, hogy az operációs rendszer folyamatkezelő rendszerhívásai között van Elalszik művelet, amelyik a hívó folyamatot várakozásba helyezi és CPU-ütemezést indít, valamint Felébreszt(p) művelet, amelyikkel egy folyamat futásra kész állapotba tudja tenni a p várakozó folyamatot.

Feltételezzük továbbá, hogy a nyelv rendelkezik listakezelő műveletekkel (Felfűz, Lefűz).

A szemafor megvalósításának pszeudo kódja:

type semaphore = record érték:integer:=1; várósor: list of folyamat; end; P(s): s.érték:=s.érték-1; if s.érték < 0 then begin Felfűz(s.várósor); Elalszik; end; V(s): s.érték:=s.érték+1; if s.érték < 1 then begin Lefűz(p,s.várósor); Felébreszt(p); end;

Megjegyzések:

  • A szemafor s változójának pillanatnyi értéke tárolja a szemaforra várakozó folyamatok számát (negatív előjellel).

  • A szemafor ütemezési elve (a várakozók közül a továbbinduló kiválasztása) a listakezelő műveletek algoritmusában van elrejtve.

3.3.2. Processzorütemezés

A multiprogramozott operációs rendszerek alapjának a CPU-ütemezés tekinthető. A rövid távú ütemezés feladata annak eldöntése, hogy a processzort melyik futásra kész folyamat kapja meg. Mivel, mint azt az előző fejezetben láttuk, a rövid távú ütemező gyakran fut, ezért gyorsnak kell lennie, hogy a CPU-idő ne az ütemezéssel teljék. Ezért ez az ütemező része a kernelnek és állandóan a memóriában van.

A rövid távú ütemezők két alapvető fajtáját különböztethetjük meg. Pre­emp­tív (preemptive) ütemezésről beszélünk, ha az operációs rendszer elveheti a futás jogát az éppen futó folyamattól, „futásra kész” állapotúvá teheti, és a CPU-t egy másik folyamatnak adhatja, azaz egy másik folyamatot indíthat el.

Nem preemptív (non preemptive) ütemezésről akkor beszélünk, ha az operációs rendszer nem veheti el a futás jogát a folyamattól, azaz a futó folyamat addig birtokolja a CPU-t, amíg egy általa kiadott utasítás hatására állapotot nem vált, azaz csak maga a folyamat válthatja ki az új ütemezést, például ha befejeződik, valamilyen erőforrásra, eseményre vár vagy önként lemond a futás jogáról.

Ütemezés következhet be, ha

  • a futó folyamat befejeződik,

  • egy folyamat felébred, futásra késszé válik,

  • a futó folyamat várakozni kényszerül (valamilyen esemény bekövetkezésére), illetve,

  • a futó folyamat önként lemond a futás jogáról vagy pedig elveszik tőle.

Az első és a harmadik esetben az ütemezés mindig környezetváltással jár, hiszen a következő futó folyamat egészen biztosan nem a korábban futott lesz. A másik két esetben előfordulhat, hogy az ütemezőnek nem kell másik folyamatot kiválasztania.

Ha történik ütemezés a második esetben (folyamat felébred), illetve a negyedik eset bizonyos eseteiben (elveszik a CPU-t a futó folyamattól), akkor egészen biztos preemptív az ütemező, egyébként lehet ilyen is és olyan is. Maga az ütemezés úgy történik, hogy az ütemező valamilyen algoritmus szerint kiválaszt egy futásra kész folyamatot a futásra kész sorból (ready queue).

Mielőtt azonban belemennénk a rövid távú ütemezési algoritmusok tárgyalásába, nézzük meg, hogyan lehet ezeket összehasonlítani, illetve milyen követelményeket fogalmazhatunk meg az ütemezési algoritmusokkal szemben.

3.3.2.1. Az ütemezési algoritmusok összehasonlítása

A különböző ütemezési algoritmusok különböző tulajdonságokkal rendelkeznek. Adott helyzetekben alkalmazott algoritmusok kiválasztásánál ezen tulajdonságok hatását kell mérlegelni és a célnak legmegfelelőbbet kiválasztani.

A leggyakrabban alkalmazott összehasonlítási mértékek a következők:

  • Központi egység kihasználtság (CPU utilization). Alapvető cél, hogy a CPU lehetőleg minél több időt fordítson „hasznos” munka végzésére. A CPU-kihasználtság azt mutatja, hogy a CPU-idő hány százaléka fordítódik ténylegesen a folyamatok utasításainak végrehajtására. A kihasználtságot csökkenti, ha a CPU henyél (idle), azaz nincs olyan folyamat, amelyik futhat, illetve amikor rendszeradminisztráció, ütemezés stb. történik (rezsi, overhead):

A kihasználtság tipikus értékei 40–90% közé esnek.

  • Átbocsátó képesség (throughput). Az egy időegység alatt elvégzett munkák számát mutatja.

Elvégzett munkák száma / Idő

Az átbocsátó képesség tipikus értékei nagyon széles tartományban szórnak, a feladatok jellegétől függően (például ...,1/h, ..., 10/sec, ...).

  • Körülfordulási idő (turnaround time). Egy-egy munkára vonatkozóan a rendszerbe helyezéstől a munka befejeződéséig eltelt időt mutatja.

Σ (Végrehajtási idő + Várakozási idő)

A fenti két összetevő közül a végrehajtási idő nem függ az ütemezéstől, ezért az ütemezési algoritmusok jellemzésére alkalmasabbnak tűnik a várakozási idő.

  • Várakozási idő (waiting time). Értéke azt mutatja, hogy egy-egy munka összességében mennyi időt tölt várakozással. A várakozó és futásra kész állapotokban töltött időn kívűl ide számítódik a felfüggesztett állapotok ideje, valamint a hosszú távú ütemezésig eltelő előzetes várakozás is:

Σ (Várakozó + Futásra kész + Felfüggesztett + Hosszú távú ütemezésig eltelt) idő

  • Válaszidő (response time). Időosztásos rendszerekben nagyon fontos, hogy a felhasználók érezzék, hogy a rendszer reagál a parancsaikra. A válaszidő az az idő, amely az operációs rendszer kezelői felületének – esetleg egy felhasználóval kommunikáló folyamatnak – adott kezelői parancs után a rendszer első látható reakciójáig eltelik, vagyis amennyi idő alatt a rendszer válaszolni képes.

3.3.2.2. Az ütemezési algoritmusokkal szemben támasztott követelmények

Az ütemezési algoritmusokkal szemben az operációs rendszerekben különböző – gyakran egymásnak ellentmondó – követelmények fogalmazhatók meg. Az alábbiakban néhányat felsorolunk ezek közül.

  • Valamilyen célfüggvény szerint legyen optimális. (Ez a követelmény messze túlmutat az operációs rendszereken, hiszen bármilyen mérnöki tervezés esetén fontos annak a megfogalmazása, hogy az adott rendszer milyen célra készül, és ennek megfelelően lehet törekedni a cél szerinti optimum elérésére.)

  • Legyen korrekt, azaz minden folyamat kapjon egy bizonyos CPU-időt, kezeljen azonosan bizonyos folyamatokat.

  • Egyes folyamatoknak biztosítson prioritást.

  • Kerülje a kiéheztetést.

  • A viselkedése legyen „jósolható”, azaz terheléstől függetlenül becsülhető legyen például a várható maximális körülfordulási idő, a futtatási költség stb.

  • Legyen minimális a rezsiidő. (Bár ez nem mindig eredményez jobb teljesítményt!)

  • Legyen minimális a batch munkák várakozási ideje.

  • Legyen maximális az átbocsátó képesség.

  • Részesítse előnyben azokat a folyamatokat, amelyek fontos (népszerű) erőforrásokat foglalnak (hiszen az ilyen folyamatok sok más folyamatot várakozásra kényszeríthetnek).

  • Részesítse előnyben a kihasználatlan erőforrásokat igénylő folyamatokat.

  • Növekvő terhelés esetén a rendszer teljesítménye „elegánsan”, azaz fokozatosan romoljon le és ne omoljon össze hirtelen (graceful de­gra­dation). (Napjainkban ez a követelmény egyre fontosabb alap-szemponttá válik, és megint csak azt kell mondanunk, hogy az operációs rendszereken túlmenően, szinte minden összetett, orvosi, diagnosztikai, folyamatirányítási, kommunikációs, beágyazott stb. rendszer kapcsán az egyik elsődleges tervezési szempontként merül fel.)

Jól látható, hogy a fenti elvárások közül több egymásnak ellentmondó, így együttesen nem teljesíthető. Ezért is olyan fontos minden rendszernél megfogalmazni azokat a célokat, amelyek kiemelt fontosságúak az adott esetben, hogy ennek megfelelően kiválaszthatók legyenek azok a szempontok, amelyek mentén optimalizálni akarunk.

3.3.2.3. Ütemezési algoritmusok

Egyszerű ütemezési algoritmusok

Legrégebben várakozó (FCFS: First Come First Served). Nem preemptív algoritmus, amely a legrégebben várakozó folyamatot választja ki futásra. Megvalósítása igen egyszerű, a futásra kész folyamatok egy várakozási sor végére fűződnek fel, az ütemező pedig mindig a sor legelején álló folyamatot kezdi futtatni.

Ennél az algoritmusnál igen nagy lehet az átlagos várakozási idő, mivel egy-egy hosszú CPU-löketű folyamat feltartja a mögötte várakozókat (ezt hívjuk konvoj hatásnak). Képzeljünk el egy rendszert egy hosszú CPU-löketidejű és több rövid CPU-löketidejű folyamattal. Az első folyamat futása alatt az összes többi várakozni kényszerül és a perifériák is tétlenek lesznek. Később, amikor a hosszú CPU-löketidejű folyamat perifériás műveletre vár, a helyzet megfordulhat, azaz a rövid folyamatok futása után a CPU lehet tétlen.

Körbeforgó (RR: Round Robin). Preemptív algoritmus, amely az időosztásos rendszerek alapjának tekinthető. Minden folyamat, amikor futni kezd, kap egy időszeletet (time slice). Ha a CPU lökete nagyobb ennél, akkor az időszelet végén az ütemező elveszi a folyamattól a processzort, és a futásra kész állapotúvá tett folyamatot a futásra kész sor végére állítja.

Ha a CPU-löket rövidebb az időszeletnél, akkor a löket végén a rendszer folyamatait újraütemezzük, és a futó folyamat időszelete újraindul.

Ezeknél az algoritmusoknál nehéz az időszelet megfelelő méretének a meghatározása. Túl hosszú időszelet esetén ugyanis az algoritmus átmegy FCFS-algoritmusba, míg túl kicsire választás esetén megnő a környezetváltások száma, ami a rendszer hasznos teljesítményét jelentősen lerontja. A statisztikai vizsgálatok alapján ökölszabályként alkalmazható, hogy a CPU-löketek kb. 80%-a legyen rövidebb az időszeletnél.

Egy másik érdekes kérdés az időszelet hossza és a körülfordulási idő közötti összefüggés. Első várakozásainkkal ellentétben az esetek jelentős részében nem monoton függvényt kapunk válaszul. Példaként próbáljuk felrajzolni (környezetváltások nélkül) a fenti összefüggést egy olyan rendszerben, ahol négy futásra kész folyamat van, a következő CPU-löketidőkkel: 6, 3, 1 és 7 időegység (3.8. ábra).

3.8. ábra. ábra - Példa a körülfordulási idő és az időszelet hosszának összefüggésére Round–Robin-rendszerekben

Példa a körülfordulási idő és az időszelet hosszának összefüggésére Round–Robin-rendszerekben


Prioritásos ütemezési algoritmusok

A prioritásos algoritmusok közös sajátossága, hogy a futásra kész folyamatok mindegyikéhez egy, a futás kívánatos sorrendjére utaló számot – prioritást (priority) rendelünk. Az algoritmusok pedig a futásra kész folyamatok közül a „legnagyobb” prioritásút választják ki következő futtatandónak.

A prioritás hozzárendelése történhet az operációs rendszeren kívüli tényezők (például a folyamat saját kérése vagy operátori beavatkozás) által – ilyenkor külső prioritásról beszélünk, vagy történhet az operációs rendszer által – ilyenkor belső prioritásról beszélünk.

A prioritások lehetnek időben állandóak – statikus prioritás vagy (az operációs rendszer által módosítottan) időben változóak – dinamikus prioritás.

A következőkben ismertetett algoritmusok esetében a prioritást a CPU löketidő határozza meg.

Legrövidebb (löket)idejű (SJF: Shortest Job First). Nem preemptív algoritmus, amely a futásra kész folyamatok közül a legrövidebb becsült löketidővel rendelkező folyamatot választja ki következőnek futásra.

Az algoritmus kiküszöböli a FCFS-nél tapasztalható konvoj hatást, és ennél az algoritmusnál optimális az átlagos várakozási és körülfordulási idő.

Komoly gondot jelenthet azonban az, hogy a löketidők általában nem ismertek. Ilyenkor az operációs rendszer becslésekből indul ki, vagy a folyamatot elindító felhasználó „bevallását” tekinti kiindulásnak. Előbbi esetben a folyamat előző viselkedése alapján, a korábbi löketidők – általában exponenciális – átlaga szolgál a prioritás alapjául.

Ha a felhasználó által megadott értékeket vesszük alapul, akkor figyelembe kell venni azt is, hogy a felhasználók „nem érdekeltek” a löketidők pontos megadásában, hiszen tisztában vannak vele, hogy kisebb érték vallása esetén előnyösebb lesz a besorolásuk (bár a rajtakapott hazugságokat büntetheti is az operációs rendszer „hátrasorolással”).

Ismételt futás esetén azonban a helyzet sokkal jobb, hiszen a rendszerstatisztikákból már ismertek lehetnek a löketidők.

Legrövidebb hátralevő idejű (SRTF: Shortest Remaining Time First). Ez az algoritmus az SJF preemptív változata. Ha egy új folyamat válik futásra késszé, akkor az ütemező megvizsgálja, hogy az éppen futó folyamat hátralevő löketideje, vagy az új folyamat löketideje kisebb, és a rövidebbet indítja el.

Egy futó folyamat megszakításához és egy másik elindításához környezetváltásra is szükség van, ami szintén időt igényel, így ezt is figyelembe kell venni, amikor egy futó folyamat megszakítása mellett döntünk.

Az algoritmus használata az előzőével azonos problémákat vet fel.

Legjobb válaszarány (HRR: Highest Response Ratio). A prioritásos algoritmusok nagy hátránya a kiéheztetés veszélye. (Vagyis, hogy a kis prioritású folyamatok elől a nagyobb prioritásúak „ellopják” a CPU-t.) Ennek kivédése az öregítés (aging) révén történhet, amikor a rendszer a régóta várakozó folyamatok prioritását fokozatosan növeli.

Ezt az elvet alkalmazza az SJF-ből kiindulva a HRR-algoritmus. A folyamatok kiválasztásánál a löketidő mellett, a várakozási időt is figyelembe veszi. A prioritás alapjául a

(Löketidő + k* Várakozási idő)/Löketidő

összefüggés szolgál (k egy alkalmasan megválasztott konstans).

Többszintű algoritmusok

A többszintű algoritmusok sajátossága, hogy a futásra kész folyamatok nem egy, hanem több sorban várakozhatnak. Minden sorhoz prioritás van rendelve és az ütemező csak akkor választ ki futásra kisebb prioritású sorból folyamatot, ha a nagyobb prioritású sorok mind üresek. Az egyes sorokon belül különböző kiválasztási algoritmusok működ(het)nek.

Statikus többszintű sorok (SMQ: Static Multilevel Queues). Ennél az algoritmusnál a folyamatokhoz statikus prioritás rendelődik, azaz minden folyamathoz az elindulásakor rendelünk valamilyen prioritást (vagyis valamilyen kritérium alapján egy adott várakozási sorba soroljuk), amely a folyamat élete során nem változik (3.9.(a) ábra).

Egy lehetséges példa a folyamattípusok prioritás besorolására a következő:

  • rendszerfolyamatok (ezekhez célszerű a legmagasabb prioritást rendelni, hiszen közvetlen hatással vannak a rendszer működésére),

  • interaktív folyamatok (hogy biztosítani tudjunk a felhasználók számára elfogadható válaszidőt),

  • interaktív szövegszerkesztők (kevésbé kritikusak, mint az előzőek),

  • kötegelt feldolgozás (általában akkor futnak, ha „van idő”),

  • rendszerstatisztikákat gyűjtő folyamatok (a későbbi futtatásokhoz, rend­szerfejlesztésekhez stb. hasznos, illetve szükséges információkat gyűjtik össze, azonban ezek általában nincsenek közvetlen hatással a pillanatnyi rendszer működésre, így alacsony lehet a prioritásuk).

A statikus prioritásra épülő algoritmusok komoly hátránya az alacsony prioritással rendelkező folyamatok nagy várakozási ideje, kiéheztetése. Erre példaként említjük azt a világot bejárt esetet, amely szerint egy 1973-ban kikapcsolt IBM számítógépen az operátor talált egy 1967-ben elindított és még mindig futásra váró folyamatot.

Visszacsatolt többszintű sorok (MFQ: Multilevel Feedback Queues). Az előző algoritmusnál mutatott probléma megoldása a már említett öregítés vagy valamilyen más, ezt teljesen vagy részlegesen kiváltó technika alkalmazása lehet. Az MFQ-ütemezésnél a folyamatokhoz dinamikus prioritás rendelődik. Ez az ütemezés tehát dinamikus, vagyis a folyamatok a prioritás hozzárendelésüknek megfelelően dinamikusan átkerülhetnek egyik sorból a másikba.

Az egyes sorokon belül általában preemptív algoritmusokat – például növekvő időszeletű RR-t – alkalmaz, kivéve a legkisebb prioritású sort, amelyen belül az ütemezés történhet egy egyszerű FCFS által.

Az algoritmus a folyamatokat futásuk alapján különböző maximális CPU löketidejű osztályokba sorolja és a rövid löketidejű folyamatokat részesíti előnyben. A folyamatok elindulásukkor általában a legnagyobb prioritású sorba lépnek be. Ha azonban túllépik az időkorlátot, azaz futásukhoz nem elegendő egy időszelet, akkor az operációs rendszer csökkenti a prioritásukat, és eggyel lejjebbi (kisebb prioritású, ám nagyobb időszeletre, illetve FCFS-re épülő) sorba kerülnek át.

Hogy feloldjuk a maximális löketidőn alapuló besorolásból következő me­rev­séget (vagyis hogy a folyamatok ne hordozzák egész életük során azt a „büntetést”, amelyet akácsak egyszeri időszelet túllépés miatt is kaptak), célszerű lehet időről időre felülvizsgálni a folyamatok besorolását, és ha szükséges, például az átlagos löketidő mérése alapján, a prioritásokat módosítani (növelni).

Hasonlóképpen, a régóta várakozó folyamatok prioritását az operációs rendszer megnövelheti (aging), és nagyobb prioritású sorba sorolhatja át (3.9.(b) ábra).

Az MFQ-ütemezőket a következő szempontok alapján lehet osztályokba sorolni:

  • Hány sorban várakoznak a futásra kész folyamatok?

  • Milyen ütemezési algoritmus(oka)t használunk az egyes sorokon belül?

  • Hogyan kaphat nagyobb prioritást egy folyamat?

  • Mikor csökken egy folyamat prioritása?

  • Hová lépnek be az elindított folyamatok?

3.9. ábra. ábra - Többszintű ütemezés (a) statikus (b) visszacsatolt többszintű sorok

Többszintű ütemezés (a) statikus (b) visszacsatolt többszintű sorok


3.3.2.4. Az ütemezési algoritmusok „jóságának” értékelése

Egy mérnök számára a „mi van benne”, „hogyan működik” és „miért így” kérdések mellett soha nem kerülhető el annak megválaszolása sem, hogyha több lehetőség közül választhatunk, akkor „melyik a jobb”, illetve a meglevő „hogyan tehető jobbá”. Ez utóbbi kérdések megválaszolása a legtöbb esetben igen bonyolult, vagy egyenesen lehetetlen. Hiszen láttuk korábban, hogy a „jóság” követelményei összetettek, sőt egymásnak ellentmondó elemeket tartalmaznak. Vagyis nem lehet általánosságban egyértelmű választ adni. A konkrét esetekben azonban – alapos elemzés után – sokszor megadhatók a prioritások, vagyis az egyes elvárások fontossága. Így már közelebb kerülhetünk ahhoz, hogy megadjuk, hogy egy-egy konkrét esetben mit tekintünk „jónak”, „optimális” működésnek.

Példaként az időosztásos, interaktív rendszereket említjük, ahol az elfogadhatóan kis válaszidő követelménye az egyik legfontosabb az elvárások között. Más rendszerek esetében ez a követelmény nem számít fontos tervezési szempontnak. Vagyis a jóság kérdését mindig a céllal szoros összefüggésben kell vizsgálnunk.

Az ütemezési algoritmusok jóságának mérésére többféle lehetőség van.

Analitikus vizsgálat

A determinisztikus modellezés analitikus eszközt kínál az algoritmusok viselkedésének elemzésére. Sajnos a rendszerek terhelése számos véletlenszerű paraméterrel jellemezhető, így a determinisztikus modellek inkább esetek elemzésére, mint jósági jellemzők számítására alkalmasak. Előre összeállított adatokból – folyamatok száma, löketidők hossza – kiindulva, és az algoritmusokat a sorbanállás elmélet és sztochasztikus modellezés segítségével kezelve lehet következtetéseket levonni, azonban bármennyire is egyszerű a vizsgálati módszer, a kapott eredmények nem általános érvényűek, hanem csak szűk körre lesznek igazak.

Szimuláció

Az ütemezési algoritmusokat számítógépes modell segítségével is vizsgálhatjuk, mely során korábbi tapasztalatok vagy mérések alapján meghatározott eloszlású véletlen számokkal, illetve konkrét mért számértékekkel jellemezhetjük a folyamatokat.

A nyert eredmények érvényessége a modell és az adatok helyességétől, valamint az elvégzett szimulációk mennyiségétől függ.

Implementáció

Elvileg lehetőségünk van az algoritmusok implementálására és így teljesítményük valós körülmények közötti mérésére. Ez a módszer a legmegbízhatóbb a felsoroltak közül, azonban értelemszerűen egyben a legköltségesebb is, így a gyakorlatban nem igen használják.

3.3.3. Ütemezés többprocesszoros rendszerekben

Az előző részben az egyprocesszoros rendszerekben történő ütemezés kérdéseivel foglalkoztunk. Napjainkban azonban egyre gyakoribbak az olyan, több processzort tartalmazó – szorosan csatolt – rendszerek, ahol igényként merül fel, hogy a futásra kész folyamatok a rendszer bármelyik szabad processzorán elindulhassanak, és így a feladatok elvégzése minél rövidebb időt igényeljen, illetve a rendszeren belül egyenletes terheléselosztást biztosítsunk a processzorok között.

A többprocesszoros rendszerekben történő processzorütemezés értelemszerűen bonyolultabb feladat az egyprocesszoros esetnél. Az előzőekhez hasonlóan itt sem létezik „legjobb” megoldás, azonban a korábban tárgyalt elvek és sajátságok az esetek egy részében itt is alapvetően igazak lesznek.

Különbséget kell tennünk heterogén és homogén rendszerek processzor-ütemezése között. A heterogén rendszerekre az jellemző, hogy a rendszerbe épített CPU-k különbözőek lehetnek nemcsak méret, sebesség, felépítés, funkció stb. tekintetében, hanem például az utasításkészlet szempontjából is. Ilyen esetekben a lefordított folyamatok kötötten, csak a nekik megfelelő gépi utasításkészlettel rendelkező processzoro(ko)n lesznek képesek futni.

Hasonlóképpen csak bizonyos processzorokon indíthatók el azok a folyamatok, amelyek valamilyen speciális, az adott processzorhoz belső buszon keresztül csatlakoztatott eszköz használatát igénylik. Ez mind homogén, mind pedig heterogén rendszereknél kötöttséget jelent.

A homogén rendszereknél, tehát ahol a beépített CPU-k funkcionalitás szempontjából egyformák, általában nagyobb szabadságunk van az ütemezésnél. A futásra kész folyamatok a rendszer bármelyik szabad processzorán elindulhatnak. Alapvető cél a terheléselosztás biztosítása, tehát ahelyett, hogy a futásra kész folyamatok CPU-khoz rendelt külön sorokban várakoznának (és így könnyen előfordulhatna, hogy egy CPU tétlenül áll, míg egy másik futásra kész sorában több folyamat is várakozik), célszerű közös várakozási sort (sorokat) létrehozni, ahonnan mindegyik processzor veheti a rajta következőként futó folyamatot.

A közös várakozási sor(ok)on alapvetően kétféle ütemezési megközelítést alkalmazhatunk. Szimmetrikus multiprocesszoros rendszerekben minden egyes CPU saját külön ütemező algoritmust futtat, amely a közös sorból választ. A sorok hibamentes megosztott használatához pedig biztosítani kell a hozzáférésre vonatkozó kölcsönös kizárást.

Az aszimmetrikus multiprocesszoros rendszerek megkerülik ezt a problémát azzal, hogy egyetlen ütemező fut egy kiválasztott processzoron és ez az egyetlen ütemező osztja szét a feladatokat a szabad CPU-k között. Értelemszerűen ez a master-slave felépítés sokkal egyszerűbb adathozzáférést eredményez.