T3
- Programowanie współbieżne
z
zastosowaniem semaforów
(ogólnych
i binarnych).
Część
II - Podstawowe
problemy
współbieżności
z
zastosowaniem semafora.
Problem producenta - konsumenta
Jeden z podstawowych problemów programowania współbieżnego.
Ten problem jest abstrakcją problemu synchronizacji i komunikacji.
Wyróżnia się dwa typy
procesów:
Producent - wykonując procedurę Produkujtworzy element danych, który musi być wysłany do konsumenta.
Konsument - po otrzymaniu elementu danych wykonuje obliczenia
w wewnętrznej procedurze Konsumuj.
Komunikacja między procesami
może mieć charakter synchroniczny lub asynchroniczny.
Najbardziej elastycznym
rozwiązaniem jest bufor - kolejka elementów danych
Bufor nieskończony
1:
B: array (0..nieskończoność) of Integer;
2:
We_ind, Wy_ind : Integer :=0;
3:
Elementy: Semafor :=0;
4:
task body Producent is
5:
I :Integer;
6:
begin
7:
loop
8:
Produkuj(I);
9:
B(We_ind) := I;
10:
We_ind := We_ind + 1;
11:
Signal(Elementy):
12:
end loop;
13:
end Producent;
14:
task body Konsument is
15:
I :Integer;
16:
begin
17:
loop
18:
Wait(Elementy);
19:
I := B(Wy_ind);
20:
Wy_ind := Wy_ind + 1;
21:
Konsumuj(I);
22:
end loop;
23:
end Konsument;
Bufor nieskończony - opis
1. Semafor
Elementy
jawnie zlicza liczbę elementów w buforze. Początkowo ma wartość
0, odzwierciedlającą fakt, że bufor jest początkowo pusty.
2.
Konsument wykonuje Wait(Elementy),
co powoduje jego wstrzymanie, gdy liczba elementów w buforze wynosi
zero.
3. Brak
pełnego protokołu wstępnego i końcowego. U producenta występuje
odpowiednik protokołu końcowego Signal(Elementy).
Natomiast konsument posiada jedynie protokół wstępny
Wait(Elementy).
Bufor cykliczny
1:
B: array (0..N-1) of Integer;
2:
We_ind, Wy_ind : Integer :=0;
3:
Elementy: Semafor :=0;
4:
Miejsca : Semafor :=N;
5:
task body Producent is
6:
I :Integer;
7:
begin
8:
loop
9:
Produkuj(I);
10:
Wait(Miejsca);
11:
B(We_ind) := I;
12:
We_ind := (We_ind + 1) mod N;
13:
Signal(Elementy):
14:
end loop;
15:
end Producent;
16:
task body Konsument is
17:
I :Integer;
18:
begin
19:
loop
20:
Wait(Elementy);
21:
I := B(Wy_ind);
22:
Wy_ind := (Wy_ind + 1) mod N;
23:
Signal(Miejsca);
24:
Konsumuj(I);
25:
end loop;
26:
end Konsument;
Bufor cykliczny - opis
1.
Praktyczny bufor musi być skończony.
2.
Konsument nie może pobrać elementu z pustego bufora oraz producent
nie może wstawiać do pełnego bufora.
3. Protokół
wstępny: 10, 20.
Protokółkońcowy:
13, 23.
Semafor Binarny
1:
B: array (0..N-1) of Integer;
2:
We_ind, Wy_ind, Licznik : Integer :=0;
3:
S: Semafor_binarny :=1;
4:
Niepusty, Niepełny: Semafor_binarny :=0;
5:
task body Producent is
6:
I :Integer;
7:
Licz_lokalny :Integer :=0;
8:
begin
9:
loop
10:
Produkuj(I);
11:
if Licz_lokalny = N then Wait(Niepełny);
12:
B(We_ind) := I;
13:
Wait(S);
14:
Licznik = Licznik + 1;
15:
Licz_lokalny := Licznik;
16:
Signal(S);
17:
if Licz_lokalny = 1 then Signal(Niepusty);
18:
We_ind := (We_ind + 1) mod N;
19:
end loop;
20:
end Producent;
21:
task body Konsument is
22:
I :Integer;
23:
Licz_lokalny :Integer :=0;
24:
begin
25:
loop
26:
if Licz_lokalny = 0 then Wait(Niepusty);
27:
I := B(Wy_ind);
28:
Wait(S);
29:
Licznik := Licznik - 1;
30:
Licz_lokalny := Licznik;
31:
Signal(S);
32:
if Licz_lokalny = N-1 then Signal(Niepełny);
33:
Wy_ind := (Wy_ind + 1) mod N;
34:
Konsumuj(I);
35:
end loop;
36:
end Konsument;
Semafor binarny - opis
1. Licznik
Licznik
służy do jawnego pamiętania liczby elementów w buforze. Semafor S
zabezpiecza tą zmienną globalną przed jednoczesnym dostępem przez
obydwa procesy.
2. Semafory
Niepusty
i Niepełny
są używane do wstrzymywania odpowiednio konsumenta i producenta.
3. Zmienne
Licz_lokalny
umożliwiają procesowi sprawdzenie , jaka była wartość zmiennej
Licz_lokalny
podczas jej ostatniej modyfikacji przez ten proces. Jest to konieczne
gdyż semafory mają pamięć, tzn. każdej operacji Signal
musi odpowiadać operacja Wait.
4. Protokół
wstępny: 13, 28.
Protokółkońcowy:
28, 31.
5. Semafory
Niepusty,
Niepełny
nie wyznaczają sekcji krytycznej.
Czytelnicy i pisarze
Wiele procesów współzawodniczy o dostęp do
sekcji krytycznej.
Dwie klasy procesów:
Czytelnicy
- procesy nie wykluczające się nawzajem.
Pisarze -
procesy wykluczające każdy inny proces.
Czytelnicy mogą jednocześnie znajdować się w
czytelni.
Pisarz zapisujący informację musi przebywać w
czytelni sam.
Problem jest abstrakcją współbieżnego dostępu
do bazy danych, kiedy wiele procesów może jednocześnie odczytywać
dane, ale proces zapisu wymaga wyłączności dostępu.
Możliwe rozwiązania
problemu
czytelników i pisarzy
Z
zagłodzeniem pisarzy:
Każdy
czytelnik, który zapragnie wejść do sekcji krytycznej, może to
zrobić, jeśli czytelnia jest pusta lub są w niej inni czytelnicy.
Każdy
pisarz może wejść do sekcji krytycznej dopiero, gdy czytelnia
jest pusta.
Z
zagłodzeniem czytelników:
Każdemu
pisarzowi, który chce wejść do sekcji krytycznej należy
umożliwić jak najszybsze wejście;
Czytelnik,
który zapragnie wejść do sekcji krytycznej, nie może tego
zrobić, jeśli jakikolwiek pisarz zgłosił chęć korzystania z
czytelni, nawet jeśli są w niej inni czytelnicy.
Rozwiązanie
poprawne:
Ustalenie
na przemian kolejności, w której pierwszeństwo mają poszczególne
grupy procesów.
Wpuszczanie
wszystkich oczekujących czytelników jednocześnie, a pisarzy
kolejno.
Rozwiązania
uproszczone:
Jeśli
przyjmie się dodatkowe założenia.
Rozwiązanie uproszczone
problemu
czytelników i pisarzy
Założenie:
Ustalona
jest liczba czytelników, jaka może korzystać z czytelni.
1:
const M = ? {liczba miejsc w czytelni}
2:
Wolne : Semafor := M;
3:
W: Semafor_binarny :=1;
4:
task body Czytelnik is
5:
begin
6:
loop
7:
Własne_sprawy_1;
8:
Wait(Wolne);
9:
Czytanie;
10:
Signal(Wolne);
11:
end loop;
12:
end;
13:
task body Pisarz is
14:
j : Integer;
15:
begin
16:
loop
17:
Własne_sprawy_2;
18:
Wait(W);
19:
for j = 1 to M do
20: Wait(Wolne);
21: end
for;
22:
Pisanie;
23:
for j = 1 to M do
24: Signal(Wolne);
25: end
for;
26:
Signal(W):
27:
end loop;
28:
end;
Rozwiązanie
problemu czytelników i pisarzy (1/2)
1:
Ac: Integer := 0; {aktywni czytelnicy}
2:
Dc: Integer := 0; {działający czytelnicy}
3:
Ap: Integer := 0; {aktywni pisarze}
4:
Dp: Integer := 0; {działający pisarze}
5:
Czyt : Semafor := 0; {wstrzymuje czytelników}
6:
Pis : Semafor := 0; {wstrzymuje pisarzy}
7:
Chroń: Semafor_binarny := 1; {do ochrony zmiennych}
8:
W: Semafor_binarny :=1: {wykluczanie pisarzy}
9:
task body Czytelnik is
10:
begin
11:
loop
12:
Własne_sprawy_1;
13:
Wait(Chroń)
14:
ac := ac + 1;
15:
if ap = 0 then
16:
while dc < ac do {wpuszczenie wszystkich} 17: dc := dc
+1; {czytelników przed sobą}
18:
Signal(Czyt); {i otwarcie sobie drogi}
19:
end while;
20:
end if;
21:
Signal(Chroń)
22:
Wait(Czyt);
23:
Czytanie;
24:
Wait(Chroń)
25:
dc := dc - 1;
26:
ac := ac - 1;
27:
if dc = 0 then
28:
while dp < ap do {wpuszczenie wszystkich}
29:
dp := dp + 1; {oczekujących pisarzy}
30:
Signal(Pis);
31:
end while;
32:
end if;
33:
Signal(Chroń)
34:
end loop;
35:
end;
Rozwiązanie
problemu czytelników i pisarzy (2/2)
36:
task body Pisarz is
37:
begin
38:
loop
39:
Własne_sprawy_2;
40:
Wait(Chroń)
41:
ap := ap + 1;
42:
if ac = 0 then
43:
while dp < ap do {wpuszczenie pisarza} 44: dp := dp
+1;