Programowanie współbieżne

Wzajemne wykluczanie

Prowadzący: dr inż. Dariusz Pierzchała

[e-mail]

Mechanizm wzajemnego wykluczania

2

Model wzajemnych oddziaływań

procesów



Komunikacja (kooperacja):



niezbędna do uporządkowanej (synchronizowanej) współpracy;



dzieli się na: synchroniczną i asynchroniczną;



często realizowana poprzez wspólną pamięć – kwalifikowana
bywa do współzawodnictwa – wymaga wówczas wzajemnego
wykluczania procesów będących stronami w komunikacji;



Współzawodnictwo:



dwa procesy ubiegają się o ten sam zasób – np.
obliczeniowy, dostęp do pewnej komórki pamięci lub
kanału komunikacyjnego;



współzawodnictwo zawsze wymaga synchronizacji, w
tym wzajemnego wykluczania;

Mechanizm wzajemnego wykluczania

3

Współzawodnictwo – przykład 1/2



Bankomaty połączone z serwerem w banku (K – stan konta
klienta);



Algorytm (uproszczony) działania systemu:



Sprawdź, czy kwota wypłaty nie przekracza kwoty na
rachunku.



Jeśli NIE, wykonaj wypłatę i zmniejsz kwotę K o wypłatę;



Jeśli TAK, odmów wykonania operacji wypłaty;



Jakie problemy mogą wystąpić?



Jeden proces sprawdza stan konta (read);



Inny proces może w tym samym czasie zmienić stan
(write) obsługując wpłatę lub wypłatę;

Mechanizm wzajemnego wykluczania

4

Współzawodnictwo – przykład 2/2



Stan konta może zmieniać się następująco (w EUR):

Bankomat / proces nr
1

Bankomat / proces nr
2

Stan konta
1

Stan konta
2

Stan konta
3

1000

2000

3000

read (1) : 1000

1000

2000

3000

write (1) = 1000-

100

900

2000

3000

read (3) : 3000

900

2000

3000

write (3) = 3000-

200

900

2000

2800

read (2) : 2000

900

2000

2800

read (2) : 2000

900

2000

2800

write (2) =

2000+200

900

2200

2800

write (2) =

2000+100

900

2100

2800

900

2100

2800

Na koncie nr 2 błąd (brakuje)200 EUR –
dlaczego?

czas

Mechanizm wzajemnego wykluczania

5

Problem wzajemnego wykluczania



Problem wzajemnego wykluczania można zdefiniować jako:



Zsynchronizować N procesów, z których każdy,

w pętli

realizuje:

o

sekcję lokalną

o

potem protokół wstępny (często oparty na pętli
aktywnego czekania)

o

następnie działania na części współdzielonej,

o

i kończy iterację protokołem końcowym;



Należy zapewnić spełnienie zasad:



W sekcji krytycznej może przebywać co najwyżej jeden
proces jednocześnie (bezpieczeństwo);



Każdy proces, który chce wykonać sekcję krytyczną, w
skończonym czasie powinien do niej wejść (żywotność) - nie
wystąpi zagłodzenie.

Mechanizm wzajemnego wykluczania

6

Problem wzajemnego wykluczania



Schemat pracy procesów współbieżnych wyglądać może
następująco:



begin



loop



begin

• sekcja lokalna;
• protokół_wstępny;
•

sekcja_krytyczna;

• protokół_końcowy;



end loop;



end;

loop

end loop

sekcja lokalna

protokół wstępny

sekcja krytyczna

protokół końcowy

Mechanizm wzajemnego wykluczania

7

Problem wzajemnego wykluczania



Dalsze założenia w rozwiązaniu wzajemnego wykluczania:



Procesy muszą być traktowane jako równoważne (brak priorytetów);



Wynik działania programu współbieżnego nie może zależeć od
przebiegu przeplotu (przełączania procesów);



Wynik działania musi być poprawny dla wszystkich możliwych
przeplotów;



Jeśli nie będzie rywalizacji o wejście do sekcji krytycznej, to proces,
który zażąda wejścia, zrealizuje to wejście;



