Przy omawianiu złożonych zagadnień synchronizacji wygodnie jest posługiwać się narzędziem synchronizacji nazywanym semaforem (ang. semaphore). Semafor jest strukturą zawierającą zmienną typu całkowitego, której można nadać wartość początkową i do której można się odwoływać tylko za pośrednictwem dwu niepodzielnych operacji: P (hol. proberen, ang. wait, pol. czekaj) oraz V (hol. verhogen, ang. signal, pol. sygnalizuj). Definicja semafora przedstawia się nastepująco [1]:
poczekaj(S):        while S<=0 do nic;
                        S:=S-1;
zasygnalizuj(S):  S:=S+1;
Ważne jest, aby zmiany wartości semafora wykonywane za pomocą operacji poczekaj i zasygnalizuj uniemożliwiały sytuację, w której dwa procesy próbowałyby modyfikować wartość semafora. Dodatkowo, podczas operacji poczekaj(S), nie może wystąpić przerwanie w trakcie sprawdzania wartości zmiennej S (dopóki S<=0) oraz jej aktualizacji. Semafory stosuje się często przy rozwiązywaniu problemów sekcji krytycznej, której przydzielone jest kilka procesorów. Procesory te obsługują wspólny semafor mutex (ang. mutual exclusion), który zapewnia wzajemne wykluczanie kilku procesów tak, aby zapewnić dostęp tylko jednemu spośród nich. Organizacja każdego z procesów korzystających z semafora przedstawia się następująco [1]:
repeat
   poczekaj(mutex);
      ...
      sekcja krytyczna
      ...
   zasygnalizuj(mutex);
      ...
      reszta działań procesu
      ...
until false;
Semafory stosujemy także przy rozwiązywaniu problemów związanych z synchronizacją. Jeżeli na przykład chcielibyśmy, aby dwa procesy P-X i P-Y, zawierające odpowiednio rozkazy S-X i S-Y, wykonały się sekwencyjnie, tzn. w kolejności X, potem Y. Możliwa jest prosta realizacja takiego problemu, gdy wprowadzimy wspólną dla obu procesów zmienną synchronizacja, nadawszy jej wartość początkową "0". Zakładając, że dołączymy do procesów P-X i P-Y instrukcje:
P-X:

S-X;
sygnalizuj(synchronizacja);

P-Y:

czekaj(synchronizacja);
S-Y;

możliwe stanie się wykonanie najpierw kodu S-X, później S-Y, ponieważ dopóki zmienna synchronizacja wynosi "0", semafor czekaj blokuje wykonanie instrukcji S-Y. Wykonanie S-Y możliwe staje się dopiero po wykonaniu rozkazu sygnalizuj(synchronizacja). Obsługa semaforów wymaga aktywnego czekania (ang. busy waiting). Polega to na tym, że procesy chcąc dostać się do sekcji krytycznej, zajmowanej przez jakiś proces, zmuszone są do wykonywania pętli w sekcji wejściowej. Aktywne czekanie marnuje czas procesora, który mógłby wykonywać nieco ważniejsze zadania. Semafory tego typu nazywa się też wirującą blokadą (ang. spinlock).

Wirujące blokady w przypadku założenia, że czas oczekiwania procesu pod blokadą jest bardzo krótki, stają się bardzo użyteczne w środowiskach wieloprocesorowych. Ich zaletą jest fakt, że postój procesu pod semaforem nie wymaga przełączania kontekstu, który może trwać długo.

Nie trzeba jednak traktować aktywnego czekania jako niezniszczalnego. Aktywne czekanie można bowiem wyeliminować. Aby było to możliwe proces, który musiałby czekać aktywnie, powinien mieć możliwość zablokowania się (ang. block). Zablokowanie się procesu powoduje umieszczenie go w kolejce do danego semafora oraz zmianę stanu procesu na "czekanie", po czym wybierany jest do wykonania kolejny z procesów. Wznowienie działania procesu zablokowanego powoduje sygnał zasygnalizuj pochodzący od innego procesu. Wykonywana jest wtedy operacja budzenia (ang. wakeup), która zmienia stan procesu na "gotowość" [1]. Powoduje to przejście procesu do kolejki procesów gotowych do wykonania przez procesor.

Semafor, o którym tak już dużo napisaliśmy można zrealizować jako prosty rekord [1]:
type semaphore = record
                    wartosc: integer;
                    L: list of proces;
                 end;
Jak widzimy semafor składa się z dwóch pól: wartości całkowitej i listy procesów, które muszą czekać pod semaforem. Operacje na tak zdefiniowanym semaforze można przedstawić następująco [1]:
poczekaj(S): S.wartosc:=S.wartosc-1;
if S.wartosc<0 then begin
                       dodaj proces do S.L;
                       blokuj;
                    end;

zasygnalizuj(S): S.wartosc:=S.wartosc+1;
if S.wartosc<=0 then begin
                        uzuń proces P z S.L;
                        obudz(P);
                     end;
Tak zaimplementowane operacje poczekaj i zasygnalizuj nie eliminują całkowicie efektu aktywnego czekania, jednakże zapewniają usunięcie tego zjawiska z wejść do sekcji krytycznych programów użytkowych. Ma to ogromne znaczenie, gdyż sekcje krytyczne tych programów mogą zajmować dużo czasu lub być często zajęte. Aktywne czekanie w takich warunkach mogłoby być fatalnym posunięciem i zakończyłoby się dużym spadkiem wydajności systemu. Mówimy, że zbiór procesów jest w stanie zakleszczenia (ang. deadlock), gdy każdy proces w tym zbiorze oczekuje na zdarzenie, które może być spowodowane tylko przez inny proces z tego zbioru [1]. Dla semaforów zdarzeniem tym jest operacja zasygnalizuj.

Przykładem takiego zdarzenia są procesy Px i Py, które korzystają z semaforów A i B, o wartościach "1", których postać przedstawia się następująco:
Px:

poczekaj(A);
poczekaj(B);
   .
   .
   .
zasygnalizuj(A);
zasygnalizuj(B);

Py:

poczekaj(B);
poczekaj(A);
   .
   .
   .
zasygnalizuj(B);
zasygnalizuj(A);

W takiej sytuacji powstaje zakleszczenie, gdyż proces Px musi czekać na wykonanie operacji zasygnalizuj(A) przez proces Py, zaś Proces Py czeka na wykonanie przez Px rozkazu zasygnalizuj(B).

Kolejnym problemem związanym z semaforami jest głodzenie, czyli konieczność nieskończonego oczekiwania przez proces pod semaforem. Problem ten jest wynikiem niskiego priorytetu danego procesu. Proces jest ignorowany np. w wyniku dużego natłoku innych procesów, które mają wyższe przerwania. Najczęściej głodzenie pojawia się w przypadku użycia kolejki LIFO (ang. Last In First Out) jako listy procesów oczekujących do semafora [1].

NASTĘPNA