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

Tomiksed: /* Řešení zablokování */

2017-05-26T17:43:07Z

Řešení zablokování

← Starší verze		Verze z 26. 5. 2017, 17:43
Řádka 29:		Řádka 29:
	#* 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 => ztracena práce... obdoba u DB)		#* 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í); ~~Viď.~~ 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á.	+	# '''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		# 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)

95.47.186.95 v 10. 6. 2015, 11:25

2015-06-10T11:25:43Z

95.47.186.95 v 10. 6. 2015, 11:21

2015-06-10T11:21:54Z

← Starší verze		Verze z 10. 6. 2015, 11:21
Řá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. Protože všechny čekají, žádný z nich událost nevygeneruje, nevzbudí jiný proces.		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ů	+	== Podmínky vzniku uvíznutí ==
−	* graf má 2 typy uzlů:	+	(musejí být splněny všechny 4, 1-3 jsou předpoklad pro 4):
−	** proces - zobrazujeme jako kruh	+	# Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu
−	** zdroj - zobrazujeme jako čtverec	+	# „hold and wait“: proces držící výhradně přiřazené zdroje může požadovat další zdroje
−	* význam hran:	+	# Nemožnost odejmutí: jednomu přiřazené zdroje nemohou být procesu násilně odejmuty
−	** od zdroje k procesu: zdroj držen procesem	+	# 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
−	** 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í	+	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:~~	+
−	~~# Ignorování~~ = ~~„pštrosí algoritmus“~~	+	== Řešení zablokování ==
−	# 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)	+	# 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)
−	# ~~Prevence pomocí strukturální negace~~ jedné z podmínek ~~pro vznik uvíznutí~~	+	# 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 $ \Rightarrow$ 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í); Viď. 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.

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}

Acolade: kategorizace

2014-02-20T06:47:22Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:47
Řádka 25:		Řádka 25:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+
		+
		+	[[Kategorie:fav-kiv-bzinf]]

Tester v 29. 8. 2011, 22:03

2011-08-29T22:03:03Z

← Starší verze		Verze z 29. 8. 2011, 22:03
Řá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.
−	· 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):
−	1. Vzájemné vyloučení: každý zdroj je buď dostupný, nebo je výhradně přiřazen právě jednomu procesu	+	* 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	+	* „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	+	* 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	+	* 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ů	+	* tyto 4 podmínky mohou být modelovány pomocí orientovaných grafů = graf alokace zdrojů
−	· graf má 2 typy uzlů:	+	* graf má 2 typy uzlů:
−	- proces - zobrazujeme jako kruh	+	** proces - zobrazujeme jako kruh
−	- zdroj - zobrazujeme jako čtverec	+	** zdroj - zobrazujeme jako čtverec
−	· význam hran:	+	* význam hran:
−	- od zdroje k procesu: zdroj držen procesem	+	** od zdroje k procesu: zdroj držen procesem
−	- od procesu ke zdroji: proces je blokován čekáním na zdroj	+	** 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í	+	* 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:
−	1. Ignorování = „pštrosí algoritmus“	+	# Ignorování = „pštrosí algoritmus“
−	2. Detekce a zotavení (odejmutí zdroje, zrušení změn, zrušení procesu)	+	# Detekce a zotavení (odejmutí zdroje, zrušení změn, zrušení procesu)
−	3. Dynamické zabrání (pečlivá alokace zdrojů)	+	# 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í	+	# Prevence pomocí strukturální negace jedné z podmínek pro vznik uvíznutí
		+
		+	{{fav-kiv-bzinf}}

Tester v 10. 8. 2011, 11:12

2011-08-10T11:12:14Z

← Starší verze		Verze z 10. 8. 2011, 11:12
Řádka 16:		Řádka 16:
	- od procesu ke zdroji: proces je blokován čekáním na zdroj		- 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í		· cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí
		+
		+	[[Soubor:Alokace-zdroju.jpg]]

	Strategie zacházení s uvíznutím:		Strategie zacházení s uvíznutím:

Tester: Založena nová stránka: 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 če...

2011-08-08T15:23:25Z

Založena nová stránka: 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 če...

Nová stránka

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í

← Starší verze		Verze z 10. 6. 2015, 11:25
Řá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 ~~$ \Rightarrow$~~ ztracena práce... obdoba u DB)	+	#* 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í); Viď. 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á.	+	# '''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í); Viď. 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	+	# 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}}