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

Verze z 29. 8. 2011, 22:03 (editovat) Tester (diskuse | příspěvky) ← Porovnání se starší verzí		Verze z 20. 2. 2014, 06:47 (editovat) (zrušit editaci) Acolade (diskuse | příspěvky) m (kategorizace) Porovnání s novější verzí →
Řádka 25:		Řádka 25:
	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+
		+
		+	[[Kategorie:fav-kiv-bzinf]]

---

Verze z 20. 2. 2014, 06:47

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:

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ů - systém rozhodne zda je bezpečné požadovaný zdroj přidělit) - mělo by předejít uvíznutí (bankéřův algoritmus)
4. Prevence pomocí strukturální negace jedné z podmínek pro vznik uvíznutí