Operációs rendszerek 3. előadás Ütemezés 1
Szemaforok • Speciális változók, melyeket csak a két, hozzájuk tartozó oszthatatlan művelettel lehet kezelni Down:
while s < 1 do üres_utasítás; s := s - 1;
Up:
s := s + 1;
• A szemaforváltozó más utasításokkal nem érhető el
2
Szemaforok • A szemaforváltozó más utasítással nem érhető el • A szemafort k kezdőértékre állítva a rendszer k darab down műveletet végrehajtó folyamatot enged tovább,a továbbiakat azonban várakoztatja • Ezután csak akkor enged tovább folyamatot a down rendszerhívásból, ha más dolyamat up műveletet hajtott végre • Ez egy olyan általánosított kritikus szakaszt hoz létre, melyiken belül egyszerre k darab folyamat tartózkodhat 3
Mutex • Bináris szemafor • Szemaforváltozója csak két értéket vehet fel (0 / 1; foglalt / szabad) • Kölcsönös kizárásra 1 kezdőértékű mutex • A kritikus szakaszba belépni kívánó folyamat down műveletet hajt végre • A kilépő pedig up műveletet
4
Monitor vs. szemafor • A monitor eljárások, változók, adatszerkezetek együttese, amelyeket egy speciális modulba gyűjtenek egybe. • A monitorok forrásnyelvi konstrukciók, a fordítóprogram pedig tudja, hogy a monitor eljárásait másképp kell kezelni, mint az egyszerű eljárásokat. (A monitor tehát programozási nyelvi fogalom, míg a szemaforok assembly nyelvbe foglalt, DOWN és UP rendszerhívások által kezelt változók. ) • A processzusok bármikor hívhatják a monitorban levő eljárásokat, de nem érhetik el közvetlenül a monitor belső adatszerkezeteit a monitoron kívül deklarált eljárásokból. 5
Monitorok • Speciális modulba gyűjtött eljárások, változók, adatszerkezetek együttese • A processzusok bármikor hívhatják a monitorban levő eljárásokat • Nem érhetik el közvetlenül a monitor belső adatszerkezeteit a monitoron kívül deklarált eljárásokból • Kritikus zóna implementációja • Minden időpillanatban csak egy processzus lehet aktív egy monitorban, és ez lehetővé teszi a kölcsönös kizárást.
6
Klasszikus IPC problémák • Folyamatok közötti kommunikáció - Inter Process Communication (IPC) – Az étkező filozófusok probléma – Az olvasók és írók probléma – Az alvó borbély probléma
7
Étkező filozófusok probléma • Dijkstra (1965) – Evéshez 2 villa szükséges – Egy időben csak 1 villa vehető fel – Gondolkodás; evés
• Holtpontot • Éheztetés • Hatékonyság 8
Holtpont • Ha mind az öt filozófus egyszerre veszi kézbe mondjuk a bal oldali villáját - a másikat nem tudja megszerezni. Holtpont alakul ki.
9
Éheztetés • Ha csak a jobb oldali villa elérhető, tegye azt le és várjon, amíg a bal oldali is szabad lesz. • Előfordulhat, hogy ezt az algoritmust mindegyik filozófus egyszerre hajtja végre, cselekszik, kivár. Mindig történik valami, de nincs előrehaladás. Az ilyen programproblémát éheztetésnek nevezzük. • NEM jó – mi van ha egyszerre teszik le, várnak ugyanannyi időt és ismétlik – mindig kudarc ÉHEZÉS Ezt a helyzetet nevezzük éhezésnek. • Evidens megoldás, hogy várjanak random ideig – helyes érvelés (pl Ethernetet használó helyi hálózatban való csomagküldés) • DE: bizonyos helyzetekben szükséges a biztos megoldás – (pl atomerőmű biztonsági berendezéseinél)
10
Hatékonyság • Ha nem azonos időközönként próbálkoznak a filozófusok, akkor sem valószínű, hogy sokáig fenntartható az, hogy mindig egyen valaki. • Gyakorlati hiba, hogy nem hatékony a módszer, amennyiben egyszerre csak egy filozófus eszik (hiszen akár kettő is megtehetné ezt).
11
Étkező filozófusok probléma • Nyilvánvaló megoldás, de hibás! Filozófusok száma
Probléma: ha egyszerre veszik fel a jobb villát
Gondolkodik Felveszi a jobb villát Felveszi a másik villát Eszik Visszateszi az egyik majd a másik villát 12
Étkező filozófusok probléma Filozófusok száma Szomszédok sorszáma Szemaforok az int speciális fajtája Speciális tömb – a filozófus tevékenységének nyomonkövetésére (eszik, gondolkodik, éhes)
Végtelen ciklus -Gondolkodik - Megszerzi mindkét villát -Eszik -Visszateszi a villákat 13
Étkező filozófusok probléma Belépés a kritikus szekcióba Rögzítjük, hogy éhes Megpróbál villát szerezni Kilépés a kritikus szekcióból Ha nincs villaszerzés, blokkol A LEFT, RIGHT makrók definiálják a szomszédokat Egy filozófus csak akkor mehet át evés állapotba, ha egyik szomszédja Tesztel, sem megfelel-e eszik a feltételeknek 14
Olvasók és írók probléma • Az adatbázisok hozzáférési problémáit modellező feladat – több olvasó lehet a bázisban egyidejűleg – de az írónak kizárólagos joga van a hozzáféréshez (csak akkor lehet írni, ha kizárólag az író szeretne hozzáférni az adatokhoz.)
• Hatékony egyidejűség sérül mert a csak író processz miatt nem engedünk olvasni az olvasó processzeket.
15
Olvasók és írók probléma • Az étkező filozófusok problémakör, és a megoldások jól hasznosíthatók, ha korlátozott számú erőforrás miatt alakul ki versenyhelyzet. • Az író-olvasó probléma nem más, mint az adatbázisok hozzáférési problémáit modellező feladat (például repülőjegy-foglalás). • Elfogadható, hogy több olvasó legyen a bázisban egyidejűleg, de az írónak kizárólagos jogot kell adni a hozzáféréshez. • Ha az olvasó mindig új olvasókat enged maga mellé, (mert teheti), akkor hatékony egyidejűséget kapunk. Ugyanakkor a bázis előtt akár a végtelenségig is várakozhat egy író, hogy az olvasók elfogyjanak, és egyedül maradjon a bázisban. • Ezt elkerülendő, ha író várakozik, és újabb olvasó érkezik, azt az író maga mögé parancsolja. Csak azt kell megvárnia, hogy a bázisban tartózkodó olvasók elfogyjanak. Ez a módszer kevésbé hatékony, mert nem támogatja az egyidejű olvasást oly mértékben mint az előző. 16
Olvasók és írók probléma Kizárólagos elérés beállítása rc-hez
A következő olvasók csak az rc számlálót növelik
Az első olvasó, aki hozzáfér az adatbázishoz, végrehajt egy down-t a db szemaforon Ha kilép az olvasó, akkor az rc számlálót csökkenti Az utolsó olvasó végrehajt egy up-ot a szemaforon Így lehetővé teszi a blokkolt írók belépését Író belépése, írás 17
Az alvó borbély probléma • Egy processzus kiszolgál más processzusokat • Ha nincs kiszolgálandó –alszik • Első érkező ébreszti • Csak bizonyos számú processzus várakozhat • Amíg az eljárás tart, más nem kerül sorra • Ha vége az eljárásnak, a processzus befejeződik, új eljárás kezdődik (ha van) és új processzus léphet be
18
Az alvó borbély probléma A borbély alszik, ha nincs vendég Hajvágásra kész
Hajvágás Kritikus szekcióba lépés Ha van szabad szék Várakozó vendégek számának növelése Bornély felébresztése Vendég kiszolgálása Üzlet teli állapot esetén nem léphet be
19
Ütemezés • Ha több processzus is képes futni de csak egy erőforrás áll rendelkezésre • Op.rsz.-nek el kell döntenie, hogy melyik processzus fusson ütemezés • Ütemezési algoritmus • Processzusra és szálakra egyaránt vonatkozhat
20
A jó ütemezési algoritmus néhány feltétele • Pártatlanság • Hatékonyság • Válaszidő minimalizálása az interaktív felhasználóknál • Áthaladási idő minimalizálása a kötegelt felhasználóknál • Áteresztőképesség, azaz maximalizálni az egy időegység alatt elvégzett munkák számát. (A fenti elvárások gyakran ellentmondanak egymásnak ) 21
Ütemezés tulajdonságok • Gyakran fut – gyorsnak kell lennie (a CPU idő ne az ütemezéssel teljék) ezért: • Része a kernelnek • Állandóan a memóriában van
• Fajtái: • Preemtív ütemezés: az op.rsz. elveheti a futás jogát az éppen futó folyamattól • Nem preemtív: a futó folyamat addig birtokolja a CPU-t, míg állapotot nem vált
22
Processzusok viselkedése • • • •
CPU dolgozik egy ideig Rendszerhívás I/O művelet befejezésére várakozik Ismét számol
Számításigényes processzus
I/O igényes processzus
23
Mikor ütemezzünk? •
Feltétlenül szükséges: 1. Processzus befejeződésekor 2. Processzus blokkolódása I/O művelet vagy szemafor miatt
•
Ezen felül még ütemezésre kerül sor: 3. Új processzus létrejöttekor 4. I/O megszakítás esetén 5. Időmegszakítás esetén
24
Ütemezési algoritmusok • Időzítő-megszakítások kezelésének vonatkozásában lehetnek: • Nem megszakítható ütemezés – Addig engedi futni,a míg az nem blokkolódik, vagy le nem mond a CPU-ról – Csak úgy valósítható meg, ha az időintervallum végén egy időzítő megszakítást generál , ezáltal a CPU visszakerül az ütemezőhöz – Ha nincs időzítő. Akkor az egyedüli megoldás a nem megszakítható ütemezés
• Megszakítható ütemezés – Csak egy előre meghatározott ideig futhat, ha a kiszabott időintervallum végén még mindig futna, akkor felfüggesztésre kerül és az ütemző egy másik processzust választ helyette. 25
Ütemezési algoritmusok csoportosítása 1. Kötegelt • Nincsenek felhasználók • Nem megszakítható ütemezési algoritmusok 2. Interaktív • Időnkénti megszakítás nélkülözhetetlen • Különben egy processzus kizárhatná a többit • Megszakításos ütemezés 3. Valós idejű • Nem mindig van szükség megszakításos ütemezésre mivel a processzusok tudják, hogy nem futhatnak hosszú ideig, rendszerint gyorsan elvégzik a 26 feladatukat.
Ütemezési algoritmusok céljai Minden rendszer
I. Kötegelt rendszerek
Pártatlanság Elvek betartása Egyensúly
Áteresztőképesség Áthaladási idő CPU kihasználtság
II. Interaktív rendszerek Válaszidő Arányosság
III. Valós idejű rendszerek Határidők betartása Adatvesztés elkerülése Előrejelezhetőség
27
I. Ütemezés kötegelt rendszerekben 1. Sorrendi ütemezés (FCFS) 2. A legrövidebb feladat először (SJF) 3. A legrövidebb maradék futási idejű következzen (SRTF) Megjegyzés: némelyik algoritmus kötegelt és interaktív rendszereknél egyaránt használatos
28
II. Ütemezés interaktív rendszerekben 1. Round Robin ütemezés 2. Prioritásos ütemezés 3. Többszörös sorok 4. Legrövidebb processzus következzen 5. Garantált ütemezés 6. Sorsjáték ütemezés 7. Arányos ütemezés Ezek mindegyike alkalmas kötegelt rendszerekben CPU ütemezésre Bár háromszintű ütemezés nem alkalmazható itt,de kétszintű igen.(memória, CPU) 29
III. Ütemezés valós idejű rendszerekben • Algoritmusok – Állandó arány algoritmus – Legkorábbi határidő először – Lazaságon alapuló algoritmus
30
1.1. Sorrendi ütemezés • FCFS (First Come Firts Served) • Olyan sorrendben osztja ki a CPU-t, ahogyan a processzusok kérik azt • A futásra kész processzusok egyetlen várakozó soron állnak – láncolt lista • A kiválasztás – a sor elejéről az első processzus levétele • Legegyszerűbb nem megszakítható algoritmus 31
1.2. A legrövidebb feladat először SJF (Shortest Job First) • Feltételezi, hogy a futási idők előre ismertek • Ha több egyformán fontos feladat van a bemenő sorban futásra készen • A legrövidebb feladatot először algoritmus bizonyíthatóan optimális. • Az ütemező a legrövidebb feladatot választja
Átlagos áthaladási idő
32
1.2. A legrövidebb feladat először – folyt. • Bizonyíthatóan optimális algoritmus Pl.: Négyfeladatos eset, a,b,c,d futási időkkel (4a + 3b + 2c + d) / 4 Megjegyzés: csak akkor optimális, ha a feladatok egyszerre a rendelkezésre állnak
33
1.3. A legrövidebb maradék futási idejű következzen • Shortest Remaining Timem First (SRTF) • A legrövidebb feladat először algoritmus megszakítható változata • Szintén előre ismerni kell a futási időket • Az ütemező azt a feladatot választja, melynek befeje zéséig legkevesebb a megmaradt ideje
34
Háromszintű ütemezés • Kötegelt rendszerekben az ütemezés három szinten történik: • Bebocsátó ütemező • Memória ütemező • CPU ütemező
35
Bebocsátó ütemező • Újonnan érkező feladatok először egy belépési várakozó sorba kerülnek • A bebocsátó ütemező dönti el, hogy mely feladatok léphetnek be a rendszerbe, a többi a sorban marad • Az itteni algoritmus a megfelelő keveréket állítja elő – számításigény I/O igény vagy a rövid feladatokat hamarabb beengedi • Ha a feladat már belépett a rendszerbe, akkor létre lehet számára hozni egy processzust és elkezdhet vetélkedni a CPU-ért 36
Memória ütemező • Az is megtörténhet, hogy olyan sok processzus van, hogy nem férnek el a memóriában • A memóriaütemező dönti el, hogy mely processzusok maradhatnak és melyek írandóak ki a lemezre • A döntést sűrűn felül kell vizsgálni, hogy a lemezen tárolt feladatoknak is legyen esélye a bekerülésre 37
CPU ütemező • Az ütemező harmadik szintje választja ki valójában, hoyg a futásra kész programok közül melyik fusson következőnek • Ez a CPU ütemező – bármilyen megfelelő algoritmus használható itt,a kár megszakító akár nem
38
II. Ütemezés interaktív rendszerekben 1. Round Robin ütemezés 2. Prioritásos ütemezés 3. Többszörös sorok 4. Legrövidebb processzus következzen 5. Garantált ütemezés 6. Sorsjáték ütemezés 7. Arányos ütemezés Ezek mindegyike alkalmas kötegelt rendszerekben CPU ütemezésre Bár háromszintű ütemezés nem alkalmazható itt,de kétszintű igen.(memória, CPU) 39
2.1. Round Robin ütemezés • Minden processzusnak ki van osztva egy időintervallum időszelet • Ha az időszelet letelte utána processzus még fut, akkor átadódik a vezérlés egy másik processzusra • Legrégebbi, legegyszerűbb, legpártatlanabb, legszélesebb körben alkalmazott algoritmus • Feltételezi, hogy minden processzus egyformán fontos.
40
2.1. Round Robin ütemezés – folyt. • Környezetátkapcsolás (processzusátkapcsolás) • Problémák: • Időszelet túl kicsire választása – túl sok processzus átkapsolást okoz – csökken a CPU hatékonysága • Időszelet túl nagyra állítása – Rövid interaktív kérésekre gyenge válaszidő 41
2.2. Prioritásos ütemezés • • • •
Minden processzushoz rendeljünk egy prioritást A legmagasabb prioritású futásra kész processzus futhasson Külső tényezők figyelembe vételének igénye A végtelen ideig történő futás megelőzésére: • Ütemező minden óraütemben csökkentheti az éppen futó processzus prioritását • Minden processzushoz hozzárendelhetünk egy időszeletet amíg futhat • Mikor ezt kihasználta; a köv. legmagasabb prioritású futhat 42
2.2. Prioritásos ütemezés – folyt. • Prioritás hozzárendelés: • Statikusan • Dinamikusan
• Prioritási osztályba sorolás • Osztályok között – prioritásos ütemezés • Osztályon belül – round robin ütemezés
43
2.2. Prioritásos ütemezés – folyt. • Amíg van futtaható processzus egy osztályon belül, mindegyik egy időszeletig fut • Ha üres, akkor a következő szint processzusai futhatnak • Szükséges a prioritások időnkénti igazítása, különben az alacsonyabb szintek éhen halnak. • MINIX rendszer által használt
44
2.3. Többszörös sorok Multilevel Queues • CPU igényes processzusok esetén hatékonyabb: – ha időnként nagy időszeleteket adnak – mintha gyakran adnak neki kicsit (sok lapcsere)
• De ha minden processzus kapna nagy időszeletet: – Gyenge válaszidő jelentkezne
• Megoldás: – Prioritási osztályok felállítása • Static Multilevel Queues • Multilevel Feddback Queues 45
2.3. Többszörös sorok – folyt. Prioritási osztály
Időszelet
N. prioritási osztály
1 időszeletig fut
N-1.prioritási osztály
2 időszeletig fut
N-2.prioritási osztály
4 időszeletig fut
N-3.prioritási osztály
8 időszeletig fut
…
…
• Ha egy processzus elhasználja a számára biztosított időszeletet, egy osztállyal lejjebb kerül
46
2.3. Többszörös sorok fajtái Statikus többszörös sorok - Static Multilevel Queues (SMQ) – Minden folyamat indulásakor rendelünk egy prioritást – Ez a folyamat élete során nem változik – Hátrány: éheztetés
Visszacsatolt többszörös sorok - Multilevel Feedback Queues (MFQ) – Öregítés technika – A folyamatokhoz dinamikus prioritás rendelődik
47
2.4. Legrövidebb processzus következzen • A kötegelt rendszerekben minimális válaszidőt adó „legrövidebb feladat először” módszer alkalmazása interaktív processzusoknál Probléma: a párhuzamosan futtatható processzusok között melyik a legrövidebb
48
2.4. Legrövidebb processzus következzen – folyt. • Legrövidebb processzus kiválasztása: • Becslés a múltbeli viselkedés alapján –legkisebb becsült futási idő alapján futtatjuk • Öregedés – sorozat következő elemét úgy becsüljük, hogy vesszük az éppen mért értéknek és az előző becslésnek a súlyozott átlagát
49
2.5. Garantált ütemezés • Ígéret és betartása a teljesítményt illetőleg • Ha n felhasználó van bejelentkezve, akkor a CPU teljesítmény kb. 1/n-ed részét fogod megkapni • Nyomon kell követni, hogy egy processzus mennyi CPU időt kapott létrehozása óta • Számolható a neki járó mennyiség • Aktuális / neki járó arány számolható • A legkisebb arányszámmal rendelkező processzus futtatja az algoritmus
50
2.6. Sorsjáték ütemezés • A processzusok között másodpercenként meghatározott számú sorsjegyet (CPU idő egységet) oszt ki az ütemező • A magasabb prioritású processzusok több sorsjegyet kapnak • Együttműködő processzusok átadhatják egymásnak a sorsjegyeiket
51
2.7. Arányos ütemezés • Az ütemező figyelembe veszi, hogy ki a processzus tulajdonosa Pl.: ha két felhasználó van felesben lett előirányozva a CPU idő akkor ennyit fognak kapni függetlenül attól, hány processzust futtatnak
52
III. Ütemezés valós idejű rendszerekben • • •
Idő alapvető szerepet játszik Aktuális fizikai mennyiségek alapján valós időn belül kell eredményt adniuk Fajtái: – –
szigorú valós idejű rendszerek, abszolút határidőkkel lágy valós idejű rendszerek, ahol a határidő elmulasztása tolerálható
53
III. Ütemezés valós idejű rendszerekben – folyt. • Valós idejű operációs rendszerekre jellemző: • Kis méret • Rövid megszakítási idő • Gyors környezetcsere • Rövid ideig tartó megszakítás • Többszörös időzítő kezelés (ezred és mikromásodperces nagyságrendben)
54
III. Ütemezés valós idejű rendszerekben – folyt. • Valósidejűség elérése: –
•
programokat rövid, megjósolható időtartamú processzusokra osztjuk, melyek viselkedése előre ismert
A valós idejű rendszerek programozható eseményei lehetnek – –
periodikusak illetve aperiodikusak
55
III. Ütemezés valós idejű rendszerekben – folyt. Pl.: legyen m periodikus eseményünk az i-dik esemény periódusa Pi az egyes események kezelésének ideje Ci A sorozat csak akkor kezelhető, ha:
m
Ci ≤1 ∑ i =1 Pi
ütemezhető rendszer
56
III. Ütemezés valós idejű rendszerekben – folyt. •
Valós idejű rendszerek ütemező algoritmusai: –
Statikusak • •
–
Döntéseket a rendszer futásának megkezdése előtt hozza Csak akkor működik ha előzetes teljes ismereteink vannak a feladatokról és határidőkről
Dinamikusak • •
Ütemezési döntéseket futás közben hozza Nincs korlátozás a használatánál 57
III. Ütemezés valós idejű rendszerekben • Algoritmusok – Állandó arány algoritmus – Legkorábbi határidő először – Lazaságon alapuló algoritmus
58
Szálütemezés • Processzuson belül több végrehajtási szál kétszintű párhuzamosság • Kernel kiválaszt egy processzust/szálat és átadja neki a vezérlést egy időszelet erejéig • Fajtái: – Felhasználói szintű - Processzuson belül nincs időzítő - A processzuson belül a szálütemező dönti el, hogy melyik szál fusson - A szálak párhuzamos futtatásához nincs időmegszakítás, így a kiválasztott szál addig futhat,ameddig akar. Ha elhasználja a processzus összes időszeletét, akkor a kernel a másik processzusra kapcsol át. Amik a processzus újra futhat, akkor a szál folytatja a futását. 59
Felhasználói szintű szálak ütemezése • Kernel csak processzust vált
60
Kernel szintű szálak ütemezése • Kernel processzust vagy szálakat vált
61
Ütemezési algoritmusok összehasonlítási szempontjai • A központi egység kihasználtság (CPU utilization):
ΣCPUidő − Σ(henyélés+ ad min isztáció) ⋅100[%] ΣCPUidő Elvégzettmunkákszáma Idő
• Átbocsátó képesség (throughput): • Körülfordulási idő (turnaround time):
Σ (végrahajtási + várakozási)idő
• Várakozási idő (waiting time): Σ (várakozó + futásra kész + felfüggesztett + hosszú távú ütemezésig eltelt ) idő
• Válaszidő (response time) 62
Ütemezési algoritmusok összehasonlítási szempontjai • A központi egység kihasználtság (CPU utilization): • A CPU idő hány százaléka fordítódik ténylegesen a folyamatok utasításainak végrehajtására. A kihasználtságot csökkenti amikor a CPU henyél (idle) vagy a rendszeradminisztráció. • A kihasználtság tipikus értékei 40-50% • Átbocsátó képesség: • Az időegység alatt elvégzett munkák száma. (Elvégzett munkák száma/idő) • Értéke nagyon széles tartományon mozoghat, ez elvégzett munka jellegétől függően
63
Ütemezési algoritmusok összehasonlítási szempontjai • Körülfordulási idő: • Egy-egy munkára vonatkozóan a rendszerbe helyezéstől a munka befejeződéséig eltelt idő. (Végrehajtási idő+Várakozási idő) • A képletben is szereplő végrehajtási idő nem függ az ütemezési algoritmustól, így azok jellemzésére alkalmasabba várakozási idő megadása • Várakozási idő: • Egy munka összesen mennyi időt tölt várakozással • Válaszidő: • Fontos az időosztásos rendszereknél, hogy a felhasználó érezze, hogy a rendszer reagál a parancsaira • Az az idő, amely az operációs rendszer kezelői felületének - esetleg egy felhasználóval kommunikáló folyamatnak- adott kezelői parancs után a rendszer első látható reakciójáig eltelik, vagyis amennyi idő alatt a rendszer válaszolni képes. 64
FCFS, SJF, RR összehasonlítása Példa:
Processzus azonosító
Érkezési idő
CPU idő szükséglet
P1
0
14
P2
7
8
P3
11
36
P4
20
10 65
Processzus azonosító
FCFS Proc. azonosító
Érkezési idő
CPU idő szükséglet
P1 P2 P3 P4
0 7 11 20
14 8 36 10
Kezdő időpont
0 14 22 58
Érkezési idő
CPU idő szükséglet
P1
0
14
P2
7
8
P3
11
36
P4
20
10
Befejezési Időpont
13 21 57 67
Várakozási idő
0 7 11 38
Összes várakozási idő: 56 Átlagos várakozási idő: 56 / 4 = 14 66
Processzus azonosító
SJF Proc. Érk. CPU idő az. idő szükséglet
P1 P2 P4 P3
0 7 20 11
14 8 10 36
Kezdő Bef. időpont Időpont
0 14 22 32
13 21 31 67
Érkezési idő
P1
0
14
P2
7
8
P3
11
36
P4
20
10
Vár. Várakozó idő processzus
0 7 2 21
CPU idő szükséglet
P2;P3 P3;P4 P3 -
Legrövidebb proc.
P2 P4 P3 -
Összes várakozási idő: 30 Átlagos várakozási idő: 30 / 4 = 7,5 67
Processzus azonosító
RR
Összes idő: 44 Átlag idő: 44 / 4 = 11
Időszelet: 10
Proc. Érk. CPU idő az. idő szükséglet
P1 P2 P1* P3 P4 P3* P3* P3*
0 7 (10) 11 20 (32) (52) (62)
14 8 4 36 10 26 16 6
Kezdő Bef. időpont Időpont
0 10 18 22 32 42 52 62
9 17 21 31 41 51 61 67
CPU idő szükséglet
P1
0
14
P2
7
8
P3
11
36
P4
20
10
Vár. Maradék idő idő
0 3 8 11 12 10 0 0
Érkezési idő
4 26 16 6 -
Várakozó proc.
P1;P2 P1;P3 P3;P4 P4;P3 P3 P3 68 -
Ütemezés többprocesszoros rendszereknél • Heterogén rendszerek esetén: – A rendszerbe építet CPU-k különböznek (utasításkészlet) – A programok kötötten futhatnak, azaz a futtatásuk utasításkészlet miatt kötődhet egy bizonyos CPU-hoz
• Homogén rendszerek esetén: – – – –
CPU-k funkcionalitás szempontjából egyformák A futásra kész folyamatok a rendszer bármely szabad CPU-ján futhatnak Közös várakozási sor Kétféle ütemezési megközelítés: • Szimmetrikus multiprocesszoros rendszer - minden CPU-nak saját ütemezője lehet, ami a közös sorból választ - Kölcsönös kizárás bitosítása • Aszimmetrikus multiprocesszoros rendszer – egyetlen ütemező egy kiválasztott processzoron, és ez osztja szétt a feladatokat a szabad CPU-k között. - Egyszerűbb adathozzáférést eredményez 69
Következő előadás témája Ütemezés megvalósítási elvei • MINIX • UNIX • Windows NT rendszerek esetén
70
