5.5. Klasicke problemy synchronizace

• V teto kapitole ukazeme nektere synchronizacni problemy, ktere jsou vyznamne zejmena proto, ze jsou to ukazky z velke tridy problemu vyplyvajicich z problemu konkurencniho pristupu. Tyto problemy se uzivaji k testovani temer kazdeho nove navrhovaneho synchronizacniho schematu. K synchronizaci v nasem reseni uzijeme semafory.

	repeat
		   ...
		vytvor polozku do nova_polozka
		   ...
		cekej(prazdny);
		cekej(vzajed);
		   ...
		uloz nova_polozka do buffer
		   ...
		signal(vzajed);
		signal(plny);
	until false;

	repeat
		cekej(plny);
		cekej(vzajed);
		   ...
		odeber polozku z buffer do nova_polozka
		   ...
		signal(vzajed);
		signal(prazdny);
		   ...
		zpracuj polozku v nova_polozka
		   ...
	until false;

	var vzajed, zps : semafor;
	    citac_cteni : integer;

	cekej(zps);
	   ...
	zapis je vykonan
	   ...
	signal(zps);

	cekej(vzajed);
	  citac_cteni := citac_cteni + 1;
	  if citac_cteni = 1 then cekej(zps);
	signal(vzajed);
		...
		cteni je vykonano
		...
	cekej(vzajed);
	  citac_cteni := citac_cteni - 1;
	  if citac_cteni = 0 then signal(zps);
	signal(vzajed);

5.5.3. Problem hladovych filozofu (The Dining-Philosophers Problem)

• Predstavme si pet filozofu, kteri travi svuj zivot premyslenim a jedenim. Filozofove sdileji jeden spolecny kulaty stul, kolem ktereho je pet zidli, kazda pro jednoho filozofa. Uprostred stolu je miska ryze a u kraje je rozlozeno pet tycek ku pojidani ryze tak, jak ukazuje nasledujici obrazek. Kdyz filozof premysli neni v jakemkoliv spojeni se svymi spolustolovniky. Cas od casu na filozofa prijde hlad a pokusi se ziskat dve tycky, ktere jsou vedle nej (ty mezi nim a jeho pravym a levym sousedem). Filozof muze v jednu chvili sebrat pouze jedno tycku. Stejne tak nemuze tycku vytrhnou z ruky jeho souseda, pokud ji tento prave pouziva. V okamziku, kdy filozof ziskal obe tycky. muze zacit konzumaci ryze. Kdyz doji, odlozi tycky na jejich puvodni mista a pokracuje v premysleni. (Hygienicke aspekty problemu neuvazujeme!)

• Problem hladovych filozofu je povazovan za klasicky synchronizacni problem ne pro jeho prakticke vyuziti, ani proto, ze by pocitacovy specialiste nemeli radi filozofy, ale proto, ze je to zastupce velke tridy problemu soubezneho rizeni (concurrency control problems). Je to jednoduchy priklad situace, kdy ruzne procesy potrebuji alokovat ruzne zdroje a muze dojit k zablokovani i umoreni procesu.

Obr. 64 Problem hladovych filozofu

• Jednoduchym resenim je reprezentovat kazdou tycku jak semafor. Kazdy filozof vezme tycku provedenim funkce cekej na dany semafor. Odlozeni tycky se provadi funkci signal. Sdilena data mohou byt tedy reprezentovana datovou strukturou:

  	var tycka: array (o .. 4) of semafor;
  

  kde vsechny prvky pole jsou na pocatku iniciovany do hodnoty 1.

• Strukturu i-teho filozofa ukazuje Vypis 1. Toto reseni garantuje, ze zadni dva sousedni filozofove nebudou konzumovat soucasne, ovsem za cenu mozneho zablokovani filozofa. Uvazme, ze vsichni filozofove by dostali hlad soucasne. Tehdy by nejprve vsichni uchopili tycku, kterou maji po leve ruce, cimz by vsechny semafory presly do stavu 0. Kazdy filozof, ktery by pak chtel uchopit tycku po sve pravici se dostava do nekonecne cekaci smycky.

	repeat
		cekej(tycka(i));
		cekej(tycka(i+1 mod 5));
			...
      		       jedeni
			...
		signal(tycka(i));
		signal(tycka(i+1 mod 5));
			...
		     premysleni
			...
	until false

Vypis 1 Struktura i-teho filozofa

• Reseni tohoto problemu je vicero:

1. Pustit ke stolu maximalne 4 filozofy.

2. Dovolit filozofovi vzit tycku pouze tehdy, ma-li k dispozici obe.

