Programowanie współbieżne i rozproszone/PWR Wykład 2

Modele współbieżności

Rozważając programy współbieżne możemy analizować dwa modele środowiska, w którym wykonują się procesy.

1. Procesy mają dostęp do tej samej przestrzeni adresowej. Oznacza to, że mogą korzystać ze wspólnych zmiennych umieszczonych we fragmencie pamięci dostępnej dla każdego z nich. Wspólna pamięć może znajdować się faktycznie na komputerze, na którym wykonują się procesy lub może być udostępniania za pomocą serwera segmentów pamięci dzielonej, procesy nie muszą jednak znać mechanizmów udostępniania tej pamięci. z punktu widzenia procesu ważna jest jedynie możliwość odczytania/modyfikacji zmiennej współdzielonej, a nie sposób implememtacji tych zmiennych.
2. Nie ma zmiennych współdzielonych. Każdy proces ma własną przestrzeń adresową i nie ma możliwości odwołania się do zmiennych innego procesu.

Komunikacja asynchroniczna

Notacja stosowana w dalszym ciągu

W dalszym ciągu wykładu będziemy abstrahować od konkretnych zawiłości technicznych związanych z realizacją komunikacji asynchronicznej za pomocą konkretnego mechanizmu (na przykład łączy nienazwanych w środowisku Unix). Skupimy się jedynie na istotnych elementach synchronizacyjnych. W tym celu przyjmujemy następujące konwencje:

• Stosujemy konstrukcje programistyczne z języka programowania Pascal.
• Rozszerzamy język o definicje procesów; składnia tych definicji jest taka, jak składnia definicji procedur bezparametrowych lub z parametrami przekazywanymi przez wartość, np.:

process P (i: integer);
begin
  ...
end

• Dodajemy wspomniane już wcześniej konstrukcje cobegin oraz coend służące do wyrażania współbieżnego wykonania. Umawiamy się przy tym, że wewnątrz cobegin i coend mogą wystąpić jedynie wywołania procesów (umieszczone ewentualnie wewnątrz pętli for), np.:

 cobegin
   P(1); P(1); P(2); Q;
 coend

• Wprowadzamy nowy, predefiniowany typ danych o nazwie buffer. Zmienne tego typu reprezentują bufory, do których wysyłamy i z których odbieramy komunikaty.
• Zmienne buforowe mogą być deklarowane jedynie poza procesami. Jedynymi operacjami na nich są operacja wyłania komunikatu i operacja odebrania komunikatu.
• Procesy nie mają dostępu do zmiennych globalnych, z wyjątkiem zmiennych buforowych.
• Bufory są nieograniczone i działają jak kolejki proste.
• Do wysłania komunikatu mdo bufora b służy operacja SendMessage(b, m). Wobec nieskończoności bufora jest ona nieblokująca, tzn.: proces nie może zostać wstrzymany na skutek jej wywołania.
• Do odbierania komunikatu z bufora b służy operacja GetMessage(b, m). Proces odbiera wtedy pierwszy komunikat z bufora i umieszcza go w zmiennej m. Typ zmiennej m musi być zgodny z typem odebranego komunikatu, w przeciwnym razie efekt operacji jest nieokreślony.
• Jeśli bufor jest pusty, to operacja GetMessage wstrzymuje wykonanie procesu, do momentu aż w buforze znajdą się jakieś dane.
• Jeśli wiele procesów oczekuje na operacji GetMessage i w buforze pojawi się jeden komunikat, to jeden z procesów oczekujących jest budzony. Nie zakładamy przy tym nic o kolejności budzenia. Oznacza to, że procesy nie muszą być budzone w kolejności wykonywania GetMessage
• Oczekiwanie jest jednak sprawiedliwe. Jeśli jakiś proces oczekuje na GetMessage, a bufor jest nieskończenie wiele razy niepusty, to proces ten zostanie w końcu obudzony.
• Zmienna m w powyższych operacjach może być dowolnego typu.
• Operacje GetMessage i SendMessage na tym samym buforze są niepodzielne i wykluczające się nawzajem.
• Procesy nie mają dostępu do zmiennych globalnych, z wyjątkiem zmiennych buforowych.

Przykłady

Wzajemne wykluczanie dwóch procesów

Problem ten rozwiążemy wprowadzając jeden bufor, do którego początkowo włożymy jeden komunikat. Nie jest przy tym istotne, co jest tym komunikatem, przyjmijmy dla ustalenia uwagi, że jest to dowolna liczba całkowita. Komunikat ten pełni funkcję biletu. Proces, który chce wejść do sekcji krytycznej musi zdobyć bilet, zatrzymuje go przy sobie przez cały czas pobytu w sekcji krytycznej i oddaje po wyjściu z niej. Prowadzi to do następującego programu:

Zmienne globalne:

var
  buf: buffer;
  bilet: integer;

Treść procesu:

process P;
var
  bilet: integer;
begin
  repeat
    własne_sprawy;
    GetMessage (buf, bilet);  { bierzemy bilet }
    sekcja_krytyczna;
    SendMessage (buf, bilet); { oddajemy bilet }
  until false
end;

Program główny:

begin
  SendMessage (buf, bilet) { umieszczamy bilet w buforze }
  cobegin            { i uruchamiamy dwa egzemplarze procesu P } 
    P; P
  coend
end 

Własność bezpieczeństwa tego rozwiązania wynika z tego, że jest tylko jeden bilet, a operacje na buforze są niepodzielne. Jeśli pewien proces przebywa w sekcji krytycznej, to w buforze nie ma już biletu, więc drugi proces będzie musiał poczekać na instrukcji GetMessage(buf, bilet).

Żywotność gwarantuje sprawiedliwość operacji GetMessage oraz założenie, że żaden proces, który wszedł do sekcji krytycznej w skończonym czasie z niej wyjdzie. Przypomnijmy, że zakładamy, jak zwykle, sprawiedliwość systemu operacyjnego.

Pięciu filozofów. Wersja 1.

Spróbujmy teraz rozwiązać problem pięciu filozofów. Najpierw musimy się zastanowić, jakie procesy będą potrzebne w rozwiązaniu. Oczywiście musi działać pięć procesów reprezentujących filozofów. Jednak co z widelcami? Tutaj możliwych jest wiele rozwiązań. Zacznijmy od przykładu, w którym każdy widelec jest po prostu komunikatem. Początkowo znajduje się on w odpowiednim buforze, co oznacza, że widelec jest wolny. Buforów musi być jednak tyle, ile widelców, bo każdy filozof podnosi ściśle określone widelce, a nie dowolne. Filozof, który podniesie widelec po prostu wyjmuje komunikat z odpowiedniego bufora i zatrzymuje go, dopóki nie skończy jeść.

Opisany schemat prowadzi do następującego schematu komunikacji. Procesy reprezentujemy na rysunku kołami, a bufory --- prostokątami:

Rysunek

Definicje globalne są zatem następujące:

const
  N = 5;
var
  widelec: array [0..N-1] of buffer;
  m: integer;                                    { wartość nieistotna }                 

Treść filozofa jest bardzo krótka:

 process Filozof (i: 0..N-1);
 var
   m: integer;
 begin
   repeat
     myśli;
     GetMessage (widelec[i], m);                 { podniesienie widelca po lewej stronie }
     GetMessage (widelec[(i+1) mod N], m);       { podniesienie widelca po prawej stronie }
     je;
     GetMessage (widelec[i], m);                 { odłożenie widelca po lewej stronie }
     GetMessage (widelec[(i+1) mod N], m);       { odłożenie widelca po prawej stronie }
   until false;
 end

Program główny musi przygotować bufory

begin
  for i := 0 to N-1 do
    SendMessage (widelec[i], m);

