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:

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

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

1. 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

1. Wprowadzamy nowy, predefiniowany typ danych o nazwie buffer. Zmienne tego typu reprezentują bufory, do których wysyłamy i z których odbieramy komunikaty.
2. Zmienne buforowe mogą być deklarowane jedynie poza procesami. Jedynymi operacjami na nich są operacja wyłania komunikatu i operacja odebrania komunikatu.
3. Procesy nie mają dostępu do zmiennych globalnych, z wyjątkiem zmiennych buforowych.
4. Bufory są nieograniczone i działają jak kolejki proste.
5. 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.
6. 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.
7. Jeśli bufor jest pusty, to operacja GetMessage wstrzymuje wykonanie procesu, do momentu aż w buforze znajdą się jakieś dane.
8. 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
9. 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.
10. Zmienna m w powyższych operacjach może być dowolnego typu.
11. Operacje GetMessage i SendMessage na tym samym buforze są niepodzielne i wykluczające się nawzajem.
12. 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