Semafor
chroniona zmienna lub abstrakcyjny typ danych, który stanowi klasyczną metodę kontroli dostępu przez wiele procesów do wspólnego zasobu w środowisku programowania równoległego. Semafory zostały po raz pierwszy opisane przez Edsgera Dijkstrę jako istotne rozwinięcie algorytmu Dekkera.
Typowy semafor implementowany jest jako zmienna typu całkowitego. Semafory dzieli się na binarne i zliczające. Semafor binarny może przyjmować wartości całkowite ze zbioru {0, 1}, zliczający
również większe niż 1. Semafor zliczający jest licznikiem zestawu dostępnych zasobów. Każdy z nich może być zastosowany, by zapobiec wystąpieniu zjawiska hazardu lub zakleszczenia (chociaż nie w każdej sytuacji są w stanie wyeliminować te problemy, co ilustruje problem ucztujących filozofów).
Spis treści [ukryj]
1 Implementacja
2 Etymologia nazw funkcji
3 Analogia semafora zliczajÄ…cego
4 Zastosowania
5 Zobacz też
6 Przypisy
Implementacja[edytuj | edytuj kod]

Semafory zliczające są dostępne poprzez stosowanie operacji analogicznych do poniższych przykładów napisanych w Pascalu. Procedura V inkrementuje semafor S, natomiast procedura P dekrementuje go:
procedure V (S : Semaphore);
begin
(* Operacja atomowa: inkrementacja semafora *)
S := S + 1;
end;

(* Operacja atomowa: dekrementacja semafora *)
procedure P (S : Semaphore);
begin
(* Cała operacja jest atomowa *)
repeat
Wait();
until S > 0;
S := S - 1;
end;
Wartość semafora S to liczba jednostek zasobu, na które nie zgłoszono żądania. Jeżeli istnieje tylko jeden taki zasób, semafor binarny jest używany jako zwykła flaga true/false. Operacja P oczekuje i zasypia, dopóki zasób kontrolowany przez semafor nie stanie się dostępny, gdy natychmiast zgłaszane jest żądanie oczekującego zasobu. Operacja V jest odwrotna: zwalnia ponownie zasób po tym, jak proces przestał go używać.
Koncepcja semafora liczącego może zostać rozszerzona poprzez możliwość zażądania lub zwrócenia więcej niż jednej jednostki od semafora
technika implementowana w Uniksie. Zmodyfikowane operacje V i P będą wyglądały następująco:
procedure V (S : Semaphore; I : Integer);
begin
S := S + I (* operacja atomowa *)
end;

procedure P (S : Semaphore; I : Integer);
begin
(* cała operacja jest atomowa *)
repeat
Wait()
until S >= I;
S := S - I
end;
Żeby uniknąć zagłodzenia, semafor może mieć połączoną kolejkę procesów (zwykle typu FIFO). Jeżeli proces wykonuje operację P na semaforze, który ma wartość 0, proces jest dodawany do kolejki semafora. Kiedy inny proces inkrementuje semafor przez wykonanie operacji V i w kolejce znajdują się inne procesy, jeden z nich jest usuwany z kolejki i wznawia działanie. Kiedy procesy mają inne priorytety, kolejka może być uporządkowana według priorytetów, tak że proces o najwyższym priorytecie jest zabierany z kolejki jako pierwszy.
Aby zagwarantować, że dwa lub więcej procesów nie zmodyfikuje jednocześnie tego samego semafora, operacje, które faktycznie inkrementują lub dekrementują semafor, są określane jako atomowe, co oznacza, że nie powinny zostać przerwane, tak jak poprzez wywłaszczenie. To wymaganie może zostać spełnione poprzez używanie instrukcji maszynowej, która jest w stanie czytać, modyfikować i zapisywać semafor w pojedynczej operacji. Pod nieobecność takiej instrukcji sprzętowej operacja atomowa może zostać zrealizowane poprzez czasowe zawieszenie wywłaszczeń lub, co jest mniej pożądane, czasowe uniemożliwienie przerwań systemowych.
Etymologia nazw funkcji[edytuj | edytuj kod]

Operację wait oznacza się również literą P, a signal literą V, które zwykle są kojarzone z niderlandzkimi słowami: passeren (przejść), proberen (próbować), vrijgeven (zwolnić), verhoog (zwiększać). Jednakże sam Dijkstra użycie liter P i V wyjaśniał nieco inaczej[1]. W Algolu 68, jądrze Linux[2] i w niektórych anglojęzycznych książkach operacje P i V są nazwane, odpowiednio, down i up. W praktyce inżynierii oprogramowania są często nazywane wait i signal, acquire i release (używane w standardowej bibliotece Java[3]), lub pend i post. Czasami bywają też nazywane procure i vacate, aby były zgodne z oryginalnymi holenderskimi inicjałami.
Analogia semafora zliczajÄ…cego[edytuj | edytuj kod]

