Programowanie współbieżne i rozproszone/PWR Ćwiczenia 3

Zadanie 1

Treść

Stosując mechanizm komunikacji asynchronicznej omówiony na wykładzie rozwiąż problem wzajemnego wykluczania dla wielu procesów. Co zmieni się w rozwiązaniu, jeśli zezwolimy na pobyt w sekcji krytycznej jednocześnie K>0 procesom?

Rozwiązanie pierwsze

Przedstawione na wykładzie rozwiązanie działa dobrze także wtedy, gdy w systemie działa wiele procesów. Każdy z nich wykonuje kod:

process Pr (i: integer);
var
  k: Komunikat;
begin
  repeat
    własne_sprawy;
    GetMessage (b, k)
    sekja_krytyczna;
    SendMessage (b, k)
  until false
end;

Przed uruchomieniem procesów (powiedzmy, że jest ich P) musimy jeszcze zadbać o to, by w buforze b było K komunikatów:

const
  P = ...;
  K = ...;
type
  Komunikat = (Bilet); 
var i: integer;
begin
  for i := 1 to K do
    SendMessage (b, Bilet);
  cobegin 
    for i := 1 to P do Pr(i) 
  coend  
end

Rozwiązanie drugie. Serwer.

Częstym rozwiązaniem stosowanym w modelu rozproszonym jest wprowadzanie dodatkowych procesów, które nadzorują synchronizację pozostałych. Zastosujmy takie podejście do omawianego zadania. Wprowadźmy dodatkowy proces o nazwie Dozorca, który będzie nadzorował dostęp do sekcji krytycznej.

Ćwiczenie (ukrywajka)

O jakich zdarzeniach powinien informować dozorcę proces?

O czym powinien informować serwer?

Jakie bufory są potrzebne?

Schemat komunikacji

Każdy proces powinien wysyłać serwerowi informację o tym, że chce wejść do sekcji krytycznej. Serwer, po odebraniu takiego komunikatu, sprawdza, czy sekcja krytyczna jest wolna. Jeśli tak, to wysyła procesowi zgodę na wejście do niej. Proces powinien cierpliwie oczekiwać na zgodę serwera, po czym wejść do sekcji krytycznej dopiero po jej otrzymaniu. Następnie po zakończonym pobycie w sekcji musi poinformować serwer, że jest ona wolna.

Opisany schemat daje się zrealizować za pomocą dwóch buforów:

• w pierwszym zam procesy umieszczają "zamówienia" na sekcję krytyczną
• w drugim zezw serwer umieszcza zezwolenia na wejście do sekcji krytycznej

Rysunek przedstawiający ten schemat.

Treść procesu

Ćwiczenie (ukrywajka)

Napisz treść procesu

Przypuśćmy, że opisane powyżej komunikaty definiujemy za pomocą wartości typu wyliczeniowego:

type
  Komunikat = (Chcę, Możesz, Zwalniam);

i mamy bufory:

var
  zam, zezw: buffer;

Wtedy treść każdego (z wielu) procesu wygląda tak:

process Pr;
var
  k: Komunikaty;
begin
  repeat
    własne_sprawy;
    SendMessage (zam, Chcę);
    GetMessage (zezw, k);
    sekcja_krytyczna;
    SendMessage (zam, Zwalniam);
  until false
end

Treść serwera

Oczywiście przy tego typu rozwiązaniach istota rozwiązania tkwi w kodzie serwera, który w nieskończonej pętli odbiera komunikat, po czym go przetwarza. W naszym zadaniu serwer musi pamiętać ile jest wolnych miejsc w sekcji krytycznej. Gdy przychodzi prośba od procesu i są wolne miejsca wtedy serwer zgadza się na wejście procesu wysyłając mu natychmiast zezwolenie, jeśli wolnych miejsc nie ma, to zezwolenie musi zostać wysłane potem.

Ćwiczenie (ukrywajka)

Co powinien dodatkowo zapamiętać serwer, gdy nie może od razu udzielić zgody na wejście do sekcji krytycznej?

Ćwiczenie (ukrywajka)

Czy wprowadzenie numerów procesów jest rzeczywiście niezbędne?

