so:sync_implementacja_semaforow

### 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.