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.
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;
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
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).
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.
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.
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
W literaturze pojawiają się też inne rodzaje semaforów. Omówmy najważniejsze z nich.
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:
Czekaj aż S >0; S := S - 1;
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.
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.
Czekaj aż S > n; S := 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 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