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

From Studia Informatyczne

Spis treści

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

Semafory w systemie Unix

System operacyjny Unix oferuje implementację semaforów w ramach pakietu InterProcess Communication (IPC). Funkcjonalność semaforów uniksowych znacznie wykracza poza klasyczne funkcje. Przede wszystkim operacje podnoszenia i opuszczania semaforów można wykonywać nie tylko o jedną jednostkę, ale o dowolną wartość. Abstrahując od rzeczywistego sposobu zapisu operacji na semaforach w języku C, oznaczmy operacje zwiększenia i zmniejszenia semafora uniksowego S o n przez odpowiednio V(S, n) i P (S, n).

Operacja V(S, n) jest nieblokująca. Proces zawsze może ją wykonać. Operacja P(S, n) zatrzymuje proces, jeśli aktualna wartość semafora jest mniejsza niż S, a zmienna semaforowa nie zmienia się. Dopiero gdy proces doczeka się na wartość co najmniej n, to zmniejsza wartość semafora o n i kończy wykonanie operacji P(S, n).

Przypuśćmy, że aktualną wartością zmiennej semaforowej jest m. Przypuśćmy, że pewien proces oczekuje na wykonanie operacji P (S, n) (bo m < n). Jeśli teraz inny proces wywoła operację P(S, k), przy k < m, to wykona on operację P(s, k) bez zawieszania. Taka implementacja może prowadzić do głodzenia procesów oczekujących na operacji P (S, n) z dużym n.

Dodatkową operacją, którą można wykonywać na semaforach uniksowych jest operacja oczekiwania aż semafor będzie miał wartość 0. Oznaczmy tę operację przez Z(S).

Zestawy semaforów i jednoczesne operacje na nich

Semafory uniksowe występują w zestawach złożonych z jednego lub więcej semaforów. Unix umożliwia wykonywanie jednoczesnych operacji na semaforach należących do tego samego zestawu. Takie jednoczesne operacje będziemy w dalszym ciągu zapisywać ujmując je w nawiasy kwadratowe. Semantyka operacji jednoczesnych [op(1), op(2), ..., op(n)] jest następująca.

System operacyjny próbuje wykonać operacje w kolejności op(1), op(2), ..., op(n). Jeśli i-ta operacja nie powoduje zawieszenia procesu, to przechodzi do wykonania operacji i+1. Jeśli jednak i-ta operacja powoduje wstrzymanie procesu, to system anuluje już wykonane operacje op(1), ..., op(i-1) przed zawieszeniem procesu. Z punktu widzenia procesu efekt jest taki, jakby zostały wykonane wszystkie operacje albo żadna. Po obudzeniu proces ponownie próbuje wykonać wszystkie operacje od op(1) do op(n).

Z powyższego opisu wynika, że kolejność operacji przeznaczonych do jednoczesnego wykonania jest istotna. Popatrzmy na przykład. Operacja [V(S, 1), P(S, 1)] jest nieblokująca: najpierw bowiem otwieramy semafor, a potem próbujemy przejść pod otwartym semaforem, co się zawsze uda. Oczywiście taka operacja nie ma żadnego efektu na semafor S. Z kolei [P(S, 1), V(S, 1)] również nie zmieni wartości semafora S, ale wstrzyma proces, jeśli semafor jest zamknięty!

Operacje P i Z na semaforach uniksowych mają także swoje nieblokujące wersje. Polegają one na tym, że zamiast wstrzymywać proces, kończą się one natychmiast przekazując informacje o niepowodzeniu. Ponadto istnieje możliwość ustawienia wartości semafora i odczytania go oraz sprawdzenia, ile procesów oczekuje na poszczególnych operacjach.

Przykład. Czytelnicy i pisarze. Wersja 1

Zilustrujmy działanie jednoczesnych operacji semaforowych do rozwiązania problemu czytelników i pisarza. Przypuśćmy, że mamy zestaw semaforów złożony z dwóch semaforów: CZYT oraz PIS. Semafor CZYT zlicza czytelników przebywających w czytelni, a semafor PIS --- pisarzy w czytelni. Czytelnik przed wejściem do czytelni powinien niepodzielnie upewnić się, że nie ma w niej pisarza i zwiększyć licznik czytelników. Prowadzi to do następującego kodu:

'process Czytelnik;
begin
  repeat
    własne_sprawy;
    [Z(PIS), V(CZYT)]
    czytanie;
    P(CZYT)
  until false
end

Proces pisarza musi upewnić się, że w czytelni nie ma nikogo i dopiero wówczas może do niej wejść zwiększając licznik pisarzu:

'process Pisarz;
begin
  repeat
    własne_sprawy;
    [Z(PIS), Z (CZYT), V(PIS)]
    czytanie;
    P(PIS)
  until false
end

Niestety, przedstawione rozwiązanie, choć ma własność bezpieczeństwa, nie gwarantuje żywotności pisarzy. Może się bowiem zdarzyć, że ciągły napływ czytelników spowoduje, że czytelnia nigdy nie będzie pusta i pisarze będą w nieskończoność oczekiwać na dostęp do czytelni.