Oprócz liczby wolnych miejsc w sekcji krytycznej serwer zapamiętuje jeszcze, ile procesów poprosiło o zgodę na wejście do sekcji i jej nie dostało. Gdy zwolni się miejsce w sekcji i są chętni do wejścia do sekcji, to serwer umieszcza jedno zezwolenie w buforze zezw.

Ćwiczenie (ukrywajka)

Napisz kod serwera

A oto przykładowy kod serwera:

process Dozorca;
var
  k: Komunikaty;
  ileWolnych: integer := K;
  iluChce: integer := 0;
begin
repeat
  GetMessage (zam, k);                   { odbiór komunikatu}
  case k of                              { który jest albo }  
    Chce: if ileWolnych > 0 then         { zamówieniem }
          begin             
            dec (ileWolnych);            { i wtedy wysyłamy zgodę, gdy mamy miejsce }
            SendMessage (zezw, Możesz)
          end else
            inc (iluChce)                { lub zwiększamy licznik oczekujących }
    Zwalniam: if iluChce > 0 then        { albo zwolnieniem miejsca } 
          begin
            SendMessage (zezw, Możesz);  { i wtedy wysyłamy zgodę, gdy ktoś czeka }
            dec (iluChce)
          end else
            inc (ileWolnych)             { lub zwiększamy licznik wolnych miejsc }
   end {case}
 until false
end;

Test wielokrotnego wyboru

To rozwiązanie jest

1. bezpieczne
2. żywotne
3. procesy wchodzą do sekcji krytycznej w kolejności odbierania przez serwer zamówień
4. serwer może wydać zgodę procesowi oczekującemu, ale skorzysta z niej proces, który nie czekał

To rozwiązanie ma pewną subtelność: procesy nie muszą wchodzić do sekcji krytycznej w kolejności jej zamawiania. Dzieje się tak, gdyż nie precyzujemy, że procesy oczekujące na GetMessage oczekują w kolejce. Może się nawet zdarzyć, że zezwolenie "przeznaczone" dla procesu oczekującego na zgodę odbierze proces, który dopiero co zgłosił zapotrzebowanie. Jednak na mocy sprawiedliwości operacji pobierania z bufora nie dojdzie do zagłodzenia żadnego procesu.

Zadanie 2. Czytelnicy i pisarze

Rozwiąż za pomocą notacji z wykładu problem czytelników i pisarzy.

Rozwiązanie pierwsze

Zanim napiszemy program zastanówmy się jaki jest ogólny schemat rozwiązywania tego typu zadań synchronizacyjnych. Mamy tutaj dwie grupy procesów, które muszą w jakiś sposób zsynchronizować korzystanie z "czytelni" --- tak będziemy nazywać wykonanie operacji czytania przez czytelnika lub pisania przez pisarza. Mamy więc następujący schemat działania czytelnika i pisarza:

process Czytelnik; begin repeat własne_sprawy; protokół_wstępny_czytelnika; CZYTANIE; protokół końcowy_czytelnika until false end

process Pisarz; begin repeat własne_sprawy; protokół_wstępny_pisarza; PISANIE; protokół końcowy_pisarza until false end

Nie znana jest nam liczba czytelników i pisarzy --- może ich być dowolnie dużo. Podobnie w żaden sposób nie limitujemy liczby miejsc w czytelni.

Z reguły projektując protokoły wstępne musimy odpowiedzieć na pytanie Kiedy proces powinien poczekać. Z kolei pisząc protokoły końcowe musimy budzić procesy uśpione w protokołach wstępnych. Trzeba wtedy często podejmować decyzję, którą grupę procesów obudzić.

Rozwiązanie tego problemu można opisać następującym algorytmem.

1. Czytelnik, który chce czytać sprawdza, czy w czytelni nie ma pisarza. Jeśli nie ma, to rozpoczyna czytanie. Jeśli jest, to czytelnik musi poczekać.
2. Pisarz, który chce pisać czeka aż czytelnia będzie pusta i rozpoczyna pisanie.
3. Pisarz

Implementując taki algorytm dobrze jest wprowadzić dodatkowy proces {\tt Czytelnia} synchronizujący dostęp do czytelni. Proces ten przechowuje informacje o tym, kto jest w czytelni i decyduje, kogo można wpuścić. Do komunikacji wprowadzimy trzy bufory: jeden do komunikacji z czytelnią, jeden do wysyłania zezwoleń dla pisarzy, jeden do wysyłania zezwoleń dla czytelników: