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;