Program musi zawierać własność wzajemnego wykluczania, tzn.
instrukcje z sekcji krytycznych dwu lub więcej procesów nie mogą
się wykonywać jednocześnie;



Rola protokołów jest następująca:



wstępnego: przy wejściu do sekcji krytycznej proces sprawdza, czy
może wejść do sekcji;



końcowego: po wyjściu z sekcji informuje inne procesy, iż opuścił
sekcję krytyczną, zatem inny proces może wejść do sekcji;

Mechanizm wzajemnego wykluczania

8

Algorytm – schemat

Proces 1

Proces 2

loop

end loop

sekcja lokalna

protokół wstępny

sekcja krytyczna

protokół końcowy

loop

end loop

sekcja lokalna

protokół wstępny

sekcja krytyczna

protokół końcowy

Czynności protokołu końcowego wpływają na warunki sprawdzane w protokole wstępnym

Mechanizm wzajemnego wykluczania

9

Algorytmy naiwne

Mechanizm wzajemnego wykluczania

10

Alg. naiwny - Pierwsza próba

1: Czyja_kolej:Integer := 1;

2: proces P1 is
3: begin
4:

loop

5:

Sekcja_lokalna_1;

6:

loop

7:

if Czyja_kolej = 1 then exit;

8:

end loop;

9:

Sekcja_krytyczna;

10:

Czyja_kolej := 2;

11:

end loop;

12: end P1;

13: proces P2 is
14: begin
15:

loop

16:

Sekcja_lokalna_2;

17:

loop

18:

if Czyja_kolej = 2 then exit;

19:

end loop;

20:

Sekcja_krytyczna;

21:

Czyja_kolej := 1;

22:

end loop;

23: end P2;

Definiujemy jedna zmienną sterującą, wskazującą czyja jest kolej na sekcję.

Uwaga: tu występuje „aktywne oczekiwanie”!

Protokół wstępny:

linie 6-8, 17-19

Protokół końcowy: linie 10, 21

Mechanizm wzajemnego wykluczania

11

Pierwsza próba – opis 1/2

1. To rozwiązanie zapewnia wzajemne wykluczanie -

nigdy dwa procesy nie znajdą się jednocześnie w sekcji

krytycznej. Zapewnia to zmienna czyja_kolej określająca

uprawnionego do wejścia do sekcji krytycznej.
2. To rozwiązanie nigdy nie doprowadzi do

zakleszczenia - aby w programie wystąpiło zakleszczenie

procesy muszą nieskończenie długo testować wartość

zmiennej czyja_kolej, przy czym warunek musi być stale

fałszywy.
3. W tym rozwiązaniu nie może wystąpić zagłodzenie -

jeden proces musi nieskończenie wiele razy wchodzić do sekcji

krytycznej, podczas gdy drugi wciąż wykonuje swój protokół

wstępny.
4. Niestety w przypadku braku współzawodnictwa to

rozwiązanie może zawieść - gdy jeden z procesów utknie w

swojej sekcji lokalnej, to drugi proces może wejść do sekcji

krytycznej co najwyżej raz.
Zatem Pkt. 4 wyklucza przyjęcie tego rozwiązania.

Mechanizm wzajemnego wykluczania

12

Pierwsza próba – opis 2/2

5. Obydwa procesy są zmuszane do pracy w tym samym

tempie:
- gdy jeden z procesów musi wchodzić bardzo często do sekcji

krytycznej (np. co 1 sekundę) a drugi bardzo rzadko (np. raz na

dobę), to takie rozwiązanie nie może być przyjęte;
- naprzemienne przekazywanie prawa wejścia do sekcji krytycznej w

takim przypadku wyklucza zadawalającą pracę programu;
- podobnie może być w przypadku, gdy dwa procesy są wykonywane

na różnych procesorach. Wtedy nawet zakładając jednakową liczbę

instrukcji w każdym procesie, może dojść do sytuacji kiedy znaczne

różnice obciążenia każdego z procesorów będą wypaczać działanie

programu. Proces na mocniej obciążonym procesorze będzie blokował

pracę procesu z mniej obciążonego procesora.
Pkt. 5 wyklucza przyjęcie tego rozwiązania.

6. Technika programowania polegająca na jawnym przekazywaniu

