Problém uvíznutí procesů, graf alokace zdrojů

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): 1. Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu 2. „hold and wait“: proces držící výhradně přiřazené zdroje může požadovat další zdroje 3. Nemožnost odejmutí: jednomu přiřazené zdroje nemohou být procesu násilně odejmuty 4. 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: 1. Ignorování = „pštrosí algoritmus“ 2. Detekce a zotavení (odejmutí zdroje, zrušení změn, zrušení procesu) 3. Dynamické zabrání (pečlivá alokace zdrojů) 4. Prevence pomocí strukturální negace jedné z podmínek pro vznik uvíznutí