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

From Studia Informatyczne

Spis treści

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

Taki podział należy przy tym rozważać na płaszczyźnie funkcjonalnej. Możemy na przykład mówić o modelu rozproszonym, choć procesy wykonują się na tym samym komputerze we wspólnej pamięci, która logicznie jest jednak podzielona na niezależne przestrzenie adresowe. Możemy także myśleć o modelu scentralizowanym, choć wspólna pamięć jest tak naprawdę realizowana za pomocą serwera segmentów pamięci dzielonej. Procesy nie muszą znać mechanizmów udostępniania tej pamięci. Z punktu widzenia procesu ważne jest jedynie to, czy istnieje możliwość odczytania/modyfikacji zmiennej współdzielonej, a nie sposób implementacji takiej zmiennej.

Model scentralizowany

Podstawową cechą modelu scentralizowanego jest możliwość stosowania zmiennych, które są dostępne do zapisu i odczytu przez wiele procesów. Takie zmienne będziemy nazywać zmiennymi dzielonymi lub zmiennymi współdzielonymi. Istnienie takich zmiennych w kontekście wykonujących się jednocześnie procesów może powodować pewne problemy. Trzeba na przykład odpowiedzieć na pytanie: co się dzieje, jeśli dwa procesy w tym samym momencie próbują zmodyfikować tę samą komórkę pamięci? Z reguły taki konflikt jest rozstrzygany przez układ sprzętowy, noszący nazwę arbitra pamięci, który w jakiś sposób szereguje takie żądania. Mamy więc gwarancję, że na skutek wykonania takiego "jednoczesnego" przypisania, zmienna dzielona będzie miała jedną z wartości, które próbowano ustawić, a nie jakąś przypadkową nieznaną nam wartość. Własność tę wykorzystaliśmy na poprzednich ćwiczeniach projektując algorytm Petersona.

Obecność zmiennych globalnych powoduje jednak często niezgodne z intuicją zachowania programów współbieżnych.

Zmienne globalne i problemy z nimi

Rozpatrzmy następujący program, złożony z dwóch identycznych procesów korzystających ze zmiennej współdzielonej x:

var
  x : integer;
process P;
var
  y, i: integer;
begin
  for i := 1 to 5 do
  begin
    y := x;
    y := y + 1;
    x := y
  end;
end;
process P;
var
  y, i: integer;
begin
  for i := 1 to 5 do
  begin
    y := x;
    y := y + 1;
    x := y
  end;
end;

Jak widać, każdy z procesów pięciokrotnie:

  1. Odczytuje zmienną globalną x kopiując jej wartość na swoją zmienną lokalną y.
  2. Zwiększa wartość zmiennej lokalnej o jeden.
  3. Zapisuje zmodyfikowaną wartość z powrotem na zmienną globalną.

Skutkiem jest zwiększenie zmiennej współdzielonej o pięć. I faktycznie, jeśli uruchomimy jeden z tych procesów, to tak się stanie. Podobnie jeśli uruchomimy drugi proces P po zakończeniu działania przez pierwszy proces --- wtedy zmienna zwiększy się o 10.

Co jednak zdarzy się, jeśli procesy uruchomimy współbieżnie? Powiedzmy, że początkową wartością zmiennej x jest 0. Jaka będzie wartość końcowa? Otóż okazuje się, że możemy otrzymać, w zależności od przeplotu akcji poszczególnych procesów, dowolną wartość między 5 a 10.


Jak pokazuje ten przykład, korzystając ze zmiennych współdzielonych trzeba zachować dużą ostrożność. Omawiany program byłby programem prawidłowo zwiększającym wartość zmiennej współdzielonej, jeśli całe wnętrze pętli było sekcją krytyczną i obliczało się z wzajemnym wykluczaniem (tak się dzieje po zaznaczeniu "Synchronizuj"). Mielibyśmy wówczas pewność, że od chwili odczytania wartości zmiennej x do chwili zapisania jej zmodyfikowanej wartości, żaden proces nie odczyta starej (tj.: jeszcze niezmodyfikowanej) wartości. Ponieważ taka niepodzielność wnętrza pętli wydaje się tu bardzo krytyczna, przeanalizujmy inny przykład.

Niepodzielność instrukcji wysokopoziomowych

var
  x : integer;
process P;
var
  i: integer;
begin
  for i := 1 to 5 do
    x := x + 1
