Klasické problémy meziprocesové komunikace – producent-konzument aj. - Historie editací

Acolade: kategorizace

2014-02-20T06:48:10Z

kategorizace

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

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

Tester: /* Problémy */

2011-08-29T20:19:01Z

Problémy

← Starší verze		Verze z 29. 8. 2011, 20:19
Řádka 122:		Řádka 122:
	* Uvíznutí (Deadlock) - cyklické čekání dvou či více procesů na událost, kterou může vyvolat pouze některý z nich, nikdy k tomu však nedojde		* Uvíznutí (Deadlock) - cyklické čekání dvou či více procesů na událost, kterou může vyvolat pouze některý z nich, nikdy k tomu však nedojde
	* Vyhladovění (starvation) - proces se nedostane k požadovaným zdrojům		* Vyhladovění (starvation) - proces se nedostane k požadovaným zdrojům
		+
		+
		+	{{fav-kiv-bzinf}}

Tester v 29. 8. 2011, 20:17

2011-08-29T20:17:55Z

← Starší verze		Verze z 29. 8. 2011, 20:17
Řádka 10:		Řádka 10:

	Problem sdilene pameti		Problem sdilene pameti
−	* Uvedene mechanismy	+	*umisteni objektu ve sdilene pameti
−	**umisteni objektu ve sdilene pameti	+	* Bezpecnost - globalni data pristupna kteremukoliv procesu bez ohledu na semafor
−	* Nekdy neni vhodne	+	* Procesy bezi na ruznych strojich, komunikuji spolu po siti Reseni - predavani zprav
−	** Bezpecnost - globalni data pristupna kteremukoliv procesu bez ohledu na semafor	+
−	* Nekdy neni mozne	+
−	** Procesy bezi na ruznych strojich, komunikuji spolu po siti Reseni { predavani zprav	+

−	Predavani zprav	+
		+	== Predavani zprav ==
		+
	* send, receive		* send, receive
	* Zavedeme 2 primitiva		* Zavedeme 2 primitiva
	** send (adresat, zprava) - odeslani zpravy		** send (adresat, zprava) - odeslani zpravy
−	** receive(odesilatel, zprava) - prijem zpravy	+	** receive (odesilatel, zprava) - prijem zpravy
−	** Send Zprava (lib. datovy objekt) bude zaslana adresatovi	+	** Send - Zprava (lib. datovy objekt) bude zaslana adresatovi
−	** Receive Prijem zpravy od urceneho odesilatele Prijata zprava se ulozi do promenne "zprava\	+	** Receive - Prijem zpravy od urceneho odesilatele Prijata zprava se ulozi do promenne "zprava"
		+
		+	Synchronizace - blokující (synchronní) (recieve) / neblokující (asynchronní) (send)
		+
		+	* blokující send
		+	** čeká na převzetí správy příjemcem
		+	* neblokující send
		+	** vrací se ihned po odeslání zprávy
		+	** většina systémů
		+	* blokující receive
		+	** není-li ve frontě žádná zpráva, zablokuje se
		+	** většina systémů
		+	* neblokující receive
		+	** není-li zpráva, vrací chybu
		+
		+	problémy, které nejsou u semaforů ani monitorů, zvláště při komunikaci po síti
		+	* ztráta zprávy (potvrzení o přijetí (acknowledgement))
		+	* ztráta potvrzení (číslování zpráv, duplicitní zprávy se ignorují)
		+	* problém autentizace (zprávy je možné šifrovat)
		+
		+	lokální komunikace
		+	* rendezvous - eliminuje frontu zpráv, send zavolán dříve než receive – odesílatel zablokován, vyvolán send i receive – zprávu zkopírovat z odesílatele přímo do příjemce
		+	* využití mechanismu virtuální paměti paměť obsahující zprávu je přemapována z procesu odesílatele do procesu příjemce
		+
		+	typické aplikace typu klient - server
		+	* WWW klient x WWW server (Apache, IIS)
		+	* účetní aplikace x databázový systém (Oracle, MySQL)
		+
		+
		+	== Volání vzdálených procedur (RPC - Remote Procedure Call) ==
		+
		+	# Klient zavolá spojku klienta, reprezentující vzdálenou proceduru
		+	# Spojková procedura argumenty zabalí do zprávy, pošle ji serveru
		+	# Spojka serveru zprávu přijme, vezme argumenty a zavolá proceduru
		+	# Procedura se vrátí, návrat. hodnotu pošle spojka serveru zpět klientovi
		+	# Spojka klienta přijme zprávu obsahující návrat. hodnotu a předá ji volajícímu
		+
		+	dnes nejpoužívanější jazyková konstrukce pro
		+	implementaci distribuovaných systémů a
		+	programů bez explicitního předávání zpráv
		+
		+
		+
		+	== Ekvivalenty uvedených primitiv ==
		+	Lze implementovat semafory pomocí zpráv a zprávy pomocí semaforů
		+
		+	Lze ukázat, že je možné implementovat
		+	* Semafory pomocí monitoru
		+	* Monitory pomocí semaforů
		+
		+
		+
		+	== Bariéry ==
		+
		+	[[Soubor:Bariera.png]]


Řádka 47:		Řádka 100:
	* Špagety jsou tak klouzavé, že filosof potřebuje 2 vidličky, aby mohl jíst		* Špagety jsou tak klouzavé, že filosof potřebuje 2 vidličky, aby mohl jíst
	* Když filosof dostane hlad, pokusí se vzít 2 vidličky; pokud uspěje, nějakou dobu jí, pak položí vidličky a pokračuje v přemýšlení		* Když filosof dostane hlad, pokusí se vzít 2 vidličky; pokud uspěje, nějakou dobu jí, pak položí vidličky a pokračuje v přemýšlení
−	* Problémy: uvíznutí (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)	+	* Problémy: uvíznutí(deadlock) (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)
	* Řešení - Dijkstra (pomocí semaforů)		* Řešení - Dijkstra (pomocí semaforů)

Řádka 59:		Řádka 112:
	* Semafor w zabrání vstupu písaře, pokud jsou čtenáři		* Semafor w zabrání vstupu písaře, pokud jsou čtenáři
	* Semafor w také zabrání vstupu čtenářům, je-li písař		* Semafor w také zabrání vstupu čtenářům, je-li písař
		+	* toto je s předností čtenářů
		+
		+	* nebo to jde udělat tak, že když chce vstoupit písař, tak už tam nepustí další čtenáře (s předností písařů)
		+
		+
		+	== Problémy ==
		+
		+
		+	* Uvíznutí (Deadlock) - cyklické čekání dvou či více procesů na událost, kterou může vyvolat pouze některý z nich, nikdy k tomu však nedojde
		+	* Vyhladovění (starvation) - proces se nedostane k požadovaným zdrojům

Tester: /* Problém večeřících filosofů */

2011-08-29T19:14:46Z

Problém večeřících filosofů

← Starší verze		Verze z 29. 8. 2011, 19:14
Řádka 38:		Řádka 38:
	* přidání prvku: P(e), V(f)		* přidání prvku: P(e), V(f)
	* odebrání prvku: P(f), V(e)		* odebrání prvku: P(f), V(e)
		+

	== Problém večeřících filosofů ==		== Problém večeřících filosofů ==
Řádka 48:		Řádka 49:
	* Problémy: uvíznutí (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)		* Problémy: uvíznutí (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)
	* Řešení - Dijkstra (pomocí semaforů)		* Řešení - Dijkstra (pomocí semaforů)
−

	== Problém čtenářů a písařů ==		== Problém čtenářů a písařů ==

Tester: /* Producent-konzument */

2011-08-29T19:05:48Z

Producent-konzument

← Starší verze		Verze z 29. 8. 2011, 19:05
Řádka 35:		Řádka 35:
	** Producent musí být schopen čekat na konzumenta, je-li buffer plný		** Producent musí být schopen čekat na konzumenta, je-li buffer plný

		+	Klasicky se zde sdílená paměť řeší pomocí pole, kde se z jedné strany položky přidávají a z druhé odebírají. Index kam zapisovat/odebírat počítáme modulo velikost pole. Kolizím zabráníme pomocí dvou semaforů, kde jeden obsahuje informaci o počtu plných prvků pole (f) a druhý o počtu prázdných prvků (e).
		+	* přidání prvku: P(e), V(f)
		+	* odebrání prvku: P(f), V(e)

	== Problém večeřících filosofů ==		== Problém večeřících filosofů ==

Tester v 29. 8. 2011, 19:00

2011-08-29T19:00:33Z

← Starší verze		Verze z 29. 8. 2011, 19:00
Řádka 1:		Řádka 1:
−	Meziprocesova komunikace:	+	Meziprocesova komunikace: // tady by to chtělo rozvést a doplnit...
−	� Predavani zprav	+	* Predavani zprav
−	� Primitiva send, receive	+	* Primitiva send, receive
−	� Mailbox, port	+	* Mailbox, port
−	� RPC	+	* RPC
−	� Ekvivalence semaforu, zprav, ...	+	* Ekvivalence semaforu, zprav, ...
−	� Bariera, problem vecericich filozofu	+	* Bariera, problem vecericich filozofu
		+
		+

	Problem sdilene pameti		Problem sdilene pameti
−	� Uvedene mechanismy	+	* Uvedene mechanismy
−	{ umisteni objektu ve sdilene pameti	+	**umisteni objektu ve sdilene pameti
−	� Nekdy neni vhodne	+	* Nekdy neni vhodne
−	{ Bezpecnost { globalni data pristupna kteremukoliv procesu bez ohledu na semafor	+	** Bezpecnost - globalni data pristupna kteremukoliv procesu bez ohledu na semafor
−	� Nekdy neni mozne	+	* Nekdy neni mozne
−	{ Procesy bezi na ruznych strojich, komunikuji spolu po siti Reseni { predavani zprav	+	** Procesy bezi na ruznych strojich, komunikuji spolu po siti Reseni { predavani zprav

	Predavani zprav		Predavani zprav
−	{ send, receive	+	* send, receive
−	� Zavedeme 2 primitiva	+	* Zavedeme 2 primitiva
−	{ send (adresat, zprava) - odeslani zpravy	+	** send (adresat, zprava) - odeslani zpravy
−	{ receive(odesilatel, zprava) - prijem zpravy	+	** receive(odesilatel, zprava) - prijem zpravy
−	{ Send Zprava (lib. datovy objekt) bude zaslana adresatovi	+	** Send Zprava (lib. datovy objekt) bude zaslana adresatovi
−	{ Receive Prijem zpravy od urceneho odesilatele Prijata zprava se ulozi do promenne "zprava\	+	** Receive Prijem zpravy od urceneho odesilatele Prijata zprava se ulozi do promenne "zprava\
		+
		+
		+	== Producent-konzument ==
		+
		+	* Dva procesy sdílejí společnou paměť (buffer) pevné velikosti N položek
		+	* Jeden proces je producent - generuje nové položky a ukládá je do vyrovnávací paměti
		+	* Paralelně běží proces konzument, který data vyjímá a spotřebovává
		+	* Procesy mohou běžet různými rychlostmi => musí být zabezpečeno, aby nedošlo k přetečení/podtečení:
		+	** Konzument musí být schopen čekat na producenta, nejsou-li data
		+	** Producent musí být schopen čekat na konzumenta, je-li buffer plný
		+
		+
		+	== Problém večeřících filosofů ==
		+
		+	* 5 filosofů sedí kolem kulatého stolu
		+	* Každý filosof má před sebou talíř se špagetami
		+	* Mezi každými dvěma talíři je vidlička
		+	* Špagety jsou tak klouzavé, že filosof potřebuje 2 vidličky, aby mohl jíst
		+	* Když filosof dostane hlad, pokusí se vzít 2 vidličky; pokud uspěje, nějakou dobu jí, pak položí vidličky a pokračuje v přemýšlení
		+	* Problémy: uvíznutí (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)
		+	* Řešení - Dijkstra (pomocí semaforů)
		+

−	~~Producent-konzument~~	+	== Problém čtenářů a písařů ==
−	~~· Dva procesy sdílejí společnou paměť (buffer) pevné velikosti N položek~~	+
−	~~· Jeden proces je producent - generuje nové položky a ukládá je do vyrovnávací paměti~~	+
−	~~· Paralelně běží proces konzument, který data vyjímá a spotřebovává~~	+
−	~~· Procesy mohou běžet různými rychlostmi~~ =~~> musí být zabezpečeno, aby nedošlo k přetečení/podtečení:~~	+
−	~~- Konzument musí být schopen čekat na producenta, nejsou-li data~~	+
−	~~- Producent musí být schopen čekat na konzumenta, je-li buffer plný~~	+
−	~~Problém večeřících filosofů~~	+
−	~~· 5 filosofů sedí kolem kulatého stolu~~	+
−	~~· Každý filosof má před sebou talíř se špagetami~~	+
−	~~· Mezi každými dvěma talíři je vidlička~~	+
−	~~· Špagety jsou tak klouzavé, že filosof potřebuje 2 vidličky, aby mohl jíst~~	+
−	~~· Když filosof dostane hlad, pokusí se vzít 2 vidličky; pokud uspěje, nějakou dobu jí, pak položí vidličky a pokračuje v přemýšlení~~	+
−	· Problémy: uvíznutí (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)	+
−	~~· Řešení - Dijkstra (pomocí semaforů)~~	+
−	Problém čtenářů a písařů	+
−	~~· Představme si velkou databázi, množina procesů se pokouší souběžně číst a zapisovat~~	+
−	~~- Více požadavků čtení - akceptovatelné~~	+
−	~~- Při zápisu nesmí nikdo jiný přistupovat, ani žádní čtenáři~~	+
−	~~- První čtenář, který dostane přístup do databáze, provede P(w), další pouze zvětšují čítač~~	+
−	~~- Po skončení čtenáři zmenšují čítač, poslední provede V(w)~~	+
−	~~- Semafor w zabrání vstupu písaře, pokud jsou čtenáři~~	+
−	~~Semafor w také zabrání vstupu čtenářům, je-li písař~~	+

−	~~bank~~	+	* Představme si velkou databázi, množina procesů se pokouší souběžně číst a zapisovat
		+	* Více požadavků čtení - akceptovatelné
		+	* Při zápisu nesmí nikdo jiný přistupovat, ani žádní čtenáři
		+	* První čtenář, který dostane přístup do databáze, provede P(w), další pouze zvětšují čítač
		+	* Po skončení čtenáři zmenšují čítač, poslední provede V(w)
		+	* Semafor w zabrání vstupu písaře, pokud jsou čtenáři
		+	* Semafor w také zabrání vstupu čtenářům, je-li písař

Tester: Založena nová stránka: Meziprocesova komunikace: � Predavani zprav � Primitiva send, receive � Mailbox, port � RPC � Ekvivalence semaforu, zprav, ... � Bariera, problem vecericich fil...

2011-08-08T15:23:42Z

Založena nová stránka: Meziprocesova komunikace: � Predavani zprav � Primitiva send, receive � Mailbox, port � RPC � Ekvivalence semaforu, zprav, ... � Bariera, problem vecericich fil...

Nová stránka

Meziprocesova komunikace:
� Predavani zprav
� Primitiva send, receive
� Mailbox, port
� RPC
� Ekvivalence semaforu, zprav, ...
� Bariera, problem vecericich filozofu

Problem sdilene pameti
� Uvedene mechanismy
{ umisteni objektu ve sdilene pameti
� Nekdy neni vhodne
{ Bezpecnost { globalni data pristupna kteremukoliv procesu bez ohledu na semafor
� Nekdy neni mozne
{ Procesy bezi na ruznych strojich, komunikuji spolu po siti Reseni { predavani zprav

Predavani zprav
{ send, receive
� Zavedeme 2 primitiva
{ send (adresat, zprava) - odeslani zpravy
{ receive(odesilatel, zprava) - prijem zpravy
{ Send Zprava (lib. datovy objekt) bude zaslana adresatovi
{ Receive Prijem zpravy od urceneho odesilatele Prijata zprava se ulozi do promenne "zprava\

Producent-konzument
· Dva procesy sdílejí společnou paměť (buffer) pevné velikosti N položek
· Jeden proces je producent - generuje nové položky a ukládá je do vyrovnávací paměti
· Paralelně běží proces konzument, který data vyjímá a spotřebovává
· Procesy mohou běžet různými rychlostmi => musí být zabezpečeno, aby nedošlo k přetečení/podtečení:
- Konzument musí být schopen čekat na producenta, nejsou-li data
- Producent musí být schopen čekat na konzumenta, je-li buffer plný
Problém večeřících filosofů
· 5 filosofů sedí kolem kulatého stolu
· Každý filosof má před sebou talíř se špagetami
· Mezi každými dvěma talíři je vidlička
· Špagety jsou tak klouzavé, že filosof potřebuje 2 vidličky, aby mohl jíst
· Když filosof dostane hlad, pokusí se vzít 2 vidličky; pokud uspěje, nějakou dobu jí, pak položí vidličky a pokračuje v přemýšlení
· Problémy: uvíznutí (všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat), vyhladovění (pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí…)
· Řešení - Dijkstra (pomocí semaforů)
Problém čtenářů a písařů
· Představme si velkou databázi, množina procesů se pokouší souběžně číst a zapisovat
- Více požadavků čtení - akceptovatelné
- Při zápisu nesmí nikdo jiný přistupovat, ani žádní čtenáři
- První čtenář, který dostane přístup do databáze, provede P(w), další pouze zvětšují čítač
- Po skončení čtenáři zmenšují čítač, poslední provede V(w)
- Semafor w zabrání vstupu písaře, pokud jsou čtenáři
Semafor w také zabrání vstupu čtenářům, je-li písař

bank