Processzorütemezés

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

vissza: OpRe / OpreVazlatFolyamatkezeles

---

---

(TK 147-155)

A multiprogramozott operációs rendszerek alapja a CPU-ütemezés.

A rövid távú ütemező gyakran fut, tehát gyorsnak kell lennie, ezért része a kernelnek és állandóan a memóriában van.

• Preemptív ütemezés: Az oprendszer elveheti a futás jogát az éppen futó folyamattól, és "futásra kész" állapotúvá teheti. Közben egy másik folyamatot indíthat el.
• Nem preemptív ütemezés: Az operációs rendszer nem veheti el a futás jogát a folyamattól. A folyamat addig fut, amíg az általa kiadott utasítás hatására állapotot nem vált, azaz csak maga a folyamat válthatja ki az új ütemezést. (Befejeződik, erőforrásra vagy eseményre vár, lemond a futásról)

Ütemezés következhet be:

• a futó folyamat befejeződik (biztosan környezetváltással jár)
• egy folyamat felébred (lehet környezetváltás)
• a futó folyamat várakozni kényszerül (biztosan környezetváltással jár)
• a futó folyamat önként lemond a futás jogáról (lehet környezetváltás)

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.

Ütemezési algoritmusok összehasonlítása

A központi egység kihasználtság (CPU utilization): 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 amikor a CPU henyél (idle) vagy a rendszeradminisztráció.

Átbocsátó képesség: Az időegység alatt elvégzett munkák száma. (Elvégzett munkák száma/idő)

Körülfordulási idő: Egy-egy munkára vonatkozóan a rendszerbe helyezéstől a munka befejeződéséig eltelt idő. (Végrehajtási idő+Várakozási idő)

Várakozási idő: Egy munka összesen mennyi időt tölt várakozással

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.

Ütemezési algoritmusok

Egyszerű ütemezési algoritmusok

• Legrégebben várakozó (FCFS: First Come First Served): Nem preemptív. A legrégebben várakozó folyamatot választja ki futásra. A futásra kész folyamatok egy várakozási sor végére kerülnek, az ütemező pedig a sor elején álló folyamatot kezdi futtatni. Hátránya: Nagy lehet az átlagos várakozási idő, mert egy hosszú CPU löketű folyamat feltarja a mögötte levőket és a perifériák is tétlenek. (konvoj hatás).

• Körbenforgó (RR: Round Robin): Preemptív algoritmus, az időosztásos rendszerek alapja. Minden folyamat, amikor futni kezd kap egy időszeletet. Ha a CPU lökete ennél nagyobb, az időszelet végén az ütemező elveszi a folyamattól a CPU-t és a futásra kész várakozási sor végére rakja. Ha a CPU löket rövidebb az időszeletnél, akkor a folyamatokat újraütemezzük, és a futó folyamat időszelete újraindul. Hátránya: Nehéz az időszelet megfelelő méretének a meghatározása. Túl hosszú esetén átmegy FCFS algoritmusba, túl rövid esetén sok a környezetváltás.

Prioritásos ütemezési algoritmusok

• Legrövidebb (löket)idejű (SJF: Shortest Job First): Nem preemptív. A legrövidebb becsült löketidejű folyamatot választja ki futásra. Ennél az algoritmusnál optimális az átlagos várakozási és körülfordulási idő. A felhasználó által megadott és az előzmények alapján becsült löketidőt veszi alapul.

• Legrövidebb hátralevő idejű (SRTF: Shortest Remaining Time First): Az SJF preemptív változata. Ha új folyamat válik futásra készzé akkor megvizsgálja hogy a futó folyamat hátralevő löketideje vagy az új folyamat löketideje a kisebb. A környezetváltás idejét is figyelembe veszi.

• Legjobb válaszarány(HRR: Highest Reponse Ratio): A folyamat kiválasztásánál a löketidőt és a várakozási időt is figyelembe veszi. Öregítést alakalmaz (aging), azaz a régóta várakozó folyamatok prioritását növeli.

Többszintű algoritmusok

A futásra kész folyamatok több, különböző prioritású sorban várakoznak. Az egyes sorokban belül különböző kiválasztási algoritmusok is lehetnek.

• Statikus többszintű sorok (SMQ: Static Multilevel Queues): A folyamatok prioritása statikus, a folyamattípus alapján (pl.: rendszerfolyamatok, interaktív folyamatok, interaktív szövegszerkesztők, kötegelt feldolgozás, rendszerstatisztika). Hátrány: kiéheztetés léphet fel.

• Visszacsatolt többszintű sorok (MFQ: Multilevel Feedback Queues): A folyamatokhoz dinamikus prioritás rendelődik. 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. Ha egy folyamat túllépi a kapott időkorlátot, akkor az oprendszer csökkenti a folyamat prioritását. A régóta várakozó folyamatok prioritását az oprendszer megnövelheti (aging).

---

Kérdések 7.3

9. Mit jelent a CPU-ütemezési algoritmusok paraméterei között a CPU-kihasználtság?

Azt mutatja, hogy a CPU-idő hány százaléka fordítódik a folyamatok utasításainak végrehajtására.