end;
process P;
var
  i: integer;
begin
  for i := 1 to 5 do
    x := x + 1
end;

Tym razem procesy zmieniają wartość zmiennej współdzielonej za pomocą pojedynczej instrukcji wysokopoziomowej. Czy gwarantuje to, że zwiększenie jest realizowane niepodzielnie? Otóż nie, jak wiemy program w języku wysokiego poziomu jest tłumaczony na język wewnętrzy. Programista nie wie, a nawet nie powinien wiedzieć, czy instrukcja x := x + 1 jest realizowana jako jeden rozkaz maszynowy, czy też rozdzielona między rozkazy odczytu pamięci, załadowania wartości do rejestru, zwiększenia rejestru i zapisu do pamięci. Zatem z naszego punktu widzenia powyższy program ma te same właściwości co poprzedni. W dalszym ciągu nie wiemy, jaka będzie końcowa wartość zmiennej x.

Zapamiętajmy. Pisząc program współbieżny nie wolno nic założyć o niepodzielności instrukcji języka, w którym ten program tworzymy.

Mechanizmy synchronizacyjne

Model scentralizowany jest trudniejszy dla programisty. Trudniej jest zapewnić poprawność programu współbieżnego korzystającego ze zmiennych współdzielonych. Z tego powodu odłożymy go na później. Już teraz jednak zapowiemy, że wśród omawianych mechanizmów synchronizacyjnych znajdą się semafory, monitory i muteksy.

Model rozproszony

Model rozproszony stosuje się najczęściej wtedy, gdy procesy składające się na program współbieżny wykonują się na różnych komputerach. Nie ma wtedy fizycznie miejsca, w którym można by składować zmienne współdzielone. Z tego powodu procesy w tym modelu komunikują się wyłącznie poprzez wymianę komunikatów. Jak wspomnieliśmy poprzednio, będziemy także mówić o modelu rozproszonym w sytuacji, gdy procesy działają na tym samym komputerze, ale ich przestrzenie adresowe tworzą logicznie odrębne jednostki i domyślnie procesy nie mogą współdzielić zmiennych globalnych. Takie środowisko wykonania procesów udostępnia m.in. system operacyjny Unix.

W modelu rozproszonym możemy mówić o komunikacji synchronicznej i asynchronicznej. Różne są też modele przekazywania/adresowania komunikatów oraz identyfikacji procesów.

Komunikacja synchroniczna

Z komunikacją synchroniczną mamy do czynienia wtedy, gdy chcące się ze sobą skomunikować procesy są wstrzymywane do chwili, gdy komunikacja będzie się mogła odbyć. Omówmy ten schemat na przykładzie procesów, z których jeden (zwany nadawcą) chce wysłać komunikat, a drugi (odbiorca) chce komunikat odebrać.

  1. Jeśli odbiorca chce otrzymać komunikat od nadawcy, to wstrzymuje swoje działanie, aż nadawca będzie chciał go wysłać. Najczęściej oznacza to po prostu oczekiwanie do chwili, aż sterowanie w procesie nadawcy dojdzie do instrukcji wysyłania.
  2. Podobnie dzieje się, jeśli nadawca chce wysłać komunikat do odbiorcy. Czeka wówczas, aż odbiorca będzie gotowy do odebrania tego komunikatu i dopiero go nadaje.
  3. Zauważmy, że ponieważ procesy oczekują na siebie, to przesłanie komunikatu może się odbyć bezpośrednio między zainteresowanymi, tzn. nie potrzebny jest żaden bufor, który przechowa wysłany komunikat do momentu jego odbioru przez odbiorcę.

Przykładem komunikacji synchronicznej jest na przykład rozmowa telefoniczna. Nadawca przekazuje swój komunikat dopiero wówczas, gdy odbiorca chce go wysłuchać. Podobnie sytuacja wygląda na tradycyjnym wykładzie z programowania współbieżnego, gdy wykładowca przekazuje komunikaty mając nadzieję, że docierają one bezpośrednio do odbiorców.

Możliwe są również inne schematy komunikacji synchronicznej, w której bierze udział wiele procesów jednocześnie, nie ograniczając się przy tym jedynie do przesyłania komunikatów.

Komunikacja asynchroniczna

