Table of Contents
W systemie działa N par procesów. Procesy z pary są nierozróżnialne. Każdy proces cyklicznie wykonuje własne_sprawy, a potem spotyka się z drugim procesem z pary (procedura spotkanie) w kawiarni przy stoliku dwuosobowym. W kawiarni jest tylko jeden stolik. Procesy mogą zająć stolik tylko wtedy, gdy obydwa są gotowe do spotkania, ale odchodzą od niego pojedyńczo (w różnym czasie kończą wykonywanie procedury spotkanie).
Zapisz treść procesu P(j: 1..N) używając do synchronizacji semaforów.
Zapisz treść procesu P(j: 1..N) i monitor Kawiarnia synchronizujący ich działanie.
process P(i: 1..N)
begin
while (true) do
begin
wlasne_sprawy();
...wejscie...
spotkanie();
...wyjscie...
end;
end;
var
i: integer;
begin
cobegin
for i:=1 to N do
begin
P(i); P(i);
end;
...
coend;
end;
var
ochrona: binary semaphore := 1;
stolik: binary semaphore := 1;
czekanie_na_pare: array[1..N] of binary semaphore := (N times 0);
proces_czeka_na_drugi: array[1..N] of boolean := (N times false);
liczba_przy_stoliku: integer;
process P(i: 1..N)
begin
while (true) do
begin
wlasne_sprawy()
P(ochrona)
if (proces_czeka_na_drugi[i]=false) then
begin
proces_czeka_na_drugi[i]:=true;
V(ochrona);
P(czekanie_na_pare[i]);
proces_czeka_na_drugi[i]:=false;
V(ochrona);
end;
else
begin
V(ochrona);
P(stolik);
P(ochrona);
liczba_przy_stoliku := 2;
V(czekanie_na_pare[i]);
end;
spotkanie()
P(ochrona);
liczba_przy_stoliku--;
if (liczba_przy_stoliku=0) then
begin
V(stolik);
end;
V(ochrona);
end;
end;
W tym rozwiązaniu nie jest wykorzystane dziedziczenie semafora ochrona. Brak dziedziczenia semafora ochrona oznacza, że pomiędzy procesem budzącym (ostatni odchodzący od stolika), a procesem budzonym (czekającym na stolik), pewien inny proces (od procesu budzonego), a nawet kilka innych procesów, może przejąć semafor ochrona. Niebezpieczeństwo jest takie, że taki inny proces (lub nawet inne procesy) zmienią stan w taki sposób, że proces budzony gdy przejmie ochroną to stan już nie będzie taki, jaki był w czasie budzenia. W zastosowanym rozwiązaniu procesy, które się wykonują w między czasie nie wpływają na bezpieczeństwo (semafor stolik wpuszcza tylko jeden proces - więc tylko jedna para może być przy stoliku), i nie wpływają na żywotność (1.gdy stolik jest zwalniany, to semafor stolik jest opuszczany i kolejny para może wejść, 2. semafor stolik jest opuszczany zawsze gdy stolik jest zwalniany) - czekający proces na semaforze stolik w końcu się doczeka (pomimo, że mogą pojawić się nowe procesy czekające na stolik razem z nim, a nawt może się zdarzyć, że taki nowy proces zajmie stolik wcześniej niż proces który czekał już w momencie budzenia).
var
ochrona: binary semaphore := 1;
stolik: binary semaphore := 1;
czekanie_na_pare: array[1..N] of binary semaphore := (N times 0);
proces_czeka_na_drugi: array[1..N] of boolean := (N times false);
liczba_przy_stoliku: integer;
liczba_par_czekajacych_na_stolik: integer := 0;
process P(i: 1..N)
begin
while (true) do
begin
wlasne_sprawy()
P(ochrona)
if (proces_czeka_na_drugi[i]=false) then
begin
proces_czeka_na_drugi[i]:=true;
V(ochrona);
P(czekanie_na_pare[i]);
proces_czeka_na_drugi[i]:=false;
V(ochrona);
end;
else
begin
liczba_par_czekajacych_na_stolik++;
V(ochrona);
P(stolik);
liczba_par_czekajacych_na_stolik--;
liczba_przy_stoliku := 2;
V(czekanie_na_pare[i]);
end;
spotkanie()
P(ochrona);
liczba_przy_stoliku--;
if (liczba_przy_stoliku=0) then
begin
if (liczba_par_czekajacych_na_stolik>0) then {drugi wychodzacy}
begin
V(stolik);
end;
else
begin
V(stolik);
V(ochrona);
end;
end;
else {pierwszy wychodzacy}
begin
V(ochrona);
end;
end;
end;
W tym rozwiązaniu dziedziczony jest semafor ochrona. Semafor stolik jest wykorzystywany do zapewnienia wyłącznego dostępu do stolika. Warto zwrócić uwagę, że nie inicjalizujemy tu zmiennej liczba_przy_stoliku, gdyż wyłączność w użytkowaniu stolika gwarantuje wykorzystanie semafora stolik. Zmienną liczba_przy_stoliku wykorzystujemy tylko do rozróżnienia procesów zwalniających stolik.
var
ochrona: binary semaphore := 1;
stolik: binary semaphore := 0;
czekanie_na_pare: array[1..N] of binary semaphore := (N times 0);
proces_czeka_na_drugi: array[1..N] of boolean := (N times false);
liczba_przy_stoliku: integer := 0;
liczba_par_czekajacych_na_stolik: integer := 0;
process P(i: 1..N)
begin
while (true) do
begin
wlasne_sprawy()
P(ochrona)
if (proces_czeka_na_drugi[i]=false) then
begin
proces_czeka_na_drugi[i]:=true;
V(ochrona);
P(czekanie_na_pare[i]);
proces_czeka_na_drugi[i]:=false;
V(ochrona);
end;
else
begin
if (liczba_przy_stoliku<>0) then
begin
liczba_par_czekajacych_na_stolik++;
V(ochrona);
P(stolik);
liczba_par_czekajacych_na_stolik--;
end;
liczba_przy_stoliku := 2;
V(czekanie_na_pare[i]);
end;
spotkanie()
P(ochrona);
liczba_przy_stoliku--;
if (liczba_przy_stoliku=0 and liczba_par_czekajacych_na_stolik>0) then
V(stolik);
else
V(ochrona);
end;
end;
W tym rozwiązaniu dziedziczymy semafor ochrona. Semafor stolik wykorzystywany jest tu inaczej, niż w poprzednich rozwiązaniach. Wcześniej służył on do zdobywania wyłącznego dostępu do stolika. W tym rozwiązaniu służy on do zawieszania procesów czekających na stolik gdy nie jest on wolny. Informacje o zajętości stolika dostarcza wartość zmiennej liczba_przy_stoliku, dlatego musimy ją odpowiednio zainicjalizować. Należy też zwrócić uwagę, że jest on teraz inicjalizowany na 0 a nie na 1.
monitor Kawiarnia;
var
stolik: condition;
czekanie_na_pare: array[1..N] of condition;
ilu_przy_stoliku: integer;
export procedure wejscie(int i)
begin
if (empty(czekanie_na_pare[i]))
wait(czekanie_na_pare[i]);
else
begin
if (ile_przy_stoliku<>0) wait(stolik);
ile_przy_stoliku:=2; { || mozna || }
signal(czekanie_na_pare[i]); { || zamienic || }
end;
end;
export procedure wyjscie(int i)
begin
dec(ile_przy_stoliku)
if (ile_przy_stoliku=0)
signal(stolik);
end;
begin
end;
process P(i: 1..N)
begin
while (true) do
begin
wlasne_sprawy();
Kawiarnia.wejscie(i);
spotkanie();
Kawiarnia.wyjscie(i);
end;
end;
Warto zwrócić uwagę na instrukcje oznaczone "mozna zamienic". W monitorze procesy wykonujące signal ustawiają się na początku kolejki wejściowej. Gdy drugi proces z pary robi signal, to wychodzi on z monitora i ustawia się na początku kolejki wejściowej. Potem obudzony (pierwszy) proces z pary wyjdzie z monitora (zaczyna spotkanie), to proces budzący (drugi z pary) który czeka na początku kolejki wejściowej zacznie się wykonywać (jest to pewne, że będzie to ten proces a nie inny). Jeśli proces pierwszy skończy spotkanie bardzo szybko, i będzie chciał wejść do monitora (wywola procedurę wyjście), to ustawi się na końcu kolejki wejściowej i wejdzie do monitora po tym jak proces drugi z niego skorzysta (kończenie procedury wejście po signal).
Istotny jest także fakt, że zamiana tych instrukcji powoduje, że procesy wychodzą z monitora (kończą procedurę wejście) w różnej kolejności. Gdy proces drugi z pary wykonuje signal jako ostatnią instrukcję to on wychodzi jako pierwszy. W sytuacji gdy signal nie jest ostatnią instrukcją (zamienione instrukcje) to on wpuszcza najpierw proces pierwszy z pary i to proces pierwszy z pary zakończy procedurę wejście jako pierwszy.