prawa do wykonywania się nazywana jest współprogramowaniem.

Mechanizm wzajemnego wykluczania

13

Alg. naiwny - Pierwsza próba

1 public class Naiwny implements Runnable {
2 volatile static int nextThd = 0;
3 private int thdNum;
4 public void run ( ) {
5

thdNum = ThreadID.get ( ) ;

6

while ( true ) {

7

// s e k c j a l o k a l n a

8

//

9

// TO DO

10

//

11

// protokół wstępny

12

while ( nextThd != thdNum) {

13

Thread.yield( ) ;

14

}

15

// s e k c j a k r y t y c z n a

16

//

17

//

18

// TO DO

19

//

20

//

21

// protokół końcowy

22

nextThd = 1 - thdNum;

23

}

24 }

Mechanizm wzajemnego wykluczania

14

Alg. naiwny - Druga próba

1: K1, K2 :Integer := 1;

2: proces P1 is
3: begin
4: loop
5: Sekcja_lokalna_1;
6: loop
7: if K2 = 1 then exit;
8: end loop;
9: K1 := 0;
10: Sekcja_krytyczna;
11: K1 := 1;
12: end loop;
13: end P1;

14: proces P2 is
15: begin
16:

loop

17:

Sekcja_lokalna_2;

18:

loop

19:

if K1 = 1 then exit;

20:

end loop;

21:

K2 := 0;

22:

Sekcja_krytyczna;

23:

K2 := 1;

24:

end loop;

25: end P2;

Druga próba

Zamiast testować i ustawiać jedna zmienną sterującą (co prowadzi do
potencjalnej blokady), procesy zostają uzupełnione o własne zmienne
sterujące;

To rozwiązanie jest tak fatalne, że nie ma nawet własności wzajemnego wykluczania

Mechanizm wzajemnego wykluczania

15

Druga próba - opis

1. Proces Pi sygnalizuje potrzebę wejścia do sekcji krytycznej nadając zmiennej Ki wartość
0.
2. To rozwiązanie jest tak fatalne, że nie ma nawet własności wzajemnego
wykluczania. Uwaga! Własność wzajemnego wykluczania jest podstawową i najłatwiejszą
do wykazania cechą programowania współbieżnego i od niej należy rozpoczynać analizę
każdego rozwiązania.
3. W tym rozwiązaniu dwa procesy mogą być jednocześnie w sekcji krytycznej.
Przykładowy ciąg instrukcji udowadnia taką możliwość:
a) P1 sprawdza wartość K2 i stwierdza, że K2 = 1.
b) P2 sprawdza wartość K1 i stwierdza, że K1 = 1.
c) P1 ustawia wartość K1 na 0.
d) P2 ustawia wartość K2 na 0.
e) P1 wchodzi do sekcji krytycznej.
f) P2 wchodzi do sekcji krytycznej.
4. W celu pokazania, że własność wzajemnego wykluczania nie zachodzi wystarczy podać
jeden przeplot instrukcji (tzw. killer’ski przeplot).

5. Wada tego rozwiązania polega także na tym, że proces po wyjściu z pętli (protokołu
wstępnego) nie może być powstrzymany przed wejściem do sekcji krytycznej.

6. Protokół wstępny: linie 6-8, 18-20
Protokół końcowy: linie 11, 23

Patrz – następny slajd

Mechanizm wzajemnego wykluczania

16

Alg. naiwny - Druga próba

1: K1, K2 :Integer := 1;

2: proces P1 is
3: begin
4: loop
5: Sekcja_lokalna_1;
6: loop
7: if K2 = 1 then exit;
8: end loop;
9: K1 := 0;
10: Sekcja_krytyczna;
11: K1 := 1;
12: end loop;
13: end P1;

14: proces P2 is
15: begin
16:

loop

17:

Sekcja_lokalna_2;

18:

loop

19:

if K1 = 1 then exit;

20:

end loop;

21:

K2 := 0;

22:

Sekcja_krytyczna;

23:

K2 := 1;

24:

end loop;

25: end P2;

