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

Zadanie 1. Wzajemne wykluczanie.

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.

Schemat komunikacji

Ćwiczenie (ukrywajka)

O jakich zdarzeniach powinien informować dozorcę proces?

O czym powinien informować serwer?

Jakie bufory są potrzebne?

Odpowiedź

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

Treść procesu

Ćwiczenie (ukrywajka)

Napisz treść procesu

Odpowiedź

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?

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

Odpowiedź

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

Odpowiedź

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 znamy liczby 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ć. Spróbujmy zatem odpowiedzieć na te pytania:

Protokół wstępny czytelnika

czytelnik czeka, jeśli w czytelni jest pisarz.

Protokół wstępny pisarza

pisarz czeka jeśli, w czytelni ktoś jest.

Protokół końcowy czytelnika

jeśli jest ostatnim wychodzącym, to wpuszcza pisarza (o ile czeka).

Protokół końcowy pisarza

jeśli czeka pisarz, to budzimy go, w przeciwnym razie, jeśli czekają czytelnicy, budzi ich wszystkich.

Zanim zaczniemy implementować to rozwiązanie, odpowiedzmy na kilka pytań:

Test wielokrotnego wyboru

1. To rozwiązanie jest żywotne
2. To rozwiązanie jest bezpieczne
3. To rozwiązanie prowadzi do zagłodzenia czytelników
4. To rozwiązanie prowadzi do zagłodzenia pisarzy

W zależności od rozwoju sytuacji, przedstawione rozwiązanie może zagłodzić pisarzy lub może zagłodzić czytelników.

Ćwiczenie (ukrywajka)

Podaj przeplot prowadzący do zagłodzenia czytelników.

Odpowiedź

Oto przeplot prowadzący do niepożądanej sytuacji:

1. Zjawia się pisarz P1 i jest wpuszczany do czytelni.
2. W trakcie pobytu pisarza w czytelni zjawi się czytelnik C1. Będziemy go głodzić.
3. Zjawia się drugi pisarz P2, który oczywiście czeka.
4. Czytelnię zwalnia P1. Wchodzi do niej P2.
5. Pisarz P1 w trakcie pobytu P2 w czytelni załatwia własne sprawy i chce znów wejść do czytelni.
6. P2 wychodzi z czytelni wpuszczając do niej P1.

I teraz wystarczy powtarzać kroki od 3 do 6.

Widać zatem, że za zaistniałą sytuację odpowiada protokół końcowy. Spróbujmy go poprawić.

Rozwiązanie drugie

Protokół wstępny czytelnika

czytelnik czeka, jeśli w czytelni jest pisarz.

Protokół wstępny pisarza

pisarz czeka, jeśli w czytelni ktoś jest.

Protokół końcowy czytelnika

jeśli jest ostatnim wychodzącym, to wpuszcza pisarza (o ile czeka).

Protokół końcowy pisarza

jeśli czekają czytelnicy, to budzi ich wszystkich, w przeciwnym razie, jeśli czeka pisarz, budzi jednego.

Zmianie uległ protokół końcowy pisarza. Aby nie dopuścić do zagłodzenia w systemie, w którym działają dwie grupy procesów, musimy dbać o to, aby grupy te budziły się naprzemiennie (no chyba, że nikt z drugiej grupy nie czeka). Czy taka poprawka jednak wystarczy?

Test wielokrotnego wyboru

1. Tym razem nie zagłodzimy czytelników.
2. Ale wpuścimy jednocześnie czytelnika i pisarza do czytelni.
3. Dalej mamy zagłodzenie czytelników
4. Dalej mamy zagłodzenie pisarzy

Tym razem uniknęliśmy głodzenia czytelników, ale w dalszym ciągu mamy zagłodzenie pisarzy. Tym razem winien jest protokół wstępny czytelnika. Zezwala on na ciągły napływ nowych czytelników do czytelni, a w konsekwencji może się zdarzyć tak, że czytelnia nigdy nie będzie pusta, bo zawsze będą w niej czytelnicy.

Ćwiczenie

Skonstruuj odpowiedni przeplot.

Zaproponuj poprawkę protokołu wstępnego. Uważaj przy tym, aby znów nie zagłodzić czytelników!

Rozwiązanie trzecie

Poprawne rozwiązanie polega na zatrzymaniu czytelnika także wtedy, gdy czeka pisarz. Choć z pozoru wygląda to na głodzenie czytelników (no bo przecież zatrzymujemy czytelnika, gdy czeka pisarz, a może się zdarzyć, że zawsze będą czekać jacyś pisarze), to jednak uprzednia zmiana protokołu końcowego powoduje, że wychodzący pisarz wpuści wszystkich czytelników, którzy nadeszli podczas jego pobytu w czytelni.

Protokół wstępny czytelnika

czytelnik czeka, jeśli w czytelni jest pisarz.

Protokół wstępny pisarza

pisarz czeka, jeśli w czytelni ktoś jest.

Protokół końcowy czytelnika

jeśli jest ostatnim wychodzącym, to wpuszcza pisarza (o ile czeka).

Protokół końcowy pisarza

jeśli czekają czytelnicy, to budzi ich wszystkich, w przeciwnym razie, jeśli czeka pisarz, budzi jednego.

Implementując taki algorytm dobrze jest wprowadzić, jak poprzednio, dodatkowy proces Czytelnia synchronizujący dostęp do czytelni i pełniący funkcję serwera. Proces ten przechowuje wszystkie informacje niezbędne do zaimplementowania powyższego algorytmu i decyduje, kogo można wpuścić do czytelni.

Ćwiczenie

