5. Synchronizace procesu

Kooperujici proces je proces, ktery muze ovlivnit nebo byt ovlivnen jinym procesem prave spustenym v systemu. Spolupracujici procesy mohou bud primo sdilet logicky adresovy prostor (jak kod tak i data) nebo mohou sdilet data pouze prostrednictvim sdilenych souboru. Konkurujici pristupy k datum mohou vest k jejich naruseni. Uvedeme ruzne mechanismy vedouci k usporadani pristupu spolupracujicich procesu k datum tak, aby zustala konzistentni.

5.1. Pozadi

Jiz jsme uvedli model systemu, ktery obsahuje mnozstvi spolupracujicich procesu, jez jsou spusteny asynchronne a mohou sdilet spolecna data. V kapitole 3.4. jsme ilustrovali tento model pomoci omezeneho bufferu (cyklickeho pole), ktery je pro OS typicky.
Vratme se k problemu omezeneho bufferu reseneho pomoci sdilene pameti. Je-li buffer velikosti n, dovoluje ulozit maximalne n-1 polozek soucasne. Tento nedostatek muzeme resit nekolika zpusoby. Jeden z nich je zavest promennou citac, jejiz hodnota se na pocatku definuje jako 0 a je inkrementovana pri kazdem pridani nove polozky do bufferu a dekrementovana pri polozky odebrani. Kod producenta a prijemce by potom vypadal nasledovne:
Producent -

		repeat
			{vytvor dalsi polozku do nova_hodnota}
			while citac = n do nic_nedelej;
			buffer(in) := nova_hodnota;
			in := in + 1 mod n;
			citac := citac + 1;
		until false;

Prijemce -

		repeat
			while citac = 0 do nic_nedelej;
			prijata_hodnota := buffer(out);
			out := out + 1 mod n;
			citac := citac - 1;
			{zpracuj prijatou polozku v prijata_hodnota}
		until false;

Jak prijemce, tak producent funguji spravne, jsou-li spusteni samostatne. K chybam muze dojit pobezi-li oba procesy soucasne. Necht je napr. hodnota promenne citac 5 a producent i prijemce soucasne bezi. V tom pripade muze byt zcela nahodne vysledna hodnota v promenne citac bud 4, 5 nebo 6! Spravna hodnota je vsak samozrejme jen 5 a ta by vznikla pokud by oba procesy bezely separovane.
Ukazme, jak k chybe muze dojit. Mozna implementace prirazeni citac := citac + 1 muze byt:
```
	registr1 := citac;
	registr1 := registr1 + 1;
	citac := registr1;
```
kde registr1 je lokalni registr CPU. Stejne tak prirazeni citac := citac - 1 muze byt implementovano jako:
```
	registr2 := citac;
	registr2 := registr2 - 1;
	citac := registr2;
```
kde registr2 je jiny lokalni registr CPU.
Registr1 i registr2 mohou byt fyzicky jeden registr (akumulator), i tehdy se vsak operace provedou spravne diky logice CPU a mechanismu preruseni.
Soucasne spusteni prikazu citac := citac + 1 a citac := citac - 1 je ekvivalentni s postupnym spoustenim jednotlivych prikazu nizsi urovne tak jak byly uvedeny v predem neurcenem poradi. Jedno z moznych prolozeni prikazu nizsi urovne muze byt:

T0	producent	spousti		registr1 := citac		{registr1 = 5}
T1	producent	spousti		registr1 := registr1 + 1	{registr1 = 6}
T2	prijemce	spousti		registr2 := citac		{registr2 = 5}
T3	prijemce	spousti		registr2 := registr2 - 1	{registr2 = 4}
T4	producent	spousti		citac := registr1		{citac = 6}
T5	prijemce	spousti		citac := registr2		{citac = 4}

