1/23 PB153 Operační systémy a jejich rozhraní Uváznutí 13 2/23  Existuje množina blokovaných procesů, každý proces vlastní nějaký prostředek (zdroj) a čeká na zdroj držený jiným procesem z této množiny  Příklad 1 ● v systému existují 2 páskové mechaniky ● procesy P1 a P2 chtějí kopírovat data z pásky na pásku, každý z procesů „vlastní“ jednu mechaniku a požaduje alokací druhé  Příklad 2 ● Semafory A a B, inicializované na 1 P0 P1 wait (A); wait(B) wait (B); wait(A) PROBLÉM UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 3/23  Most s jednosměrným provozem  Každý vjezd mostu lze chápat jako zdroj  Dojde-li k uváznutí, lze ho řešit tím, že se jedno auto vrátí ● Preempce zdroje (přivlastnění si zdroje, který vlastnil někdo jiný) a vrácení soupeře do situace před žádostí o přidělení zdroje (preemption a rollback)  Při řešení uváznutí se může vracet i více vozů  Může docházet ke stárnutí PŘÍKLAD: ÚZKÝ MOST PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 4/23 ANIMACE ÚZKÉHO MOSTU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 5/23  Uváznutí ● množina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředku, 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. DEFINICE UVÁZNUTÍ A STÁRNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 6/23  Typy zdrojů R1, R2, …, Rm ● tiskárna, paměť, I/O zařízení, …  Každý zdroj Ri má Wi instancí  Každý proces používá zdroj následujícím způsobem 1. žádost 2. použití 3. uvolnění (v konečném čase) MODEL PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 7/23  K uváznutí dojde, když začnou současně platit 4 následující podmínky ● vzájemné vyloučení (mutual exclusion) ● sdílený zdroj může v jednom okamžiku používat pouze jeden proces ● ponechání si zdroje a čekání na další (hold and wait) ● proces vlastnící alespoň zdroj čeká na získání dalšího zdroje, dosud vlastněného jiným procesem ● bez předbíhání (no preemption) ● zdroj lze uvolnit pouze procesem, který ho vlastní, dobrovolně po té, co daný proces zdroj dále nepotřebuje ● kruhové čekání (circular wait) ● existuje takový seznam čekajících procesů (P0, P1, …, Pn), že P0 čeká na uvolnění zdroje drženého P1, P1 čeká na uvolnění zdroje drženého P2, …, Pn-1čeká na uvolnění zdroje drženého Pn, a Pn čeká na uvolnění zdroje drženého P0 CHARAKTERISTIKA UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 8/23  Resource-Allocation Graph, RAG  Množina uzlů V a množina hran E  uzly jsou dvou typů: ● P= {P1, P2, …, Pn}, množina procesů existujících v systému ● R = {R1, R2, …, Rm}, množina zdrojů existujících v systému  Hrana požadavku – orientovaná hrana Pi → Rj  Hrana přidělení – orientovaná hrana Rj → Pi  Proces:  Zdroj se 4 instancemi:  Proces Pi požadující prostředek Rj:  Proces Pi vlastnící prostředek Rj : GRAF PŘIDĚLENÍ ZDROJŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Pi Pi Pi 9/23 PŘÍKLAD RAG (BEZ CYKLU) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 R1 R3 R2 R4 10/23 PŘÍKLAD RAG (S UVÁZNUTÍM) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 R1 R3 R2 R4 11/23 PŘÍKLAD RAG (BEZ UVÁZNUTÍ) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 P4 R1 R2 12/23  Jestliže se v RAG nevyskytuje cyklus – k uváznutí nedošlo  Jestliže se v RAG vyskytuje cyklus ● existuje pouze jedna instance zdroje daného typu → k uváznutí došlo ● existuje více instancí zdroje daného typu → k uváznutí může (ale nemusí) dojít RAG: ZÁVĚRY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 13/23  Ochrana před uváznutím prevencí ● zajistíme, že se systém nikdy nedostane do stavu uváznutí ● zrušíme platnost některé nutné podmínky  Obcházení uváznutí ● detekce potenciální možnosti vzniku uváznutí a nepřipuštění takového stavu ● zamezujeme současné platnosti všech nutných podmínek ● prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí)  Obnova po uváznutí ● uváznutí povolíme, ale jeho vznik detekujeme a řešíme  Ignorování hrozby uváznutí ● uváznutí je věc aplikace ne systému ● způsob řešení zvolený většinou OS PROBLÉM UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 14/23  Nepřímé metody ● zneplatnění některé nutné podmínky ● Virtualizací prostředků, ruším nutnost vzájemné výlučnosti při přístupu ● požadováním všech prostředků najednou ● odebíráním prostředků  Přímé metody ● nepřipuštění platnosti postačující podmínky (cyklus v grafu) ● uspořádání pořadí vyžadování prostředků OCHRANA PREVENCÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 15/23  Vzájemné vyloučení ● podmínka není nutná pro sdílené zdroje ● u nesdílených zdrojů musí podmínka platit ● řeší se např. virtualizací prostředků (např. tiskárny)  Ponechání zdrojů a čekání na další ● při žádosti o zdroje proces žádné zdroje „vlastnit“ nesmí ● proces musí požádat o zdroje a obdržet je dříve než je spuštěn běh procesu ● důsledkem je nízká efektivita využití zdrojů a možnost stárnutí PREVENCE UVÁZNUTÍ (1) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 16/23  Zakázané předbíhání ● jestliže proces držící nějaké zdroje a požadující přidělení dalšího zdroje, nemůže zdroje získat okamžitě, pak se uvolní všechny tímto procesem držené zdroje ● „odebrané“ zdroje se zapíší do seznamu zdrojů, na které proces čeká ● proces bude obnoven, pouze jakmile může získat jak jím původně držené zdroje, tak jím nově požadované zdroje  Zabránění kruhovému pořadí ● zavedeme úplné uspořádání typů zdrojů a každý proces bude žádat o prostředky v pořadí daném vzrůstajícím pořadí výčtu PREVENCE UVÁZNUTÍ (2) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 17/23  Systém musí mít nějaké dodatečné apriorní informace  Nejjednodušší a nejužitečnější model požaduje, aby každý proces udal maxima počtu prostředků každého typu, které může požadovat  Algoritmus řešící obcházení uváznutí dynamicky zkouší, zda stav systému přidělování zdrojů zaručuje, že se procesy v žádném případě nedostanou do cyklické fronty čekání  Stav systému přidělování zdrojů se definuje počtem dostupných a přidělených zdrojů a maximem žádostí procesů OBCHÁZENÍ UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 18/23  Umožníme, aby došlo k uváznutí  Ale toto uváznutí detekujeme  Aplikujeme plán obnovy DETEKCE UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 19/23  Udržuje se graf čekání (wait-for graph) ● uzly jsou procesy ● Pi → Pj jestliže Pi čeká na Pj  Periodicky se provádí algoritmus, který v grafu hledá cykly  Algoritmus pro detekci cyklu v grafu požaduje provedení n2 operací, kde n je počet uzlů v grafu 1 INSTANCE PROSTŘEDKU KAŽDÉHO TYPU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 20/23 Graf přidělení zdrojů Odpovídající graf čekání GRAFY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P5 R1 R3 R4 R5R2 P1 P2 P3 P4 P5 P1 P2 P3 P4 (a) (b) 21/23  Násilné ukončení uváznutých procesů  Násilně se ukončuje jednotlivě proces po procesu, dokud se neodstraní cyklus  Čím je dáno pořadí násilného ukončení? ● priorita procesu ● doba běhu procesu, doba potřebná k ukončení procesu ● prostředky, které proces použil ● prostředky, které proces potřebuje k ukončení ● počet procesů, které bude potřeba ukončit ● preference interaktivních nebo dávkových procesů OBNOVA: UKONČENÍ PROCESU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 22/23  Výběr oběti: minimalizace ceny  Návrat zpět (rollback) – návrat do některého bezpečného stavu, proces restartujeme z tohoto stavu  Stárnutí – některý proces může být vybírán jako oběť trvale ● řešení: do cenové funkce zahrneme počet restartů (rollbacků) OBNOVA: NOVÉ ROZDĚLENÍ PROSTŘEDKŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 23/23 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Í