Problém uvíznutí procesů, graf alokace zdrojů
Z FAV wiki
(Rozdíly mezi verzemi)
m (→Řešení zablokování) |
|||
| (Není zobrazena 1 mezilehlá verze od 1 uživatele.) | |||
| Řádka 24: | Řádka 24: | ||
== Řešení zablokování == | == Řešení zablokování == | ||
| − | # Pštrosí algoritmus - Zablokování se ani nedetekuje, ani se mu nezabraňuje, ani se neodstraňuje, Uživatel sám rozhodne o řešení (kill). Nespotřebovává prostředky OS - nemá režii ani neomezuje podmínky provozu. (Nejčastější řešení - Unix, Windows) | + | # '''Pštrosí algoritmus''' - Zablokování se ani nedetekuje, ani se mu nezabraňuje, ani se neodstraňuje, Uživatel sám rozhodne o řešení (kill). Nespotřebovává prostředky OS - nemá režii ani neomezuje podmínky provozu. (Nejčastější řešení - Unix, Windows) |
| − | # Detekce a zotavení - Hledá kružnici v orientovaném grafu (hrany vedou od procesu, který čeká, k procesu, který prostředek vlastní), pokud tam je kružnice, nastalo zablokování a je třeba ho řešit: | + | # '''Detekce a zotavení''' - Hledá kružnici v orientovaném grafu (hrany vedou od procesu, který čeká, k procesu, který prostředek vlastní), pokud tam je kružnice, nastalo zablokování a je třeba ho řešit: |
#* Odebrání prostředku - dohled operátora, pouze na přechodnou dobu | #* Odebrání prostředku - dohled operátora, pouze na přechodnou dobu | ||
#* Zabíjení procesů z cyklu (resp. mimo cyklus vlastnící identický prostředek) | #* Zabíjení procesů z cyklu (resp. mimo cyklus vlastnící identický prostředek) | ||
| − | #* Rollback (OS ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu | + | #* Rollback (OS ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu => ztracena práce... obdoba u DB) |
| − | # Vyhýbání se - Bezpečný stav (procesy/prostředky nejsou zablokovány, existuje cesta, jak uspokojit všechny požadavky na prostředky spouštěním procesů v jistém pořadí); | + | # '''Vyhýbání se''' - Bezpečný stav (procesy/prostředky nejsou zablokovány, existuje cesta, jak uspokojit všechny požadavky na prostředky spouštěním procesů v jistém pořadí); Viz bankéřův algoritmus. Nutné je předem znát všechny prostředky, které budou programy potřebovat; OS pak dává prostředky tomu, který je nejblíž svému maximu potřeby a navíc pro který je prostředků dost na dokončení. Dnes se moc nepoužívá. |
| − | # | + | # P'''ředcházení (prevence)''' - napadení jedné z Coffmanových podmínek |
| − | # Vzájemné vyloučení - spooling (prostriedky spravuje jeden systemový proces, ktory dohliada na to, aby jeho stav bol konzistentny (tiskarna) - pozor na místo na disku) | + | # '''Vzájemné vyloučení''' - spooling (prostriedky spravuje jeden systemový proces, ktory dohliada na to, aby jeho stav bol konzistentny (tiskarna) - pozor na místo na disku) |
| − | # Drž a čekej - žádat o všechny prostředky před startem procesu. Nejprve všechno uvolnit a pak znovu žádat o všechny najednou | + | # '''Drž a čekej''' - žádat o všechny prostředky před startem procesu. Nejprve všechno uvolnit a pak znovu žádat o všechny najednou |
| − | # Neodnímatelnost - vede k chaosu | + | # '''Neodnímatelnost''' - vede k chaosu |
| − | # Čekání do kruhu - nejvýše jeden prostředek - všechny prostředky jednoznačně očíslovány, procesy mohou žádat o prostředky jen ve vzestupném pořadí | + | # '''Čekání do kruhu''' - nejvýše jeden prostředek - všechny prostředky jednoznačně očíslovány, procesy mohou žádat o prostředky jen ve vzestupném pořadí |
| − | # Dvojfázové zamykání - nejprve postupně všechno zamykám (první fáze). Potom se může pracovat se zamčenými prostředky - a na závěr se už jen odemyká (druhá fáze) - viď transakční spracování u databází ((striktní/konzervativní) dvoufázové zpracování) | + | # '''Dvojfázové zamykání''' - nejprve postupně všechno zamykám (první fáze). Potom se může pracovat se zamčenými prostředky - a na závěr se už jen odemyká (druhá fáze) - viď transakční spracování u databází ((striktní/konzervativní) dvoufázové zpracování) |
| − | Bankéřův algoritmus: Bankéř má klienty a těm slíbil jistou výšku úvěru. Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky do maximální výšky úvěru. Až klient skončí s obchodem, vrátí bance vypůjčené peníze. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu. | + | ''Bankéřův algoritmus'': Bankéř má klienty a těm slíbil jistou výšku úvěru. Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky do maximální výšky úvěru. Až klient skončí s obchodem, vrátí bance vypůjčené peníze. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu. |
{{fav-kiv-bzinf}} | {{fav-kiv-bzinf}} | ||
Aktuální verze z 26. 5. 2017, 17:43
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.
[editovat] 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í
[editovat] Řešení zablokování
- Pštrosí algoritmus - Zablokování se ani nedetekuje, ani se mu nezabraňuje, ani se neodstraňuje, Uživatel sám rozhodne o řešení (kill). Nespotřebovává prostředky OS - nemá režii ani neomezuje podmínky provozu. (Nejčastější řešení - Unix, Windows)
- Detekce a zotavení - Hledá kružnici v orientovaném grafu (hrany vedou od procesu, který čeká, k procesu, který prostředek vlastní), pokud tam je kružnice, nastalo zablokování a je třeba ho řešit:
- Odebrání prostředku - dohled operátora, pouze na přechodnou dobu
- Zabíjení procesů z cyklu (resp. mimo cyklus vlastnící identický prostředek)
- Rollback (OS ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu => ztracena práce... obdoba u DB)
- Vyhýbání se - Bezpečný stav (procesy/prostředky nejsou zablokovány, existuje cesta, jak uspokojit všechny požadavky na prostředky spouštěním procesů v jistém pořadí); Viz bankéřův algoritmus. Nutné je předem znát všechny prostředky, které budou programy potřebovat; OS pak dává prostředky tomu, který je nejblíž svému maximu potřeby a navíc pro který je prostředků dost na dokončení. Dnes se moc nepoužívá.
- Předcházení (prevence) - napadení jedné z Coffmanových podmínek
- Vzájemné vyloučení - spooling (prostriedky spravuje jeden systemový proces, ktory dohliada na to, aby jeho stav bol konzistentny (tiskarna) - pozor na místo na disku)
- Drž a čekej - žádat o všechny prostředky před startem procesu. Nejprve všechno uvolnit a pak znovu žádat o všechny najednou
- Neodnímatelnost - vede k chaosu
- Čekání do kruhu - nejvýše jeden prostředek - všechny prostředky jednoznačně očíslovány, procesy mohou žádat o prostředky jen ve vzestupném pořadí
- Dvojfázové zamykání - nejprve postupně všechno zamykám (první fáze). Potom se může pracovat se zamčenými prostředky - a na závěr se už jen odemyká (druhá fáze) - viď transakční spracování u databází ((striktní/konzervativní) dvoufázové zpracování)
Bankéřův algoritmus: Bankéř má klienty a těm slíbil jistou výšku úvěru. Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky do maximální výšky úvěru. Až klient skončí s obchodem, vrátí bance vypůjčené peníze. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu.