Vysledkem teto sekvence prikazu je chybna hodnota citac = 4, ktera uvadi ze v bufferu jsou 4 polozky a ve skutecnosti je jich tam po provedeni obou operaci 5. V pripade opacneho poradi ve vykonavani prikazu v T4 a T5, vysledkem by byla opet chyba, tentokrat citac = 6.
K teto chybe jsme zakonite museli dospet, protoze jsme obema procesu povolili aby soucasne manipulovaly s promennou citac. Tato situace, kdy ruzne procesy pristupuji a meni sdilena data soucasne a vysledek jejich cinnosti zavisi na poradi v jakem jsou jejich jednotlive prikazy provadeny se nazyva soubeh (race condition).
Pro ochranu pred soubehem musime mit jistotu, ze pouze jeden proces v danem case muze menit promennou citac. K tomu je nutna synchronizace obou procesu.

5.2. Problem kriticke sekce

Uvazujme system obsahujici n procesu {P0, P1, ..., Pn-1}. Kazdy proces ma cast kodu zvanou kriticka sekce, ve ktere muze menit spolecne promenne, updatovat tabulky, zapisovat do souboru apod. Hlavni myslenka je, ze pokud proces spousti svou kritickou sekci, nesmi zadny jiny proces mit moznost spustit ji take. Spousteni kritickych sekci procesu je vzajemne jedinecne v case (mutually exlusive in time). Problemem kriticke sekce je vytvorit protokol, ktery procesum umozni spolupracovat. Kazdy proces musi mit pravo provest svou kritickou sekci. Cast kodu implementujici tento dotaz se nazyva vstupni (entry) sekce. Kriticka sekce pak muze byt ukoncena ukoncovaci (exit) sekci. Zbyvajici kod se nekdy nazyva zbyvajici (remainder) sekce.

	repeat

		vstupni sekce

		kriticka sekce

		ukoncovaci sekce

		zbyvajici sekce

	until false

Reseni problemu kriticke sekce musi zohlednovat nasledujici 3 pozadavky:

vzajemnou jedinecnost (mutual exclusion): Jestlize proces Pi vykonava svou kritickou sekci, zadny jiny proces ji vykonavat nesmi.
progress: Jestlize u zadneho procesu neprobiha jeho kriticka sekce a existuji nejake procesy, ktere chteji svou kritickou sekci spustit, pak pouze ty procesy, ktere vykonavaji zbyvajici sekci se mohou ucastnit rozhodnuti ktera kriticka sekce ktereho procesu bude spustena a tento vyber nesmi byt neomezene odlozen.
omezene cekani (bounded waiting): Musi existovat omezeni v poctu casovych kvant mezi odeslanim pozadavku na vykon kriticke sekce procesem a umoznenim tohoto vykonu.

V nasledujicich kapitolach ukazeme reseni problemu kriticke sekce, ktera zohlednuji vyse uvedene vlastnosti.

5.2.1. Reseni pro dva procesy

V teto kapitole zuzime svoji pozornost na algoritmy aplikovatelne pouze pro dva procesy v case. Procesy budou oznaceny P0 a P1. V obecnem oznaceni procesu uzijeme Pi a Pj, tzn. j = 1 - i.

Algoritmus 1

Prvni pristup spociva ve sdilene celociselne promenne otacka, ktera bude moci nabyvat hodnot pouze 0 a 1. Jestlize otacka = i, potom proces Pi muze spoustet svou kritickou sekci, jak ukazuje nasledujici obrazek.

	repeat
		while otacka <> i do nic_nedelej;
		
		kriticka sekce

		otacka := j;

		zbyvajici sekce
	
	until false;

Obr. 52 Struktura procesu Pi v algoritmu 1

Toto reseni zajistuje, ze pouze jeden proces ve stejne dobe muze mit spustenu kritickou sekci. Je-li otacka = 0, proces P1 svou kritickou sekci spustit nemuze (viz. vyse).

Algoritmus 2

Problem algoritmu 1 je v tom, ze nedrzi dostatecne informace o stavu kazdeho procesu, rozhoduje pouze ktery proces muze spustit kritickou sekci. Reseni toho problemu tkvi v nahrazeni promenne otacka nasledujicim polem:

	var priznak: array (0..1) of