3. Resit problem asymetricky, tj. Lisi filozofove by nejdrive sebrali levou tycku a potom pravou. Sudi filozofove naopak nejdrive pravou a potom levou.

4. Reseni za uziti monitoru si ukazeme v patricne kapitole.

• Uspokojive reseni problemu musi take garantovat, ze zadny z filozofu nebude umoren k smrti hlady. Je- li odstranen deadlock (moznost zablokovani) nekterym z vyse uvedenych postupu, umoreni nastat nemuze.

• Ackoliv semafory jsou vhodnym a efektivnim resenim problemu synchronizace procesu, jejich nespravne pouziti muze vyvolat nejruznejsi chyby v casovani, ktere se velmi tezko odhaluji, protoze nastavaji pouze "nekdy" - tehdy jsou-li v urcitem okamziku spusteny urcite sekvence urcitych procesu.

• V kapitole 5.1 jsme ukazaly jeden priklad chyb, ktere mohou nastat pri reseni problemu producenta a prijemce. V tomto pripade dochazi k problemu v casovani pomerne zridka a reseni pomoci semaforu je jednoduche a ucinne.

• Bohuzel, chyby v casovani mohou nastat i pri uziti semaforu. K ilustraci, jak k tomu muze dojit je treba si pripomenout, jak je pomoci semaforu resen problem kriticke sekce. Vsechny procesy sdili promennou semafor vzajed, ktera je na pocatku iniciovana do hodnoty 1. Kazdy proces musi spustit funkci cekej(vzajed) pred tim, nez vstoupi do kriticke sekce a funkci signal(vzajed) pote, co z kriticke sekce vystoupi. Jestlize neni tato sekvence zachovana, mohou byt dva procesy soucasne ve svych kritickych sekcich.

• Uvazme potize, ktere mohou pri tomto reseni vyvstat. Poznamenejme, ze k temto potizim dochazi pouze v pripade, kdyz se nektery proces chova nekorektne. K tomu muze dojit bud chybou programu, nebo nespolupracuje-li proces s ostatnimi.

1. Uvazujme, ze by nektery proces volal funkce cekej a signal v opacnem poradi, tj.:

   		signal(vzajed);
   		       ...
   		kriticka sekce
   		       ...
   		cekej(vzajed);
   
   

   Diky teto chybe muze nastat situace, ze vice procesu sdilejicich semafor vzajed bude soucasne ve sve kriticke sekci. Odhaleni teto chyby je mozne pouze v pripade, ze takova situace nastane (tj. ze vice procesu bude soucasne aktivni ve svych kritickych sekcich).

2. Necht jeden proces obsahuje tuto sekvenci prikazu:

   		cekej(vzajed);
   		       ...
   		kriticka sekce
   		       ...
   		cekej(vzajed);
   

   V tomto pripade muze nastat zablokovani (deadlock) procesu.

3. Uvazme, ze nektery proces vynecha bud funkci cekej nebo signal nebo obe dve. V tom pripade nastava bud poruseni vzajemne jednoznacnosti nebo deadlock.

• Tyto priklady ukazuji ruzne chyby, ktere mohou velmi jednoduse nastat, pokud je nespravne pracovano se semafory pri reseni problemu kriticke sekce. Jine problemy jsme jiz diskutovali v predchazejici kapitole.

• Ukazeme si prvni reseni takovychto problemu, ktere spociva ve vytvoreni synchronizacniho mechanismu vyssi urovne - kritickych oblasti (critical regions), nekdy tez nazyvanych podminene kriticke oblasti (conditional critical regions). V nasledujici kapitole ukazeme dalsi zakladni reseni, reseni pomoci monitoru.

• V prezentaci obou synchronizacnich konstrukci budeme uvazovat, ze proces obsahuje lokalni data a sekvencni program, ktery s nimi pracuje. Lokalni data mohou byt modifikovana pouze sekvencnim programem tehoz procesu. To znamena, ze zadny proces nemuze primo modifikovat lokalni data jineho procesu. Procesy mohou, nicmene, sdilet globalni data.

• Synchronizacni konstrukce vyssi urovne - kriticka oblast vyzaduje nejakou promennou p typu T, ktera bude sdilena ruznymi procesy. Deklarace:

	var p: shared T;

• K promenne p je mozno pristoupit pouze uvnitr oblasti nasledujicim prikazem

	region p when B do S;

• Tato konstrukce znamena, ze dokud je spusten prikaz S, zadny jiny proces nemuze pristoupit k promenne p. Promenna B je logicka promenna, ktera ridi vstup do kriticke oblasti. Kdyz proces hodla vstoupit do oblasti, je zkontrolovana hodnota promenne B. Jestlize je true, prikaz S muze byt spusten. Je-li false, proces se musi vzdat vstupu do oblasti a vyckat, dokud mu nebude promenna B priznive naklonena a zadny jiny proces nebude v kriticke oblasti asociovane s promennou p.

