Problém uvíznutí procesů, graf alokace zdrojů
Z FAV wiki
V množině procesů nastalo uvíznutí, jestliže každý proces množiny čeká na událost, kterou může způsobit pouze jiný proces množiny. Protože všechny čekají, žádný z nich událost nevygeneruje, nevzbudí jiný proces.
Podmínky vzniku uvíznutí (musejí být splněny všechny 4, 1-3 jsou předpoklad pro 4):
- Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu
- „hold and wait“: proces držící výhradně přiřazené zdroje může požadovat další zdroje
- Nemožnost odejmutí: jednomu přiřazené zdroje nemohou být procesu násilně odejmuty
- Cyklické čekání: musí být cyklický řetězec dvou nebo více procesů, kde každý z nich čeká na zdroj držený dalším členem
- tyto 4 podmínky mohou být modelovány pomocí orientovaných grafů = graf alokace zdrojů
- graf má 2 typy uzlů:
- proces - zobrazujeme jako kruh
- zdroj - zobrazujeme jako čtverec
- význam hran:
- od zdroje k procesu: zdroj držen procesem
- od procesu ke zdroji: proces je blokován čekáním na zdroj
- cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí
Strategie zacházení s uvíznutím:
- Ignorování = „pštrosí algoritmus“
- Detekce a zotavení (odejmutí zdroje, zrušení změn, zrušení procesu)
- Dynamické zabrání (pečlivá alokace zdrojů - systém rozhodne zda je bezpečné požadovaný zdroj přidělit) - mělo by předejít uvíznutí (bankéřův algoritmus)
- Prevence pomocí strukturální negace jedné z podmínek pro vznik uvíznutí