boolean;

Prvky pole priznak jsou na pocatku inicializovany do hodnoty false. Je-li P(i) = true, potom proces Pi je pripraven vstoupit do sve kriticke sekce. Strukturu tohoto algoritmu pro proces Pi ukazuje nasledujici obrazek:

	repeat

		priznak(i) := true;
		while priznak(j) do nic_nedelej;

		kriticka sekce

		priznak(i) := false;

		zbyvajici sekce

	until false;

Obr. 53 Struktura procesu Pi v algoritmu 2

Je-li proces Pi pripraven vstoupit do sve kriticke sekce, nastavi hodnotu priznak(i) na true a kontroluje priznak(j), zdali proces Pj neprovadi prave svou kritickou sekci. Pokud ano, Pi musi cekat az bude kriticka sekce procesu Pj dokoncena a potom muze spustit svou. Po jejim ukonceni nastavi hodnotu priznak(i) na false, cimz dava na vedomi, ze dalsi proces muze zacit se svou kritickou sekci (je-li takovy).
U tohoto algoritmu je pozadavek vzajemne jednoznacnosti vyresen, bohuzel narozdil od pozadavku progresivnosti. Pro ilustraci problemu uzijme nasledujici spoustenou sekvenci:
T0: ... P0 nastavuje priznak(0) = true
T1: ... P1 nastavuje priznak(1) = true
V tomto pripade nastava u obou procesu zacykleni v cyklu while.

Algoritmus 3

Kombinuje myslenku algoritmu 1 i 2 a vysledkem je reseni problemu kriticke sekce, ktere splnuje vsechny tri drive uvedene pozadavky. Oba procesy sdileji 2 promenne:

	var	priznak: array (0..1) of boolean;
		otacka: 0..1;

Na pocatku jsou hodnoty promennych inicializovany priznak(0) = priznak(1) = false, hodnota promenne otacka je nepodstatna. Strukturu algoritmu 3 pro proces Pi ukazuje nasledujici obrazek:

	repeat

		priznak(i) := true;
		otacka := j;
		while (priznak(j) and otacka = j) do 
			nic_nedelej;

		kriticka sekce

		priznak(i) := false;

		zbyvajici sekce

	until false;

Obr. 54 Struktura procesu Pi v algoritmu 3

Pred vstupem do kriticke sekce procesu Pi se nejprve nastavi promenna priznak(i) na hodnotu true a potom tvrdi, ze druhy proces nechce vstoupit do kriticke sekce (otacka := j). Jestlize oba procesy se pokousi soucasne spustit sve kriticke sekce, promenna otacka urci, ktery z obou procesu muze spustit svou kritickou sekci jako prvni. Rozhodne o tom posledni prirazeni hodnoty promenne otacka, predchazejici bude prepsano.
K implementaci bodu 1 (vzajemna jednoznacnost) je mozno podotknout, ze maji-li byt spusteny soucasne kriticke sekce obou procesu P0 i P1, je k tomu zapotrebi, aby priznak(0) = priznak(1) = true ovsem promenna otacka muze nabyt pouze hodnoty 1 nebo 0, ne vsak obou najednou, takze k soucasnemu spusteni kritickych sekci obou procesu dojit nemuze. Pro jeden z nich je splnena podminka cyklu while, budiz to proces Pi, a dostava se do cekaci smycky az do doby, kdy se priznak(j) nastavi do hodnoty false, k cemuz dojde az po ukonceni kriticke sekce procesu Pj.
K implementaci bodu 2 a 3 poznamenejme, ze procesu Pi muze byt zabraneno vstoupit do kriticke sekce pouze pokud je zadrzen cyklem while s podminkou priznak(j) je true a otacka = j a tento cyklus je jen jeden. Pokud se Pj nechysta vstoupit do kriticke sekce, je hodnota priznak(j) = false a Pi muze vstoupit do kriticke sekce. Pokud proces Pj nastavil priznak(j) = true, potom je otacka = j nebo otacka = i. Jestlize otacka = i potom proces Pi vstoupi do kriticke sekce. Jestlize otacka = j potom svou kritickou sekci vykona proces Pj. Presto po vykonani kriticke sekce procesem Pj bude hodnota priznak(j) nastavena na false, cimz je umozneno procesu Pi opustit cyklus while a vykonat svou kritickou sekci. Jestlize proces Pj nastavi hodnotu priznak(j) na true musi nastavit promennou otacka na i. Protoze Pi nemuze zmenit hodnotu promenne otacka zatimco je blokovan cyklem while, Pi vstoupi do kriticke sekce (progress) maximalne po jednom prubehu kriticke sekce procesu Pj (omezene cekani).