• To jest, jestlize dva prikazy:

	region p when true do S1;
	region p when true do S2;

• jsou soucasne spusteny v ruznych sekvencnich procesech, je vysledek ekvivalentni posloupnosti prikazu "S1 nasleduje za S2" nebo "S2 nasleduje za S1."

• Konstrukce kriticke oblasti zabranuje vzniku nekterych jednoduchych programatorskych chyb spojenych s resenim problemu kriticke sekce pomoci semaforu. Nepredchazi vsem chybam, ale zmensuje jejich pocet. Jestlize totiz chyba nastane v logice programu, vysledna sekvence udalosti nemusi byt prave nejjednoduseji postizitelna.

• Konstrukce kriticke oblasti muze byt efektivne vyuzita k reseni nekterych synchronizacnich problemu. Pro ilustraci takoveho reseni vyuzijeme problem omezeneho bufferu. Prostor pro buffer i ukazatele jsou definovany jako:

	var buffer: shared record
			pool: array (0..n-1) of polozka;
			citac, in, out : integer;
		    end;

• Producent ulozi do bufferu hodnotu v polozce nova_hodnota nasledujici sekvenci prikazu:

	region buffer when citac < n
	do begin
		pool(in) := nova_hodnota;
		in := in + 1 mod n;
		citac := citac + 1;
	end;

• Prijemce odebere z bufferu polozku a ulozi ji do promenne prijata_hodnota nasledujici 
  sekvenci prikazu:
  

	region buffer when citac > 0
	do begin
		prijata_hodnota := pool(out);
		out := out + 1 mod n;
		citac := citac - 1;
	end;

• Ukazme si nyni moznou implementaci kriticke oblasti. S kazdou sdilenou promennou jsou asociovany nasledujici promenne:

	var vzajed, prvni_cekani, druhe_cekani : semafor;
	    prvni_citac, druhy_citac : integer;

• Semafor vzajed je na pocatku inicializovan do 1, prvni_cekani a druhe_cekani do 0, stejne jako celociselne promenne prvni_citac a druhy_citac.

• Vzajemne jedinecny pristup do kriticke sekce je rizen semaforem vzajed. Jestlize proces nemuze vstoupit do sve kriticke sekce, nebot logicka promenna B je false, proces ceka na semaforu prvni_cekani. Nezli je nastavena hodnota promenne B na true, je proces presunut na semafor druhe_cekani. V promennych prvni_citac a druhy_citac je sledovan pocet procesu cekajicich na semaforech prvni_cekani a druhe_cekani.

	cekej(vzajed);
	while not B do begin
		prvni_citac := prvni_citac + 1;
		if druhy_citac > 0
			then signal(druhe_cekani)
			else signal(vzajed);
		cekej(prvni_cekani);
		prvni_citac := prvni_citac - 1;
		druhy_citac := druhy_citac +1;
		if prvni_citac > 0
			then signal(prvni_cekani)
			else signal(druhe_cekani);
		cekej(druhe_cekani);
		druhy_citac := druhy_citac - 1;
	end;
	S;
	if prvni_citac > 0
		then signal(prvni_cekani)
			else if druhy_citac > 0
				then signal(druhe_cekani)
				else signal(vzajed);

• Kdyz proces opousti kritickou sekci, mohl zmenit nejakou hodnotu v podmince B a umoznit tak jinemu procesu ve vstupu do jeho kriticke sekce. Proto musime sledovat procesy cekajici na semaforech prvni_cekani a druhe_cekani (v tomto poradi) a u kazdeho testovat jeho podminku B. Muze se behem tohoto testovani stat, ze nove overena hodnota podminky je true. V tom pripade proces vstupuje do sve kriticke sekce. Jinak musi proces nadale cekat na semaforech prvni_cekani a druhe_cekani. Pro kazdou sdilenou promennou x muze byt tedy prikaz

  	region x when B do S;
  

  implementovan tak, jak ukazuje Vypis 2. Pripomenme, ze tato implementace vyzaduje aktualizaci hodnoty promenne B vzdy, kdyz nejaky proces opousti svou kritickou sekci. Jestlize nektere procesy prilis dlouho cekaji na nastaveni sve podminky do hodnoty true, muze vest neustale vyhodnocovani jejich podminky ke zpomaleni systemu a existuji ruzne optimalizacni metody, ktere lze uzit k reseni tohoto problemu.

Zpet Obsah Vpred