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 sprawdza, czy może rozpocząć jedzenie i jeśli tak, to otwiera sobie ten semafor. Po zakończeniu jedzenia i odłożeniu widelców, filozof sprawdza, czy jego sąsiedzi są głodni i mają już komplet widelców. Jeśli tak, to ich budzi.

Procedura test zajmuje się sprawdzeniem, czy i-ty filozof może rozpocząć jedzenie:

procedure test (i: 0..4);
begin
  if stan[i] = głodny and 
           stan[(i+1) mod 5] <> je and
           stan[(i+4) mod 5] <> je then
  begin
    stan[i] := je;
    V (furtka[i]
  end
end; 

Treść procesu filozof wygląda następująco:

process Filozof (i:0..4);
begin
  repeat
    myśli;
    P(mutex);
    stan[i] := głodny;
    test (i);
    V(mutex);
    P (furtka[i]);
    je;
    stan[i] := myśli;
    test ((i+4) mod 5);
    test ((i+1) mod 5);
    V (mutex);
  until false
end