Komunikacja asynchroniczna nie wymaga współistnienia komunikujących się procesów w tym samym czasie. Polega na tym, że nadawca wysyła komunikat nie czekając na nic. Komunikaty są buforowane w jakimś miejscu (odpowiada za to system operacyjny lub mechanizmy obsługi sieci) i stamtąd pobierane przez odbiorcę.

Mamy więc następujący schemat:

  1. Nadawca wysyła komunikat nie czekając na nic. Komunikat wędruje do bufora.
  2. Odbiorca odbiera komunikat z bufora. Jeśli bufor jest pusty, to odbiorca jest wstrzymywany (wersja blokująca) lub przekazuje w wyniku błąd (wersja nieblokująca).

Przykładem komunikacji asynchronicznej są wykłady zdalne, które właśnie czytasz. Nadawca - wykładowca umieścił komunikaty w buforze - Internecie, nie czekając na gotowość odbiorcy - studenta do ich odbioru.

Modele przekazywania komunikatów

W modelu rozproszonym istnieje też wiele sposobów przekazywania komunikatów.

  1. Komunikat może być przeznaczony dla konkretnego procesu. Nadawca zna nazwę odbiorcy, a odbiorca zna nazwę nadawcy. Mówimy wtedy o identyfikacji symetrycznej
  2. Komunikat może być przeznaczony dla konkretnego procesu. Jedna ze stron zna nazwę procesu, druga nie wie kogo obsługuje. Mówimy wtedy o identyfikacji asymetrycznej. Jest to model charakterystyczny dla architektury klient-serwer.
  3. Komunikat może być wysyłany po kanale komunikacyjnym. Wysyłający zna nazwę kanału, ale nie wie, do kogo trafi komunikat, bo nie musi wiedzieć z kim jest ten kanał połączony.
  4. Komunikat może być wstawiany do konkretnego bufora, z którego może go odebrać dowolny proces.

Komunikacja asynchroniczna

W ciągu dalszych dwóch wykładów zajmiemy się modelem asynchronicznym. Rozpatrzymy prosty schemat z udziałem bufora i nieco bardziej złożony mechanizm umożliwiający stosowanie tzw. wyboru selektywnego. Zilustrujemy ten mechanizm konkretnymi narzędziami dostępnymi w środowisku Unix.

Cechy komunikacji asynchronicznej

Przypomnijmy zatem najważniejsze cechy komunikacji asynchronicznej:

  1. Wysyłanie komunikatu nie wstrzymuje nadawcy (z pewnymi wyjątkami).
  2. Wysłane, ale jeszcze nieodebrane komunikaty znajdują się w buforze.
  3. Bufor może być nieograniczony (abstrakcyjnie) lub ograniczony. Proces próbujący umieścić komunikat w buforze pełnym może:
    • być wstrzymywany do chwili aż w buforze będzie miejsce (wersja blokująca)
    • wracać z funkcji wysyłającej natychmiast z sygnalizacją błędu
  4. Próba odebrania komunikatu z bufora pustego kończy się:
    • wstrzymaniem procesu (wersja blokująca)
    • błędem (wersja nieblokująca)

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ść.


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 widelców 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 widelców, 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.

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. Jeśli 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 widelców). 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.

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;

Tym razem dało się nam uniknąć zakleszczenia. Ale ... No właśnie, mamy rozwiązanie, w którym filozofowie podnoszą oba widelce na raz. Jak widzieliśmy to poprzednio, możemy w ten sposób doprowadzić do zagłodzenia filozofa. Zatem to rozwiązanie jest również niepoprawne.

Pięciu filozofów. Wersja 4.

Powróćmy do pierwszej wersji rozwiązania (tej z zakleszczeniem), ale wprowadźmy dodatkowo "bilety do stołu". Filozof, który zechce jeść, musi najpierw otrzymać jeden z czterech (nie pięciu!) biletów do stołu. Potem postępuje tak jak w rozwiązaniu pierwszym.

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

Program główny:

begin
  for i := 1 to N-1 do
    SendMessage (bilety, m);
  for i := 0 to N-1 do
    SendMessage (widelec[i], m);
  cobegin
    for i := 0 to N-1 do
      Filozof (i)
  coend
end.

Tym razem otrzymujemy rozwiązanie poprawne. Zakleszczenia unikamy, gdyż przy stole może być co najwyżej czterech filozofów jednocześnie. Zatem na pewno któryś z nich otrzyma dwa widelce i będzie mógł jeść.