6-8: P1 sprawdza wartość K2 i stwierdza, że K2 =
1.
18-20: P2 sprawdza wartość K1 i stwierdza, że K1 =
1.
9: P1 ustawia wartość K1 na 0.
21: P2 ustawia wartość K2 na 0.
10: P1 wchodzi do sekcji krytycznej.

22: P2 wchodzi do sekcji krytycznej.

Mechanizm wzajemnego wykluczania

17

Alg. naiwny – Trzecia próba

1: K1, K2 :Integer := 1;

2: proces P1 is
3: begin
4:

loop

5:

Sekcja_lokalna_1;

6:

K1 := 0;

7:

loop

8:

if K2 = 1 then exit;

9:

end loop;

10:

Sekcja_krytyczna;

11:

K1 := 1;

12:

end loop;

13: end P1;

14: proces P2 is
15: begin
16:

loop

17:

Sekcja_lokalna_2;

18:

K2 := 0;

19:

loop

20:

if K1 = 1 then exit;

21:

end loop;

22:

Sekcja_krytyczna;

23:

K2 := 1;

24:

end loop;

25: end P2;

Trzecia próba

Uznajemy praktycznie pętlę za część sekcji krytycznej i ustawianie zmiennej
przesuwamy przed petlę;

Mechanizm wzajemnego wykluczania

18

Trzecia próba - opis

1. Proces Pi sygnalizuje potrzebę wejścia do sekcji krytycznej nadając zmiennej Ki
wartość 0. Przypisanie odpowiedniej zmiennej wartości zero sygnalizuje nie tylko chęć
wejścia do sekcji krytycznej, ale oznacza także naleganie na przyznanie tego prawa, co
niestety może doprowadzić do blokady.

2. To rozwiązanie zapewnia własność wzajemnego wykluczania - czyli nie zdarzy
się sytuacja, że dwa procesy będą jednocześnie w sekcji krytycznej.

3. Niestety już po kilku instrukcjach może nastąpić zakleszczenie. Przykładowy
ciąg instrukcji udowadnia taką możliwość:
a) P1 nadaje zmiennej K1 wartość 0.
b) P2 nadaje zmiennej K2 wartość 0.
c) P1 sprawdza wartość K2 i pozostaje w pętli.
d) P2 sprawdza wartość K1 i pozostaje w pętli.

4. Protokół wstępny: linie 6-9, 18-21
Protokół końcowy: linie 11, 23

P1

P2

„R1”

„R2”

linie 8 i 20

K1 := 0

K2 := 0

Patrz – następny slajd

Mechanizm wzajemnego wykluczania

19

Alg. naiwny – Trzecia próba

1: K1, K2 :Integer := 1;

2: proces P1 is
3: begin
4:

loop

5:

Sekcja_lokalna_1;

6:

K1 := 0;

7:

loop

8:

if K2 = 1 then exit;

9:

end loop;

10:

Sekcja_krytyczna;

11:

K1 := 1;

12:

end loop;

13: end P1;

14: proces P2 is
15: begin
16:

loop

17:

Sekcja_lokalna_2;

18:

K2 := 0;

19:

loop

20:

if K1 = 1 then exit;

21:

end loop;

22:

Sekcja_krytyczna;

23:

K2 := 1;

24:

end loop;

25: end P2;

6: P1 nadaje zmiennej K1 wartość 0.
18: P2 nadaje zmiennej K2 wartość 0.
7-9: P1 sprawdza wartość K2 i pozostaje w pętli.

19-21: P2 sprawdza wartość K1 i pozostaje w pętli.

Mechanizm wzajemnego wykluczania

20

Alg. naiwny – Czwarta próba

1: K1, K2 :Integer := 1;

2: proces P1 is
3: begin
4: loop
5: Sekcja_lokalna_1;
6: K1 := 0;
7: loop
8: if K2 = 1 then exit;
9: K1 := 1;
10: K1 := 0;
11: end loop;
12: Sekcja_krytyczna;
13: K1 := 1;
14: end loop;
15: end P1;

16: proces P2 is
17: begin
18:

loop

19:

Sekcja_lokalna_2;

20:

K2 := 0;

21:

loop

22:

if K1 = 1 then exit;

23:

K2 := 1;

24:

K2 := 0;

25:

end loop;

26:

Sekcja_krytyczna;

27:

K2 := 1;

28:

end loop;

29: end P2;

Czwarta próba

Naleganie na przyznanie prawa wejścia do sekcji może powodować blokadę;
Algorytm działania procesów modyfikujemy tak, aby potrafiłu rezygnować z
chęci wejścia do sekcji krytycznej w przypadku wykrycia współzawodnictwa;

Ten ciąg przypisań ma sens tylko w programie współbieżnym (nie w sekwencyjnym)

Mechanizm wzajemnego wykluczania

21

Czwarta próba - opis (1/3)

1. Proces Pi sygnalizuje potrzebę wejścia do sekcji krytycznej nadając zmiennej Ki wartość 0.

2. Wprowadzono wymaganie, aby proces po wykryciu współzawodnictwa o wejście do sekcji
krytycznej rezygnował z tego prawa na rzecz innego procesu.
Świadczy o tym ciąg instrukcji typu: K1 := 1; K1 := 0; tj. linie 9 i 10 oraz przez analogię linie
23 i 24.

3. To rozwiązanie zapewnia własność wzajemnego wykluczania - czyli nie zdarzy się
sytuacja, że dwa procesy będą jednocześnie w sekcji krytycznej.
4. Niestety może dojść do zagłodzenia procesu. Przykładowy ciąg instrukcji udowadnia
taką możliwość:
a) P1 przypisuje K1 wartość 0.
b) P2 przypisuje K2 wartość 0.
c) P2 sprawdza wartość K1 i przypisuje K2 wartość 1.
d) P1 wykonuje pełny obrót pętli:
- sprawdza wartość K2,
- wchodzi do sekcji krytycznej,
- przywraca wartość 1 zmiennej K1,
- wykonuje sekcję lokalną,
- przypisuje zmiennej K1 wartość 0.
e) P2 przypisuje zmiennej K2 wartość 0.
f) Jeżeli przejdziemy do kroku c) to mamy zagłodzenie procesu P2.

Patrz – następny slajd

Mechanizm wzajemnego wykluczania

22

Czwarta próba - opis (2/3)

1: K1, K2 :Integer := 1;

2: proces P1 is
3: begin
4: loop
5: Sekcja_lokalna_1;
6: K1 := 0;
7: loop
8: if K2 = 1 then exit;
9: K1 := 1;
10: K1 := 0;
11: end loop;
12: Sekcja_krytyczna;
13: K1 := 1;
14: end loop;
15: end P1;

16: proces P2 is
17: begin
18:

loop

19:

Sekcja_lokalna_2;

20:

K2 := 0;

21:

loop

22:

if K1 = 1 then exit;

23:

K2 := 1;

24:

K2 := 0;

25:

end loop;

26:

Sekcja_krytyczna;

27:

K2 := 1;

28:

end loop;

29: end P2;

Przykład przeplotu prowadzącego do zagłodzenia procesu P2:

6, 20, 8, 22, 9, 23, 10, 8, 12, 13, 5, 6, 24,

8, 22, 9, 23, 10, 8, 12, 13, 5, 6, 24,
8, 22, 9, 23, 10, 8, 12, 13, 5, 6, 24, itd.

Warto zwrócić uwagę na powtarzającą się linię 5 - sekcja krytyczna wielokrotnie
niezajęta!

Mechanizm wzajemnego wykluczania

23

Czwarta próba - opis (3/3)

5. W tym rozwiązaniu może wystąpić półblokada (inaczej livelock).
W przypadku zakleszczenia nie ma żadnego możliwego ciągu wykonań instrukcji, który
by doprowadził do wejścia do sekcji krytycznej. W przypadku półblokady możliwe są
obliczenia kończące się sukcesem, ale można też podać jeden lub więcej ciągów wykonań
instrukcji, w których żaden proces nigdy nie wejdzie do sekcji krytycznej.
Przykładowy ciąg instrukcji udowadnia taką możliwość. Zakładamy, że instrukcje obydwu
procesów występują naprzemiennie.
a) P1 przypisuje K1 wartość 0.
b) P2 przypisuje K2 wartość 0.
c) P1 bada wartość K2 i pozostaje w pętli.
d) P2 bada wartość K1 i pozostaje w pętli.
e) P1 przywraca zmiennej K1 wartość 1.
f) P2 przywraca zmiennej K2 wartość 1.
g) P1 przypisuje K1 wartość 0.
h) P2 przypisuje K2 wartość 0.
i) P1 bada wartość K2 i pozostaje w pętli.
j) P2 bada wartość K1 i pozostaje w pętli.