Załóżmy, że "zasoby" to stoliki w restauracji a "procesy" to jej klienci. "Semafor" jest reprezentowany przez maître dÅ‚hôtel, która jako jedyna osoba decyduje o udostÄ™pnianiu stolików. Maître dÅ‚hôtel liczy w pamiÄ™ci wolne stoliki (utables) i zawsze wie kogo umieÅ›cić jako pierwszego przy zwolnionym stoliku. Jest ona bardzo zajÄ™ta i skoncentrowana i nikt nie może jej przeszkadzać w trakcie wykonywania obowiÄ…zków.
Kiedy restauracja rozpoczyna dziaÅ‚alność bÄ™dzie poczÄ…tkowo pusta. Innymi sÅ‚owy "wartość" "semafora" bÄ™dzie równa liczbie stolików (tables) w restauracji (czyli utables=tables). Kiedy ktoÅ› przybywa, maître dÅ‚hôtel umieÅ›ci go (lub jÄ…) przy stoliku i zmniejszy w pamiÄ™ci liczbÄ™ wolnych stolików (utables=utables-1). Teraz "wartość" "semafora" jest równa liczbie stolików w restauracji minus 1.
Jeżeli wielu klientów przybÄ™dzie jednoczeÅ›nie, maître dÅ‚hôtel ulokuje ich przy stolikach w kolejnoÅ›ci przybycia zakÅ‚adajÄ…c, że na sali znajduje siÄ™ wystarczajÄ…ca liczba stolików, aby zmieÅ›cić wszystkich (utables>0). PrzybywajÄ…cy goÅ›cie z rezerwacjami mogÄ… zostać ulokowani przy stolikach przed innymi, którzy nie majÄ… rezerwacji, gdyż majÄ… przed nimi pierwszeÅ„stwo. Po zajÄ™ciu każdego ze stolików maître dÅ‚hôtel ponownie wyliczy wartość utables=utables-1. Jeżeli wszystkie stoliki sÄ… zajÄ™te (czyli utables=0), nowo przybywajÄ…cy goÅ›cie muszÄ… poczekać na zwolnienie jakiegoÅ› stolika.
Jeżeli któryÅ› z nich zwolni stolik, maître dÅ‚hôtel wyliczy w pamiÄ™ci nowÄ… wartość utables=utables+1. Jeżeli kolejny gość czeka na stolik i przynajmniej jeden stolik jest dostÄ™pny, maître dÅ‚hôtel ulokuje jego/jÄ… przy tym stoliku i ponownie wyliczy nowÄ… wartość utables=utables-1. Ostatecznie wszyscy goÅ›cie opuszczÄ… lokal i kolejne obliczenia wartoÅ›ci utables dadzÄ… wartość utables=tables
restauracja jest znowu pusta.
Zastosowania[edytuj | edytuj kod]

Najczęstszym zastosowaniem jest synchronizacja dostępu do zasobów systemowych współdzielonych przez kilka zadań, aby zapobiec problemom wynikającym z prób jednoczesnego dostępu i modyfikacji danego zasobu.
Semafory są zwykle implementowane w obszarze jądra systemu operacyjnego. Pozwala to na zaawansowaną obsługę zadań chcących uzyskać dostęp do zasobu:
wstrzymywanie ich do czasu zwolnienia semafora powiÄ…zanego z danym zasobem,
wznowienie pracy zadania oczekujÄ…cego na semaforze,
utrzymywanie semafora nawet po zakończeniu zadania, które go utworzyło.
Semafory pozostają w powszechnym użyciu przez języki programowania, które nie wspierają wewnętrznie innych form synchronizacji. Są one prymitywną formą synchronizacji w wielu systemach operacyjnych. W rozwoju języków programowania istnieje jednak trend zmierzania do bardziej ustrukturyzowanych form synchronizacji, takich jak monitory (choć te zaawansowane struktury zwykle korzystają także z semaforów). Poza nieskutecznym radzeniem sobie z problemem zakleszczenia, semafory także nie chronią programisty przed popełnianiem prostych błędów takich jak pobieranie semafora, który już jest trzymany przez ten sam proces i zapominanie o zwolnieniu semafora, który został pobrany.