Semafor (informatyka)

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

Implementacja

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ć zrealizowana poprzez czasowe zawieszenie wywłaszczeń lub, co jest mniej pożądane, czasowe uniemożliwienie przerwań systemowych.

Etymologia nazw funkcji

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 P od Prolaag czyli probeer verlaag (spróbuj zmniejszyć) oraz V od verhoog (zwiększać).^[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

Załóżmy, że "zasoby" to stoliki w restauracji a "procesy" to jej klienci. "Semafor" jest reprezentowany przez kelnera, który jako jedyna osoba decyduje o udostępnianiu stolików. Kelner liczy w pamięci wolne stoliki (utables) i zawsze wie kogo umieścić jako pierwszego przy zwolnionym stoliku. Jest on bardzo zajęty i skoncentrowany i nikt nie może mu 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, kelner 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, kelner 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 któregoś ze stolików kelner ponownie wyliczy wartość utables=utables-1. Jeżeli wszystkie stoliki są zajęte (czyli utables=0), nowo przybywający goście muszą poczekać w kolejce na zwolnienie stolika.

Jeżeli klient zwolni stolik, kelner wyliczy w pamięci nową wartość utables=utables+1. Jeżeli kolejny gość czeka na stolik i przynajmniej jeden stolik jest dostępny, kelner 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.

Rodzaje semaforów

• binarny zwany też muteksem (mutex)^[4]
• ogólny^[4]
• rozdzielny (split semaphore)^[5]
• silny^[6]
• słaby^[6]
• z aktywnym czekaniem (busy-wait semaphore)^[7]
• z kolejką oczekujących^[8]
• ze zbiorem oczekujących^[7]

Zastosowania

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.

Przypisy

Bibliografia

• Zbigniew Czech: Wprowadzenie do obliczeń równoległych. Wyd. 2. Warszawa: Wydawnictwo Naukowe PWN, 2013. ISBN 978-83-01-17290-9.

Zobacz też

• sekcja krytyczna
• problem ucztujących filozofów
• wątek (informatyka)
• wielowątkowość, wielozadaniowość