6. Protokół wstępny: linie 6-11, 20-25
Protokół końcowy: linie 13, 27

Mechanizm wzajemnego wykluczania

24

Algorytm Dekkera

Mechanizm wzajemnego wykluczania

25

Alg. Dekkera (poprawny)

1: K1, K2 :Integer := 1;

2: Czyja_kolej: Integer := 1;

3: proces P1 is

4: begin

5:

loop

6:

Sekcja_lokalna_1;

7:

K1 := 0;

8:

loop

9:

if K2 = 1 then exit;

10:

if Czyja_kolej = 2 then

11:

K1 := 1;

12:

loop

13:

if Czyja_kolej = 1

then exit;

14:

end loop;

15:

K1 := 0;

16:

end if;

17:

end loop;

18:

Sekcja_krytyczna;

19:

K1 := 1;

20:

Czyja_kolej := 2;

21:

end loop;

22: end P1;

23: proces P2 is

24: begin

25:

loop

26:

Sekcja_lokalna_2;

27:

K2 := 0;

28:

loop

29:

if K1 = 1 then exit;

30:

if Czyja_kolej = 1 then

31:

K2 := 1;

32:

loop

33:

if Czyja_kolej = 2

then exit;

34:

end loop;

35:

K2 := 0;

36:

end if;

37:

end loop;

38:

Sekcja_krytyczna;

39:

K2 := 1;

40:

Czyja_kolej := 1;

41:

end loop;

42: end P2;

Mechanizm wzajemnego wykluczania

26

Alg. Dekkera (poprawny) – opis 1/2

1. Algorytm Dekkera (poprawny) jest połączeniem pierwszego i
czwartego rozwiązania.

2. W pierwszym podejściu jawnie przekazywano prawo wejścia do sekcji
krytycznej, co przy braku współzawodnictwa wykluczało to rozwiązanie.

3. W czwartym podejściu każdy proces miał własną zmienną co
zapobiegało brakowi współzawodnictwa.
Jednak, gdy ono wystąpiło to procesy albo głodziły siebie nawzajem,
albo półblokowały.

4. Algorytm Dekkera jest podobny do rozwiązania proponowanego w
czwartym podejściu lecz prawo do nalegania jest jawnie przekazywane
między procesami.

5. Zmienne Ki zapewniają wzajemne wykluczanie. Zmienna
czyja_kolej służy do przekazywania prawa nalegania.

Mechanizm wzajemnego wykluczania

27

Alg. Dekkera (poprawny) – opis 2/2

6. Każdy proces sprawdza, czy teraz jest jego kolej na naleganie. Jeśli
nie, to przywraca początkową wartość zmiennej (K1 na 1 dla P1, K2
na 2 dla P2), po czym cierpliwie czeka na swoją kolej.

7. Jeżeli proces wejdzie do protokołu wstępnego, to po pewnym
czasie wejdzie do sekcji krytycznej.

8. Żaden proces nie może być zagłodzony i przy braku
współzawodnictwa proces może natychmiast wejść do swojej sekcji
krytycznej.

9. Protokół wstępny: linie 7-17, 27-37
Protokół końcowy: linie 19-20, 39-40

Mechanizm wzajemnego wykluczania

28

Alg. Dekkera (poprawny) – przykład

1/2

1 // Przykład alg. Dekkera w Java

2

