Prostředky pro synchronizaci procesů - Historie editací

95.47.186.95 v 10. 6. 2015, 11:51

2015-06-10T11:51:16Z

← Starší verze		Verze z 10. 6. 2015, 11:51
Řádka 55:		Řádka 55:
	# Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.		# Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.

		+
		+
		+	----
		+
		+
		+	== Synchronizační primitiva ==
		+
		+	jsou v operačních systémech prostředky, umožňující zároveň běžícím
		+	aplikacím ošetřit současný přístup ke sdíleným prostředkům. Ve smyslu algoritmu se jedná o rozhraní
		+	a jeho implementace není důležitá.
		+
		+
		+	Chybné použití synchronizačních primitiv může vést k jejich '''neúčinnosti''' (tedy k prostředku stejně
		+	mohou přistoupit dva procesy najednou) nebo k '''deadlocku''' (vzájemnému zablokování).
		+
		+
		+	'''Deadlock''' (česky také uváznutí) je odborný výraz pro situaci, kdy úspěšné dokončení nějaké akce je
		+	podmíněno předchozím dokončením jiné akce, přičemž tato jiná akce může být dokončena až po
		+	dokončení původní akce. Vzniká paradox, často označovaný jako ''Co bylo dříve? Slepice nebo vejce?''.
		+
		+
		+	V počítači se jedná o zablokování procesů (případně vláken) způsobené čekáním na synchronizačních
		+	primitivech. Obvykle k němu dochází v důsledku chyby při jejich programování. Pokud uváznutí
		+	nastane, řeší se například zrušením transakce (rollback) nebo násilným ukončením procesů.
		+	Některé systémy spoléhají na to, že deadlock nastává zřídka a uživatel si pomůže sám.
		+
		+
		+	=== K uváznutí dojde jen při splnění všech následujících podmínek: ===
		+
		+	* '''Vzájemné vyloučení (Mutual exclusion)'''
		+	Prostředek může v jednom okamžiku používat jenom jeden proces (jinak dojde k chybě).
		+	* '''Drž a čekej (Hold & wait)'''
		+	Proces může žádat o další prostředky, i když už má nějaké přiděleny.
		+	* '''Neodnímatelnost (No preemption)'''
		+	Jakmile proces zmíněný prostředek vlastní, nelze mu ho bezpečně odejmout, musí ho sám vrátit.
		+	* '''Čekání do kruhu (Circular wait)'''
		+	Je možné uzavřít cyklus z procesů čekající každý na svého předchůdce – respektive k deadlocku
		+	dojde, jakmile je tento cyklus uzavřen.
		+
		+
		+	Mezi synchronizační primitiva patří '''zámek''' a jejich zobecnění '''semafory''', '''fronty zpráv''' a '''monitor'''.
		+
		+
		+	'''Zámky a semafory''' bývají implementovány operačním systémem pomocí atomických operací na
		+	sdílené paměti a plánovače.
		+
		+	Pro synchronizaci v paralelním programování stačí atomické operace na sdílené paměti (čekají na
		+	sebe procesy na různých procesorech a tedy mohou čekat aktivně) a je možné je implementovat i bez
		+	pomoci operačního systému.
		+
		+
		+	'''Fronty zpráv''' jsou primitivní operací v případě paralelního programování, ale je možné je
		+	implementovat v operačním systému i na jednom procesoru.
		+
		+
		+	'''Monitor''' je možné realizovat pouze s podporou programovacího jazyka.
		+
		+
		+	Korektní paralelní program - Nutné podmínky
		+	# Dva procesy se nesmí nacházet současně ve stejné sdružené sekci.
		+	# Žádné předpoklady nesmí být kladeny na rychlost a počet procesorů.
		+	# Pokud proces běžící mimo kritickou sekci nesmí být blokován ostatní procesy.
		+	# Žádný proces nesmí do nekonečna čekat na vstup do kritické sekce

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

Acolade: kategorizace

2014-02-20T06:46:57Z

kategorizace

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

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

Tester v 29. 8. 2011, 15:01

2011-08-29T15:01:08Z

