PB 153 Operační systémy a jejich rozhraní1 Plánování CPU PB153 Operační systémy a jejich rozhraní PB 153 Operační systémy a jejich rozhraní2 Multiprogramování  Multiprogramování zvyšuje využití CPU  Pokud jeden proces čeká na dokončení I/O operace může jiný proces CPU využít  Nejlepšího výsledku dosáhneme při vhodné kombinaci procesů orientovaných na I/O a na využití CPU PB 153 Operační systémy a jejich rozhraní3 Střídání využití CPU a I/O  Proces obvykle střídá části využívající CPU a části vyžadující I/O.  Při zahájení I/O je proces zařazen mezi procesy čekající na událost.  Teprve při ukončení I/O operace se proces opět dostává mezi procesy „připravené“. PB 153 Operační systémy a jejich rozhraní4 Histrogram doby využití CPU PB 153 Operační systémy a jejich rozhraní5 Stavy procesu PB 153 Operační systémy a jejich rozhraní6 Plánování CPU  Krátkodobý plánovač – dispečer  Vybírá proces, kterému bude přidělen CPU  Vybírá jeden z procesů, které jsou zavedeny operační paměti a které jsou „připravené“  Plánovací rozhodnutí může vydat v okamžiku, kdy proces: • 1. přechází ze stavu běžící do stavu čekající • 2. přechází ze stavu běžící do stavu připravený • 3. přechází ze stavu čekající do stavu připravený • 4. končí  Případy 1 a 4 se označují jako nepreemptivní plánování (plánování bez předbíhání)  Případy 2 a 3 se označují jako preemptivní plánování (plánování s předbíháním) PB 153 Operační systémy a jejich rozhraní7 Dispečer  Výstupní modul krátkodobého plánovače nebo plánovač sám, který předává procesor procesu vybranému krátkodobým plánovačem  Předání zahrnuje:  přepnutí kontextu  přepnutí režimu procesoru na uživatelský režim  skok na odpovídající místo v uživatelském programu pro opětovné pokračování v běhu procesu  Dispečerské zpoždění (Dispatch latency)  Doba, kterou potřebuje dispečer pro pozastavení běhu jednoho procesu a start běhu jiného procesu PB 153 Operační systémy a jejich rozhraní8 Kritéria plánování [a optimalizace]  Využití CPU [maximalizace]  cílem je udržení CPU v kontinuální užitečné činnosti  Propustnost [maximalizace]  počet procesů, které dokončí svůj běh za jednotku času  Doba obrátky [minimalizace]  doba potřebná pro provedení konkrétního procesu  Doba čekání [minimalizace]  doba, po kterou proces čekal ve frontě „připravených“ procesů  Doba odpovědi [minimalizace]  doba, která uplyne od okamžiku zadání požadavku do doby první reakce (první odpovědi, nikoli poskytnutí plného výstupu) PB 153 Operační systémy a jejich rozhraní9  Algoritmus „Kdo dřív přijde, ten dřív mele“ (First Come, First Served), FCFS  Máme 3 procesy P1 (vyžaduje 24 dávek CPU), P2 (vyžaduje 3 dávky CPU), P3 (vyžaduje 3 dávky CPU)  Procesy vznikly v pořadí: P1, P2, P3  Ganttovo schématické vyjádření plánu:  Doby čekání: P1 = 0, P2 = 24, P3 = 27  Průměrná doba čekání: (0+24+27)/3 = 17 Algoritmus FCFS P1 P2 P3 24 27 300 PB 153 Operační systémy a jejich rozhraní10  Varianta jiná: procesy vznikly v pořadí P2, P3, P1  Ganttovo schématické vyjádření plánu:  Doby čekání: P2 = 0, P3 = 3, P1 = 6  Průměrná doba čekání: (6+0+3)/3 = 3  To je mnohem lepší výsledek než v předchozím případě, i když se jedná o stejné procesy a stejný plánovací algoritmus  Krátké procesy následující po dlouhém procesu ovlivňuje „konvojový efekt“ Algoritmus FCFS (2) P1P3P2 63 300 PB 153 Operační systémy a jejich rozhraní11 Algoritmus SJF  Algoritmus Shortest-Job-First  Musíme znát délku příštího požadavku na dávku CPU pro každý proces  Vybírá se proces s nejkratším požadavkem na CPU  Dvě varianty:  nepreemptivní, bez předbíhání • jakmile se CPU předá vybranému procesu, tento nemůže být předběhnut žádným jiným procesem, dokud přidělenou dávku CPU nedokončí  preemptivní, s předbíháním • jakmile se ve frontě připravených procesů objeví proces s délkou dávky CPU kratší než je doba zbývající k dokončení dávky právě běžícího procesu, je právě běžící proces ve využívání CPU předběhnut novým procesem • tato varianta se rovněž nazývá Shortest-Remaining-Time-First (SRTF)  SJF je optimální algoritmus (pro danou množinu procesů dává minimální průměrnou dobu čekání) PB 153 Operační systémy a jejich rozhraní12 Příklad nepreemptivního algoritmu SJF  Proces Doba příchodu Délka dávky CPU  P1 0.0 7  P2 2.0 4  P3 4.0 1  P4 5.0 4  Ganttovo schématické vyjádření plánu:  Průměrná doba čekání: (0+6+3+7)/4 = 4 P1 P3 P2 73 160 P4 8 12 PB 153 Operační systémy a jejich rozhraní13 Příklad preemptivního algoritmu SJF  Proces Doba příchodu Délka dávky CPU  P1 0.0 7  P2 2.0 4  P3 4.0 1  P4 5.0 4  Ganttovo schématické vyjádření plánu:  Průměrná délka čekání: (9+1+0+2)/4 = 3 P1 P3P2 42 110 P4 5 7 P2 P1 16 PB 153 Operační systémy a jejich rozhraní14 Určení délky příští dávky CPU procesu  Délku příští dávky CPU procesu neznáme, můžeme ji pouze odhadovat  To můžeme udělat na základě historie  Musíme znát délky předchozích dávek CPU  Použijeme exponenciální průměrování: :jakoodhaddefinujemepak4. historiekoeficient1,0,3. davkuCPUdalsiprohodnotaanapredpoklad2. davkyte-ndelkaskutecna1. 1      n nt   .11 nnn t   PB 153 Operační systémy a jejich rozhraní15 Příklad  α = 0 (historii nebereme v úvahu)  τn+1 = τn  α = 1 (budoucí odhad = skutečná minulá hodnota)  τn+1 = tn  Když formuli rozvineme, dostaneme τn+1=α tn + (1- α)αtn-1+ … + (1- α)i αtn-i + … + (1- α)nt0  α a (1- α) jsou <= 1,  Každý další člen výrazu má na výslednou hodnotu menší vliv než jeho předchůdce PB 153 Operační systémy a jejich rozhraní16 Prioritní plánování  S každým procesem je spojeno prioritní číslo  prioritní číslo – preference procesu pro výběr příště běžícího procesu  CPU se přiděluje procesu s největší prioritou  nejvyšší prioritě obvykle odpovídá nejnižší prioritní číslo   Opět dvě varianty  nepreemptivní, bez předbíhání • jakmile proces získá přístup k CPU nemůže být předběhnut jiným procesem dokud dávku neukončí  preemptivní, s předbíháním • jakmile se ve frontě připravených procesů objeví proces s vyšší prioritou než je priorita běžícího procesu, je běžící proces předběhnut  SJF je prioritní plánování, prioritou je předpokládaná délka příští CPU dávky  stárnutí  procesy s nižší prioritou se nemusí nikdy provést  řešení: zrání – priorita se s postupem času zvyšuje PB 153 Operační systémy a jejich rozhraní17 Round Robin (RR)  Každý proces dostává CPU na malou jednotku času – časové kvantum  Desítky až stovky ms  Po uplynutí této doby je běžící proces předběhnut nejstarším procesem ve frontě připravených procesů a zařazuje se na konec této fronty  Je-li ve frontě připravených procesů n procesů a časové kvantum je q, pak každý proces získává 1/n doby CPU, najednou nejvýše q časových jednotek  Žádný proces nečeká na přidělení CPU déle než (n-1)q časových jednotek  Výkonnostní hodnocení  q velké → ekvivalent FIFO  q malé → velká režie; v praxi musí být q musí být dostatečně velké s ohledem na režii přepínání kontextu PB 153 Operační systémy a jejich rozhraní18 Příklad RR s časovým kvantem = 20  Proces Délka dávky CPU  P1 53  P2 17  P3 68  P4 24  Ganttovo schématické vyjádření plánu:  Typicky se dosahuje delší průměrné doby obrátky než při plánování SJF, avšak doba odpovědi je výrazně nižší P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 PB 153 Operační systémy a jejich rozhraní19 Časové kvantum a doba přepnutí kontextu  Příklad: doba přepnutí kontextu = 0,01  Ztráty související s režií OS při q = 12, 6 a 1 jsou 0,08; 0,16 a 1 % PB 153 Operační systémy a jejich rozhraní20 Doba obrátky  Doba obrátky se mění se změnou délky časového kvanta PB 153 Operační systémy a jejich rozhraní21 Fronta procesů  Fronta „připravených“ procesů nemusí být jediná  procesy můžeme dělit na interaktivní, dávkové, apod.  pro každou frontu můžeme použít jiný plánovací algoritmus PB 153 Operační systémy a jejich rozhraní22 Příklad: Linux  Plánovací algoritmus je součástí jádra OS  Skládá se ze 2 funkcí  schedule() – plánování procesů  do_timer() – aktualizuje informace o procesech (spotřebovaný čas v uživatelském režimu, v režimu jádra, priority apod.)  Časové kvantum je 1/100 sekundy  Plánovací algoritmus byl předmětem vývoje PB 153 Operační systémy a jejich rozhraní23 Příklad: Linux (2)  Plánovací algoritmus  4 kategorie procesů z hlediska plánování • SCHED_FIFO • SCHED_RR • SCHED_OTHER • SCHED_BATCH  první dva typy jsou procesy se zvláštními nároky na plánování (soft real time), mají přednost před ostatními procesy a může je vytvářet pouze root  procesy SCHED_FIFO jsou plánovány metodou FIFO • Běží dokud není předběhnut, blokován I/O nebo se vzdá procesoru  procesy SCHED_RR jsou plánovány metodou RR • Upravené SCHED_FIFO s časovým kvantem podle sched_rr_get_interval()  procesy SCHED_FIFO a SCHED_RR mají přirazenu prioritu (1-99), při plánování jsou vybírány procesy s vyšší prioritou, plánovací algoritmu je preemptivní PB 153 Operační systémy a jejich rozhraní24 Příklad: Linux (3)  Plánovací algoritmus – pokračování  do SCHED_OTHER patří všechny klasické timesharingové procesy  v rámci SCHED_OTHER jsou procesy plánovány na základě dynamických priorit • tzv. hodnota nice • priorita je 0 • zvyšována při stárnutí procesu • neadministrátorský proces může jen zhoršit prioritu • resp. od jádra 2.6.12 limit RLIMIT_RTPRIO • procesy se stejnou prioritou jsou plánovaný pomocí RR PB 153 Operační systémy a jejich rozhraní25 Příklad: Linux (4)  Plánovací algoritmus  Do jádra 2.4 algoritmus procházející globální (pro všechny procesory) frontu a hledající vhodný proces (složitost O(n) kde n počet čekajících procesů)  Od jádra 2.6 (resp 2.5) nový, tzv. O(1) algoritmus, fronty procesů per-CPU  Od 2.6.23 nahrazen algoritmem CFS (completely fair scheduler), který pro seznamy procesů používá červeno-černý strom. Výběr procesu pro běh na procesoru v konstantním čase, jeho znovuvložení O(log n). PB 153 Operační systémy a jejich rozhraní26 Příklad: Linux (5) System Calls Related to Scheduling System Call Description nice( ) Change the priority of a conventional process. getpriority( ) Get the maximum priority of a group of conventional processes. setpriority( ) Set the priority of a group of conventional processes. sched_getscheduler( ) Get the scheduling policy of a process. sched_setscheduler( ) Set the scheduling policy and priority of a process. sched_getparam( ) Get the scheduling priority of a process. sched_setparam( ) Set the priority of a process. sched_yield( ) Relinquish the processor voluntarily without blocking. sched_get_ priority_min( ) Get the minimum priority value for a policy. sched_get_ priority_max( ) Get the maximum priority value for a policy. sched_rr_get_interval( ) Get the time quantum value for the Round Robin policy. PB 153 Operační systémy a jejich rozhraní27 Příklad: Win32 (1)  Z pohledu Win32:  procesy při vytvoření přiděleny do jedné z následujících tříd • Idle • Below Normal • Normal • Above Normal • High • Realtime  Vlákna dále mají relativní prioritu v rámci třídy, do které patří • Idle • Lowest • Below_Normal • Normal • Above_Normal • Highest • Time_Critical PB 153 Operační systémy a jejich rozhraní28 Příklad: Win32/W2k (2)  Plánovací algoritmu ve Windows 2000  plánuje vlákna, ne procesy  vlákna mají priority 0 až 31 31 16 15 1 0 i 16 “real-time” levels 15 variable levels Used by zero page thread Used by idle thread(s) PB 153 Operační systémy a jejich rozhraní29 Příklad: Win32 (3)  Přehled priorit ve Win32 PB 153 Operační systémy a jejich rozhraní30 Příklad: Win32 (4)  Get/SetPriorityClass  Get/SetThreadPriority – relativní vůči základní prioritě procesu  Get/SetProcessAffinityMask  SetThreadAffinityMask – musí být podmožinou masky procesu  SetThreadIdealProcessor – preferovaný procesor  Get/SetProcessPriorityBoost  Suspend/ResumeThread PB 153 Operační systémy a jejich rozhraní31 Příklad: Win32 (5)  Plánovací algoritmus je řízen především prioritami  32 front (FIFO seznamů) vláken, která jsou „připravena“ • pro každou úroveň priority jedna fronta • fronty jsou společné pro všechny procesory  když je vlákno „připraveno“ • buď běží okamžitě • nebo je umístěno na konec fronty „připravených“ procesů ve své prioritě  na jednoprocesorovém stroji vždy běží vlákno s nejvyšší prioritou  V rámci jedné prioritní skupiny se plánuje algoritmem round-robin pomocí časových kvant