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.