PB 153 Operační systémy a jejich rozhraní1 Uváznutí PB153 Operační systémy a jejich rozhraní PB 153 Operační systémy a jejich rozhraní2 Problém uváznutí 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) PB 153 Operační systémy a jejich rozhraní3 Příklad: úzký most 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í PB 153 Operační systémy a jejich rozhraní4 Definice uváznutí a stárnutí 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. PB 153 Operační systémy a jejich rozhraní5 Model 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) PB 153 Operační systémy a jejich rozhraní6 Charakteristika uváznutí 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 PB 153 Operační systémy a jejich rozhraní7 Graf přidělení zdrojů 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 : Pi Pi Pi PB 153 Operační systémy a jejich rozhraní8 Příklad RAG (bez cyklu) PB 153 Operační systémy a jejich rozhraní9 Příklad RAG (s uváznutím) PB 153 Operační systémy a jejich rozhraní10 Příklad RAG (bez uváznutí) PB 153 Operační systémy a jejich rozhraní11 RAG: závěry 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 PB 153 Operační systémy a jejich rozhraní12 Problém uváznutí 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 PB 153 Operační systémy a jejich rozhraní13 Ochrana prevencí 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ů PB 153 Operační systémy a jejich rozhraní14 Prevence uváznutí (1) 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í PB 153 Operační systémy a jejich rozhraní15 Prevence uváznutí (2) 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 PB 153 Operační systémy a jejich rozhraní16 Obcházení uváznutí 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ů PB 153 Operační systémy a jejich rozhraní17 Detekce uváznutí Umožníme, aby došlo k uváznutí Ale toto uváznutí detekujeme Aplikujeme plán obnovy PB 153 Operační systémy a jejich rozhraní18 1 instance prostředku každého typu 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 PB 153 Operační systémy a jejich rozhraní19 Grafy Graf přidělení zdrojů Odpovídající graf čekání PB 153 Operační systémy a jejich rozhraní20 Obnova: ukončení procesu 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ů PB 153 Operační systémy a jejich rozhraní21 Obnova: nové rozdělení prostředků 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ů)