Szemaforok • Speciális változók, melyeket csak a két, hozzájuk tartozó oszthatatlan művelettel lehet kezelni
Operációs rendszerek
Down:
MINB240
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
3. előadás Ütemezés 1
2
Mutex
Monitorok
• Bináris szemafor • Szemaforváltozója csak két értéket vehet fel (0 / 1; foglalt / szabad)
• 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
• 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
4
Klasszikus IPC problémák
Étkező filozófusok probléma • Dijkstra (1965)
• Folyamatok közötti kommunikáció - Inter Process Communication (IPC)
– 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?
– Az étkező filozófusok probléma – Az olvasók és írók probléma – Az alvó borbély probléma
• Éheztetés • Hatékonyság
5
Étkező filozófusok probléma
Étkező filozófusok probléma
• Nyilvánvaló megoldás, de hibás! Filozófusok száma
6
Filozófusok száma Szomszédok sorszáma
Probléma: ha egyszerre veszik fel a jobb villát
Szemaforok az int speciális fajtája
Gondolkodik Felveszi a jobb villát
Speciális tömb – a filozófus tevékenységének nyomonkövetésére (eszik, gondolkodik, éhes)
Felveszi a másik villát Eszik Visszateszi az egyik majd a másik villát 7
Végtelen ciklus -Gondolkodik - Megszerzi mindkét villát -Eszik -Visszateszi a villákat 8
Étkező filozófusok probléma
Olvasók és írók probléma
Belépés a kritikus szekcióba Rögzítjük, hogy éhes 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
• 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
Egy filozófus csak akkor mehet át evés állapotba, ha egyik szomszédja Tesztel, sem megfelel-e eszik a feltételeknek 9
Olvasók és írók probléma Kizárólagos elérés beállítása rc-hez
Az alvó borbély probléma
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
Író belépése, írás
10
Az utolsó olvasó végrehajt egy up-ot a szemaforon Így lehetővé teszi a blokkolt írók belépését
11
• 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
12
Az alvó borbély probléma
Ütemezés
A borbély alszik, ha nincs vendég Hajvágásra kész Hajvágá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
Kritikus szekcióba lépés Ha van szabad szék Várakozó vendégek számának növelése
• Processzusra és szálakra egyaránt vonatkozhat
Bornély felébresztése Vendég kiszolgálása Üzlet teli állapot esetén nem léphet be
13
14
Ütemezés tulajdonságok
Processzusok viselkedése
• 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:
• • • •
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
• 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
15
I/O igényes processzus
16
Mikor ütemezzünk? •
Ütemezési algoritmusok
Feltétlenül szükséges:
• Időzítő-megszakítások kezelésének vonatkozásában lehetnek:
1. Processzus befejeződésekor 2. Processzus blokkolódása I/O művelet vagy szemafor miatt
•
• Nem megszakítható ütemezés – Addig engedi futni,a míg az nem blokkolódik, vagy le nem mond a CPU-ról
Ezen felül még ütemezésre kerül sor:
• Megszakítható ütemezés
3. Új processzus létrejöttekor 4. I/O megszakítás esetén 5. Időmegszakítás esetén
– Csak egy előre meghatározott ideig futhat
17
Ü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 19
18
Ü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
20
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
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
21
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 • Az ütemező a legrövidebb feladatot választja
23
22
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
24
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 befejezéséig legkevesebb a megmaradt ideje
Háromszintű ütemezés • Kötegelt rendszerekben az ütemezés három szinten történik: • Bebocsátó ütemező • Memória ütemező • CPU ütemező
25
Háromszintű ütemezés – folyt.
26
II. Ütemezés interaktív rendszerekben 1. 2. 3. 4. 5. 6. 7.
27
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
2.1. Round Robin ütemezés
2.1. Round Robin ütemezés – folyt.
• 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
• 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ő
29
2.2. Prioritásos ütemezés
30
2.2. Prioritásos ütemezés – folyt.
• 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 31
• 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
32
2.3. Többszörös sorok Multilevel Queues
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
• 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
33
2.3. Többszörös sorok – folyt. Prioritási osztály
2.3. Többszörös sorok fajtái Statikus többszörös sorok - Static Multilevel Queues (SMQ)
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
…
…
34
– Minden folyamat indulásakor rendelünk egy prioritást – Ez a folyamat élete során nem változik – Hátrány: éheztetés
• Ha egy processzus elhasználja a számára biztosított időszeletet, egy osztállyal lejjebb kerül
35
Visszacsatolt többszörös sorok - Multilevel Feedback Queues (MFQ) – Öregítés technika – A folyamatokhoz dinamikus prioritás rendelődik
36
2.4. Legrövidebb processzus következzen
2.4. Legrövidebb processzus következzen – folyt.
• 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
• 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
37
2.5. Garantált ütemezés
38
2.6. Sorsjáték ü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
39
• 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
40
2.7. Arányos ütemezés
III. Ütemezés valós idejű rendszerekben
• 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
•
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ó
41
III. Ütemezés valós idejű rendszerekben – folyt.
42
III. Ütemezés valós idejű rendszerekben – folyt. • Valósidejűség elérése:
• 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)
– 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
43
44
III. Ütemezés valós idejű rendszerekben – folyt. Pl.: legyen m periodikus eseményünk
III. Ütemezés valós idejű rendszerekben – folyt. •
az i-dik esemény periódusa Pi az egyes események kezelésének ideje Ci A sorozat csak akkor kezelhető, ha:
Valós idejű rendszerek ütemező algoritmusai: – Statikusak • •
m
Ci ≤1 ∑ P i =1 i
ütemezhető rendszer
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
45
III. Ütemezés valós idejű rendszerekben
46
Szálütemezés • Processzuson belül több végrehajtási szál kétszintű párhuzamosság
• Algoritmusok – Állandó arány algoritmus – Legkorábbi határidő először – Lazaságon alapuló algoritmus
• 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ő – Kernel szintű » A processzuson belül a szálütemező dönti el, hogy melyik szál fusson
47
48
Felhasználói szintű szálak ütemezése • Kernel csak processzust vált
Kernel szintű szálak ütemezése • Kernel processzust vagy szálakat vált
49
Ütemezési algoritmusok összehasonlítási szempontjai
50
FCFS, SJF, RR összehasonlítása Példa:
• 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) 51
Processzus azonosító
Érkezési idő
CPU idő szükséglet
P1
0
14
P2
7
8
P3
11
36
P4
20
10 52
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
Processzus azonosító
SJF
Érkezési idő
P1
0
14
P1
0
14
P2
7
8
P2
7
8
P3
11
36
P3
11
36
P4
20
10
P4
20
10
Befejezési Időpont
0 14 22 58
Várakozási idő
14 22 58 68
0 7 11 38
Összes idő: 56 Átlag idő: 56 / 4 = 14
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
Vár. Várakozó idő processzus
0 7 2 21
P2;P3 P3;P4 P3 -
Processzus azonosító
Ö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
10 18 22 32 42 52 62 68
Érkezési idő
P1
0
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 -
14
Várakozó proc.
P1;P2 P1;P3 P3;P4 P4;P3 P3 P3 55-
Legrövidebb proc.
P2 P4 P3 -
Összes idő: 30 Átlag idő: 30 / 4 = 7,5
53
RR
CPU idő szükséglet
54
Ü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
• 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 56
Következő előadás témája Ütemezés megvalósítási elvei • MINIX • UNIX • Windows NT rendszerek esetén
57
