Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- mgr-szz:in-pos:1-pos [2019/06/05 14:59]
lachmanfrantisek plánování procesů, plánovače
+++ mgr-szz:in-pos:1-pos [2020/04/12 16:56] (aktuální)
@@ Řádek 53: / Řádek 53: @@
   * příklad: MACH
   * ➕ snadná přenositelnost OS, jádro je malé
-  * ➕ vyšší spolehlivost (moduly mají jasné API a jsou snadněji
+  * ➕ vyšší spolehlivost (moduly mají jasné API a jsou snadněji testovatelné)
-testovatelné)
   * ➕ vyšší bezpečnost (méně kódu OS běží v režimu jádra)
   * ➕ flexibilita (jednodušší modifikace, přidání, odebrání modulů)
@@ Řádek 95: / Řádek 94: @@
   * OS spravuje zdroje přidělováním procesům podle zvolené politiky (priorita, vzájemná výlučnost, zabraňuje uváznutí).
   * OS podporuje tvorbu procesu a jejich komunikaci.
-  * OS s multiprogramováním <color red> multiprogramování = multitasking</color>
+  * OS s multiprogramováním (<color red>multiprogramování = multitasking</color>)
@@ Řádek 245: / Řádek 244: @@
   * Toto je úkol dlouhodobého (strategického) plánovače
     * Vybírá který proces lze zařadit mezi připravené procesy.
+    * Řeší přechod ze stavu ''nový'' do stavu ''připravený''.
   * Plánovač je spouštěn je relativně málo často.
     * Typicky při ukončení jednoho procesu rozhodne, kterou úlohu dále vybrat k zavedení do paměti a spuštění.
     * Nemusí být super rychlý.
   * Určuje stupeň multiprogramování.
+  * Nemusí být ve všech systémech přítomen.
 === Krátkodobý plánovač ===
@@ Řádek 266: / Řádek 267: @@
 {{:mgr-szz:in-pos:planovac-strednedoby.png?500|}}
-===== Synchronizace procesů =====
+==== Algoritmy ====
+<box 95% round blue|FCFS>
+Algoritmus „Kdo dřív přijde, ten dřív mele“ (First Come, First Served).
+Př.:
+  * P1 (vyžaduje 24 dávek CPU)
+  * P2 (vyžaduje 3 dávky CPU)
+  * P3 (vyžaduje 3 dávky CPU)
+  * P1, P2, P3
+    * Doby čekání: P1 = 0, P2 = 24, P3 = 27
+    * Průměrná doba čekání: (0+24+27)/3 = 17
+{{:mgr-szz:in-pos:fcfs.png?300|}}
+  * P2, P3, P1
+    * Doby čekání: P2 = 0, P3 = 3, P1 = 6
+    * Průměrná doba čekání: (6+0+3)/3 = 3
+{{:mgr-szz:in-pos:fcfs2.png?300|}}
+</box>
+<box 95% round blue|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í)
+Př.:
+^ 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 |
+  * Nepreemtivní
+    * Průměrná doba čekání: (0+6+3+7)/4 = 4
+{{:mgr-szz:in-pos:sjf-nepre.png?300|}}
+  * Preemptivní
+    * Průměrná délka čekání: (9+1+0+2)/4 = 3
+{{:mgr-szz:in-pos:sjf-pre.png?300|}}
+</box>
+<box 95% round blue|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.
+</box>
+<box 95% round blue|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
+  * 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ř.:
+^ Proces ^ Délka dávky CPU ^
+| P1 | 53 |
+| P2 | 17 |
+| P3 | 68 |
+| P4 | 24 |
+  * časové kvantum: 20
+{{:mgr-szz:in-pos:round-robin.png?300|}}
+</box>
+===== Komunikace a synchronizace procesů =====
+Synchronizace běhu procesů = "Jeden proces čeká na událost z druhého procesu."
+<note tip>
 Se souběžně běžícími procesy se můžeme setkat buď v přímo paralelním prostředí, kde je jedna paměť sdílena více procesy, nebo v prostředí distribuovaném, kde má každý proces vlastní lokální paměť. Hlavním problémem výskytu souběžných procesů je sdílení prostředků (paměť, zařízení, soubory, atd.) Tento problém se vyskytuje dokonce i v mnohouživatelských OS, kdy se např. řeší sdílení paměti mezi hlavní linií výpočtu v jádře a obslužnou rutinou přerušení při I/O operaci. Především při sdíleném přístupu do paměti nebo do souboru mohou vznikat neočekávané problémy – časové závislé chyby.