10. Mi a kapcsolat a CPU-ütemezési algoritmusok jellemzésére használt körülfordulási idő és várakozási idő között?

körülfordulási idő = szumma(végrehajtási idő + várakozási idő)

11. Mikor nevezünk egy ütemezőt preemptívnek?

Preemptív ü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.

12. Milyen paraméterek alapján lehet különböző CPU ütemezési algoritmusokat értékelni? Definiálja a különböző paraméterek jelentését! Hasonlítsa össze valamely fenti paraméter alapján a legrégebben várakozó (FCFS) és a legrövidebb löketidejű (SJF) algoritmusokat.

• CPU kihasználtság:100*(szumma(CPU idő) - szumma(henyeles + adminisztráció))/szumma(CPU ido) [%]
• Átbocsátó képesség: elvégzett munkák száma/idő
• Körülfordulási idő: szumma(végrehajtási idő + várakozási idő)
• Várakozási idő: szumma(várakozó + futásra kész + felfüggesztett + hosszú távú ütemezésig eltelt) idő
• Válaszidő: adott kezelői parancs után a rendszer első látható reakciójáig eltelt idő

Várakozási idő szempontjából az SJF algoritmus jobb, mint az FCFS.

13. Ismertesse a legrövidebb löketidejű (SJF) és a legrövidebb hátralévő löketidejű (SRTF) ütemezési algoritmusokat, kiemelve a közöttük lévő lényeges különbségeket.

Az SRTF algoritmus az SJF algoritmus preemptív változata. Míg az SJF, ha már elkezdett feldolgozni egy folyamatot, akkor azt be is fejezi, az SRTF, amennyiben felébredt vagy elindult olyan folyamat, amelynek kisebb a (maradék) löketideje, mint az éppen feldolgozottnak, akkor a jelenlegit várakoztatja, és a legrövidebb hátralévő löketidejűt választja ki feldolgozásra.

Edit : -- PappIstvanPeter - 2005.05.31.

14. Definiálja a preemptív és a nem preemptív ütemező közötti különbséget! Rajzoljon fel egy felfüggesztett állapotokat nem tartalmazó folyamat állapotátmeneti diagramot, és illusztrálja ezen is a preemptív és a nem preemptív ütemezo közötti különbséget!

lásd. előbbi kérdések. Rajz u.a. felfüggesztett állapotok kivételével. Preemptív ütemezés esetén futó folyamatot az operációs rendszer futásra kész állapotba tehet (elvéve tőle a CPU-t).

15.Milyen szempontok alapján lehet osztályozni a folyamatok ütemezésénél megismert visszacsatolt többszintű sorokat (Multilevel Feedback Queues)?

• Hány sorban várakoznak a futásra kész folyamatok
• Milyen ütemezési algoritmusokat hszná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

16. Hogyan lehet a CPU-löketidőn (burst time) alapuló ütemezési algoritmusoknál a futásra kész folyamatok következő löketidejét meghatározni?

Az operációs rendszer becslésekből indul ki, vagy a folyamatot elindító felhasználó “bevallását” tekinti kiindulópontnak. 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.

(16+1). Hogyan kerülhetö el az éhezés prioritásos ütemezés esetén?

• aging*: a régóta várakozó folyamatok prioritását a operációs rendszer megnövelheti, és nagyobb prioritású sorba sorolhatja át.

18. Melyik ütemezési algoritmus esetén a legkisebb a válaszidő szórása?

• Legrégebben várakozó (FCFS)
• Körbeforgó (Round Robin) ??
• Legrövidebb löketidejű (SJF)

19. Mely állítások igazak a CPU-ütemezésnél használt körbeforgó algoritmusra?

• Biztosítja a legkisebb átlagos várakozási időt.
• Használata esetén nem lép fel a folyamatok kiéheztetése.
• Használatával lehet valósidejű operációs rendszert készíteni.

20. Mely állítások igazak a preemtív ütemező algoritmusra?

• Mindig prioritásos ütemezési algoritmusokat használ annal eldöntésére, hogy mikor és melyik folyamatot kezdje el futtatni.
• Alkalmazása esetén egy éppen futó folyamatot bármelyik időpillanatban megszakíthat és futásra kész állapotúvá tehet az operációs rendszer. ?? (Szerintem igaz. Akkor történik ilyen, ha egy nagyobb prioritású folyamat feébred. -- zslevi )
• Használatával az operációs rendszer átlagos válaszideje csökkenthető.

21. Mely állítások igazak a prioritásos ütemező algoritmusokra?

• Jobban kihasználják a CPU-t.
• Használata holtpont kialakulásához vezethet. ??
• Használata kiéheztetéshez vezethet.

(Megjegyzés: A nagyobb prioritású folyamat kiéhezteti a kisebb prioritásút, sőt, ha nem preemptív erőforrást használnak, a kisebb prioritású is kiéhezteti a nagyobb prioritásút, de a kiéheztetés nem deadlock. Deadlock kialakulása a folyamatok együttműködésének algoritmusától függ. -- zslevi - 2005.06.18.)

---

vissza: OpRe / OpreVazlatFolyamatkezeles