← Starší verze		Verze z 29. 8. 2011, 15:01
Řádka 54:		Řádka 54:
	# Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.		# Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.
	# Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.		# Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.
		+
		+
		+	{{fav-kiv-bzinf}}

Tester v 29. 8. 2011, 14:57

2011-08-29T14:57:59Z

← Starší verze		Verze z 29. 8. 2011, 14:57
Řádka 1:		Řádka 1:
	Zakázání přerušení		Zakázání přerušení
−	· V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení	+	* V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení
−	· Zakážeme-li přerušení, k přepínání nedochází	+	* Zakážeme-li přerušení, k přepínání nedochází
−	· Nejjednodušší řešení, možné pouze v jednoprocesorovém systému	+	* Nejjednodušší řešení, možné pouze v jednoprocesorovém systému
−	· Není dovoleno v uživatelském režimu	+	* Není dovoleno v uživatelském režimu

	Řešení s aktivním čekáním		Řešení s aktivním čekáním
	Základní předpoklady o systému:		Základní předpoklady o systému:
−	1) Zápis a čtení ze společné datové oblasti jsou nedělitelné operace	+	# Zápis a čtení ze společné datové oblasti jsou nedělitelné operace
−	2) Kritické sekce nemohou mít přiřazenou prioritu	+	# Kritické sekce nemohou mít přiřazenou prioritu
−	3) Relativní rychlost procesů je neznámá	+	# Relativní rychlost procesů je neznámá
−	4) Proces se může pozastavit mimo kritickou sekci	+	# Proces se může pozastavit mimo kritickou sekci
		+
		+	Průběžně se testuje, zra už může proces do kritické sekce vstoupit - plýtvání časem CPU
		+

	Petersonovo řešení		Petersonovo řešení
−	· Na začátku není v kritické sekci žádný proces	+	* Na začátku není v kritické sekci žádný proces
−	· Proces 0 volá enter_CS(0)	+	* Proces 0 volá enter_CS(0)
−	- Nastaví interested[0]:=true, turn:=0;	+	** Nastaví interested[0]:=true, turn:=0;
−	- Protože interested[1]=false, nebude čekat ve smyčce	+	** Protože interested[1]=false, nebude čekat ve smyčce
−	· Pokud proces 1 volá enter_CS(1)	+	* Pokud proces 1 volá enter_CS(1)
−	- Nastaví interested[1]:=true, turn:=1;	+	** Nastaví interested[1]:=true, turn:=1;
−	- Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_CS(0))	+	** Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_CS(0))
−	· Co kdyby oba procesy volaly enter_CS téměř současně?	+	* Co kdyby oba procesy volaly enter_CS téměř současně?
−	- Oba nastaví interested na true	+	** Oba nastaví interested na true
−	- Oba nastaví turn na své číslo; „téměř souběžný zápis“ se ale provede sekvenčně, tj. nejdříve nastaví turn jeden, hodnota bude přepsána druhým	+	** Oba nastaví turn na své číslo; „téměř souběžný zápis“ se ale provede sekvenčně, tj. nejdříve nastaví turn jeden, hodnota bude přepsána druhým
−	- Oba se dostanou do while, proces 0 projde, proces 1 aktivně čeká	+	** Oba se dostanou do while, proces 0 projde, proces 1 aktivně čeká
		+

	Spin-lock s instrukcí TSL		Spin-lock s instrukcí TSL
−	~~· Proměnná zámek - na počátku 0~~
−	~~· Proces, který chce vstoupit do KS otestuje~~
−	~~- Pokud 0 nastaví na 1 a vstoupí do KS~~
−	~~- Pokud 1 čeká~~
−	~~· Problém časového souběhu:~~
−	~~- Jeden proces přečte, vidí 0~~
−	~~- Druhý proces je naplánován, přečte, vidí 0, nastaví na 1, vstoupí do KS~~
−	~~- Po naplánování první zapíše 1 a máme 2 procesy v KS~~
−	~~· Řešení vyžaduje HW podporu~~
−	~~- Většina současných počítačů má instrukci, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (TSL - „Test and Set Lock“)~~