+</note>
+Umožňuje:
+  * **Komunikaci mezi procesy**
+    * zasílání zpráv
+    * synchronizace
+    * sdílená paměť
+    * vzdálené volání procedur (RPC)
+  * **Sdílení prostředků**
+    * procesy používají a modifikují sdílená data
+    * operace zápisu musí být vzájemně výlučné
+    * operace zápisu musí být vzájemně výlučné s operacemi čtení
+      * operace čtení mohou být realizovány souběžně
+    * pro zabezpečení integrity dat se používají kritické sekce
+Komunikace – způsob synchronizace, koordinace různých aktivit
+  * může dojít k uváznutí (každý proces čeká na zprávu od nějakého jiného procesu)
+  * může dojít ke stárnutí (dva procesy si opakovaně posílají zprávy zatímco třetí proces čeká na zprávu nekonečně dlouho)
+==== Race condition ====
+  * podmínka soupeření, souběh
+  * více procesů současně přistupuje ke sdíleným zdrojům a manipulují s nimi
+  * konečnou hodnotu zdroje určuje poslední z procesů, který zdroj po manipulaci opustí
 ==== Vzájemné vyloučení ====
-Vzájemné vyloučení je prostředek, jak zamezit dvěma procesům, aby zároveň přistupovaly k určitým datům nebo prováděly současně určité operace. Jedná se obvykle o funkce, po nichž požadujeme, aby je jeden proces provedl celé sám bez přerušování jinými procesy. Obecně se těmto funkcím říká **kritické sekce**. Kritické sekci obvykle předchází tzv. preludium (vstup do KS) – místo soupeření procesů o vstup – a je ukončena tzv. postludiem (výstup z KS) – kritická sekce je opět uvolněna pro jiný proces.
+Vzájemné vyloučení je prostředek, jak zamezit dvěma procesům, aby zároveň přistupovaly k určitým datům nebo prováděly současně určité operace. Jedná se obvykle o funkce, po nichž požadujeme, aby je jeden proces provedl celé sám bez přerušování jinými procesy. Obecně se těmto funkcím říká **kritické sekce**.
 === Kritická sekce ===
-Problémem kritické sekce je umožnit přístup ke kritické oblasti procesům, které o to usilují, při dodržení následujících podmínek:
-  *výhradní přístup - v každém okamžiku smí být v kritické sekci nejvýše jeden proces
+  * N procesů soupeří o právo používat jistá sdílená data.
-  *vývoj - rozhodování o tom, který proces vstoupí do kritické sekce, ovlivňují pouze procesy, které o vstup do kritické sekce usilují; toto rozhodnutí pro žádný proces nemůže být odkládáno do nekonečna; nedodržení této podmínky může vést například k tomu, že je umožněna pouze striktní alternace (dva procesy se při průchodu kritickou sekcí musí pravidelně střídat)
+  * V každém procesu se nachází segment kódu programu nazývaný **kritická sekce**, ve kterém proces přistupuje ke sdíleným zdrojům.
-  *omezené čekání; pokud jeden proces usiluje o vstup do kritické sekce, nemohou ostatní procesy tomuto vstupu zabránit tím, že se v kritické sekci neustále střídají - mohou do této kritické sekce vstoupit pouze omezený počet krát (zpravidla pouze jednou)
+  * **Problém: je potřeba zajistit, že v kritické sekci, sdružené s jistým zdrojem, se bude nacházet nejvýše jeden proces.**
-Pokud o přístup do kritické sekce usiluje některý proces v době, kdy je v ní jiný proces, případně o přístup usiluje v jednom okamžiku více procesů, je nutné některé z nich pozdržet. Toto pozdržení je možné realizovat smyčkou. Toto tzv. aktivní čekání (busy waiting) však zbytečně spotřebovává čas CPU - je možné čekající proces zablokovat a obnovit jeho běh až v okamžiku, kdy proces, který je v kritické sekci, tuto sekci opustí.
+    * **výhradní přístup** - v každém okamžiku smí být v kritické sekci nejvýše jeden proces
+    * **vývoj**:- rozhodování o tom, který proces vstoupí do kritické sekce, ovlivňují pouze procesy, které o vstup do kritické sekce usilují; toto rozhodnutí pro žádný proces nemůže být odkládáno do nekonečna; nedodržení této podmínky může vést například k tomu, že je umožněna pouze striktní alternace (dva procesy se při průchodu kritickou sekcí musí pravidelně střídat)
+    * **omezené čekání**: pokud jeden proces usiluje o vstup do kritické sekce, nemohou ostatní procesy tomuto vstupu zabránit tím, že se v kritické sekci neustále střídají - mohou do této kritické sekce vstoupit pouze omezený počet krát (zpravidla pouze jednou)
+  * Pokud o přístup do kritické sekce usiluje některý proces v době, kdy je v ní jiný proces, případně o přístup usiluje v jednom okamžiku více procesů, je nutné některé z nich pozdržet. Toto pozdržení je možné realizovat smyčkou. Toto tzv. aktivní čekání (**busy waiting**) však zbytečně spotřebovává čas CPU - je možné čekající proces zablokovat a obnovit jeho běh až v okamžiku, kdy proces, který je v kritické sekci, tuto sekci opustí.
 === Nástroje a algoritmy pro vzájemné vyloučení ===