i uruchomić odpowiednią liczbę filozofów:

  cobegin
    for i := 0 to N-1 do
      Filozof (i)
  coend
end.

Bardzo łatwo zauważyć, że powyższy program jest implementacją rozwiązania, w którym każdy filozof podnosi najpierw lewy widelec, a następnie prawy. Nie powinno nas zatem dziwić to, że może tu dojść do zakleszczenia. Przypomnijmy, jeśli wszyscy skończą myśleć w tym samym czasie i każdy podniesie lewy widelec, to nigdy nie doczeka się już na prawy.

Pięciu filozofów. Wersja 2.

Spróbujmy teraz postąpić inaczej. Zaimplementujemy widelce jako procesy, a filozofowie będą podnosić widelce w niedeterministycznej kolejności. Implementowanie obiektów statycznych (takich jak widelce, bufory w problemie producentów i konsumentów) w postaci procesów jest dość często stosowane w modelu rozproszonym.

Skoro i filozofowie i widelce są teraz procesami, musimy opracować pewien protokół do komunikacji między nimi. Kluczowe momenty w działaniu całego systemu to "zgłodnienie" któregoś filozofa oraz zakończenie jedzenia przez filozofa. Filozof musi zawiadomić o zaistnieniu tych faktów, procesy, których mogą one dotyczyć. W tym wypadku będą to sąsiednie widelce. Przyjmijmy więc, że filozof, który kończy jedzenie wysyła do obu widelców, które podniósł komunikat (nazwijmy go OdkładamCię), po odbiorze którego widelec wie, że jest wolny. Z kolei filozof, który zakończy myślenie wysyła do obu widelcy komunikat (ChcęCię). Ale to nie wszystko. Czasem filozof będzie musiał poczekać, bo widelec jest zajęty --- je nim inny filozof. Zatem tuż po wysłaniu komunikatu ChcęCię filozof musi zostać wstrzymany w oczekiwaniu na komunikat WeźMnie, wysyłany przez wolny widelec w odpowiedzi na żądanie ChcęCię. Taki schemat żądań (w tym wypadku ChcęCię) i potwierdzeń (WeźMnie) jest dość charakterystyczny dla komunikacji asynchronicznej.

Zastanówmy się jeszcze nad tym, czy i tym razem wystarczy wysłanie komunikatu, czy potrzebna jest jakaś jego treść. Filozof chcący rozpocząć jedzenie wysyła komunikaty do sąsiednich widelcy, które --- jeśli są wolne --- muszą na nie odpowiedzieć. Muszą zatem wiedzieć, do kogo wysłać potwierdzenie. Zatem w komunikacie zamawiającym widelec musi pojawić się numer filozofa. W przypadku potwierdzeń nie jest istotna ich treść, a jedynie sam fakt pojawienia się, a w komunikatach zwalniających wystarczy znów jedynie numer filozofa. Widelec, który jest w użyciu odróżni bowiem komunikat zamiawiający od komunikatu zwalniającego --- wystarczy, że będzie pamiętał, kto nim je. Tak więc w omawianym rozwiązaniu nie wystąpią komunikaty ChcęCię i OdkładamCię explicite, lecz będą po prostu komunikaty niosące ze sobą numer nadającego je filozofa.

Do ustalenia schematu komunikacji pozostaje jeszcze kwestia liczby buforów. Zauważmy, że każdy widelec odbiera komunikaty od dwóch filozofów. Nie wie przy tym w jakiej przyjdą kolejności i powinien być w każdej chwili gotowy zareagować na komunikat od każdego z nich. Ponieważ bezczynny widelec powinien czekać nieaktywnie, więc powinien wykonać operację GetMessage na jakimś buforze. Komunikaty od filozofów powinny być umieszczane właśnie w tym buforze. Prowadzi to naturalnie do rozwiązania, w którym każdy widelec ma własny bufor, gromadzący komunikaty przesyłane do niego. Analogicznie, każdy filozof będzie miał swój bufor, do którego widelce będą wpisywać potwierdzenia. Zatem schemat komunikacji jest następujący:

Rysunek

A oto odpowiadające mu deklaracje zmiennych globalnych:

var
  w: array [0..N-1] of buffer { bufory odbiorcze widelców }
  f: array [0..N-1] of buffer { bufory odbiorcze filozofów }

Proces filozof działa następująco:

process Filozof (i: 0..4);
var
  potw: integer;
begin
  repeat
    myśli;
    SendMessage (w[i], i);   { komunikat z numerem filozofa oznaczający ChcęCię }
    GetMessage (f[i], potw); { czeka na potwierdzenie }
    SendMessage (w[(i+1) mod N], i); { to samo do prawego widelca }     
    GetMessage (f[i], potw); { czeka na potwierdzenie }
    je;
    SendMessage (w[i], i);   { komunikat z numerem filozofa oznaczający odkładamCię }
    SendMessage (w[(i+1) mod N], i);   { to samo do prawego widelca }
  until false
end;

Proces widelca jest nieco bardziej złożony. Będą w nim potrzebne trzy zmienne lokalne:

• zmienna kto_je przechowuje numer filozofa, który podniósł widelec.
• zmienne k1 i k2 to numery filozofów, którzy przesłali dwa ostatnio odebrane komunikaty.

Widelec powinien oczekiwać na komunikat. Po jego odbiorze powinien wysłać potwierdzenie do nadawcy, a następnie oczekiwać na dwa kolejne komunikaty. Będą to: komunikat zwalniający, a następnie zamawiający albo odwrotnie: najpierw zamawiający (na który na razie nie odpowiadamy na niego), a potem zwalniający (i wtedy trzeba wysłać potwierdzenie zamawiającemu). W obu przypadkach schemat jest ten sam: oczekujemy na dwa komunikaty, po czym wysyłamy potwierdzenie na zamówienie. Zobaczmy jak schemat ten można zaimplementować w postaci programu wykonywanego przez proces Widelec:

 proces Widelec;
 var
   kto_je, k1, k2: integer;
 begin
   kto_je := 0; k2 := 0; { inicjacja na dowolne wartości, ale tak aby kto_je = k1 }
   repeat
     GetMessage (w[i], k1); 
     if k2 = kto_je then  { przy pierwszym obrocie prawda }
       kto_je := k1                   { zamówienie było od k1 }
     else 
       kto_je := k2;                  { zamówienie było od k2 }
     SendMessage (f[kto_je], i);      { potwierdzenie o dowolnej treści }
     GetMessage (w[i], k2);           { czekamy na komunikat }
   until false
 end;

Zauważmy, że jeśli pod koniec pętli k2=kto_je, to właśnie odebrany komunikat jest komunikatem zwalniającym i w kolejnym obrocie pętli będzie wykonane kto_je:=k1, bo kolejny komunikat będzie komunikatem zamawiającym. Jęsli jednak pod koniec pętli było kto_je=k1, to ostatnio odebrany komunikat był zamówieniem. Wtedy komunikat odebrany na początku kolejnego obrotu pętli jest zwolnieniem, po którym wykona się kto_je := k2 i zostanie wysłane zaległe potwierdzenie.

Zauważmy jednak, że zaimplementowanie widelców jako procesów nic nie zmieniło. W dalszym ciągu jest to ten sam algorytm powodujący zakleszczenie! Można teraz jednak próbować coś poprawić. Zmieńmy kolejność instrukcji w filozofie:

process Filozof (i: 0..4);
var
  potw: integer;
begin
  repeat
    myśli;
    SendMessage (w[i], i);   { komunikat z numerem filozofa oznaczający ChcęCię }
    SendMessage (w[(i+1) mod N], i); { to samo do prawego widelca }     
    GetMessage (f[i], potw); { czeka na potwierdzenie }
    GetMessage (f[i], potw); { czeka na potwierdzenie }
    je;
    SendMessage (w[i], i);   { komunikat z numerem filozofa oznaczający odkładamCię }
    SendMessage (w[(i+1) mod N], i);   { to samo do prawego widelca }
  until false
