Ütemezés (Scheduling),

Nyíregyházi Főiskola Matematika és Informatika Intézete

03

Ütemezés (Scheduling),  Alapfogalmak  Ütemezési feltételek (kritériumok)  Ütemezési algoritmusok  Több-processzoros eset  Algoritmus kiértékelése

Dr. Bajalinov Erik

Operációs rendszerek (PMB1206)

1


03

Alapfogalmak  A multiprogramozás célja: a CPU foglaltság (kihasználás) hatásfokának növelése/javítása  A multiprogramozás lényege: egyidőben több folyamat is az operatív tárban helyezkedik el, készen állva a CPU kiszolgálására. Ha egy folyamatnak várnia kell (pl. I/O-műveletre), a CPU-t egy másik folyamat kapja meg.  CPU Burst cycle – a CPU foglaltsági ciklus (burst = robbanás), vagy „CPU löket”, azaz olyan időintervallum, amikor folyamatnak csak CPU-ra és operatív memóriára van szüksége.  I/O Burst Cycle – az I/O műveleti ciklus, „Periféria löket”, amikor a folyamat perifériás átvitelt hajt végre, ilyenkor CPU-ra szükség nincsen.  Rövid távú ütemezés (short term scheduling, vagy CPU scheduling) olyan ütemterv előállítása, amely meghatározza, melyik folyamat kerül a CPU egységbe végrehajtásra) Dr. Bajalinov Erik


2


03

 Közép távú ütemezés (medium term scheduling) olyan ütemterv előállítása, amely meghatározza migrációs folyamatokat fő memória és a „page” memória között.  Hosszú távú ütemezés (long term scheduling) olyan ütemterv előállítása, amely meghatározza, melyik folyamat kerül a RAM-be.  Rövid távú ütemezési döntéshelyzet áll elő, ha egy folyamat 1. futó állapotból várakozó állapotba kerül, vagy 2. futó állapotból készenléti állapotba kerül, vagy 3. várakozó állapotból készenléti állapotba kerül, vagy 4. megáll  Az 1. és 4. esetben az ütemezés nem preemptív (nem beavatkozó: a processzus maga mond le a CPU-ról) – (MS Windows)  Az 2. és 3. esetben az ütemezés preemptív (beavatkoz(hat)ó: a rendszer elveszik tőle a CPU-t)

Dr. Bajalinov Erik


3


03

 A Diszpécser (dispatcher) –egy módul, az OS szerves része. A diszpécser adja át a vezérlést a rövid-távú ütemező (scheduler) által kiválasztott folyamatnak, azaz biztosítja rövid-távú ütemező által meghatározott „menetrend” megtartását és végrehajtását. Ez magában foglalja: 1. a kontextus módosítását (átkapcsolást, switching) 2. user módba kapcsolást 3. a megfelelő című utasításra ugrást (program-counter, azaz PC beállítását)  Diszpécser (Dispatch latency, i.e. „reaction time”): egy processzus megállításához és egy másik processzus elindításához szükséges idő, latencia  Mivel diszpécser feladata a folyamatok közötti átkapcsolás, nagyon gyorsan kell működnie.

Dr. Bajalinov Erik


4


03

Ütemezési feltételek (kritériumok)  CPU kiszolgálás (CPU utilization) – a CPU az idő minél nagyobb részében legyen foglalt, azaz a CPU az idejének hány százalékát használja a folyamatok utasításainak végrehajtására. Kihasználtságot csökkenti: CPU henyél (idle, azaz üres járat), a rendszer-adminisztrációra fordított idő („rezsi”).  Átbocsátóképesség (throughput, teljesítmény) – egységnyi idő alatt befejeződő processzusok száma, azaz az OS időegységenként hány munkát futtat le.  Végrehajtási (turnaround, fordulási) idő: T = a várakozás a memóriába kerülésre + a készenléti sorban töltött idő + a CPU-n töltött idő + az I/O-val töltött idő.  Várakozási idő (waiting time) – készenléti sorban (ready queue) töltött idő.

Dr. Bajalinov Erik


5


03

 Válaszidő (response time) – az OS reakció ideje, a „kérés benyújtásától” az első válasz megjelenéséig eltelt idő. (Interaktív rendszerekben a turnaround nem jó jellemző).  Ütemezés feladatai és céljai: „tisztességes” és „igazságos” kiszolgálás, minimum-, maximum-, átlag-idő optimalizálása, szórás optimalizálása, jósolhatóság.

Dr. Bajalinov Erik


6


03

Ütemezési algoritmusok 1. Egyszerű algoritmusok 2. Prioritásos algoritmusok 3. Többszintű algoritmusok 4. Többprocesszoros ütemezések

Dr. Bajalinov Erik


7


03

Egyszerű algoritmusok 1. Igény-bejelentési sorrend szerinti kiszolgálás (mint FIFO: First-Come,

First-Served = FCFS). A futásra kész folyamatok a várakozási sor végére kerülnek, az ütemező a sor elején álló folyamatot kezdi futtatni. – Nem preemptív (nem beavatkozó). – Egyszerűen megvalósítható. – Konvoj hatás (egy hosszú CPU-igényes folyamat feltartja a mögötte várakozókat) – Az átlagos várakozási idő nagy szórása

Dr. Bajalinov Erik


8


03

Példa:

2. Körforgó (Round Robin, azaz RR, körleosztásos, körbejáró ütemezés)

Minden processzus sorban q ideig (q=10-100 milliszekundum) használhatja a CPU-t. Folyamatok időszeletet kapnak (time slice). a. Ha a CPU löket nagyobb mint az időszelet, akkor az időszelet végén az ütemező elveszi a CPU-t, a folyamat futásra kész lesz és beáll a várakozó sor végére. Dr. Bajalinov Erik


