==== Implementacja  semaforów ====

Podstawową wadą rozwiązań problemu wzajemnego wykluczania w rozwiązaniach
programowych i podanej uprzednio definicji semafora jest to, że wszystkie one
wymagają aktywnego czekania (ang. busy waiting). Podczas gdy jeden proces jest w
swojej sekcji krytycznej, pozostałe procesy usiłujące wejść do sekcji
krytycznych muszą nieustannie wykonywać instrukcję pętli w sekcji wejściowej. To
ciągłe wykonywanie pętli jest w oczywisty sposób kłopotliwe w rzeczywistym
systemie wieloprogramowym, w którym jeden procesor jest dzielony między wiele
procesów. Aktywne czekanie marnuje cykle procesora, które mogłyby być
produktywnie zużytkowane przez inne procesy. Semafor tego rodzaju bywa również
nazywany wirującą blokadą (ang. spinlock), ponieważ oczekujący z powodu
zamkniętego semafora proces "wiruje" w miejscu. Wirujące blokady są użyteczne w
systemach wieloprocesorowych. Zaletą tych blokad jest to, że jeśli proces musi
poczekać pod semaforem, to nie trzeba przełączać kontekstu, a przełączanie
kontekstu może zabierać sporo czasu. Jeśli więc przewiduje się, że czas
oczekiwania procesu będzie bardzo krótki, to wirujące blokady są pożyteczne.

Aby ominąć konieczność aktywnego czekania, można zmodyfikować semaforowe
operacje czekaj i sygnalizuj. Proces, który wykonuje operację czekaj i zastaje
niedodatnią wartość semafora, musi czekać. Jednakże zamiast czekać aktywnie,
proces może się zablokować (ang. block). Operacja blokowania umieszcza proces w
kolejce związanej z danym semaforem i powoduje przełą­czenie stanu procesu na
czekanie. Następnie sterowanie zostaje przekazane do planisty przydziału
procesora, który wybiera do wykonania inny proces.  Działanie procesu
zablokowanego pod semaforem S powinno zostać wznowione wskutek wykonania
operacji sygnalizuj przez jakiś inny proces. Wznowienie procesu następuje za
pomocą operacji budzenia (ang. wakeup), która zmienia stan procesu z oczekiwania
na gotowość. Proces przechodzi wówczas do kolejki procesów gotowych do
wykonania. (Procesor może, lecz nie musi, zostać przełączony z aktualnie
wykonywanego procesu na nowo przygotowany proces; zależy to od algorytmu
planowania procesora).  

Aby zrealizować semafor według tej definicji, określimy go jako rekord:

  type semaphore = record 
          wartość: integer;
                L: list of proces;
  end; 


Każdy semafor ma wartość całkowitą i listę procesów. Kiedy proces musi czekać
pod semaforem, wtedy dołącza się go do listy procesów. Operacja sygnalizuj usuwa
jeden proces z listy czekających procesów i budzi go. Operacje semaforowe można
teraz zdefiniować tak: 


   czekaj(S):
              S.wartość := S.wartość - 1;
              if S.wartość < 0 then
              begin
                  dołącz dany proces do S.L;
                  blokuj;
              end;
   sygnalizuj(S):
              S.wartość := S.wartość + 1;
              if S.wartość < 0 then 
              begin 
                  usuń jakiś proces P z S.L; 
                  obudź(P);
              end; 


Operacja blokuj (ang. block) wstrzymuje proces, który ją wywołuje. Operacja
obudź(P) (ang. wakeup) wznawia działanie zablokowanego procesu P. Operacje te są
dostarczane przez system operacyjny jako elementarne funkcje systemowe.  Zwróćmy
uwagę, że chociaż w klasycznej definicji semafora z aktywnym czekaniem wartość
semafora nie jest nigdy ujemna, w powyższej implementacji semafory mogą
przyjmować wartości ujemne. Jeśli wartość semafora jest ujemna, to jej moduł
określa liczbę procesów czekających na ten semafor. Wynika to ze zmiany porządku
instrukcji zmniejszania i sprawdzania wartości zmiennej w implementacji operacji
czekaj.  

Listę czekających procesów można łatwo zbudować, dodając pole dowią­zań
(łącznikowe) do bloku kontrolnego każdego procesu. Każdy semafor zawiera wartość
całkowitą i wskaźnik do listy bloków kontrolnych procesów. Jednym ze sposobów
dodawania i usuwania procesów z tej listy, gwarantują­cym ograniczone czekanie,
może być kolejka "pierwszy na wejściu - pierwszy na wyjściu" (FIFO), przy czym
semafor zawiera wskaźniki do początku i końca tej kolejki. Jednak w ogólnym
przypadku lista może być obsługiwana według dowolnej strategii tworzenia
kolejek. Poprawne użycie semaforów nie zależy od poszczególnych strategii
obsługi kolejek list semaforowych. 

Decydującym aspektem poprawnego działania semaforów jest ich niepodzielne
wykonywanie. Należy zagwarantować, że żadne dwa procesy nie wykonają operacji
czekaj ani sygnalizuj na tym samym semaforze w tym samym czasie.  Ten wymóg
należy do problemów dotyczących sekcji krytycznej i może być osiągnięty jednym
z dwu sposobów.  

W środowisku jednoprocesorowym (tj. gdy istnieje tylko jeden procesor) można po
prostu zabronić wykrywania przerwań podczas wykonywania operacji czekaj i
sygnalizuj. Schemat ten działa w środowisku jednoprocesorowym, bo od chwili
zablokowania przerwali nie mogą być przeplatane rozkazy z różnych procesów. Do
chwili przywrócenia przerwań, kiedy to planista mo­że znów przejąć nadzór nad
procesorem, działa tylko proces bieżący.  W środowisku wieloprocesorowym zakaz
wykrywania przerwań nie skutkuje.  Rozkazy z różnych procesów (wykonywane w
różnych procesorach) mogą ulegać dowolnym przeplotom. Jeśli nie ma żadnych
specjalnych rozkazów sprzętowych, to można zastosować dowolne z poprawnych
rozwiązań programowych problemu sekcji krytycznej. W tym przypadku sekcje
krytyczne będą się składały z procedur czekaj i sygnalizuj.  

Powinniśmy jednak zdawać sobie sprawę z tego, że za pomocą definicji  operacji
czekaj i sygnalizuj nie wyeliminowaliśmy całkowicie aktywnego czekania. W zamian
nastąpiło usunięcie aktywnego czekania z wejść do sekcji krytycznych w
programach użytkowych. Co więcej, udało się nam je ograniczyć wyłącznie do
sekcji krytycznych operacji czekaj i sygnalizuj., które są krótkie (dobrze
zakodowane nie powinny zajmować więcej niż około 10 rozkazów). Zatem sekcja
krytyczna jest rzadko kiedy zajmowana i aktywne czekanie zdarza, się rzadko, a
gdy już wystąpi, to trwa krótko. Zupełnie inna sytuacja występuje w programach
użytkowych, których sekcje krytyczne mogą być długie (minuty lub nawet godziny)
lub prawie zawsze zajęte. W tym przypadku aktywne czekanie byłoby skrajnie
nieekonomiczne.  
