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" Algiritmus 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