−	~~Semafory~~	+	Většina současných počítačů má instrukci, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (TSL - „Test and Set Lock“) - HW podpora
−	~~viz 7~~	+
−	~~Mutexy~~	+	* Proměnná zámek - na počátku 0
−	~~Někdy~~ nepotřebujeme použít schopnost semaforů čítat, tj. stačila by nám pouze jejich schopnost zajistit vzájemné vyloučení => mutex	+	* Proces, který chce vstoupit do KS otestuje
−	Monitory	+	** Pokud 0 nastaví na 1 a vstoupí do KS
−	~~viz 8~~	+	** Pokud 1 čeká
		+	* Problém časového souběhu (pokud by TSL nebyla atomická):
		+	** Jeden proces přečte, vidí 0
		+	** Druhý proces je naplánován, přečte, vidí 0, nastaví na 1, vstoupí do KS
		+	** Po naplánování první zapíše 1 a máme 2 procesy v KS
		+	* Řešení vyžaduje HW podporu
		+
		+
		+
		+	Další možnosti
		+	* [[Semafory, jejich použití a implementace\|Semafory]]
		+	* Mutexy - někdy nepotřebujeme použít schopnost semaforů čítat, tj. stačila by nám pouze jejich schopnost zajistit vzájemné vyloučení => mutex
		+	* [[Monitory]]
		+
		+
	Předávání zpráv - primitiva send a receive		Předávání zpráv - primitiva send a receive
−	1. Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.	+	# Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.
−	2. Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.	+	# Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.

Tester: Založena nová stránka: Zakázání přerušení · V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení · Zakážeme-li přerušení, k přepínání nedo...

2011-08-08T15:22:24Z

Založena nová stránka: Zakázání přerušení · V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení · Zakážeme-li přerušení, k přepínání nedo...

Nová stránka

Zakázání přerušení
· V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení
· Zakážeme-li přerušení, k přepínání nedochází
· Nejjednodušší řešení, možné pouze v jednoprocesorovém systému
· Není dovoleno v uživatelském režimu

Řešení s aktivním čekáním
Základní předpoklady o systému:
1) Zápis a čtení ze společné datové oblasti jsou nedělitelné operace
2) Kritické sekce nemohou mít přiřazenou prioritu
3) Relativní rychlost procesů je neznámá
4) Proces se může pozastavit mimo kritickou sekci

Petersonovo řešení
· Na začátku není v kritické sekci žádný proces
· Proces 0 volá enter_CS(0)
- Nastaví interested[0]:=true, turn:=0;
- Protože interested[1]=false, nebude čekat ve smyčce
· Pokud proces 1 volá enter_CS(1)
- Nastaví interested[1]:=true, turn:=1;
- Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_CS(0))
· Co kdyby oba procesy volaly enter_CS téměř současně?
- Oba nastaví interested na true
- Oba nastaví turn na své číslo; „téměř souběžný zápis“ se ale provede sekvenčně, tj. nejdříve nastaví turn jeden, hodnota bude přepsána druhým
- Oba se dostanou do while, proces 0 projde, proces 1 aktivně čeká

Spin-lock s instrukcí TSL
· Proměnná zámek - na počátku 0
· Proces, který chce vstoupit do KS otestuje
- Pokud 0 nastaví na 1 a vstoupí do KS
- Pokud 1 čeká
· Problém časového souběhu:
- Jeden proces přečte, vidí 0
- Druhý proces je naplánován, přečte, vidí 0, nastaví na 1, vstoupí do KS
- Po naplánování první zapíše 1 a máme 2 procesy v KS
· Řešení vyžaduje HW podporu
- Většina současných počítačů má instrukci, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (TSL - „Test and Set Lock“)

Semafory
viz 7
Mutexy
Někdy nepotřebujeme použít schopnost semaforů čítat, tj. stačila by nám pouze jejich schopnost zajistit vzájemné vyloučení => mutex
Monitory
viz 8
Předávání zpráv - primitiva send a receive
1. Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.
2. Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.