end;

Tym razem filozof najpierw zamawia widelce, a potem oczekuje na dwa potwierdzenia. Przyjdą one w nieznanej nam z góry kolejności --- w kolejności zwalniania się widelców. Mamy więc rozwiązanie, w którym kolejność podnoszenia widelcy jest niedeterministyczna: filozof podnosi najpierw ten widelec, który jest wolny.

Czy jednak taka zmiana coś zmienia? Nie, bo w dalszym ciągu możliwy jest ten sam, prowadzący do zakleszczenia przeplot.

Pięciu filozofów. Wersja 3.

Popróbujmy teraz zupełnie odmiennego rozwiązania. Przypuśćmy, że oprócz filozofów działa jeszcze jeden proces Serwer, który zarządza wszystkimi widelcami. Serwer pamięta stan każdego filozofa (a tym samym stan poszczególnych widelcy). Każdy filozof może myśleć lub być głodny, gdy skończył myślenie, ale oczekuje na widelce, lub jeść, jeśli ma oba widelce. Tak jak poprzednio filozof informuje o kluczowych zdarzeniach (chęć rozpoczęcia jedzenia i jego zakończenie) oraz przed rozpoczęciem jedzenia oczekuje na potwierdzenie --- tym razem od serwera. Ponieważ filozof wysyła do serwera na zmianę komunikaty zamawiające oraz komunikaty zwalniające, serwer pamiętając stan każdego filozofa będzie wiedział, czego dotyczy komunikat. Musi jednak być w nim zawarta, tak jak poprzednio, numer filozofa. Prowadzi to więc do następującego schematu komunikacyjnego:

Rysunek

A oto deklaracje buforów:

var
  serw: buffer; { do serwera }
  f: array [0..N-1] of buffer;

I proces filozofa:

process Filozof (i: 0..4);
var
  potw: integer;
begin
  repeat
    myśli;
    SendMessage (serw, i);   { komunikat z numerem filozofa oznaczający ChcęJeść }
    GetMessage (f[i], potw); { czeka na potwierdzenie }
    je;
    SendMessage (serw, i);   { komunikat z numerem filozofa oznaczający odkładamCię }
  until false
end;

Cała synchronizacja jest ukryta w procesie serwera:

process Serwer;
var
  stan: array [0..N-1] of (Myśli, Głodny, Je); 
  k: integer;

Wprowadźmy pomocniczą procedurę Sprawdź(k), której zadaniem jest sprawdzenie, czy k-ty filof jest głodny i czy można mu dać oba widelce. Procedura wysyła w takim przypadku potwierdzenie do filozofa o numerze k.

procedure Sprawdź (k: 0..N-1);
begin
  if (s[k] = Głodny) and 
           (s[(k-1) mod N) <> Je and 
           (s[(k+1) mod N) <> Je  then
  begin
    s[k] := je;
    SendMessage (f[k], k)   { potwierdzenie o dowolnej treści }
  end
end

Właściwa treść filozofa zaczyna się od inicjacji tablicy stanów poszczególnych filozofów:

begin
  for k := 0 to N-1 do
    stan[k] := Myśli;

W głównej pętli serwera sprawdzamy czy przyszło zamówienie czy zwolnienie i podejmujemy stosowne działania:

  repeat
    GetMessage (serw, k);
    if stan[k] = Myśli then   { jest to zamówienie }
    begin
      stan[k] := Głodny;
      Sprawdź (k)
    end else
    begin
      stan[k] := Myśli;
      Sprawdź ((k-1) mod N);        { być może można obudzić sąsiadów }
      Sprawdź ((k+1) mod N)
    end
   until false;
 end;