1/37 PB153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Plánování CPU 07 2/37 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 MULTIPROGRAMOVÁNÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 3/37 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é“. STŘÍDÁNÍ VYUŽITÍ CPU A I/O PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ wait for I/O wait for I/O wait for I/O load store add store read from file store increment index write to file load store add store read from file CPU burst I/O burst CPU burst CPU burst I/O burst I/O burst 4/37 HISTOGRAM DOBY VYUŽITÍ CPU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 160 140 120 100 80 60 40 20 0 8 16 24 32 40 burst duration (miliseconds) frequency 5/37 STAVY PROCESU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ new terminated ready running waiting admitted interrupt exit I/O or event completion I/O or event wait scheduler dispatch 6/37 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) PLÁNOVÁNÍ CPU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 7/37 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 DISPEČER PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 8/37 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) KRITÉRIA PLÁNOVÁNÍ [A OPTIMALIZACE] PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 9/37 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 PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 24 27 300 10/37 ANIMACE ALGORITMU FCFS PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 11/37 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) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1P3P2 63 300 12/37 ANIMACE ALGORITMU FCFS (2) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 13/37 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í) ALGORITMUS SJF PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 14/37 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 PŘÍKLAD NEPREEMPTIVNÍHO ALGORITMU SJF PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P3 P2 73 160 P4 8 12 15/37 ANIMACE: PŘÍKLAD NEPREEMPTIVNÍHO ALGORITMU SJF PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 16/37 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 PŘÍKLAD PREEMPTIVNÍHO ALGORITMU SJF PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P3P2 42 110 P4 5 7 P2 P1 16 17/37 ANIMACE: PŘÍKLAD PREEMPTIVNÍHO ALGORITMU SJF PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 18/37 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í: URČENÍ DÉLKY PŘÍŠTÍ DÁVKY CPU PROCESU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ :jakoodhaddefinujemepak4. historiekoeficient1,0,3. davkuCPUdalsiprohodnotaanapredpoklad2. davkyte-ndelkaskutecna1. 1 ≤≤ = = + αα τn nt ( ) .11 nnn t ταατ −+=+ 19/37 α = 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 PŘÍKLAD PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 20/37 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 PRIORITNÍ PLÁNOVÁNÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 21/37 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 dostatečně velké s ohledem na režii přepínání kontextu ROUND ROBIN (RR) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 22/37 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žší PŘÍKLAD RR S ČASOVÝM KVANTEM = 20 PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 23/37 ANIMACE ROUND ROBIN PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 24/37 ČASOVÉ KVANTUM A DOBA PŘEPNUTÍ KONTEXTU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 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 % 0 0 0 10 106 6 7 8 9 1054321 process time = 10 quantum context switches 12 0 6 1 1 9 25/37 Doba obrátky se mění se změnou délky časového kvanta DOBA OBRÁTKY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ time quantum averageturnaroundtime 1 2 3 4 5 6 7 9.0 9.5 10.0 10.5 11.0 11.5 12.0 12.5 process time P1 P2 P3 P4 6 3 1 7 26/37 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 FRONTA PROCESŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ system processes interactive processes interactive editing processes batch processes student processes highest priority lowest priority 27/37 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 PŘÍKLAD: LINUX PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 28/37 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í PŘÍKLAD: LINUX (2) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 29/37 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 PŘÍKLAD: LINUX (3) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 30/37 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). PŘÍKLAD: LINUX (4) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 31/37 PŘÍKLAD: LINUX (5) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 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. 32/37 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 PŘÍKLAD: WIN32 (1) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 33/37 Přehled priorit ve Win32 PŘÍKLAD: WIN32 (3) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ real-time high above normal normal below normal idle priority time-critical 31 15 15 15 15 15 highest 26 15 12 10 8 6 above normal 25 14 11 9 7 5 normal 24 13 10 8 6 4 below normal 23 12 9 7 5 3 lowest 22 11 8 6 4 2 idle 16 1 1 1 1 1 34/37 Plánovací algoritmu ve Windows 2000 ● plánuje vlákna, ne procesy ● vlákna mají priority 0 až 31 PŘÍKLAD: WIN32/W2K (2) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 31 16 15 1 0 i 16 „real-time“ levels 15 variable levels Used by zero page thread Used by idle thread(s) 35/37 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 PŘÍKLAD: WIN32 (4) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 36/37 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 PŘÍKLAD: WIN32 (5) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 37/37 Výukovou pomůcku zpracovalo Servisní středisko pro e-learning na MU http://is.muni.cz/stech/ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