Počítačové sítě a operační systémy Jaromír Plhák, 3/5/2018 PB169 Počítačové sítě a operační systémy Jaromír Plhák xplhak@fi.muni.cz Plánování CPU Správa paměti PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Motivace k plánování •V multitaskingových systémech existuje více procesů připravených k běhu •Procesorů je ve výpočetním systému (prakticky vždy) méně než procesů •OS musí rozhodovat, který proces poběží jako příští, tj. kterému procesu přidělí (případně na omezenou dobu) procesor Racionální zohlednění očekávání uživatelů: zdržení korekce obrazovky po uzavření okna o 2s kvůli emailu je neakceptovatelné, naopak zdržení odeslaní emailu o 2s kvůli korekci obrazovky je akceptovatelné PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Stavy procesu Procesy mohou být také odložené (mimo operační paměť) Nový - než se inicializují všechny struktury Připraven znamená, že ho můžeme plánovat - když ho vybereme může hned běžet Čekající - čekám na událost (například nějaké zdroje ze sítě) PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Plánovače v OS (1) •Dlouhodobý plánovač (strategický plánovač, job scheduler) –Vybírá který požadavek na výpočet lze zařadit mezi procesy –Definuje stupeň multiprogramování –Je vyvoláván řídce, nemusí být rychlý –Nejlepšího výsledku dosáhneme při vhodné kombinaci procesů orientovaných na I/O a na využití CPU -Typickým dlouhodobým plánovačem jsou uživatelé  -Má smysl v dávkových systémech - 1000 úloh, které máte vyřešit v následujících třech měsících -Dlouhodobý plánovač rozhodne, jestli spustí 5 nebo 10 a pak bude spouštět další -Rozhodně nespouštět všechny zároveň (Problém s pamětí) PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Plánovače v OS (2) •Střednědobý plánovač (taktický plánovač) –Logicky náleží částečně i do správy hlavní paměti (FAP) –Taktika využívání omezené kapacity FAP při multitaskingu –Vybírá který proces je nutné zařadit mezi odložené procesy (odebírá mu prostor ve FAP) –Vybírá kterému odloženému procesu lze opět přidělit prostor ve FAP •Krátkodobý plánovač (operační plánovač, dispečer, dispatcher) –Reprezentace správy procesoru(-ů) –Vybírá proces, který poběží na uvolněném procesoru a přiděluje procesu procesor (CPU) –Vyvoláván velmi často, desítky až stovky milisekund, musí být rychlý Sleduje paměť - pokud je příliš zaplněná a odloží procesy (zvyšuje efektivitu - ostatní procesy mají více prostoru v paměti) Střednědobé si mohou dělat statistiky a dělat zajímavé výpočty PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Plánovače v OS (3) PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Kritéria kvality plánování (1) •Uživatelsky orientovaná kritéria –Doba obrátky, Turnaround time •Doba běhu + doba čekání na zdroje vč. CPU •Vhodná míra pro dávkové zpracování •Přirozená je snaha o minimalizaci doby obrátky v dimenzi doby čekání •Normalizovaná doba obrátky = doba obrátky I doba běhu –Doba reakce, Response time •Míra pro interaktivní systémy •Doba od zadání požadavku do doby očekávané reakce •Cíl – snaha o minimalizaci pro co největší komunitu uživatelů •V interaktivně orientovaných systémech mívají interaktivní úlohy přednost před dávkovými úlohami –Časové limity + Časová proporcionalita (45 s na uzavření spojení OK, ale nikoliv čekání na odpověď) Doba obrátky: Když mám něco, co má běžet den, jestli jsem čekal hodinu nebo týden (hlídá se poměr) Doba reakce: Když kliknu, za jak dlouho se spustí PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Kritéria kvality plánování (2) •Systémově orientovaná kritéria –Propustnost, Throughput •Počet procesů dokončených za jednotku času •Přirozená je snaha o maximalizaci propustnosti •Požadavek dosažení vysoké propustnosti nebývá kompatibilní s požadavkem minimalizace doby obrátky –Využití CPU •Maximalizace ve víceuživatelských systémech •Pro real-time systémy a jednouživatelské systémy nepodstatné kritérium –Spravedlivost, Fairness •Porovnatelné procesy musí získat porovnatelnou obsluhu •Pokud uživatel nebo systém neřekne jinak, mají všechny procesy stejnou šanci, vč. ochrany před stárnutím + Prosazování priorit + Vyrovnání zátěže Spravedlnost: Jeden uživatel si spustí 90 procent procesů a druhý 10. Co tedy chceme? Musíme si zadefinovat, a pak to můžeme implementovat Kritéria jsou nezávislá, nelze optimalizovat všechna současně: Například interaktivní uživatelské systémy: minimalizace doby reakce, doby obrátky a maximalizace počtu interaktivních procesů a spravedlivost PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Plánování CPU – 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) Krátkodobý plánovač Preemptivní - mám 100 milisekund, ale můžu o ně přijít (přijde prioritnější proces) PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Dispečer •Předání procesu procesoru 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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Algoritmus FCFS (1) •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 P1 P2 P3 24 27 30 0 Algoritmů je více než budeme ukazovat, tohle jsou takové základní a hodně využívané Budeme se věnovat algoritmům pro jednoprocesorové systémy Někdy také FIFO Jednoduchá implementace PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Algoritmus FCFS (2) •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“ P1 P3 P2 6 3 30 0 Konvojový efekt: Jeden dlouhý proces zhoršuje statistiky dalších procesů Hodí se, pokud nemáte interaktivní procesy (dávkové úlohy) PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Round Robin (RR) (1) •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 Potkáte ho jak v Linuxu tak i ve Windows PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Round Robin (RR) (2) •Žádný proces nečeká na přidělení CPU déle než (n-1)q časových jednotek •Výkonnostní hodnocení –q velké → ekvivalent FCFS –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 –Zlaté pravidlo volby q – 80 % dávek CPU by mělo být < q Když je kratší než q, tak se nemusí se prostřídat ostatní PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Č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 % PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Algoritmus SJF (1) •Algoritmus Shortest-Job-First (Shotest-Process-Next) •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 •SJF je optimální algoritmus (pro danou množinu procesů dává minimální průměrnou dobu čekání) Musím znát délku kolik bude zabírat procesoru, což často nevím ... Domýšlí ... Odhaduje na základě minulosti procesu (sleduje ten proces a dělá si statistiky) Příklad word - stiknu klávesu (jak dlouho to bude trvat - kolik bude potřeba dávek) - vím, kolik to trvalo minule. Exponenciální průměrování PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Algoritmus SJF (1) •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) SRTF - nezajímá mne, co už bylo provedeno PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Nepreemptivní algoritmus 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 7 3 16 0 P4 8 12 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Preemptivní algoritmum 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 P3 P2 4 2 11 0 P4 5 Textové pole: 7 7 Textové pole: P2 P2 Textové pole: P1 P1 16 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Prioritní plánování (1) •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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Prioritní plánování (2) •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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Příklad – Win32 (1) •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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Příklad – Win32 (2) •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 Priority boost (to co mám na popředí) ... Ale neplatí pro server Liinux Round robin ... Nice (renice) ... Nastavení priorit -20 - 20 (čím méně tím vyšší priorita) PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 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) –Včetně dat •Z programu se stává proces (aktivní entita schopná spuštění na CPU) provedením celé řady kroků –Naplnění tabulek, umístění do operační paměti –Vázání adres instrukcí a dat na adresy operační paměti Virtualizace paměti: - Každý proces má dojem, že má stále k dispozici celý svůj adresový prostor - Časoprostorová lokalita programu – pohybuje se v části, proces je sekvenční - HW + služby procesu pohlídají, že má proces to co potřebuji – mohu mít více procesů v paměti - Nevyužívá celý prostor najednou - Virtualizace snižuje výkon procesoru (100x zrychlení procesoru, ale aplikace jen třeba 3x) - Proces až do zavedení do vnitřní paměti se pohybuje v logickém adresovém prostoru (instrukce se nemodifikují) - Až při interpretaci instrukce se převádí adresa instrukce z logického adresového prostoru do FAP - LAP je dán strukturou adres instrukčního repertoáru - FAP je dán šířkou adresové sběrnice (kapacita nemusí být naplněna, ale nemůže být více) - LAP bývá kapacitně větší než FAP (šířka adres LAP je vetší) - Chceme je na sebe vázat PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 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 - Mikroprogram, který umožní, abychom dynamicky řešili vazbu mezi LAP a FAP - Relokační registr je bázový registr měnitelný v privilegovaném režimu - Nechci programovat tak, abych se musel zabývat správou operační paměti - Přeložený program netuší, kde bude zaveden v paměti PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Relokační registr Proces může mít prostor kdekoliv, každý prostor začíná od „nuly“ (logické) a instrukce používají relativní adresu (JUMP 400, LOAD 1200) Obsah bázového registru připočte k logické adresa Výhoda ochrana paměti (nemohu se dostat do záporných adres – ty neexistují) - Mezní registr PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Adresový prostor •Logický adresový prostor (LAP), fyzický adresový prostor (FAP) –LAP – (logická adresa, virtuální adresa) dána adresou ve strojovém jazyku, generuje CPU –FAP – (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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Souvislé oblasti •Operační paměť se dělí do dvou sekcí –Rezidentní OS, obvykle na počátku FAP s tabulkou ovladačů přerušení –Uživatelské procesy •Přidělování jedné souvislé části paměti –Pro ochranu procesů uživatelů mezi sebou a OS lze použít schéma s relokačním registrem –Relokační registr – hodnota nejmenší fyzické adresy paměti procesu –Mezní registr – rozpětí logických adres, logická adresa musí být menší nebo rovna meznímu registru PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 HW podpora PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Souvislé oblasti •Přidělování několika částí paměti –Díra – blok dostupné paměti •Bloky jsou roztroušeny po FAP –Evidenci 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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 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? –First-fit •Přiděluje se první dostatečně dlouhá volná oblast resp. její počátek –Best-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 –Worst-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 PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Problém fragmentace •Vnější fragmentace –Souhrn volné paměti je dostatečný, ale ne v dostatečné souvislé oblasti •Vnitřní fragmentace –Př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 –Přesouvají se obsahy paměti s cílem vytvořit (jeden) velký volný blok –Použitelné jen když je možná dynamická relokace (viz MMU) –Provádí se v době běhu –Problé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 Například plněné přes DMA PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 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) –Pevná 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) –Pevná 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 Na konci 70. let. Vždyť nemusíme mít ten prostor spojitý. Rozbijeme ho na malé části a jen musíme mít HW podporu pro to, abychom dokázali přepsat logickou adresu na fyzickou. Stránkování a segmentace: PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Segmentování 1 3 2 4 1 4 2 3 user space physical memory space PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Segmentování •Logická adresa je dvojice (segment s, offset d) •Tabulka segmentů, Segment table, ST –Base – počáteční adresa umístění segmentu ve FAP –Limit – délka segmentu •Segment-table base register (STBR) –Odkaz na umístění ST v paměti •Segment-table length register (STLR) –Počet segmentů, s je legální když s < STLR •Relokace – dynamická, pomocí ST PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Příklad segmentace PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Stránkování, LAP na FAP PB169 Počítačové sítě a operační systémy Snímek ‹#› z 42 Stránkování a segmentování (Intel 386)