Zwróćmy uwagę, że taka modyfikacja nie zadziałałaby w przypadku poprzedniego rozwiązania. W przeplocie prowadzącym do zagłodzenia bierze udział bowiem trzech filozofów.


Implementacje tego mechanizmu w systemie Unix

Jak wspomnieliśmy na początku, wprowadzona tu notacja jest abstrakcją rzeczywistych mechanizmów komunikacji asynchronicznej dostępnych na różnych platformach sprzętowych i pod różnymi systemami operacyjnymi. Przyjrzyjmy się teraz niektórym mechanizmom komunikacji asynchronicznej dostępnych dla platformy uniksowej.

Jednym z mechanizmów są łącza nienazwane (ang. pipe). Za pomocą łączy nienazwanych mogą komunikować się ze sobą spokrewnione procesy. Łącza nienazwane to po prostu bufory utrzymywane przez system operacyjny. Są one ograniczone i pojemność każdego z nich wynosi co najmniej 4KB. Odpowiednikiem operacji SendMessage(b, m) jest funkcja systemowa

write (b, m, sizeof(m)),

przy czym b jest deskryptorem przeznaczonym do zapisu do uprzednio utworzonego łącza. Wszystkie właściwości funkcji SendMessage są zachowywane przez funkcję systemową write do łącza. Mamy więc gwarancję niepodzielności, nieblokujące działanie w sytuacji, gdy komunikat mieści się w łączu, dyscyplinę kolejki prostej. Różnice w obsłudze łącza ujawniają się przy próbie zapisu do łącza, gdy komunikat nie mieści się w nim w całości. Wtedy nadawca jest wstrzymywany (z pewnymi wyjątkami, szczegóły na ćwiczeniach). Odpowiednikiem funkcji GetMessage (b, m) jest funkcja systemowa

read (b, m, sizeof(m))

przy czym b jest deskryptorem przeznaczonym do odczytu z uprzednio utworzonego łącza. I tak jak w przypadku GetMessage funkcja systemowa read powoduje wstrzymanie procesu wykonującego ją, jeśli łącze jest puste.

Tak jak w przypadku abstrakcyjnej notacji, komunikacja za pomocą łączy nakłada na programistę obowiązek dbania o zgodność typów komunikatów wysyłanych i odbieranych. W przypadku łączy komunikat to po prostu strumień bajtów, który programista interpretuje w dogodny dla siebie sposób.

Oczywiście użycie łączy wymaga odpowiednich technicznych zabiegów, na przykład utworzenia go za pomocą funkcji systemowej pipe(fd), której wynikiem jest para deskryptorów fd, z których jeden służy do zapisywania do łącza, a drugi do odczytu z niego. Istnieją też pewne ograniczenia, np. nie można zapisywać do łącza, które nie jest przez nikogo otwarte do odczytu. Gdyby pominąć jednak wszystkie technikalia, to programowanie za pomocą łączy przypomina programowanie za pomocą mechanizmu abstrakcyjnego.

Podobnym do łączy nienazwanych mechanizmem dostępnym w środowisku uniksowym jest mechanizm łączy nazwanych. Tak jak w przypadku łączy nienazwanych takie łącza należy najpierw utworzyć (funkcja mkfifo). Następnie korzysta się z nich za pomocą funkcji systemowych read i write. W przypadku stosowania łączy nazwanych istnieją dodatkowe możliwości synchronizacji procesów na etapie otwierania łącza do odczytu i zapisu.

Trzecim popularnym mechanizmem komunikacji asynchronicznej stosowanym w systemie Unix są kolejki komunikatów. I znów są to bufory utrzymywane przez system operacyjny, do których procesy mogą zapisywać komunikaty (funkcja systemowa sndmsg) i z których komunikaty odbierają (funkcja getmsg). I tak jak poprzednio, są to kolejki komunikatów, choć istnieje również możliwość traktowania ich jak kolejek priorytetowych lub wręcz wyboru selektywnego - komunikaty mogą mieć typy, po których dokonuje się selekcji. Funkcja wysłania komunikatu w normalnych warunkach jest nieblokująca, a funkcje odbierająca wstrzymuje proces usiłujący pobrać coś z pustej kolejki. W odróżnieniu od łączy odbiór i wysyłanie komunikatów odbywa się tu jednak nie na poziomie strumieni bajtów, lecz całych komunikatów.