Processzus ütemezése

Processzus ütemezése

Ha több processzus van futáskész, akkor dönteni kell, hogy melyik fusson közülük.

Ütemező:

Az op. rendszer azon része, amelyik dönt a futáskész folyamatok közül melyik fusson.

Ütemező algoritmus:

Eldönti, hogy a futáskész folyamatok közül melyik fusson.

Az ütemező algoritmusnak szem előtt kell tartania:

-   &nb 343b11d sp;   &nb 343b11d sp; Pártatlanság (minden processzus megkapja a neki járó CPU-t)

-   &nb 343b11d sp;   &nb 343b11d sp; Hatékonyság (A CPU-időt maximálisan kihasználja)

-   &nb 343b11d sp;   &nb 343b11d sp; Válaszidő (minimalizálni az interaktív felhasználók válaszidejét)

-   &nb 343b11d sp;   &nb 343b11d sp; Áthaladási idő (a kötegelt felhasználók eredményre várási idejét minimalizálni)

-   &nb 343b11d sp;   &nb 343b11d sp; Áteresztőképesség (maximalizálni az óránként végrehajtott feladatok számát)

Sajnos ezek a célok ellentmondásosak.

Bizonyos időközönként az op. rendszer dönt, hogy melyik processzus fusson.

Nem megszakítható ütemezés: a processzusok nem megszakíthatóak.

Megszakítható ütemezés: az a stratégia, amelyik a logikailag futtatható processzusoknak megengedi, hogy ideiglenesen felfüggesztődjenek.

1.   &nb 343b11d sp;  Round robin ütemezés

Minden processzushoz tartozik egy időszelet, amely alatt futhat.

Ha a folyamat ideje lejárt, átkapcsolódik egy másik processzus futtatására.

Ha a processzus véget ér vagy blokkolódik az időszelet lejárta előtt, akkor is átkapcsol egy másik processzusig.

Egyedüli probléma az időszelet nagysága. Az átkapcsolás is időt vesz igénybe. Túl kevés időszelet esetén az átkapcsolás túl nagy időarányú. Túl nagy időszelet esetén a több felhasználó esetében sokat kell várni a futtatott programra. 100 ezredmásodperc ésszerű kompromisszum.

2.   &nb 343b11d sp;  Prioritásos ütemezés

Külső tényezők figyelembe vételével pl. a hadseregben a tábornok processzusa fontosabb, mint az ezredesé, a századosé, a tizedesé, a honvédé.

Minden processzushoz rendeljünk egy prioritást és a legmagasabb prioritású processzus futhat.

-   &nb 343b11d sp;   &nb 343b11d sp; Elkerülendő, hogy egy processzus a végtelenségig fusson, a prioritását egy bizonyos idő eltelte után csökkentik (az aktuálisan futóét).

-   &nb 343b11d sp;   &nb 343b11d sp; Minden processzushoz hozzárendelnek egy maximális időszeletet, amit folyamatos CPU lekötéssel tölthet. Ezt kihasználva a másik legmagasabb prioritású folyamatra kapcsol át.

A prioritások hozzárendelése történhet:

-   &nb 343b11d sp;   &nb 343b11d sp; Statikusan: fixen, pl. tábornok 100, ezredes 90, őrnagy 80

-   &nb 343b11d sp;   &nb 343b11d sp; Dinamikusan: futás során változik. A B/K igényes processzusok sokat várnak az írás vagy olvasás befejeztére. Ha f az utolsó időszeletből a processzus által használt rész, akkor a prioritás 1/f-re állítása jó hatást vált ki.

Pl.: 100 ezredből csak 2-t használt a processzus, akkor f=2/100=0,02 így 1/f=50 lesz a prioritása.

Prioritási osztályokat lehet létrehozni a processzusok között, azonos prioritásúak között pedig round robin-t.

4. prioritásban mind egy időszeletet vesz igénybe round robin módon.

Ha a 4. osztály kiürül, előveszi a 3. osztály elemeit round robin módon.

Nem a legigazságosabb, és éheztetéshez vezet.

3.   &nb 343b11d sp;  Többszörös sorok

Az egyik ősi időzítő, amely a CTSS op. rendszerben valósult meg és 7094-esen futott.

Egyetlen processzust tudott a memóriában tárolni, ezért váltásnál mindent lemezre mentett, így nagyon lassú volt.

Ezért a következőt találták ki:

Prioritási osztályok felállítása, és a legmagasabb 1 időegységig futottak, az alacsonyabb 2 időegységig, az ennél is alacsonyabb 4 időegységig és így tovább.

Ha egy processzus elhasználja az összes számára biztosított időszeletet, egy osztállyal lejjebb kerül.

Pl.: egy processzus 100 időszeletet igényelne, akkor először 1 szeletet kap, következőleg 2-t, 4, 8, 16, 32, 64-et, de az utolsóból már csak 37-et vesz igénybe. Ezalatt 7 cserére volt szükség a round robin 100-ához képest.

Mivel azonban prioritása egyre lejjebb kerül, egyre ritkábban fog futni.

Az interaktív processzusok védése érdekében valahányszor leütöttek egy "E"-t, a processzus visszakerült a legfelsőbb prioritású osztályba. Ám ha ezt a felhasználók felfedezik, ütögetik az "E"-t.

Az időosztás választása függ attól, hogy a gépet mire használják.

4.   &nb 343b11d sp;  A legrövidebb feladatot először

Az előző algoritmusok interaktív rendszerekben jól működnek.

Ez az algoritmus kötegelt feldolgozásnál, előre ismert futási időnél működik helyesen.

