Information Technology | Operating systems » Ütemezés

http://www.doksihu Operációs rendszerek MINB240 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 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 3 1 http://www.doksihu 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ő adatszekezeteit a monitoron kívül deklarált eljárásokból • Kritikus zóna implementációja 4 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 5 É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 Hogy kerüljük el a holdpontot? • Éheztetés • Hatékonyság 6 2 http://www.doksihu Étkező filozófusok probléma • Nyilvánvaló megoldás, de hibás! Probléma: ha egyszerre veszik fel a jobb villát Filozófusok száma Gondolkodik Felveszi a jobb villát Felveszi a másik villát Eszik Visszateszi az egyik majd a másik villát 7 É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 8

Étkező filozófusok 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 Egy filozófus csak akkor mehet át evés állapotba, ha egyik szomszédja Tesztel, sem megfelel-e eszik a feltételeknek 9 3 http://www.doksihu 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 • Hatékony egyidejűség 10 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 11 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 12 4 http://www.doksihu 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 13 Ü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 14 Ü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 15 5 http://www.doksihu Processzusok viselkedése • • • • 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 I/O igényes processzus 16 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 17 Ü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 • Megszakítható ütemezés – Csak egy előre meghatározott ideig futhat 18 6 http://www.doksihu Ü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 Ü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 21 7 http://www.doksihu 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 22 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 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 8 http://www.doksihu 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 25 Háromszintű ütemezés • Kötegelt rendszerekben az ütemezés három szinten történik: • Bebocsátó ütemező • Memória ütemező • CPU ütemező 26 Háromszintű ütemezés – folyt. 27 9 http://www.doksihu II. Ütemezés interaktív rendszerekben 1. 2. 3. 4. 5. 6. 7. 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 • 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 29 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ő 30 10 http://www.doksihu 2.2 Prioritásos ütemezés • 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 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 32 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 33 11 http://www.doksihu 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 34 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 35 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 36 12 http://www.doksihu 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 37 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 38 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 39 13 http://www.doksihu 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 40 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 41 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ó 42 14 http://www.doksihu 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) 43 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 44 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 ütemezhető rendszer i 45 15 http://www.doksihu 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 46 III. Ütemezés valós idejű rendszerekben • Algoritmusok – Állandó arány algoritmus – Legkorábbi határidő először – Lazaságon alapuló algoritmus 47 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ő – Kernel szintű » A processzuson belül a szálütemező dönti el, hogy melyik szál fusson 48 16 http://www.doksihu Felhasználói szintű szálak ütemezése • Kernel csak processzust vált 49 Kernel szintű szálak ütemezése • Kernel processzust vagy szálakat vált 50 Ü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)

51 17 http://www.doksihu 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 52 Processzus azonosító FCFS Kezdő időpont Érkezési idő CPU idő szükséglet P1 0 14 P2 7 8 P3 11 36 P4 20 10 Proc. azonosító Érkezési idő CPU idő szükséglet Befejezési Időpont Várakozási idő P1 P2 0 7 14 8 0 14 14 22 0 7 P3 P4 11 20 36 10 22 58 58 68 11 38 Összes idő: 56 Átlag idő: 56 / 4 = 14 53 Processzus azonosító SJF Proc. Érk CPU idő az. idő szükséglet Kezdő Bef. időpont Időpont Érkezési idő CPU idő szükséglet P1 0 14 P2 7 8 P3 11 36 P4 20 Vár. Várakozó idő processzus 10 Legrövidebb proc. P1 P2 0 7 14 8 0 14 14 22 0 7 P2;P3 P3;P4 P2 P4 P4 P3 20 11 10 36 22 32 32 68 2 21 P3 - P3 - Összes idő: 30 Átlag idő: 30 / 4 = 7,5 54 18 http://www.doksihu Processzus azonosító RR Összes

idő: 44 Átlag idő: 44 / 4 = 11 Időszelet: 10 Proc. Érk CPU idő az. idő szükséglet Kezdő Bef. időpont Időpont Érkezési idő CPU idő szükséglet P1 0 14 P2 7 8 P3 11 36 P4 20 10 Vár. Maradék idő idő Várakozó proc. P1 P2 0 7 14 8 0 10 10 18 0 3 4 - P1;P2 P1;P3 P1* P3 P4 (10) 4 11 36 20 10 18 22 32 22 32 42 8 11 12 26 - P3;P4 P4;P3 P3* P3* P3* (32) 26 (52) 16 (62) 6 42 52 62 52 62 68 10 0 0 16 6 - P3 P3 55- Ü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 19