PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 1 Plánování CPU Správa paměti PB 169 Počítačové sítě a operační systémy j0310902[1] PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 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 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 3 Stavy procesu ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 4 Plánování CPU ¢Krátkodobý plánovač – dispečer lVybírá proces, kterému bude přidělen CPU lVybírá jeden z procesů, které jsou zavedeny operační paměti a které jsou „připravené“ lPlá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čí lPřípady 1 a 4 se označují jako nepreemptivní plánování (plánování bez předbíhání) lPřípady 2 a 3 se označují jako preemptivní plánování (plánování s předbíháním) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 5 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: lpřepnutí kontextu lpřepnutí režimu procesoru na uživatelský režim lskok 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) lDoba, kterou potřebuje dispečer pro pozastavení běhu jednoho procesu a start běhu jiného procesu PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 6 ¢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 30 0 PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 7 ¢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) P1 P3 P2 6 3 30 0 PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 8 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: lnepreemptivní, 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čí lpreemptivní, 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 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 9 Příklad nepreemptivního algoritmu SJF ¢Proces Doba příchodu Délka dávky CPU lP1 0.0 7 lP2 2.0 4 lP3 4.0 1 lP4 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 7 3 16 0 P4 8 12 PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 10 Příklad preemptivního algoritmu SJF ¢Proces Doba příchodu Délka dávky CPU lP1 0.0 7 lP2 2.0 4 lP3 4.0 1 lP4 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 P3 P2 4 2 11 0 P4 5 7 P2 P1 16 PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 11 Prioritní plánování ¢S každým procesem je spojeno prioritní číslo lprioritní číslo – preference procesu pro výběr příště běžícího procesu lCPU se přiděluje procesu s největší prioritou lnejvyšší prioritě obvykle odpovídá nejnižší prioritní číslo J ¢Opět dvě varianty lnepreemptivní, 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čí lpreemptivní, 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í lprocesy s nižší prioritou se nemusí nikdy provést lřešení: zrání – priorita se s postupem času zvyšuje PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 12 Round Robin (RR) ¢Každý proces dostává CPU na malou jednotku času – časové kvantum lDesí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í lq velké → ekvivalent FIFO lq 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 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 13 Příklad RR s časovým kvantem = 20 ¢Proces Délka dávky CPU lP1 53 lP2 17 lP3 68 lP4 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 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 14 Č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 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 15 Příklad: Win32 (1) ¢Z pohledu Win32: lprocesy při vytvoření přiděleny do jedné z následujících tříd •Idle •Below Normal •Normal •Above Normal •High •Realtime lVlá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 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 16 Příklad: Win32 (2) ¢Plánovací algoritmus je řízen především prioritami l32 front (FIFO seznamů) vláken, která jsou „připravena“ •pro každou úroveň priority jedna fronta •fronty jsou společné pro všechny procesory lkdyž je vlákno „připraveno“ •buď běží okamžitě •nebo je umístěno na konec fronty „připravených“ procesů ve své prioritě lna 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 ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 17 Paměť: principy, základy ¢Pro běh procesu je nutné, aby program, který je vykonáván byl umístěn v operační paměti (hlavní paměti) ¢Z programu se stává proces (aktivní entita schopná spuštění na CPU) provedením celé řady kroků lnaplnění tabulek, umístění do operační paměti lvázání adres instrukcí a dat na adresy operační paměti l PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 18 Memory-Management Unit ¢Hardwarový modul převádějící logické adresy na fyzické adresy ¢Uživatelský program pracuje s logickými adresami, uživatelský program nevidí fyzické adresy ¢Připočítává se obsah „relokačního registru“ k adresám generovaným uživatelským procesem v okamžiku, kdy je předávána jako ukazatel do operační paměti PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 19 Relokační registr PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 20 Adresový prostor ¢Logický adresový prostor (LAP), fyzický adresový prostor (FAP) lLAP – (logická adresa, virtuální adresa) dána adresou ve strojovém jazyku, generuje CPU lFAP – (fyzická) adresa akceptovaná operační pamětí ¢Logické a fyzické adresové prostory se shodují v době kompilace a v době zavádění ¢Logické a fyzické adresové prostory mohou být rozdílné při vázání v době běhu PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 21 Souvislé oblasti ¢Operační paměť se dělí do dvou sekcí lrezidentní OS, obvykle na počátku FAP s tabulkou ovladačů přerušení luživatelské procesy ¢Přidělování jedné souvislé části paměti lpro ochranu procesů uživatelů mezi sebou a OS lze použít schéma s relokačním registrem lrelokační registr: hodnota nejmenší fyzické adresy paměti procesu lmezní registr: rozpětí logických adres, logická adresa musí být menší nebo rovna meznímu registru PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 22 HW podpora PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 23 Souvislé oblasti ¢Přidělování několika částí paměti ldíra – blok dostupné paměti •Bloky jsou roztroušeny po FAP levidenci o přidělených a volných sekcí udržuje OS OS process 5 process 8 process 2 OS process 5 process 2 OS process 5 process 2 OS process 5 process 9 process 2 process 9 process 10 PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 24 Přidělování paměti ¢Kterou oblast délky n přidělit, když volná paměť je rozmístěna ve více souvislých nesousedních sekcích? lFirst-fit: •přiděluje se první dostatečně dlouhá volná oblast resp. její počátek lBest-fit: •přiděluje se nejmenší dostatečně dlouhá volná oblast resp. její počátek •generují se velmi malé (nejmenší) možné volné díry lWorst-fit: •přiděluje se největší dostatečně dlouhá volná oblast resp. její počátek •generují se největší možné volné díry ¢Z hlediska rychlosti a kvality využití paměti jsou First-fit a Best-fit lepší techniky než technika Worst-fit PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 25 Problém fragmentace ¢Vnější fragmentace lsouhrn volné paměti je dostatečný, ale ne v dostatečné souvislé oblasti ¢vnitřní fragmentace lpřidělená oblast paměti je větší než požadovaná velikost, tj. část přidělené paměti je nevyužitá ¢Snižování vnější fragmentace setřásáním lpřesouvají se obsahy paměti s cílem vytvořit (jeden) velký volný blok lpoužitelné jen když je možná dynamická relokace (viz MMU) lprovádí se v době běhu lproblém I/O •s vyrovnávacími paměťmi plněnými z periférií autonomně nelze hýbat – umisťují se proto do prostoru OS PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 26 Stránkování ¢LAP procesu nemusí být jedinou souvislou sekcí FAP, LAP se zobrazuje do (po částech volných) sekcí FAP ¢FAP se dělí na sekce zvané rámce (frames) lpevná délka, délka v násobcích mocnin 2 (obvykle mezi 512 až 8192 bajty) ¢LAP se dělí na sekce zvané stránky (pages) lpevná délka, shodná s délkou rámců ¢Udržujeme seznam volných rámců ¢Program délky n stránek se umístí (zavede) do n rámců ¢Překlad logická adresa → fyzická adresa − pomocí překladové tabulky nastavované OS a interpretované MMU ¢Vniká vnitřní fragmentace, neboť paměť je procesu přidělována v násobcích velikosti rámce PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 27 Segmentování 1 3 2 4 1 4 2 3 user space physical memory space PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 28 Segmentování ¢Logická adresa je dvojice (segment s, offset d) ¢Tabulka segmentů, Segment table, ST lbase – počáteční adresa umístění segmentu ve FAP llimit – délka segmentu ¢Segment-table base register (STBR) lodkaz na umístění ST v paměti ¢Segment-table length register (STLR) lpočet segmentů, s je legální když s < STLR ¢Relokace – dynamická, pomocí ST PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 29 Příklad segmentace PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 30 Stránkování a segmentování (Intel 386)