CPU ütemezés

Előbb jött, előbb fut (FCFS – First Come First Served)

A legegyszerűbben megvalósítható ütemezési módszer. Semmi más nem kell hozzá, mint egy jól ismert várakozási sor. A folyamatok egyszerűen érkezési sorrendben kapják meg a processzort és egészen addig maguknál tarthatják, amíg be nem fejeződnek, vagy egy periféria-művelet miatt várakozni nem kényszerülne.

Előny: Egyszerű, biztos.
Hátrány: A folyamatok érkezési sorrendjétől nagy mértékben függ a várakozási idő.

A módszer működéséből fakadó előny az egyszerűsége mellett az, hogy biztosan mindegyik folyamat előbb-utóbb sorra kerül. De az is látszik, hogy inkább utóbb. Ha egy nagy futási idejű folyamat keveredik a rendszerbe, az a folyamatok egész sorát tarthatja fel (kamion hatás). A többi erőforrás is feltehetően kihasználatlanul marad, hiszen a rövidebb munkák periféria igényei a hosszú folyamat futása alatt már valószínűleg kielégítést nyertek és azok visszakerültek a futásra várók sorába. Az eljárás a hosszú folyamatoknak kedvez, nekik processzorigényükhöz képest viszonylag keveset kell várniuk.

Az alábbi példában az eljárás minősítésére az átlagos várakozási idők vannak feltüntetve. Az algoritmus bemenő adatai a tapasztalatból vett, becsült értékek vagy egyszerűen véletlen számok lehetnek. A számítás elvégzéséhez ismerni kell az egyes folyamatok érkezési idejét, valamint processzor igényét. (Az idő mértékegysége most légyegtelen. ☺)

folyamat érkezési idő processzor-igény
F1 0 3
F2 1 5
F3 3 2
F4 9 5
F5 12 5

A feladat megoldásához a táblázatot ki kell bővíteni néhány oszloppal.

folyamat érkezési idő processzor-igény kezdési idő befejezési idő várakozási idő
F1 0 3 0 3 0
F2 1 5 3 8 2
F3 3 2 8 10 5
F4 9 5 10 15 1
F5 12 5 15 20 3
várakozási idők átlaga 2,2

Meg kell jegyezni, hogy a valóságban nem igaz az, hogy egy folyamat azonnal elkezdődhet, amint egy másik befejeződött. Hiszen a „régi” folyamat állapotának mentése, a következő folyamat kiválasztása, állapotának betöltése időt igényel. Tehát a fenti számításokból adódó várakozási értékeknél a valóságban rosszabb a helyzet, a várakozási idő a környezetváltozások számával arányosan nő.


Legrövidebb előnyben (SJF – Shortest Job First)

Míg az előző módszer a leghosszabb folyamatoknak kedvez, ez az ütemezési eljárás előnyben részesíti a rövid processzoridőt igénylő munkákat. Ha több egyforma idejű folyamat is lenne, közülük az futhat, amelyik előbb érkezett (FCFS).

Előny: A legrövidebb várakozási időt adja.
Hátrány: A hosszú folyamatokkal mostohán bánik.

Az FCFS módszernél a folyamatok processzor igényét csak a példa feladat miatt kellett ismerni, itt azonban nagyon fontos, hiszen ettől függ az alacsony szintű ütemező döntése! Ez a módszer egyik gyengéje. A kívánt időtartam csak statisztikailag, vagy a programozó becslése alapján állapítható meg.
A következő probléma, hogy ha a rendszerben folyamatosan érkeznek a munkák, előfordulhat, hogy egy hosszú folyamat sohasem kerül sorra, mindig lesz egy rövidebb, amelyik elé vág. Az SJF algoritmus garantálja a legrövidebb átlagos várakozási időt. De miért örüljön ennek egy örökre kizárt hosszú folyamat? A számítási példa egyszerű, azonban bonyolultabb esetekben célszerű külön oszlopot fenntartani az egyes folyamatok befejezésekor várakozó folyamatoknak, ill. közülük a legrövidebbnek.