Przeczytaj opis protokołów. Jakie zmienne będą potrzebne do ich zaimplementowania?

Jak zrealizować zawieszenie czytelnika i pisarza?

Czy czytelnicy i pisarze mogą oczekiwać w tym samym miejscu?

Schemat komunikacji

Ćwiczenie (ukrywajka)

Jakie komunikaty będą wymieniać procesy?

Ile buforów jest potrzebnych?

Odpowiedź

Jak zwykle przy rozwiązaniach typu klient-serwer główny ciężar spoczywa na serwerze. Procesy muszą jedynie informować serwer o swoich działaniach i oczekiwać na jego zgodę na nie. Czytelnik przez rozpoczęciem czytania prosi serwer o zgodę. Podobnie postępuje pisarz przed rozpoczęciem pisania. Następnie procesy oczekują na zgodę. Do przekazywania zezwoleń wykorzystamy dwa bufory: osobny dla czytelnika, osobny dla pisarza. Jest to konieczne, gdyż serwer musi mieć możliwość obudzenia jedynie pisarzy lub jedynie czytelników. Procesy przed opuszczeniem czytelni informują o tym serwera.

Prowadzi to do definicji typów wyliczeniowych oraz zmiennych buforowych:

type 
  Komunikat = (ChcęCzytać, ChcęPisać, Wychodzę);
  Zezwolenie = (Wejdź)  
var
  czytelnia, czytelnicy, pisarze: buffer;

oraz schematu komunikacji:

Rysunek

Proces czytelnika i pisarza

Treść procesów jest prosta. Protokół wstępny polega na wysłaniu komunikatu do serwera i oczekiwaniu na zgodę, podobnie protokół końcowy to poinformowanie serwera, że pobyt w czytelni zakończył się:

process Czytelnik; var z: Zezwolenie; begin repeat własne_sprawy; SendMessage (czytelnia, ChcęCzytać); GetMessage (czytelnicy, z); CZYTANIE; SendMessage (czytelnia, Wychodzę) until false end;

process Pisarz; var z: Zezwolenie; begin repeat własne_sprawy; SendMessage (czytelnia, ChcęPisać); GetMessage (pisarze, z); PISANIE; SendMessage (czytelnia, Wychodzę) until false end;

Proces Czytelnia

Główna trudność to proces serwera. Musi on przechowywać liczniki:

• dc --- liczba działających czytelników, tj. czytelników przebywających w czytelni
• cc --- liczba czekających czytelników
• dp --- liczba działających pisarz, tj. pisarzy przebywających w czytelni
• cp --- liczba czekających pisarzy, tj.

Ćwiczenie

Które z powyższych zmiennych mogłyby być zmiennymi logicznymi zamiast licznikami?

Proces Czytelnia będziemy tworzyć stopniowo. Zacznijmy od deklaracji zmiennych lokalnych i początku głównej pętli:

process Czytelnia;
var
  dc, dp : integer; 
  cc, cp : integer; 
  kom: Komunikat;
begin
  dc := 0; dp := 0; cc := 0; cp := 0;
  repeat
    GetMessage (czytelnia, kom);
    case kom of
      ChcęCzytać: 
          ... 

Po odbiorze komunikatu serwer rozstrzyga do jakiego zdarzenia doszło (ChcęCzytać zgłosił czytelnik, który chce wejść do czytelni) i obsługuje je w odpowiedni sposób.

Ćwiczenie (ukrywajka)

Zaimplementuj obsługę komunikatu ChcęCzytać.

Odpowiedź

Serwer po odbiorze komunikatu ChcęCzytać powinien:

1. Zmodyfikować odpowiednie zmienne
2. Sprawdzić, czy można dać czytelnikowi zgodę na wejście do czytelni
3. Jeśli tak, to wysłać zgodę i zmodyfikować odpowiednie zmienne
4. Jeśli nie, to zmodyfikować zmienne.

W efekcie otrzymujemy kod:

      ChcęCzytać: 
        begin
          if dp + cp > 0 then  
            inc (cc)           
          else                        { żaden pisarz nie działa ani nie czeka }
          begin
            inc (dc);
            SendMessage (czytelnicy, Wejdź);
          end
        end;

W podobny sposób implementujemy obsługę komunikatu ChcęPisać

Ćwiczenie (ukrywajka)

Zaimplemetuj ją.

Odpowiedź

Jedyna różnica polega na innym warunku oczekiwania:

      ChcęPisać: 
        begin
          if dp + dc > 0 then  
            inc (cp)           
          else                        { nie działa ani czytelnik ani pisarz } 
          begin
            inc (dp);
            SendMessage (pisarze, Wejdź);
          end
        end;

Pozostała już tylko implementacja protokołu końcowego, który rozbija się na dwa fragmenty w zależności od wartości zmiennej dp:

      Wyjdź: 
        if dp > 0 then                   { wychodzi pisarz }
        begin
          dec (dp); 
          if cc > 0 then                 { czekają czytelnicy }
            while cc > 0 do              { wpuszczamy wszystkich }
            begin
              SendMessage (czytelnicy, Wejdź)
              dec (cc); inc (dc);
            end
          else if cp > 0 then            { nie czekali czytelnicy, ale jest pisarz }
          begin
            inc (dp); 
            SendMessage (pisarze, Wejdź) { wpuszczamy jednego } 
          end
        end else { wychodzi czytelnik }
        begin
          dec (dc);                      
          if (dc = 0) and (cp > 0) then  { jest to ostatni czytelnik i są pisarze }
          begin
            inc (dp); dec (cp); 
            SendMessage (pisarze, Wejdź)
          end
        end
    end {case}
  until false
end;