5.2.2. Reseni pro vice procesu

Algoritmus 3 resi korektne problem kriticke sekce pro 2 procesy. Nyni rozsirime reseni na n procesu. Tento algoritmus je znam pod nazvem bakery algorithm (pekaruv algoritmus) a je postaven na planovacim algoritmu, ktery se uziva v pekarstvi, skladech zmrzliny, masnach a vsude jinde, kde je treba z chaosu udelat poradek. Tento algoritmus byl vyvinut pro distribuovane prostredi, ale nyni se budeme venovat pouze tem jeho aspektum, ktere se tykaji prostredi koncentrovaneho.
Pri vstupu do obchodu dostane kazdy zakaznik cislo. Zakaznik s nejmensim cislem bude obsluhovan nejdrive. Pekaruv algoritmus nemuze garantovat, ze dva procesy neobdrzi stejne cislo. V tomto pripade je obslouzen drive algoritmus s mensim "jmenem", tzn. jestlize procesy Pi a Pj dostaly stejne cislo a i <j, potom Pi bude obslouzen nejdrive. Protoze jmena procesu jsou jedinecna a absolutne usporadana, algoritmus je kompletne deterministicky.
Datove struktury nutne pro implementaci pekarova algoritmu jsou:

	var	vyber: array (0..n-1) of boolean;
		cislo: array (0..n-1) of integer;

Na pocatku jsou obe pole inicializovana na hodnoty false a 0. Pro zjednoduseni zapisu algoritmu definujme nasledujici vztahy:
- (a,b) <(c,d) <=> ((a <c) or (a = c)) and (b <d).
- max(a0, a1, ..., an-1) = k <=> k>= ai pro i = 0, 1, ..., n-1.
Strukturu procesu Pi ukazuje Obr. 55.
Pro overeni spravnosti pekarova algoritmu musime nejprve ukazat, ze jestlize Pi provadi svou kritickou sekci a Pk (k <> i) ma prideleno cislo cislo(k), potom (cislo(i),i) < (cislo(k),k).
Vyse uvedene tvrzeni dokazuje splneni pozadavku vzajemne jednoznacnosti u pekarova algoritmu. Dale uvazujme, ze Pi vykonava svou kritickou sekci a Pk tou dobou chce spustit svou kritickou sekci. Kdyz Pk vstoupi do druheho cyklu while s tim, ze j = i, podminky jsou:
- cislo(i) <> 0
- (cislo(i),i) <(cislo(k),k).
Tyto podminky vedou cykleni procesu Pk v cyklu while dokud proces Pi bude provadet svou kritickou sekci.
Pro dolozeni vlastnosti progresivnosti a omezeneho cekani je vhodne si uvedomit, ze kazdy proces spousti svou kritickou sekci systemem first-come first-serverd.

	repeat

		vyber(i) := true;
		cislo(i) := max(cislo(0), ... cislo(n-1))+ 1;
		vyber(i) := false;
		for j = 0 to n - 1 do begin
			while vyber(j) do nic_nedelej;
			while cislo(j) <> 0 and (cislo(j),j) < (cislo(i),i) do 
				nic_nedelej;
		end;

		kriticka sekce
		
		cislo(i) := 0;

		zbyvajici sekce
	
	until false;

Obr. 55 Pekaruv algoritmus pro proces Pi

Zpet

Obsah

Vpred