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.