‹#›/23 PB153 Operační systémy a jejich rozhraní Uváznutí 09 ‹#›/23 lExistuje 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 lPří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é lPří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Í ‹#›/23 lMost s jednosměrným provozem lKaždý vjezd mostu lze chápat jako zdroj lDojde-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) lPři řešení uváznutí se může vracet i více vozů lMůže docházet ke stárnutí PŘÍKLAD: ÚZKÝ MOST PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 ANIMACE ÚZKÉHO MOSTU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lUvá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 lStá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Í ‹#›/23 lTypy zdrojů R1, R2, …, Rm ●tiskárna, paměť, I/O zařízení, … lKaždý zdroj Ri má Wi instancí lKaž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Í ‹#›/23 lK 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Í ‹#›/23 lResource-Allocation Graph, RAG lMnožina uzlů V a množina hran E luzly 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 lHrana požadavku – orientovaná hrana Pi → Rj lHrana přidělení – orientovaná hrana Rj → Pi lProces: l lZdroj se 4 instancemi: l lProces Pi požadující prostředek Rj: l lProces Pi vlastnící prostředek Rj : l GRAF PŘIDĚLENÍ ZDROJŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Pi Pi Pi ‹#›/23 PŘÍKLAD RAG (BEZ CYKLU) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 R1 R3 R2 R4 ‹#›/23 PŘÍKLAD RAG (S UVÁZNUTÍM) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 R1 R3 R2 R4 ‹#›/23 PŘÍKLAD RAG (BEZ UVÁZNUTÍ) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 P4 R1 R2 ‹#›/23 lJestliže se v RAG nevyskytuje cyklus – k uváznutí nedošlo lJestliž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Í ‹#›/23 lOchrana 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 lObchá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í) lObnova po uváznutí ●uváznutí povolíme, ale jeho vznik detekujeme a řešíme lIgnorová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Í ‹#›/23 lNepří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ů lPří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Í ‹#›/23 lVzá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) lPonechá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Í ‹#›/23 lZaká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 lZabrá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Í ‹#›/23 lSystém musí mít nějaké dodatečné apriorní informace lNejjednodušší 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 lAlgoritmus ř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í lStav 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Í ‹#›/23 lUmožníme, aby došlo k uváznutí lAle toto uváznutí detekujeme lAplikujeme plán obnovy l DETEKCE UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lUdržuje se graf čekání (wait-for graph) ●uzly jsou procesy ●Pi → Pj jestliže Pi čeká na Pj lPeriodicky se provádí algoritmus, který v grafu hledá cykly lAlgoritmus 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Í ‹#›/23 lGraf přidělení zdrojů lOdpovídající graf čekání GRAFY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P5 R1 R3 R4 R5 R2 P1 P2 P3 P4 P5 P1 P2 P3 P4 (a) (b) ‹#›/23 lNásilné ukončení uváznutých procesů lNásilně se ukončuje jednotlivě proces po procesu, dokud se neodstraní cyklus lČí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Í ‹#›/23 lVýběr oběti: minimalizace ceny lNávrat zpět (rollback) – návrat do některého bezpečného stavu, proces restartujeme z tohoto stavu lStá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 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Í