3 public class JDekker implements Runnable {

4

5 static AtomicIntegerArray kSter = new AtomicIntegerArray( 2 ) ;

6 static volatile int nextThd = 0 ;

7 int thdNum;

8

9 static {

10

kSter.set ( 0 , 1) ;

11

kSter.set ( 1 , 1) ;

12 }

13

14 public void run ( ) {

15

16

thdNum = ThreadID.get ( ) ;

17

18

while ( true ) {

19

20

// s e k c j a l o k a l n a

21

// TO DO

22

//

23

//

24

// END TO DO

25

26

// protokół wstępny

27

kSter.set(thdNum, 1) ;

Mechanizm wzajemnego wykluczania

29

Alg. Dekkera (poprawny) – przykład

2/2

29

while ( kSter.get (1 - thdNum) == 1) {

30

if ( nextThd != thdNum) {

31

kSter.set (thdNum, 0) ;

32

while (nextThd != thdNum) {

33

Thread.yield ( ) ;

34

}

35

kSter.set(thdNum, 1) ;

36

}

37

}

38

39

// s e k c j a k r y t y c z n a

41

// TO DO

42

//

43

//

44

// END TO DO

46

47

// protokół końcowy

48

nextThd = 1 - thdNum;

49

kSter.set (thdNum, 0) ;

50 }

51 }

52

53 public JDekker ( ) {

54 }

55

56 public static void main ( String [ ] args ) {

57

58

new Thread (new JDekker ( ) , "A" ).start ( ) ;

59

new Thread (new JDekker ( ) , "B" ).start ( ) ;

60 }

61 }

Mechanizm wzajemnego wykluczania

30

Inne podejścia i algorytmy:

-scentralizowane

-rozproszone

-oparte na żetonie

Mechanizm wzajemnego wykluczania

31

Algorytm centralnego koordynatora



Podejście scentralizowane:



Wymagany jest dodatkowy proces koordynujący dostęp do
sekcji krytycznej;



Własności algorytmu:



Jest sprawiedliwy w sensie FIFO (zgodnie z kolejnością
żądań);



Spełnia własności:



bezpieczeństwa (wyklucza możliwość zajęcia sekcji przez
więcej niż jeden proces);



oraz żywotności (każdy z procesów będzie mógł kiedyś
uruchomić swoją sekcję krytyczną) - nie powoduje zagłodzenia;



Jest prosty w implementacji – wejście/wyjście do/z sekcji
krytycznej wymaga wymiany trzech wiadomości;



Wada podejścia: awaria scentralizowanego koordynatora
uniemożliwia poprawne wykluczanie;

Mechanizm wzajemnego wykluczania

32

Algorytm centralnego koordynatora

- ilustracja

Mechanizm wzajemnego wykluczania

33

Algorytm rozproszony Lamporta



Wykorzystuje mechanizm synchronizacji zegarów Lamporta;



R

i

- zbiór żądań procesu P

i

(zbiór procesów, od których

wymagane są pozwolenia zajęcia sekcji krytycznej);



Każdy proces kolejkę żądań sekcji krytycznej uszeregowanych
według znaczników czasowych;



Każdy proces P

i

przechowuje kolejkę żądań, który zawiera żądania

wejścia do sekcji krytycznej uszeregowane według ich znaczników
czasowych;



Do zajęcia/zwolnienia sekcji potrzeba co najmniej 3 komunikaty (ich
liczba zależy od liczby procesów)



Założenie: komunikaty przesyłane pomiędzy każdą parą procesów
przechowywane są wg porządku FIFO (ang. First In, First Out);



Ulepszoną wersją algorytmu Lamporta jest algorytm Ricarta i Agrawali



odbywa się bez wiadomości ZWOLNIJ (sekcję krytyczną)
poprzez połączenie z wiadomościami typu ODPOWIEDŹ;

Mechanizm wzajemnego wykluczania

34

Algorytm rozproszony Lamporta



Proces P

i

żąda dostępu do sekcji krytycznej



wysyła żądanie ze znacznikiem czasu (@t(i),i) do wszystkich
procesów ze zbioru R

i

;



dodaje żądanie lokalnie do kolejki żądań;



każdy inny proces P

j

odsyła odpowiedź ze znacznikiem czasu i

umieszcza P

i

w swojej kolejce żądań;



Proces P

i

wejdzie do sekcji krytycznej, jeśli:



odpowiedzi od wszystkich procesów P

j

mają znaczniki czasowe

(@t(j),i) większe od znacznika żądania:



żądanie jest na początku własnej kolejki procesu P

i

;



Zwolnienie sekcji krytycznej wymaga:



wysłania wiadomości ZWOLNIJ do innych procesów, które
skojarzone z tym żądanie usuwają ze swoich kolejek (inne
żądania w kolejkach przesuwają się o 1 miejsce do przodu);



usunięcia żądania z początku własnej kolejki;

Mechanizm wzajemnego wykluczania

35

Algorytm Lamporta - ilustracja

żądanie dostępu do sekcji krytycznej
odpowiedź na żądanie dostępu do sekcji krytycznej
zwolnienie sekcji krytyczne

P

1

P

2

P

3

@1, 2

@1, 2

@1, 2

@1, 2

@1, 2

@2, 1

@2, 1

@2, 1

@2, 1

P

2

wchodzi

do sekcji
krytycznej

@2, 1

@2, 1

@2, 1

P

2

wychodzi
do sekcji
krytycznej

Mechanizm wzajemnego wykluczania

36

Algorytm Suzuki-Kasami - oparty na

żetonie



W algorytmie Suzuki-Kasami wykorzystywany jest żeton:



o żeton ubiegają się procesy chcące wejść do sekcji krytycznej;



proces posiadający żeton może wchodzić do sekcji krytycznej:



ma wyłączność do czasu, gdy o żeton nie poprosi inny proces;



Żądania mają postać ŻĄDANIE(j, n): mówimy, że proces P

j

żąda n-

tego wykonania sekcji krytycznej;



RN

i

[1..N] jest tablicą utrzymywaną przez proces P

i

;



RN

i

[j] przechowuje największą liczbę porządkową otrzymaną

dotychczas w żądaniach od procesu P

j

;



Problemy w podejściu:



Czy są stare (przedawnione) żądania?



Który proces ma zaległe żądania?



ŻĄDANIE(j, n) otrzymane przez P

i

jest przedawnione jeżeli RN

i

[j]>n:



Po otrzymaniu przez Pi wiadomości ŻĄDANIE(j, n) następuje:



RNi[j] = max(RNi[j], n);

Mechanizm wzajemnego wykluczania

37

Algorytm Suzuki-Kasami - oparty na

żetonie



Kroki algorytmu:



Żądanie sekcji krytycznej



wysłanie przez proces żądania o żeton,



jeżeli go nie ma odesłanie wolnego żetonu;



Wejście do sekcji po otrzymaniu żetonu;



Zwalnianie sekcji krytycznej:



aktualizacja tablicy oraz kolejki żetonu:



każdy żeton składa się z kolejki żetonu Q i tablicy
żetonu LN;



Q jest kolejką procesów żądających;



LN jest tablicą o rozmiarze N, gdzie LN[j] to liczba
porządkowa ostatnio wykonanego żądania przez proces
P

j

;



wysłanie żetonu do następnego procesu w kolejce;

Mechanizm wzajemnego wykluczania

38

Algorytm Raymonda - oparty na

żetonie



Inne podejście zaproponował Raymond:



Używa struktury drzewiastej o węzłach zawierających procesy;



Korzeniem drzewa jest proces, który posiada żeton
pozwalający na wejście do sekcji krytycznej;



Każdy proces dysponuje zmienną wskazującą na kolejny proces
na ścieżce prowadzącej do korzenia drzewa;



Każdy proces przechowuje kolejkę żądań sąsiednich procesów,
które nie posiadały jeszcze żetonu;



Struktura zmienia się dynamicznie w zależności od posiadacza
żetonu;

Mechanizm wzajemnego wykluczania

39

Podsumowanie

Mechanizm wzajemnego wykluczania

40

Wnioski – zapowiedź następnych

spotkań



Oprócz Dekkera znane są następujące algorytmy:



Petersona



piekarniany



Hymana



Dijkstry



Lamporta;



W praktyce stosuje się wysokopoziomowe mechanizmy
synchronizacji:



semafory



regiony krytyczne



monitory



oraz mechanizmy synchronizacji i komunikacji



spotkania symetryczne i asymetryczne



przestrzenie krotek



potoki, komunikaty i kanały;