Létezik interaktív processzusokhoz is modell:

A feladat ismétlődő: várakozás ***, utasítás végrehajtása, várakozás, végrehajtás.

Ha az utasítás végrehajtását külön feladatnak tekintjük, akkor a legrövidebbet futtatva először elvet követve minimalizálhatjuk az öszzválaszidőt.

5.   &nb 343b11d sp;  Garantált ütemezés

A felhasználónak egy ígéretet teszünk a végrehajtásról.

Egy reális ígéret:

Egy processzor és n processzus esetén, 1 processzus a CPU idejének 1/n-ed részét kapja.

Kiszámolunk minden processzushoz egy arányt a következőképpen:

A létrehozása óta eltelt időt elosztjuk n-nel. Mivel minden processzusnál ismerjük a valódi felhasznált processzus idejét, kiszámoljuk az aktuálisan felhasznált és a neki járó CPU arányt.

Az algoritmus a legkisebb arányszámmal rendelkező processzust fogja futtatni, ami ezután nyilván nő.

(0,5 arány azt jelenti, hogy a processzus a neki járó idő felét használta el. A 2 azt, hogy a processzus kétszer annyit használt, mint ami megillette volna)

6.   &nb 343b11d sp;  Sorsjáték ütemezés

Minden processzus kap egy sorsjegyet, és az ütemező sorsol, az fut, akinek kihúzták a sorsjegyét. Ha egy fontos processzusunk van, akkor annak adhatunk több sorsjegyet, növelve az esélyt.

Előre: együttműködő processzusok cserélhetik a sorsjegyeket.

Pl.: ha egy processzus blokkol egy másikat, akkor átadhatja a sorsjegyeit a futónak, hogy hamarabb szabaduljon.

7.   &nb 343b11d sp;  Valós idejű ütemezés

Valós idejű ütemezésnél fontos a gyors reagálás.

Pl.: ***megfigyelő az interaktív osztályban

Robotpilóta a repülőgépen

Atomreaktor biztonsági felügyelete

Két fajtája:

-   &nb 343b11d sp;   &nb 343b11d sp; Szigorúan valós idejű rendszerek: a reagálás kötelező az adott időtartamon belül.

-   &nb 343b11d sp;   &nb 343b11d sp; Lágy valós idejű rendszerek: egy *** esetleges alkalmazása tolerálható.

Az események, amelyekre reagálni kell, lehetnek:

-   &nb 343b11d sp;   &nb 343b11d sp; Periodikusak

-   &nb 343b11d sp;   &nb 343b11d sp; Aperiodikusak

Pl.: Ha m periodikus amíg van. Pi az i-edik periódusa. Ci CPU idő***, akkor a rendszer ütemezhető, ha

Az ütemező algoritmusok lehetnek:

-   &nb 343b11d sp;   &nb 343b11d sp; Statikus: ütemezési döntést a rendszer futásának megkezdésekor hozza.

-   &nb 343b11d sp;   &nb 343b11d sp; Dinamikus: ütemezési döntést futás közben hozza.

Néhány algoritmus:

Állandó arány algoritmus:

A kiváltó esemény gyakoriságának arányában egy prioritási számot rendelünk a processzusokhoz. Az ütemező mindig a legmagasabb prioritású futtatható processzust futtatja. Pl.: 20 e másodpercenként futó folyamat 50-8, 100 e másodpercenként futóhoz 10-est rendelünk.

Bizonyítható, hogy ez az ütemezés optimális.

Legkorábbi határidő először:

Egy esemény bekövetkeztével felvesszük a processzust a futási listára, a futási sorrendet megőrizzük, a periodikus eseménynél a következő előfordulás ideje. Az ütemező a lista legelső elemét futtatja.

Legkisebb lazaság:

Lazaság: A processzusnak a felesleges időmennyisége. Ha egy processzus 200 ezredmásodpercet igényel, és 250 ezredmásodpercen belül be kell fejeződnie, akkor a lazasága 50. Azt a processzust választjuk futónak, amelyik a legkisebb időfelesleggel rendelkezik.

8.   &nb 343b11d sp;  Kétszintű ütemezés:

Ha a memória kevés az összes processzushoz, akkor ezek egy részét lemezen kell tárolni. A lemezen lévő processzusra átkapcsolni nagyon időigényes.

A processzusokat két csoportba osztjuk, egyiket memóriában, másikat lemezen tároljuk. Az ütemező először csak az első csoportból választ átkapcsolásra. Időnként egy magasabb szintű ütemezőt hívnak meg, amely kiválasztja azokat, amelyek az első csoportba (a memóriába) kerülhetnek.

A magasabb szintű ütemező a következőket veheti figyelembe:

-   &nb 343b11d sp;   &nb 343b11d sp; Mennyi idő telt el a processzus kicserélése óta?

-   &nb 343b11d sp;   &nb 343b11d sp; Mennyi CPU időt használt el a processzus az utóbbi időben?

-   &nb 343b11d sp;   &nb 343b11d sp; Milyen magas a processzus prioritása?

9.   &nb 343b11d sp;  Cél és megvalósítás modell:

Egyes processzusok gyerekprocesszusokat hoznak létre, és azok jobban tudják, hogy melyiket kellene jobban felügyelni. Ilyen esetekben az ütemezési algoritmust a processzusok ***.

Pl.: Prioritásos algoritmus esetén bevezethetünk egy olyan rendszerhívást, amellyel a felhasználói processzusok a gyerekeinek a prioritását írhatja felül.