-  *aktivní čekání – softwarově – pouze vzájemná výlučnost R/W s pamětí, bez podpory programovacího jazyka / OS
-  *aktivní čekání – speciální instrukce TST, EXCHANGE – bez podpory programovacího jazyka / OS
-  *pasivní čekání – podpora v programovacím jazyku / OS: semafory, monitory, zasílání zpráv
-=== Sdílené vzájemné vyloučení ===
+  * **aktivní čekání -- softwarově**: pouze vzájemná výlučnost R/W s pamětí; bez podpory programovacího jazyka / OS
-Jedná se o exkluzivní vzájemné vyloučení operací zápisu s jakoukoli jinou operací a sdílené čtení. U tohoto typu vzájemného vyloučení se objevuje také další typ úloh – tzv. úloha o čtenářích a písařích.
+  * **aktivní čekání -- procesor**: speciální instrukce TST, EXCHANGE; bez podpory programovacího jazyka / OS
+  * **pasivní čekání**: podpora v programovacím jazyku / OS, př: semafory, monitory, zasílání zpráv
+== Semafor ==
+  * Synchronizační nástroj, který lze implementovat i bez „busy waiting“.
+    * Proces je (operačním systémem) „uspán“ a „probuzen“ (tj. řešení na úrovni OS).
+  * Chybné použití semaforu v jednom procesu hroutí souhru všech spolupracujících procesů.
+== Monitor ==
+Synchronizační nástroj vysoké úrovně.
+  * Umožňuje bezpečné sdílení abstraktního datového typu souběžnými procesy
+  * Provádění P1 , P2 , ... se implicitně vzájemně vylučují.
+=== Sdílené vzájemné vyloučení ===
+Jedná se o exkluzivní vzájemné vyloučení operací zápisu s jakoukoli jinou operací a sdílené čtení.
+<note tip>
+Úloha o čtenářích a písařích
-== Úloha o čtenářích a písařích ==
   *libovolný počet čtenářů může číst ze sdílené oblasti, v jednom okamžiku smí do sdílené oblasti zapisovat pouze jeden písař, jestliže písař píše do sdílené oblasti, nesmí současně z ní číst žádný čtenář.
   *Příklad výskytu této úlohy v praxi může vypadat takto: sdílenou oblast reprezentuje knihovna programů, čtenáři nazveme sestavující programy a písařem může být knihovník.
@@ Řádek 295: / Řádek 459: @@
     *priorita písařů (pomocí semaforů) -- první čtenář zablokuje všechny písaře, poslední čtenář je uvolní, první písař zakáže přístup novým čtenářům
     *priorita písařů (zasíláním zpráv) -- první čtenář zablokuje všechny písaře, poslední čtenář je uvolní, první písař zakáže přístup novým čtenářům, ke sdílené oblasti řídí přístup referenční monitor se třemi mailboxy, každý čtenář / písař má svůj mailbox
+</note>
 ===== Uváznutí =====
 Množina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředků, zaslání zprávy), kterou vyvolá pouze některý z procesů P.
+**Stárnutí** = požadavky 1 nebo více procesů z P nebudou splněny v konečném čase
+  * z důvodů vyšších priorit jiného procesu
+  * z důvodů prevence uváznutí apod.
 === Nutná a postačující podmínka uváznutí ===
   * Nutné podmínky uváznutí:
