Mutex • Bináris szemafor • Szemaforváltozója csak két értéket vehet fel (0 / 1; foglalt / szabad)
Operációs rendszerek MINB240
• 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
3. előadás Ütemezés 1
3
Szemaforok
Monitorok
• Speciális változók, melyeket csak a két, hozzájuk tartozó oszthatatlan művelettel lehet kezelni Down:
• 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ő adatszekezeteit a monitoron kívül deklarált eljárásokból • Kritikus zóna implementációja
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
4
1
2
Klasszikus IPC problémák
Étkező filozófusok probléma
• Folyamatok közötti kommunikáció - Inter Process Communication (IPC)
• Nyilvánvaló megoldás, de hibás!
Probléma: ha egyszerre veszik fel a jobb villát
Filozófusok száma Gondolkodik
– Az étkező filozófusok probléma – Az olvasók és írók probléma – Az alvó borbély probléma
Felveszi a jobb villát Felveszi a másik villát Eszik Visszateszi az egyik majd a másik villát 5
7
Étkező filozófusok probléma
Étkező filozófusok probléma
• Dijkstra (1965)
Filozófusok száma Szomszédok sorszáma
– Evéshez 2 villa szükséges – Egy időben csak 1 villa vehető fel – Gondolkodás; evés Hogy kerüljük el a holdpontot?
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)
• Éheztetés Végtelen ciklus -Gondolkodik - Megszerzi mindkét villát -Eszik -Visszateszi a villákat
• Hatékonyság
6
8
3
4
Étkező filozófusok probléma
Olvasók és írók probléma Kizárólagos elérés beállítása rc-hez
Belépés a kritikus szekcióba Rögzítjük, hogy éhes
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
Megpróbál még egy 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
Ha kilép az olvasó, akkor az rc számlálót csökkenti
Egy filozófus csak akkor mehet át evés állapotba, ha egyik szomszédja Tesztel, sem megfelel-e eszik a
Író belépése, írás
Az utolsó olvasó végrehajt egy up-ot a szemaforon Így lehetővé teszi a blokkolt írók belépését
feltételeknek 9
11
Olvasók és írók probléma
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
• 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
• Hatékony egyidejűség
10
12
5
6
Az alvó borbély probléma
Ütemezés tulajdonságok • Gyakran fut – gyorsnak kell lennie (a CPU idő ne az ütemezéssel teljék) ezért:
A borbély alszik, ha nincs vendég
• Része a kernelnek • Állandóan a memóriában van
Hajvágásra kész
• Fajtái:
Hajvágás
• 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
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
13
15
Ütemezés
Processzusok viselkedése
• 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
I/O igényes processzus
CPU dolgozik egy ideig Rendszerhívás I/O művelet befejezésére várakozik Ismét számol
Sztámításigényes processzus
14
16
7
8
Mikor ütemezzünk? •
Ütemezési algoritmusok csoportosítása
Feltétlenül szükséges:
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
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
17
19
Ütemezési algoritmusok
Ütemezési algoritmusok céljai
• 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
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
• Megszakítható ütemezés – Csak egy előre meghatározott ideig futhat II. Interaktív rendszerek Válaszidő Arányosság
18
III. Valós idejű rendszerek Határidők betartása Adatvesztés elkerülése Előrejelezhetőség
20
9
10
1.2. A legrövidebb feladat először
I. Ütemezés kötegelt rendszerekben
SJF (Shortest Job First)
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)
• 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 • Az ütemező a legrövidebb feladatot választja
Megjegyzés: némelyik algoritmus kötegelt és interaktív rendszereknél egyaránt használatos
21
23
1.2. A legrövidebb feladat először – folyt.
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
• 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
22
24
11
12
1.3. A legrövidebb maradék futási idejű következzen
Háromszintű ütemezés – folyt.
• 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 befejezéséig legkevesebb a megmaradt ideje
25
27
Háromszintű ütemezés
II. Ütemezés interaktív rendszerekben
• Kötegelt rendszerekben az ütemezés három szinten történik:
1. 2. 3. 4. 5. 6. 7.
• Bebocsátó ütemező • Memória ütemező • CPU ütemező
26
Round Robin ütemezés Prioritásos ütemezés Többszörös sorok Legrövidebb processzus következzen Garantált ütemezés Sorsjáték ütemezés Arányos ütemezés
28
13
14
2.1. Round Robin ütemezés
2.2. Prioritásos ü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
• Minden processzushoz rendeljünk egy prioritást • A legmagasabb prioritású futásra kész processzus futhasson • 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
29
31
2.2. Prioritásos ütemezés – folyt.
2.1. Round Robin ütemezés – folyt.
• Prioritás hozzárendelés:
• Környezetátkapcsolás (processzusátkapcsolás)
• Statikusan • Dinamikusan
• Prioritási osztályba sorolá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ő
• Osztályok között – prioritásos ütemezés • Osztályon belül – round robin ütemezés
30
32
15
16
2.3. Többszörös sorok – folyt.
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
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
33
35
2.3. Többszörös sorok Multilevel Queues
2.3. Többszörös sorok fajtái Statikus többszörös sorok - Static Multilevel Queues (SMQ)
• CPU igényes processzusok esetén hatékonyabb:
– Minden folyamat indulásakor rendelünk egy prioritást – Ez a folyamat élete során nem változik – Hátrány: éheztetés
– ha időnként nagy időszeleteket adnak – mintha gyakran adnak neki kicsit (sok lapcsere)
• De ha minden processzus kapna nagy időszeletet:
Visszacsatolt többszörös sorok - Multilevel Feedback Queues (MFQ)
– Gyenge válaszidő jelentkezne
• Megoldás:
– Öregítés technika – A folyamatokhoz dinamikus prioritás rendelődik
– Prioritási osztályok felállítása
34
36
17
18
2.4. Legrövidebb processzus következzen
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
• 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
37
39
2.4. Legrövidebb processzus következzen – folyt.
2.6. Sorsjáték ütemezés
• Legrövidebb processzus kiválasztása:
• 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
• 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
38
40
19
20
III. Ütemezés valós idejű rendszerekben – folyt.
2.7. Arányos ütemezés • Az ütemező figyelembe veszi, hogy ki a processzus tulajdonosa
• 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)
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
41
43
III. Ütemezés valós idejű rendszerekben – folyt. • Valósidejűség elérése:
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ó
A valós idejű rendszerek programozható eseményei lehetnek – –
42
programokat rövid, megjósolható időtartamú processzusokra osztjuk, melyek viselkedése előre ismert
periodikusak illetve aperiodikusak
44
21
22
III. Ütemezés valós idejű rendszerekben
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
∑P i =1
≤1
• Algoritmusok – Állandó arány algoritmus – Legkorábbi határidő először – Lazaságon alapuló algoritmus
ütemezhető rendszer
i
45
47
III. Ütemezés valós idejű rendszerekben – folyt. •
Szálütemezés • Processzuson belül több végrehajtási szál kétszintű párhuzamosság
Valós idejű rendszerek ütemező algoritmusai: –
• •
–
• Kernel kiválaszt egy processzust/szálat és átadja neki a vezérlést egy időszelet erejéig • Fajtái:
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
– Felhasználói szintű » Processzuson belül nincs időzítő – Kernel szintű » A processzuson belül a szálütemező dönti el, hogy melyik szál fusson
Dinamikusak • •
Ütemezési döntéseket futás közben hozza Nincs korlátozás a használatánál 46
48
23
24
Ütemezési algoritmusok összehasonlítási szempontjai
Felhasználói szintű szálak ütemezése • Kernel csak processzust vált
• 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) 49
51
Kernel szintű szálak ütemezése
FCFS, SJF, RR összehasonlítása
• Kernel processzust vagy szálakat vált
Példa:
Processzus azonosító
50
Érkezési idő
CPU idő szükséglet
P1
0
14
P2
7
8
P3
11
36
P4
20
10 52
25
26
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
Érkezési idő
CPU idő szükséglet
P1
0
14
P2
7
8
P3
11
36
P4
20
10
Befejezési Időpont
0 14 22 58
RR
Átlag idő: 44 / 4 = 11 Időszelet: 10
Várakozási idő
14 22 58 68
Proc. Érk. CPU idő az. idő szükséglet
P1 P2 P1* P3 P4 P3* P3* P3*
0 7 11 38
Összes idő: 56 Átlag idő: 56 / 4 = 14 53
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
14 22 32 68
Érkezési idő 0
14
P2
7
8
P3
11
36
P4
20
10
Vár. Várakozó idő processzus
0 7 2 21
P2;P3 P3;P4 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
10 18 22 32 42 52 62 68
Érkezési idő
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
CPU idő szükséglet
4 26 16 6 -
Várakozó proc.
P1;P2 P1;P3 P3;P4 P4;P3 P3 P3 55-
Ütemezés többprocesszoros rendszereknél
CPU idő szükséglet
P1
Processzus azonosító
Összes idő: 44
• 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
Legrövidebb proc.
P2 P4 P3 -
• 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 • Aszimmetrikus multiprocesszoros rendszer – egyetlen ütemező egy kiválasztott processzoron
Összes idő: 30 Átlag idő: 30 / 4 = 7,5 54
56
27
28
Következő előadás témája Ütemezés megvalósítási elvei • MINIX • UNIX • Windows NT rendszerek esetén
57
29