9


03

b. Ha a CPU löket rövidebb, akkor a löket végén a folyamatokat újraütemezzük. Ez preemptív (beavatkozó) algoritmus, az időosztásos rendszerek valamennyi ütemezési algoritmusainak az alapja. Időszelet „szerencsés” meghatározása nehéz feladat. – Nagy időszelet esetén: az eredmény hasonló az FCFS algoritmus eredményéhez. – Kis időszelet esetén: folyamatok a CPU-t egyenlő mértékben használják, viszont a sok környezetváltás a teljesítményt rontja (magas rezsi költség).

Szabály: CPU löketek kb. 80% legyen rövidebb az időszeletnél

Dr. Bajalinov Erik


10


03

Példa:

Dr. Bajalinov Erik


11


03

Prioritásos algoritmusok A futásra kész folyamatokhoz egy prioritást (rendszerint egy egész számot) rendelünk (priority) . A legnagyobb prioritású folyamat lesz a következő futtatandó folyamat. Prioritás meghatározása lehet belső (az OS határozza meg) vagy külső (az OS-en kívüli tényező (operátor, a folyamat saját kérése, stb.) határozza meg. Prioritás lehet statikus (végig azonos, azaz a folyamat befejeződéséig nem változik) vagy dinamikus (az OS változtathatja, időszeletenként).

Dr. Bajalinov Erik


12


03

Példa:

Dr. Bajalinov Erik


13


03

Prioritást sokszor a löketidő alapján határozzák meg. A löketidő szükséglet meghatározása: – a folyamat (felhasználó) bevallása alapján (a „hazugságot” az OS később bünteti) – előző viselkedés alapján (a korábbi löketidők alapján történő becslés). Kiéheztetés: A folyamat sokáig (esetleg soha) nem jut processzorhoz. Prioritásos algoritmusoknál kiéheztetés felléphet. Ennek kivédése a folyamatok öregítése (aging): – a régóta várakozó folyamatok prioritását növeljük.

Dr. Bajalinov Erik


14


03

Dinamikus prioritás: 1. Legrövidebb (löket) idejű - Shortest Job First, SJF (Nincs konvoj hatás, optimális körülfordulási idő, optimális várakozási idő.) 2. Legrövidebb hátralévő idejű – Shortest Remaining Time First, SRTF (A folyamat megszakítása és egy másik elindítása környezetváltozást igényel, ezt az időt is figyelembe kell vennünk, ezért költséges). 3. Legjobb válaszarány – Highest Response Ratio, HRR (az SJF algoritmus olyan változata, ahol a várakozó folyamatok öregednek)

Dr. Bajalinov Erik


15


03

Többszintű algoritmusok (Multilevel Queue - több várakozási sor) Futásra kész folyamatokat több külön sorban várakoztatják. A sorokhoz prioritás van rendelve. Egy kisebb prioritású sorból csak akkor indulhat el egy folyamat, ha a nagyobb prioritású sorok üresek. Az egyes sorokon belül különböző kiválasztási algoritmusok működhetnek. Statikus többszintű sorok - Static Multilevel Queue, SMQ. A folyamat élete során végig ugyanabban a sorban marad. Visszacsatolt többszintű sorok - Multilevel Feedback Queues, MFQ. A sorokhoz egy időszelet tartozik: minél nagyobb a prioritás, annál kisebb az időszelet. A folyamatok futásuk során átkerülhetnek másik sorokba. (Feedback – visszacsatolás, visszajelzés) Dr. Bajalinov Erik


16


03

Indításkor folyamat mindig legfelső sorba kerül. Ha egy időszelet alatt nem fejeződött be, akkor alacsonyabb prioritású sorba kerül:

Rövidebb folyamatok magasabb prioritású sorba kerülnek, hosszabb – alacsonyabb prioritású sorba …

Dr. Bajalinov Erik


17


03

Többprocesszoros ütemezések Napjainkban egyre jobban terjednek a többprocesszoros (többmagos) rendszerek, ahol felmerül az igény, hogy a futásra kész folyamatok a rendszer bármely processzorán (magon) elindulhassanak.  Heterogén rendszerek esetében egy folyamat csak bizonyos processzorokon futhat.  Homogén rendszerekben a futásra kész folyamatokat közös sorokban tárolja. Szimmetrikus multiprocesszoros rendszer. Minden CPU saját ütemezőt futtat, amely a közös sorokból választ. A sorok osztott használatához a kölcsönös kizárást biztosítani kell! Aszimmetrikus multiprocesszoros rendszer. Az ütemező modul egy dedikált CPU-n fut, ez osztja szét a folyamatokat a szabad CPU-k között.

Dr. Bajalinov Erik


18


03

Algoritmus kiértékelése Analitikus értékelés Determinisztikus modellezés: Előre elkészített numerikus adatokkal vizsgáljuk az algoritmus viselkedését. Egyszerű, de az eredmények csak szűk körben érvényesek.

Sztochasztikus modellezés: Az adateloszlások paraméterei adottak Az algoritmusok matematikai eszközökkel vizsgálhatók - sorbanállás elmélete (queueing theory)

Szimuláció Korábbi tapasztalatok alapján meghatározott véletlen eloszlású számokkal vizsgáljuk az algoritmus működését. Az eredmények nagyban függnek az adatok helyességétől.

Implementáció A legmegbízhatóbb megoldás az algoritmusok implementálása és teljesítményük valós körülmények közötti mérése. Legköltségesebb megoldás.

Dr. Bajalinov Erik


19

Ütemezés (Scheduling),

Recommend Documents