Principy operačních systémů. Lekce 7: Obrana proti deadlocku

Principy operačních systémů

Lekce 7: Obrana proti deadlocku

Principy operačních systémů – Ing. Nulíček Vladimír

Deadlock • Deadlock = uváznutí, zablokování • Vznik problému: proces drží určité prostředky, požaduje přidělení dalších prostředků, tyto nedostane a je převeden do stavu blokovaných procesů, přičemž drží nadále již dříve přidělené prostředky požadované jinými (čekajícími) procesy. • Např. jeden proces má přidělenu tiskárnu a požaduje modem, druhý proces má přidělen modem a požaduje tiskárnu – vzniká tzv. cyklické čekání.


2


Model zablokování – orientovaný graf


3


4 Coffmanovy podmínky zablokování 1. Vzájemné vyloučení (Exclusive use) - prostředek vlastní právě jeden proces nebo je volný 2. Drž a čekej (Hold and wait) - proces může vlastnit prostředek a žádat o další 3. Neodnímatelnost (No preemption) - přidělené prostředky nemohou být odebrány 4. Čekání do kruhu (Cyclic dependency) - procesy čekají na prostředky v kruhu, každý článek čeká na prostředek vlastněný dalším článkem Lekce 7: Obrana proti deadlocku

4


Řešení problému zablokování • pštrosí algoritmus – předstíráme, že problém neexistuje • detekce a zotavení (detection and recovery) – řešíme, až když nastane problém • vyhýbání se zablokování (avoidance) – „opatrným“ přidělováním zabráníme realizaci všech Coffmanových podmínek • předcházení zablokování (prevention) – napadení jedné z Coffmanových podmínek


5


Pštrosí algoritmus • Ve skutečnosti nejde o algoritmus • Problém zablokování se nedetekuje ani neřeší • Používá se tehdy, pokud zablokování nastává jen výjimečně (nebo pokud by náklady na jeho řešení by byly vyšší než případné důsledky problému) • Pokud dojde k zablokování, uživatel musí problém řešit tak, že jeden z procesů násilně ukončí a tím přeruší kruh čekání na přidělení prostředků. • Používá se ve většině univerzálních OS (Unix, Windows…) Lekce 7: Obrana proti deadlocku

6


Detekce a zotavení (detection and

recovery)

• Systém se nesnaží předcházet výskytu uváznutí, tzn. procesy mohou uváznout. • V případě výskytu uváznutí se tuto situaci snaží detekovat a na základě toho se pokusí uváznutí odstranit.


7


Detekce uváznutí


8


Detekce uváznutí


9


Detekce uváznutí


10


Detekce uváznutí - příklad


11


Zotavení z uváznutí • Zotavení pomocí odebrání

• Dočasné násilné odebrání prostředku a půjčení jinému procesu. Ve většině případů to vyžaduje manuální intervenci, (např. odebrání pásky nebo tiskárny).

• Zotavení pomocí návratu

• Periodicky si ukládáme důležité informace o procesech, tak abychom později byli schopni je vrátit do předchozích stavů. • Při detekci uváznutí, proces, který vlastní kritický prostředek, je vrácen zpět v čase do stavu, kdy daný prostředek ještě nevlastnil. Uvolněný kritický prostředek je přidělen jednomu z uváznutých procesů.

•

Zotavení pomocí ukončení procesů

• Ukončíme proces, který je součástí smyčky v alokačním grafu. • Problém s některými typy procesů (překlad x modifikace databáze).


12


Zamezení vzniku uváznutí (avoidance) • Většinou procesy alokují prostředky postupně jeden po druhém. • V okamžiku žádosti o další prostředek, systém musí rozhodnout, zda přidělení prostředku je bezpečné (tzn. že nedojde k uváznutí) či nebezpečné. • Prostředek bude přidělen pouze pokud to bude bezpečné. • Systém se snaží předejít uváznutí opatrnou alokací prostředků. • Postupový prostor (postupová cesta) lze použít pro modelování vzniku uváznutí. Lekce 7: Obrana proti deadlocku

13


Postupový prostor


14


• Procesy nesmí vstoupit do nebezpečné oblasti (Unsave region). Vstup do této oblasti vždy skončí uváznutím. • V bodě t, systém musí rozhodnout, zda přidělí plotter procesu B. • Abychom se vyhnuli uváznutí, B musí být pozastaven. • Proces B bude pokračovat, až proces A použije a opět uvolní plotter. Lekce 7: Obrana proti deadlocku

15


Bankéřův algoritmus • Algoritmus, který předchází vzniku uváznutí (Dijkstra, 1965). • Bezpečný stav • Pokud nedošlo k uváznutí a existuje takové alokační pořadí, které zaručuje, že každý proces bude postupně uspokojen a skončí. • Bankéřův algoritmus kontroluje, zda přidělení prostředku vede na bezpečný stav. • Pokud ne, pak je žádost odmítnuta. • Pokud ano, prostředek je přidělen. • Nevýhoda: proces musí dopředu vědět, které prostředky bude během svého života potřebovat. Lekce 7: Obrana proti deadlocku

16


Bankéřův algoritmus - příklad


17


Prevence uváznutí (prevention) • Spočívá v napadení jedné ze 4 Cofmannových podmínek: 1. Vzájemné vyloučení (Exclusive use) 2. Drž a čekej (Hold and wait) 3. Neodnímatelnost (No preemption) 4. Čekání do kruhu (Cyclic dependency)


18


Porušení vzájemného vyloučení • Sdílení prostředku s výlučným přístupem pomocí virtualizace. • Příklad: sdílení tiskárny – Každý proces pošle svůj požadavek do tiskové fronty. – Tiskový démon (server) postupně požadavky z tiskové fronty posílá na fyzickou tiskárnu. – Pouze tiskový démon přistupuje přímo k fyzické tiskárně. • Bohužel toto řešení nelze použít ve všech případech.


19


Porušení podmínky Hold and Wait • Každý proces musí alokovat všechny požadované prostředky v okamžiku spuštění (např. OS/360) – tzv. „úplné vyhrazování prostředků“ • Prostředky nebudou využívány optimálně. • Například: – Proces si alokuje disk, 5 minut z něj načítá vstupní data, potom 50 minut provádí výpočet a nakonec výsledek tiskne 5 minut na tiskárnu. – Disk i tiskárna jsou alokovány po celých 60 minut. • Pokud budeme znát požadavky na prostředky v okamžiku spuštění procesu můžeme použít bankéřův algoritmus. Lekce 7: Obrana proti deadlocku

20


Porušení podmínky neodnímatelnosti • V praxi v podstatě nelze realizovat


21


Porušení podmínky čekání do kruhu • Proces může mít přidělen v daném okamžiku pouze jeden prostředek. • Proces může alokovat více prostředků, ale pouze v přesně definovaném pořadí. – Prostředky mají přiřazena čísla (např. tiskárna 1, plotter 2, páska 3). – Proces může požádat pouze o prostředek s vyšším číslem než je maximum z již alokovaných prostředků. • Problém: pro daný počet procesů a prostředků nemusí existovat vhodné očíslování prostředků. V praxi v podstatě nelze realizovat Lekce 7: Obrana proti deadlocku

22

Principy operačních systémů. Lekce 7: Obrana proti deadlocku

Recommend Documents