A példánk az SJF algoritmusra alkalmazva:

folyamat érkezési idő processzor-igény kezdési idő befejezési idő várakozási idő
F1 0 3 0 3 0
F2 1 5 5 10 4
F3 3 2 3 5 0
F4 9 5 10 15 1
F5 12 5 15 20 3
várakozási idők átlaga 1,6

Körben járó algoritmus (RR – Round Robin)

A körben járó algoritmus az „utolsó pár előre fuss” elvet valósítja meg. Interaktív rendszerekben, ahol a felhasználók a terminálok előtt ülve várják programjuk eredményeit, nem megengedhető sem a FCFS hosszú folyamatokat, sem a SJF rövid folyamatokat előnyben részesítő stratégiája. Az RR módszer demokratikusabb. Egy bizonyos időszelet eltelte után az ütemező elveszi a folyamattól a processzort. Az addig futó folyamat a várakozási sor végére kerül, a következő folyamat futhat, de ő is csak egy ideig.

Előny: Demokratikus, a legrövidebb a válaszideje.
Hátrány: Jelentős adminisztrációt igényel.

Minden egyes folyamatváltásnál környezetváltásra is sor kerül, ami az időszelet nem megfelelő megválasztása esetén túlsúlyba is kerülhet. A megnövekedett adminisztrációt már az egyszerű példa kapcsán is megtapasztalhatjuk, most már végképp kevés az egy táblázat. A folyamatok adatai a régiek, de mivel egy-egy folyamat nem egy lépcsőben fut le, a sorok száma már több kell legyen, mint a folyamatok száma, sőt előre nem is igazán lehet tudni, hogy mennyi. Az időszelet hossza legyen 4 egység!

folyamat érkezési idő processzor-igény kezdési idő befejezési idő várakozási idő
F1 0 3 0 3 0
F2 1 5 5 10 4
F3 3 2 3 9 4
F4 9 5 10 19 5
F5 12 5 15 20 3
várakozási idők átlaga 1,6

folyamat érkezési idő kezdeti igény kezdési idő befejezési idő várakozási idő maradék igény befejezéskor várakozó folyamatok
F1 0 3 0 3 0 0 F2, F3
F2 1 5 3 7 2 1 F3, F2
F3 3 2 7 9 4 0 F2, F4
F2* (7) (1) 9 10 2 0 F4
F4 9 5 10 14 1 1 F5, F4
F5 12 5 14 18 2 1 F4, F5
F4* (14) (1) 18 19 4 0 F5
F5* 18 1 19 20 1 0

A várakozási idők átlaga az összes várakozási idő osztva a folyamatok számával. Ebben a példában: 16/5=3,2.

Megjegyezés: A táblázatban *-gal jelölt az a folyamat, amely felfüggesztődött, majd újra sorra került. Ilyenkor az érkezési idő oszlopban a felfüggesztés ideje, míg a kezdeti igény oszlopban a maradék idő szerepel. Azért, hogy ezt megkülönböztessük a tényleges érkezési időtől és kezdeti igénytől, zárójelek között kerültek beírásra.


Prioritásos módszerek

A folyamatokat fontosság szerint rangsorba állíthatjuk. Ez persze felborít minden egyszerű algoritmust. A prioritás az FCFS és SJF technikáknál azt jelenti, hogy a magasabb rendű folyamat a várakozási sor elejére kerül. Az RR algoritmusnál az elsőbbséget nagyobb időszelet biztosításával lehet elérni. A prioritásos rendszereknél fennáll a veszélye annak, hogy a kevesebb joggal rendelkező folyamatok háttérbe szorulnak, nem futhatnak.

A prioritás azonban a gyengék javát is szolgálhatja. Ha a várakozási sorban lévő folyamatok prioritását idővel automatikusan növeljük, előbb-utóbb az alacsony jogú, hátrányos helyzetű folyamatok is futhatnak.