Problém uvíznutí procesů, graf alokace zdrojů
Z FAV wiki
(Rozdíly mezi verzemi)
| Řádka 1: | Řádka 1: | ||
| − | 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. | + | 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): | 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í | |
[[Soubor:Alokace-zdroju.jpg]] | [[Soubor:Alokace-zdroju.jpg]] | ||
Strategie zacházení s uvíznutím: | 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í | |
| + | |||
| + | {{fav-kiv-bzinf}} | ||
Verze z 29. 8. 2011, 22:03
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í