Przykład. Czytelnicy i pisarze. Wersja 2

Spróbujmy poprawić rozwiązanie. Niech semafor CZYT w dalszym ciągu zlicza czytających czytelników. Zamiast semafor zliczającego pisarzy tym razem zastosujemy semafor POCZ chroniący dostęp do poczekalni. Każdy proces musi najpierw przejść przez poczekalnie. Proces pisarza po wejściu do poczekalni blokuje do niej dostęp, czeka aż wszyscy czytający czytelnicy opuszczą czytelnię, rozpoczyna pisanie i po jego zakończeniu zwalnia dostęp do poczekalni. Początkowo semafor CZYT jest równy zero, a semafor POCZ jest inicjowany na 1.

'process Pisarz;
begin
  repeat
    własne_sprawy;
    P(POCZ);
    Z(CZYT);
    pisanie;
    V(POCZ)
  until false
end

Proces czytelnika wchodzi do poczekalni nie blokując dostępu do niej dla innych i rozpoczyna czytanie zwiększając licznik czytelników. Po wyjściu z czytelni zmniejsza semafor CZYT.

'process Czytelnik;
begin
  repeat
    własne_sprawy;
    [P(POCZ), V(POCZ), V(CZYT)]
    czytanie;
    P(CZYT)
  until false
end

Inne rodzaje semaforów

W literaturze pojawiają się też inne rodzaje semaforów. Omówmy najważniejsze z nich.

Semafory dwustronnie ograniczone

Inspiracją dla semaforów dwustronnie ograniczonych był problem producenta i konsumenta. Semafory dwustronnie ograniczone charakteryzują się symetrycznymi operacjami P i V. Obie operacje mogą spowodować wstrzymanie procesu. Dodatkowym parametrem semafora dwustronnie ograniczonego jest maksymalna wartość k, jaką może przyjmować zmienna semaforowa.

Operacje na semaforze dwustronnie ograniczonym definiuje się w następujący sposób:

  • P(S):
 Czekaj aż S >0;
 S := S - 1;
  • V(S):
 Czekaj aż S < k;
 S := S + 1

Oczywiście założenia dotyczące niepodzielności i ich wzajemnym wykluczaniu się pozostają w mocy.

Semafory dwustronnie ograniczone nie zwiększają mocy wyrazu zwykłych semaforów --- można je zaimplementować za pomocą dwóch semaforów ogólnych.

Semafory uogólnione

Semafor uogólniony w odróżnieniu od semafora ogólnego umożliwia wykonywanie operacji P i V o większą liczbę jednostek, a niekoniecznie o 1.

  • P(S, n):
 Czekaj aż S > n;
 S := S - n;
  • V(S, n):
 S := S + n

Jak już wspomnieliśmy przy omówieniu semaforów uniksowych, dość ostrożnie należy podchodzić do implementacji takich semaforów ze względu na możliwość głodzenia procesów, próbujących wykonać operację P(S, n) z dużą wartością n. Implementację gwarantującą żywotność przedstawiamy na ćwiczeniach.

Semafory Agerwali

Semafory Agerwali wprowadzają jednoczesne operacje na zwykłych semaforach, przy czym wykonanie operacji zamykania zależy od stanu innych semaforów. Operacja P jako argument bierze dwie grupy semaforów:

P(S1, S2, ..., Sn; T1, T2, ..., Tm):
 Czekaj aż wszystkie semafory S będą otwarte, a wszystkie semafory T zamknięte;
 for i := 1 to n do
   Si := Si - 1

Operacja V podnosi wszystkie przekazane jej jako argumenty semafory:

V(S1, ..., Sn): 
 for i := 1 to n do
   Si := Si + 1
 

Motywacją dla semaforów Agerwali było m.in. wprowadzenie priorytetowego dostępu do zasobów. Przypuśćmy, że w systemie znajduje się jeden zasób, z którego korzystają procesy P(1..N). Jednocześnie z zasoby może korzystać co najwyżej jeden proces. Jeśli zasób staje się wolny, a oczekuje na niego wiele procesów, to pierwszeństwo ma ten o mniejszej wartości parametru.

Rozwiązanie polega na wykorzystaniu semaforów Agerwali. Z każdym procesem związany jest jego prywatny semafor chce. Jego podniesienie oznacza, że proces chce skorzystać z zasobu i jeszcze go nie otrzymał. Oprócz tego korzystamy z semafora mutex gwarantującego wyłączny dostęp do zasobu:

var
  chce: array [1..N] of binary semaphore 
    := (0, 0, ..., 0);
  mutex: binary semaphore := 1;

Tekst procesu możemy wówczas zapisać następująco:

process P (i: 1..N);
begin
  repeat
    własne_sprawy;
    V (chce[i]);
    P (mutex; chce[1], ..., chce[i-1]);
    P (chce[i]);
    sekcja_krytyczna;
    V (mutex)
  until false
end