-    - **vzájemné vyloučení** (//Mutual exclusion//)
+    - **vzájemné vyloučení** (**//Mutual exclusion//**)
       * se sdíleným zdrojem může v jednom okamžiku pracovat právě jeden proces
-    - **inkrementálnost požadavků** (též postupné uplatňování požadavků, //Hold-and-Wait//)
+    - **inkrementálnost požadavků** (též postupné uplatňování požadavků, **//Hold-and-Wait//**)
       * proces vlastnící nějaký zdroj potřebuje ke své činnosti zdroj další, který je však držen jiným procesem
-    - **nepředbíhatelnost** (//No preemption//)
+    - **nepředbíhatelnost** (**//No preemption//**)
       * zdroje lze uvolnit pouze procesem, který tyto vlastní a to pouze dobrovolně, až je nebude potřebovat
   * Postačující podmínka:
     * **cyklické čekání** (též zacyklení pořadí, //Circular Wait//)
@@ Řádek 313: / Řádek 487: @@
       * existuje množina //n// procesů (//P<sub>0</sub>...P<sub>n</sub>//), kde proces //P<sub>0</sub>// čeká na uvolnění zdroje drženého procesem //P<sub>1</sub>//, //P<sub>1</sub>// čeká na uvolnění zdroje drženého //P<sub>2</sub>// atd. až //P<sub>n</sub>// čeká na uvolnění zdroje drženého //P<sub>0</sub>//
-=== Bezpečný stav ===
-Stav je bezpečný, jestliže **systém může alokovat zdroje každému procesu** (v mezích maximálního počtu) v nějakém pořadí a zároveň nenastane deadlock (uváznutí). Formálně, systém je v bezpečném stavu, jestliže existuje bezpečná sekvence. Sekvence procesů <P1, P2, ..., Pn> je bezpečná pro aktuální stav alokace, jestliže každému procesu Pi mohou být přiděleny požadované zdroje ze zdrojů volných + zdrojů držených procesy Pj, kde j < i. Za této situace, pokud zdroje požadované procesem Pi nejsou momentálně volné, potom Pi čeká, dokud nejsou ukončeny všechny procesy Pj. V momentě, kdy dokončeny jsou, Pi může dostat všechny požadované zdroje, splnit svou úlohu, zdroje uvolnit a skončit. Je-li proces Pi ukončen, může dostat všechny požadované zdroje proces Pi+1 atd. Pokud v systému neexistuje bezpečná sekvence, říkáme o něm, že není bezpečný.
 ===Metody ochrany proti uváznutí===
-  *ignorovat je - přestože tato strategie vypadá nepřijatelně, používá ji například OS Unix; v případě uváznutí musí zasáhnout některý z uživatelů a jeden nebo více procesů násilím ukončit; v krajním případě může být nutné znovu nastartovat celý systém
-  *prevence uváznutí – ruší se platnost některé nutné podmínky
-  *detekce uváznutí – detekuje se existence uváznutí a řeší se následky
-  *vyhýbání se uváznutí – zamezuje se současné platnosti nutných podmínek
-  *nepřímé metody (zneplatnění nutné podmínky)
-    *virtualizace prostředků – rušení vzájemné výlučnosti (mimo spooling nepoužitelné)
-    *požadování všech prostředků najednou – ruší se požadavek inkrementálnosti požadavků
-      *klady: nemusí se nic odebírat, vhodné pro procesy s jednou nárazovou činností
-      *zápory: neefektivní, možná prodleva při zahájení procesu
-    *odebírání prostředků – ruší se vlastnost nepředbíhatelnosti procesů z hlediska používání prostředků
-      *1. možnost: proces, jemuž byl odmítnut požadavek, uvolní vše co vlastní a o vše požádá znovu
-      *2. možnost: jestliže proces požaduje prostředek držený jiným procesem, držitel je požádán, aby uvolnil vše co vlastní a o vše požádal znovu (procesy nesmí být stejné priority)
-      *klady: vhodné pro prostředky s uchovatelným a obnovitelným stavem (FAP, procesor)
-      *zápory: režijní ztráty, možnost cyklického restartu
-  *přímé metody (nepřipuštění planosti postačující podmínky)
-    *uspořádání prostředků – ruší se možnost vzniku zacyklení při čekání: procesy smí požadovat prostředky pouze ve stanoveném pořadí
-      *klady: lze kontrolovat při kompilaci, nic se neřeší za běhu
-      *zápory: neefektivní
-===Detekce uváznutí===
+== Ochrana před uváznutím prevencí ==
-„každý dostává co chce kdy chce“, OS periodicky testuje existenci uváznutí (detekce cyklu v grafu), klady: žádný prostoj při zahájení, zápory: nutnost řešit uváznutí a posteriori
+  * zajistíme, že se systém nikdy nedostane do stavu uváznutí
+  * zrušíme platnost některé nutné podmínky
+  * **nepřímé metody** (zneplatnění nutné podmínky)
+    * **Virtualizací prostředků** zrušíme **//Mutual exclusion//**.
+    * **Požadováním všech prostředků najednou** zrušíme **//Hold-and-Wait//**.
+      * ➕ nemusí se nic odebírat, vhodné pro procesy s jednou nárazovou činností
+      * ➖ neefektivní, možná prodleva při zahájení procesu
+    * **Odebíráním prostředků** zrušíme **//No preemption//**
+      * Proces, jemuž byl odmítnut požadavek, uvolní vše co vlastní a o vše požádá znovu.
+      * ➕ vhodné pro prostředky s uchovatelným a obnovitelným stavem (FAP, procesor)
+      * ➖ režijní ztráty, možnost cyklického restartu
+  * **přímé metody** (nepřipuštění planosti postačující podmínky)
+    * **uspořádáním prostředků** zrušíme možnost vzniku zacyklení při čekání: procesy smí požadovat prostředky pouze ve stanoveném pořadí
+      * ➕ lze kontrolovat při kompilaci, nic se neřeší za běhu
+      * ➖ neefektivní
+== Obcházení uváznutí ==
-===Způsoby řešení uváznutí===
+  * detekce potenciální možnosti vzniku uváznutí a nepřipuštění takového stavu
-  *zrušit všechny uváznuté procesy (nejčastěji používaná metoda)
+  * zamezujeme současné platnosti všech nutných podmínek
-  *návrat uváznutých procesů k poslednímu kontrolnímu bodu (možnost opakování situace)
+  * prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí)
-  *postupně rušit uváznuté procesy (podle spotřebovaného času procesoru, počtu tiskových řádků, času do dokončení procesu, priority, množství vlastněných prostředků)
-  *postupně předbíhat uváznuté procesy
-  *zamezit současné platnosti nutných podmínek
-  *bankéřův algoritmus
-===Algoritmus prevence uváznutí===
+<box 95% round blue|Bankéřův algoritmus >
-Základní myšlenkou je zajistit, aby systém byl neustale v **bezpečném stavu**. Na počátku systém v bezpečném stavu pochopitelně je. V okamžiku, kdy proces žádá zdroj, který je aktuálně volný, musí systém rozhodnout, zda procesu zdroj přidělí, nebo ho nechá čekat. **Zdroj může byt procesu přidělen pouze v případě, ze systém i po přiděleni zůstane v bezpečném stavu**.
-== Bankéřův algoritmus ==
+  * Algoritmus používaný u zdrojů, kterých se přiděluje určité množství.
-  *Algoritmus grafu alokace zdrojů je použitelný pouze v systému, kde každá třída zdroje obsahuje max. 1 instanci. Algoritmus, který si popíšeme nyní, tento problém eliminuje. Není ovšem tak efektivní jako algoritmus grafu alokace zdrojů.
+  * Když vstoupí novy proces do systému, musí deklarovat maximální počet instanci všech tříd, které bude pro svůj běh potřebovat. Tato maxima nesmi přesahovat celkový počet zdrojů v systému. Když uživatel požaduje množinu zdrojů, musí systém zjistit nepřevede-li alokace těchto zdrojů systém do nebezpečného stavu. Pokud by tomu tak bylo, musí proces čekat než jiný proces neuvolní dostatek zdrojů. V případe opačném jsou zdroje procesu alokovány.
-  *Když vstoupí novy proces do systému, musí deklarovat maximální počet instanci všech tříd, které bude pro svůj běh potřebovat. Tato maxima nesmi přesahovat celkový počet zdrojů v systému. Když uživatel požaduje množinu zdrojů, musí systém zjistit nepřevede-li alokace těchto zdrojů systém do nebezpečného stavu. Pokud by tomu tak bylo, musí proces čekat než jiný proces neuvolní dostatek zdrojů. V případe opačném jsou zdroje procesu alokovány.
+  * Pro zajištěni chodu bankéřova algoritmu je třeba udržovat množství datových struktur. Tyto struktury kódují stav systému alokace zdrojů. Nechť n je celkový počet procesu v systému a m je počet typu zdrojů. Potřebujeme následující datové struktury:
-  *Pro zajištěni chodu bankéřova algoritmu je třeba udržovat množství datových struktur. Tyto struktury kódují stav systému alokace zdrojů. Nechť n je celkový počet procesu v systému a m je počet typu zdrojů. Potřebujeme následující datové struktury:
     *Volny: vektor delky m indikujici pocet volnych instanci kazdeho typu zdroje. Jestlize Volny(j) = k, potom je v systemu k volnych instanci zdroje Rj.
     *Max: matice typu (n,m) definujici maximalni pozadavek kazdeho procesu na kazdou tridu zdroju. Jestlize Max(i,j) = k, potom proces Pi muze pozadat maximalne o k instanci zdroje Rj.
@@ Řádek 362: / Řádek 527: @@
   *Kazdou radku matic Alokace a Potreba muzeme zpracovavat jako vektor a oznacovat jako Alokacei a Potrebai. Vektor Alokacei specifikuje zdroje, ktere jsou aktualne alokovany procesu Pi a vektor Potrebai specifikuje dalsi zdroje, ktere proces Pi potrebuje pro sve dokonceni.
-<box 95% round blue|Příklad >
 Uvazujme system s peti procesy P0 az P4 a tri zdroje typu A, B, C.
   *Zdroj typu A ma 10 instanci
@@ Řádek 388: / Řádek 553: @@
   *V teto situaci je system v bezpecnem stavu. Sekvence < P1, P3, P4, P2, P0,> je bezpecna sekvence.
+</box>
+== Detekce a obnova po uváznutí ==
+  * Uváznutí povolíme, ale jeho vznik detekujeme a řešíme.
+  * OS periodicky testuje existenci uváznutí (detekce cyklu v grafu).
+  * ➕ žádný prostoj při zahájení
+  * ➖ nutnost řešit uváznutí
+Způsoby řešení uváznutí:
+  * zrušit všechny uváznuté procesy (nejčastěji používaná metoda)
+  * návrat uváznutých procesů k poslednímu kontrolnímu bodu (možnost opakování situace)
+  * postupně rušit uváznuté procesy (podle spotřebovaného času procesoru, počtu tiskových řádků, času do dokončení procesu, priority, množství vlastněných prostředků)
+  * postupně předbíhat uváznuté procesy
+  * zamezit současné platnosti nutných podmínek
+<box 90% blue|Resource-Allocation Graph, RAG>
+  * množina uzlů (procesy ⚫, zdroje ⬛)
+  * hrany
+    * požadavků (proces -> zdroj)
+    * přidělení (zdroj -> proces)
+  * zdroje mohou mít více instancí
+Jestliže se v RAG nevyskytuje cyklus:
+  * => k uváznutí nedošlo
+Jestliže se v RAG vyskytuje cyklus:
+  * existuje pouze jedna instance daného typu => k uváznutí došlo
+  * existuje více instancí daného typu => k uváznutí může dojít
 </box>
+<box 90% blue|Wait-for-Graph, WFG>
+  * vztahy pouze mezi procesy
+  * hrana = proces čeká na uvolnění zdroje druhým procesem
+  * Systém uvázl, pokud je v grafu cyklus.
+</box>
-===== Práce s pamětí, logický a fyzický adresový prostor, správa paměti a způsoby jejího provádění =====
+== Ignorování hrozby uváznutí ==
+  * uváznutí je věc aplikace ne systému
+  * způsob řešení zvolený většinou OS
+===== Správa paměti a virtualizace paměti =====
 ===Obecné poznatky správy paměti===
-  *
- Pro běh procesu je nutné, aby program, který ho řídí, byl umístěn v operační paměti.
+Pro běh procesu je nutné, aby program, který ho řídí, byl umístěn v operační paměti.
-  * Program se převádí do formy schopné interpretace procesorem ve více krocích, jednou musí někdo rozhodnout kde bude v operační paměti (FAP) umístěn.
+  * 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
+  * Více procesů může sdílet společnou část paměti, aniž by se tím porušovala ochrana paměti
+    * neboť sdílení jedné datové struktury je lepší řešení než udržování konzistence násobných kopií vlastněných jednotlivými proces
   * Roli dlouhodobé paměti programu plní vnější paměť.
   * Vnitřní operační paměť uschovává data a programy právě běžících, resp. plánovatelných procesů.
@@ Řádek 407: / Řádek 623: @@
 ===Požadavky na správu paměti===
 ==Možnost relokace programů==
   * programátor nemůže vědět, ze které části paměti bude jeho program interpretován
@@ Řádek 426: / Řádek 643: @@
 === LAP a FAP ===
-<box 95% round blue|Správa paměti, základní pojmy>
+<box 95% round blue|Fyzický a logický adresový prostor>
-**Vstupní fronta (input queue)**: Fronta procesů čekajících na zavedení do paměti.
 **Logický adresový prostor (LAP)**: virtuální adresový prostor, se kterým pracuje procesor při provádění kódu (každý proces i jádro mají svůj). Dán šířkou a formou adresy. Kapacita je dána šířkou adresy v instrukci.
@@ Řádek 433: / Řádek 649: @@
 **Fyzický adresový prostor (FAP)**: adresový prostor fyzických adres paměti (společný pro všechny procesy i jádro). Adresa akceptovaná operační pamětí. Kapacita je dána šířkou adresové sběrnice operační paměti
 </box>
+{{:mgr-szz:in-pos:vazani-adres.png?300|}}
 ==Vázání adres LAP na adresy FAP==
@@ Řádek 448: / Řádek 666: @@
     * nutná HW podpora
     * proces může měnit svoji polohu ve FAP během provádění
+{{:mgr-szz:in-pos:relokacni-registr.png?300|}}
 ===Přidělování souvislých oblastí===
@@ Řádek 453: / Řádek 674: @@
   * sekce pro rezidentní část OS, obvykle bývá umístěna od počátku
   * sekce pro uživatelské procesy
+{{:mgr-szz:in-pos:rezidentni-oblast-pameti.png?300|}}
 Pro ochranu procesů uživatelů mezi sebou a OS při přidělování sekce procesům lze použít schéma s relokačním a mezním registrem:
@@ Řádek 478: / Řádek 701: @@
 ==Překryvy (Overlays)==
 Historická, klasická technika. V operační paměti se uchovávají pouze ty instrukce a data, která je potřeba zde uchovat "v nejbližší budoucnosti". Vyvolávání překryvů je implementované uživatelem, není potřeba speciální podpory ze strany OS.
+{{:mgr-szz:in-pos:overlays.png?300|}}
 ==Stránkování==
   * LAP procesu není zobrazován do jediné souvislé sekce FAP, zobrazuje se po částech do volných sekcí FAP
   * FAP se dělí na //rámce// -- pevná délka (např. 512 B)
@@ Řádek 490: / Řádek 716: @@
   *Problém snížení efektivnosti dvojím přístupem lze řešit speciální rychlou HW cache (asociativní paměť, TLB -- Translation Look-aside Buffer)
+{{:mgr-szz:in-pos:strankovani.png?300|}}
+==Segmentace==
+  * 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
+{{:mgr-szz:in-pos:segmentace.png?300|}}
+== Virtuální pamět ==
+  * Uložení obrazu LAP (virtuální paměti) v externí paměti
+    * nepoužívá se standardní systém souborů OS, používají se speciální metody, optimalizované pro tento účel
+    * speciální partition/slice disku
+  * Stránkování / segmentaci musí podporovat hardware správy paměti
+    * stránkování na žádost
+    * segmentování na žádost
+    * **žádost** – dynamicky kontextově generovaná indikace nedostatku
+  * OS musí být schopen organizovat tok stránek / segmentů mezi vnitřní a vnější pamětí
+<box 95% round blue|Stránkování na žádost (Demand paging)>
+  * stránka se zobrazuje do FAP při odkazu na ni, pokud ve FAP není již zobrazena
+  * počáteční shluky výpadků stránek
+</box>
+<box 95% round blue|Předstránkování (Prepaging)>
+  * umístění na vnější paměti sousedních stránek v LAP bývá blízké („sousedi“)
+  * princip lokality
+  * zavádí se více stránek než se žádá
+  * vhodné při inicializaci procesu
+</box>
+== Výpadek stránky ==
+Pokud se stránka nenachází ve FAP je aktivován OS pomocí přerušení „page fault“ (výpadek stránky)
+  * OS zjistí:
+    * nelegální reference → procesu je informován (např. signál SIGSEGV)
+    * legální reference, ale stránka chybí v paměti → zavede ji
+  * Zavedení stránky
+    * získání prázdného rámce
+    * zavedení stránky do tohoto rámce
+    * úprava tabulky, nastaven bit valid/invalid na 1
+  * Pak se opakuje instrukce, která způsobila „page fault“
+== Algoritmy určující oběť ==
+  * **Algoritmus LRU (Least Recently Used)**
+    * oběť = nejdéle neodkazovaná stránka
+  * **Algoritmus FIFO (First-In-First-Out)**
+    * oběť = stránka nejdéle zobrazená ve FAP
+  * **Algoritmus poslední šance**
+    * FIFO + vynechávání z výběru těch stránek, na které od posledního výběru bylo odkázáno
+===== Ovládání vstupů a výstupů =====
+  * HW pro I/O je značně rozmanitý
+  * Existují však určité běžně používané prvky:
+    * port
+    * sběrnice (bus)
+    * řadič (host adapter, controller)
+  * I/O zařízení jsou řízeny I/O instrukcemi (IN, OUT)
+  * Adresy I/O zařízení
+    * uváděné přímo v I/O instrukcích (např. IN AL, DX : DX port, AL získaný bajt)
+    * I/O se mapuje na přístup k paměti (např. grafická karta, videopaměť)
+==== Základní způsoby ovládání I/O ====
+=== Polling, programované I/O operace ===
+  * aktivní čekání na konec operace
+  * opakovaně se ptám na stav zařízení
+    * připraven
+    * pracuje
+    * chyba
+=== Přerušení ===
+  * zahájení I/O pomocí I/O příkazu
+  * paralelní běh I/O s během procesoru
+  * I/O modul oznamuje přerušením konec přenosu
+  * Přerušení obsluhuje ovladač přerušení (kód OS)
+  * Maskováním lze některá přerušení ignorovat nebo oddálit jejich obsluhu
+  * Patřičný ovladač přerušení se vybírá přerušovacím vektorem
+    * některá přerušení nelze maskovat
+    * přerušení mohou být uspořádána podle priorit
+  * Přerušení se používá i pro řešení výjimek (nejsou asynchronní)
+=== DMA ===
+  * kopírování bloků mezi pamětí a I/O zařízením na principu kradení cyklů paměti
+  * přerušení po přenosu bloku (indikace konce)
+  * nahrazuje programovaný I/O při velkých přesunech dat
+  * vyžaduje speciální DMA řadič
+  * při přenosu dat se obchází procesor, přístup do paměti
+  * zajišťuje přímo DMA řadič
+  * procesor a DMA soutěží o přístup k paměti
+==== Aplikační rozhraní I/O ====
+  * Jádro OS se snaží skrýt rozdíly mezi I/O zařízeními a programátorům poskytuje jednotné rozhraní.
+  * Dále vrstva ovladačů ukrývá rozdílnost chování I/O řadičů i před některými částmi jádra
+  * Některé vlastnosti I/O zařízení
+    * mód přenosu dat: znakové (terminál) / blokové (disk)
+    * způsob přístupu: sekvenční (modem) / přímý (disk)
+    * sdílené/dedikované: klávesnice / páska
+    * rychlost přenosu: vystavení, přenos, ...
+    * read-write, read only, write only
+==== Síťová zařízení ====
+  * Přístup k nim se značně liší jak od znakových, tak od blokových zařízení
+    * proto mívají samostatné rozhraní OS
+  * Unix i Windows obsahující rozhraní nazývané „sockets“
+    * separují síťové protokoly od síťových operací
+    * přístup jako k souborům (včetně funkce select)
+  * Existuje celá řada přístupů k síťovým službám
+    * Pipes (roury), FIFOs, streams, queues, mailboxes
+==== Blokující a neblokující I/O ====
+  * Blokující
+    * z hlediska procesu synchronní
+    * proces čeká na ukončení I/O
+    * snadné použití (programovaní), snadné porozumění (po provedení operace je hotovo to co jsem požadoval)
+    * někdy však není dostačující (z důvodu efektivity)
+  * Neblokující
+    * řízení se procesu vrací co nejdříve po zadání požadavku
+    * vhodné pro uživatelské rozhraní, bufferovaný I/O
+    * bývá implementováno pomocí vláken
+    * okamžitě vrací počet načtených či zapsaných znaků
+  * Asynchronní
+    * proces běží souběžně s I/O
+    * konec I/O je procesu hlášen signály
+    * obtížné na programovaní, složité používání, ale v případě vhodně promyšleného programu velice efektivní
+==== I/O subsystém v jádře ====
+  * Plánování
+    * některé I/O operace požadují řazení do front na zařízení
+    * některé OS se snaží o „spravedlnost“
+  * Vyrovnání (vyrovnávací paměti), buffering
+    * ukládání dat v paměti v době přenosu k/ze zařízení
+    * řeší rozdílnost rychlosti
+    * řeší rozdílnost velikosti datových jednotek
+  * Caching
+    * rychlá paměť udržuje kopii dat
+    * vždy pouze kopii
+    * caching je klíčem k dosažení vysokého výkonu
+  * Spooling
+    * udržování fronty dat určených k výpis na zařízení
+    * pokud zařízení může vyřizovat požadavky pouze sekvenčně
+    * typicky tiskárna
+  * Rezervace zařízení
+    * exkluzivita přístupu k zařízení pro proces
+    * rezervace / uvolnění – volání systému
+    * pozor na uváznutí (deadlock)
+  * Chybové řízení
+    * Vzpamatování se po poruše při chybě čtení z disku, zjištění nedostupnosti zařízení, po náhodné chybě zápisu, ...
+    * Volání požadující I/O operaci získá číslo chyby
+      * typicky záporná hodnota
+    * Udržuje se záznam o chybách v systému
+      * pro následné analýzy
+      * syslog, events (viewer), ...
@@ Řádek 496: / Řádek 915: @@
   * http://statnice.dqd.cz/home:prog:ap5
   * http://statnice.dqd.cz/mgr-szz:ap-ap:7
-  * slidy PB153
+  * slidy PB153 (text i schémata)
     * 04 Principy výstavby OS
     * 05 Procesy
     * 06 Vlákna
+    * 07 Plánování CPU
+    * 08 Synchronizace procesů
+    * 09 Uváznutí
+    * 10 Správa paměti
+    * 11 Virtuální paměť
+    * 12 I/O systém

mgr-szz/in-pos/1-pos.1559739584.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru