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

Semafory

Przykład. Pięciu filozofów. Wersja 1.

Popatrzmy teraz, jak za pomocą semaforów można zapisać różne wersje rozwiązań problemu pięciu filozofów. Zacznijmy od wersji najprostszej. Role widelców grają semafory binarne, przy czym semafor otwarty oznacza, że widelec jest dostępny, a semafor zamknięty, że widelcem ktoś już się posługuje. Każdy filozof najpierw bierze widelec po swojej lewej stronie, potem po stronie prawej:

var
  wid: array [0..4] of binary semaphore := (1, 1, 1, 1, 1); 

process Filozof (i: 0..4);
begin
  repeat
    Myśli;
    P (wid[i]);
    P (wid[(i+1) mod 5];
    Je;
    V (wid[i]);
    V (wid[(i+1) mod 5];
  until false
end;
   

Oczywiście z powodów już uprzednio omawianych ten program powoduje zakleszczenie filozofów.

Przykład. Pięciu filozofów. Wersja 2.

Przypomnijmy, że rozwiązanie poprawne polega na dopuszczeniu do stołu co najwyżej 4 filozofów. W tym celu do poprzedniego przykładu dodamy semafor ogólny lokaj zainicjowany na 4:

var
  lokaj: semaphore := 4;
  wid: array [0..4] of binary semaphore := (1, 1, 1, 1, 1); 

process Filozof (i: 0..4);
begin
  repeat
    Myśli;
    P (lokaj);
    P (wid[i]);
    P (wid[(i+1) mod 5];
    Je;
    V (wid[i]);
    V (wid[(i+1) mod 5];
    V (lokaj)
  until false
end;

Przykład. Pięciu filozofów. Wersja 3.

Spróbujmy jeszcze zapisać rozwiązanie, w którym filozofowie podnoszą jednocześnie oba widelce. Przypomnijmy, że taki algorytm może prowadzić do zagłodzenia filozofa przez jego sąsiadów. Zobaczmy jednak, jakiego rodzaju problemy techniczne występują przy zapisie tego rozwiązania za pomocą semaforów.

Po pierwsze wprowadzamy tablicę stanów poszczególnych filozofów:

stan: array [0..4] of (myśli, głodny, je) 
  := (myśli, myśli, myśli, myśli, myśli);
mutex: binary semaphore := 1;
furtka: array [0..4] of binary semaphore
  := (0, 0, 0, 0, 0);

Każdy filozof ma swój własny semafor furtka. Jest on początkowo zamknięty. Każdy filozof