Ami 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.
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 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.
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.
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.
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 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.
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.
Nincsenek megjegyzések:
Megjegyzés küldése