Semafor, jako mechanizm synchronizacji procesów, został zaproponowany przez Dijkstrę.
Semafor jest zmienną całkowitą, która z logicznego punktu widzenia (z punktu widzenia aplikacji) przyjmuje wartości nieujemne (≥0) lub — w przypadku semaforów binarnych — logiczne. Zmienna semaforowa musi mieć nadaną początkową wartość (oczywiście nieujemną).
Po nadaniu początkowej wartości zmiennej semaforowej można na niej wykonywać tylko dwa rodzaje operacji:
P — opuszczanie semafora (hol. proberen),
V — podnoszenie semafora (hol. verhogen).
Operacja opuszczania powoduje zmniejszenie wartości zmiennej semaforowej, a operacja podnoszenia jej zwiększenie. Wykonując operację semaforową, proces może zastać zablokowany (przejść w stan oczekiwania). Typowym przypadkiem jest blokowanie w operacji opuszczania semafora. Operacja opuszczania nie zakończy się do czasu, aż wartość zmiennej semaforowej będzie na tyle duża (być może zostanie zwiększona w międzyczasie), że zmniejszenie jej wartości w wyniku tej operacji nie spowoduje przyjęcia wartości ujemnej. W przypadku semaforów dwustronnie ograniczonych blokowanie może wystąpić również w przypadku podnoszenia semafora.
Typowym semaforem jest semafor binarny, który może mieć dwa stany: true (podniesiony otwarty) i false (opuszczony zamknięty). Wielokrotne podnoszenie takiego semafora nie zmieni jego stanu — skutkiem będzie stan otwarcia. W niektórych rozwiązaniach przyjmuje się, że próba podniesienia otwartego semafora sygnalizowana jest błędem.
W przeciwieństwie do semafora binarnego, semafor ogólny „pamięta” liczbę operacji podniesienia. Przy wartości początkowej 0 można zatem bez blokowania procesu wykonać tyle operacji opuszczenia semafora, ile razy został on wcześniej podniesiony. Stąd określenie — semafor zliczający.
Semafor uogólniony (semafor zliczający) można zwiększać lub zmniejszać o dowolną podaną wartość pod warunkiem, że w wyniku zmniejszenia zmienna semaforowa nie osiągnie wartości ujemnej. Jeśli zatem wartość parametru, o którą ma być zmniejszona zmienna semaforowa jest większa od wartości tej zmiennej, następuje zablokowanie procesu.
Dla semafora dwustronnie ograniczonego (semafor ogólny) definiuje się górne ograniczenie, po osiągnięciu którego następuje blokowanie procesu również w operacji podnoszenia.
W implementacji na poziomie maszynowym semafor ogólny jest zmienną całkowitą nieujemną (teoretycznie nieograniczoną od góry), na której wykonywane są operacje P i V. Takie podejście do implementacji wynika zatem bezpośrednio z definicji.
W celu wyeksponowania przepływu sterowania i wskazania instrukcji, które muszą być wykonane niepodzielnie, implementację operacji P można przedstawić następująco:
procedure P(var s : Semaphore)begin próbuj: zablokuj_obsługę_przerwań; if s = 0 then begin odblokuj_obsługę_przerwań; goto próbuj end; else begin s := s – 1; odblokuj_obsługę_przerwań end; end;
Ciąg instrukcji pomiędzy zablokowaniem, a odblokowaniem przerwań wykonywany jest niepodzielnie. Istotne jest zatem niepodzielne sprawdzenie i zmniejszenie wartości zmiennej s (pod warunkiem, że jest większa od 0).
Skok do linii zaetykietowanej jako próbuj oznacza aktywne czekanie.
Zasada implementacji jest dokładnie taka sama, jak w przypadku semafora ogólnego, różnią się tylko wartości zmiennej s.
Celem implementacji na poziomie systemu operacyjnego jest zlikwidowanie aktywnego czekania i związanego z tym marnotrawstwa czasu procesora.
Zamiast permanentnego testowania zmiennej semaforowej, stan procesu zmieniany jest na oczekujący, w związku z czym planista przydziału procesora nie uwzględnia go, wybierając proces do wykonania. Z semaforem wiąże się kolejka procesów oczekujących na jego podniesienie. W definicji struktury danych na potrzeby semafora użyto abstrakcyjnej konstrukcji list of. Kolejkę taką można zbudować w oparciu o odpowiednie pola do wskazywania procesów, przechowywane w deskryptorze procesu. W strukturze semaforowej jest wówczas tzw. głowa listy, czyli wskaźnik na deskryptor pierwszego z oczekujących procesów.
W samej implementacji operacji opuszczania interesujący jest sposób modyfikacji pola wartość struktury semaforowej. Jest ono zmniejszane bezwarunkowo i może osiągnąć wartość ujemną. Interpretacja wartości tego pola jest następująca:
Zwiększenie wartości zmiennej semaforowej (pole wartość struktury semafora) jest operacją oczywistą, ale wartość ta mogła być ujemna, co oznacza, że w kolejce są procesy oczekujące na podniesienie semafora. Wówczas z kolejki wybierany jest jeden z procesów, który jest z niej usuwany, a następnie jest budzony (jego stan z oczekujący zmienia się na gotowy).
W podobny sposób można zrealizować semafor binarny, z tą różnicą, że jeśli pole wartość jest równe 1 (co oznacza otwarcie), a wykonywana jest operacja podnoszenia, to stan semafora nie ulega zmianie, czyli:
procedure V(var s : Semaphore) begin if s.wartość < 1 then s.wartość := s.wartość + 1; if s.wartość ≥ 0 then begin wybierz i usuń jakiś / kolejny proces z kolejki s.L; zmień stan wybranego procesu na „gotowy” end; end;
Nieco bardziej skomplikowany jest przypadek implementacji semaforów uogólnionych. Pozostawia się to jako ćwiczenie. Warto mieć jednak na uwadze dwa kryteria przy podnoszeniu semafora:
Wzajemne wykluczanie z użyciem semafora polega na opuszczaniu tego semafora w sekcji wejściowej i podnoszeniu w sekcji wyjściowej. Jeśli wartość początkowa semafora jest równa 1 (lub jest to semafor binarny, ustawiony początkowo na true), po wykonaniu jednej operacji opuszczania wartość zmiennej semaforowej osiągnie 0 i kolejne operacje opuszczania spowodują zablokowanie procesów. W ten sposób pozostałe procesy utkną w sekcji wejściowej do czasu, aż nie nastąpi podniesienie semafora. Podniesienie z kolei nastąpi dopiero po wyjściu z sekcji krytycznej i umożliwi jednemu z oczekujących procesów zakończenie operacji opuszczania.
Algorytm taki można zastosować dla dowolnego zbioru procesów, ale gwarancja spełnienia warunku ograniczonego czekania zależy od sposobu implementacji operacji semaforowych. Jeśli procesy, zablokowane pod semaforem, budzone są w kolejności FIFO, warunek ograniczonego czekania jest spełniony. Gdyby semafor implementowany był na poziomie maszynowym, jak to przedstawiono wcześniej, nie ma gwarancji ograniczonego czekania.
Mechanizmy synchronizacji są częścią standardu POSIX związaną z obsługą wielowątkowości. Mechanizmy te powstały zatem na potrzeby synchronizacji wątków i w takim kontekście będą rozważane w dalszej części.
Jeśli zmienne mają być użyte do synchronizacji, muszą znajdować się w obszarze pamięci dostępnym dla synchronizowanych wątków. We wszystkich operacjach zmienne synchronizujące udostępniane są przez wskaźniki. Użycie zmiennej synchronizującej musi być poprzedzone jej inicjalizacją.
Zamki są podobne do semaforów binarnych i używane są do zapewnienie wzajemnego wykluczania. Zmienne warunkowe używane są wówczas, gdy stan przetwarzania uniemożliwia wątkowi dalsze działanie i wątek musi wejść w stan oczekiwania.
Ponieważ interfejs operacji synchronizujących w standardzie POSIX wyspecyfikowany jest w języku C, w takiej samej formie będzie zaprezentowany na kolejnych slajdach.
Zamek jest obiektem typu pthread_mutex_t i do wszystkich operacji na nim jest przekazywany przez wskaźnik. Przed użyciem zamek powinien zostać zainicjalizowany. Najprostszy sposób, to podstawienie odpowiedniej stałej inicjalizującej przy jego definicji. Nieco bardziej złożone jest użycie odpowiedniej funkcji.
Jak już wspomniano, działanie zamka zbliżone jest do działania semafor binarnego. Operacja zaryglowania (zajmowania zamka, ang. lock) jest odpowiednikiem opuszczania semafora, a operacja odryglowania (zwalniania zamka, ang. unlock) jest odpowiednikiem podnoszenia semafora. Jednak z zamkiem, w przeciwieństwie do semafora binarnego, wiąże się zasada własności. Ten wątek, który zajmie zamek (zarygluje, wykona lock), musi go zwolnić (odryglować, wykonać unlock). Podnieść i opuścić semafor może natomiast dowolny proces.
Biorąc pod uwagę te analogie funkcja pthread_mutex_lock powoduje zajęcie (zaryglowanie) zamka, wskazywanego przez parametr, jeśli zamek ten jest zwolniony. W przeciwnym przypadku następuje zawieszenie wątku w oczekiwaniu na zwolnienie (odryglowanie). Zwolnienie zamka z kolei następuje w wyniku wywołania funkcji pthread_mutex_unlock przez ten wątek, który wcześniej zamek zajął. Funkcja pthread_mutex_trylock służy również do zajmowania zamka, ale nie powoduje zablokowania wątku w przypadku, gdy zamek jest zajęty. Zwracany jest wówczas tylko odpowiedni status zakończenia operacji, po którym można rozpoznać efekt.
pthread_mutex_tpthread_mutex_lock(pthread_mutex_t *m) —zajęcie zamkapthread_mutex_inlock(pthread_mutex_t *m) — zwolnienie zamkapthread_mutex_trylock(pthread_mutex_t *m) — próba zajęcia zamka w sposób nie blokujący wątku w przypadku niepowodzeniaImplementacja zamka jest zbliżona do implementacji semafora binarnego z tą różnicą, że w celu weryfikacji własności w odpowiedniej strukturze musiałby być przechowywany identyfikator wątku, który zajął zamek. Próba zwolnienia zamka poprzez wywołanie funkcji pthread_mutex_unlock wymagałaby zatem weryfikacji właściciela i ewentualnego zwrócenia błędu.
pthread_mutex_lock
pthread_mutex_unlock
pthread_mutex_trylock
Zmienna warunkowa jest obiektem typu pthread_cond_t i podobnie, jak w przypadku zamaka:
Zmienna warunkowa nie jest używana samodzielnie. Ze względu na ryzyko hazardu (różnicy w działaniu w zależności od kolejności operacji w przeplocie) pewne operacje na zmiennej warunkowej muszą być wykonywane sekcji krytycznej, chronionej przez zamek.
Wywołanie funkcji pthread_cond_wait powoduje wejście wątku w stan oczekiwania na sygnał, który z kolei musi wysłać inny wątek, wywołując funkcję pthread_cond_signal lub pthread_cond_broadcast. Na czas oczekiwania następuje zwolnienie zamka, do którego wskaźnik przekazywany jest jako drugi parametr funkcji pthread_cond_wait. Jak można się domyślać funkcja ta wywoływana jest w sekcji krytycznej. Dokładniej zostanie to omówiony przy schematach synchronizacji w dalszej części.
Funkcja pthread_cond_signal budzi jeden z oczekujących wątków, a pthread_cond_broadcast budzi wszystkie oczekujące wątki. Obudzenie wątku nie musi oznaczać natychmiastowego uzyskania stanu gotowości, podobnie jak sygnał budzika nie oznacza natychmiastowego wstania z łóżka. Wątek budzony musi jeszcze ponownie zająć zamek, który zwolnił na czas oczekiwania. Jeśli zamek jest zajęty musi poczekać na jego zwolnienie.
W kontekście przedstawionych wcześniej implementacji semaforów i zamków powyższy opis jest dość oczywisty. Warto tylko zwrócić uwagę na dwie sprawy:
pthread_cond_waitpthread_cond_signalpthread_cond_broadcastDziałanie zmiennej warunkowej kojarzone jest niekiedy z semaforem. W operacjach semaforowych używa się czasami takich samych nazw, czyli wait — opuszczanie oraz signal — podnoszenie.
Zasadnicza różnica pomiędzy zmienna warunkową a semaforem polega na tym, że sygnał na zmiennej warunkowej budzi oczekujący wątek lub jest ignorowany, jeśli żaden wątek nie oczekuje na tej zmiennej. Efekt operacji podnoszenia semafora jest natomiast odzwierciedlany w stanie semafora i może być „skonsumowany” przez późniejsza operację opuszczenia. W przypadku zmiennej warunkowej istnieje zatem ryzyko hazardu — jeśli wątek nie zdąży usnąć na zmiennej warunkowej, można stracić sygnał, który miał go obudzić.
Można rozważać dwa typowe schematy synchronizacji z użyciem zmiennych warunkowych:
W schemacie 1 wątek sprawdza warunek kontynuacji przetwarzania i jeśli jest niespełniony, wchodzi w stan oczekiwania. Jakakolwiek zmiana interesujących go aspektów stanu, będąca skutkiem aktywności innych wątków, powinna spowodować jego obudzenie. Obudzenie nie oznacza jednak, że oczekiwany stan musi wystąpić, w związku z czym wątek ponownie sprawdza warunek kontynuacji przetwarzania. Cała pętla wykonuje się w sekcji krytycznej, chronionej przez zamek, który zwalniany jest na czas oczekiwania. Z tego samego zamka korzysta wątek sygnalizujący, zatem zwolnienie jest konieczne w celu umożliwienia mu dostępu do fragmentów kodu, związanych z modyfikacją stanu przetwarzania.
Brak sekcji krytycznej podczas sprawdzania warunku kontynuacji przetwarzania, nawet jeśli sprawdzanie nie wiąże się ze modyfikacją współdzielonych zmiennych, mógłby z kolei prowadzić do hazardu i utraty sygnału. Wykazanie niepoprawności takiego podejścia pozostawia się jako ćwiczenie.
Wątek sygnalizujący w schemacie 1 budzi wątek oczekujący każdorazowo, gdy dokona modyfikacji tych aspektów stanu (tych zmiennych współdzielonych), które interesują watek oczekujący. Obudzenie może okazać się niepotrzebne, gdyż pomimo dokonanych modyfikacji, nie jest to jeszcze taki stan, na jaki czeka wątek budzony. Tę wiedzę ma jednak tylko wątek oczekujący i to on musi zweryfikować stan, ewentualnie ponownie wejść w stan oczekiwania.
Omówienie schematu 2 rozpoczynamy od wątku sygnalizującego. Znając oczekiwania wątku współpracującego, uśpionego na zmiennej warunkowej, wątek sygnalizujący może mu wysłać sygnał wówczas, gdy sprawdzi, że oczekiwany stan zaistniał.
Wątek oczekujący ma pewność, że zostanie obudzony dopiero wówczas, gdy przetwarzanie osiągnie oczekiwany stan. Po opuszczeniu funkcji pthread_cond_wait nie musi on ponownie sprawdzać warunku. Musi natomiast wykonać pthread_mutex_unlock, gdyż wychodząc z pthread_cond_wait zajmuje ponownie zamek. Schemat ten jest bardziej ryzykowny w użyciu, gdyż ten sam warunek sprawdzany jest w dwóch lub większej liczbie miejsc. Jakiekolwiek korekty w programie, dotyczące warunku, wymagają zatem modyfikacji kodu w kilku miejscach i któreś z tych miejsc można przeoczyć. Poza tym przy większej liczbie współpracujących wątków kolejność zajmowania sekcji krytycznej może być nieokreślona i narazić na zmianę stanu przetwarzania pomiędzy obudzeniem wątku, a ponownym zajęciem przez niego sekcji krytycznej. Z tego powodu w ogólnym przypadku ten schemat nie jest zalecany. Może on być stosowany w prostych rozwiązaniach z dość precyzyjnie przewidywalnym przeplotem operacji współbieżnych wątków.
Wysłanie sygnału przez wątek sygnalizujący (wywołanie pthread_cond_signal) na ogół odbywa się w sekcji krytycznej i najczęściej jest ostatnią operacją wykonywaną w tej sekcji. Warto zwrócić uwagę, że dopiero opuszczenie sekcji krytycznej (wywołanie funkcji pthread_mutex_unlock) umożliwia przejście wątku budzonego w stan gotowości, czyli właściwe opuszczenie funkcji pthread_cond_wait. Wątek sygnalizujący nie musi jednak natychmiast wyjść z sekcji krytycznej. Potencjalnie nawet mógłby dokonać kolejnych modyfikacji współdzielonych zmiennych, w wyniku których oczekiwany warunek byłby ponownie niespełniony, co kwestionowałoby zasadność schematu 2. Szerszą dyskusję na ten temat można znaleźć w literaturze przy okazji omawiania monitorów.
Można również rozważać wysłanie sygnału po wyjściu z sekcji krytycznej. Nie jest to błąd, ale zmniejsza przewidywalność decyzji planisty przydziału procesora.
Problem producenta i konsumenta dotyczy przekazywania danych — w szczególności strumienia danych — pomiędzy procesami z wykorzystaniem bufora o ograniczonej pojemności. Bufor może być zapełniony, co zmusza producenta do ograniczenia swojej aktywności, lub może być pusty, co blokuje konsumenta.
Problem czytelników i pisarzy jest ilustracją synchronizacji dostępu do współdzielonych danych, które mogą być czytane lub modyfikowane. Modyfikacja danych wymaga wyłączności dostępu do danych, podczas gdy ich odczyt może być wykonywany współbieżnie. Jest to namiastka problemu, z jakim stykają się twórcy systemów zarządzania bazami danych, projektując mechanizmy współbieżnego wykonywania transakcji.
Problem pięciu filozofów wiąże się z dostępem procesu do wielu różnych zasobów (w tym przypadku dwóch) w tym samym czasie. Skutkiem braku odpowiedniej koordynacji może być zakleszczenie (ang. deadlock), zagłodzenie któregoś procesu (ang. starvation) lub uwięzienie (ang. livelock).
Problem śpiących fryzjerów jest odzwierciedleniem zagadnień interakcji klienta z serwerem (np. w komunikacji sieciowej), w której początkowo aktywną stroną jest klient żądający obsługi, a po zaakceptowaniu żądania występuje aktywność zarówno po stronie klienta jaki i serwera. Ze względu na ograniczoną pojemność kolejki oczekujących żądań, próba nawiązania interakcji ze strony klienta może być odrzucona.
Bufor dla współpracy producenta i konsumenta ma pojemność ograniczoną do pewnej (ustalonej) liczby jednostek przekazywanego produktu. W literaturze spotkać można również nieco uproszczoną wersję tego problemu, w którym nie ma ograniczenia na rozmiar bufora. Nie ma wówczas potrzeby blokowania producenta, konieczne jest tylko blokowanie konsumenta, żeby „nie wyprzedził” producenta.
W przypadku jednego producenta i jednego konsumenta rozwiązanie wymaga dwóch semaforów ogólnych. Stan semafora wolne określa liczbę wolnych pozycji w buforze, a stan komplementarnego semafora zajęte określa liczbę pozycji zajętych. Przy założeniu, że początkowo bufor jest pusty, wartość semafora wolne wynosi n (n wolnych pozycji), a semafora zajęte 0 (żadna pozycja w buforze nie jest zajęta).
Producent ma lokalną zmienną i, która wskazuje kolejną pozycję do zapełnienia w buforze. W przypadku wielu producentów zmienna ta musiałaby być przez nich współdzielona. Zmienna zwiększana jest cyklicznie (modulo n) po każdym wstawieniu elementu do bufora. Tak funkcjonujący bufor określą się jako ograniczony bufor cykliczny.
Wstawienie elementu do bufora poprzedzone jest operacją opuszczenia semafora wolne. Brak wolnego miejsca oznacza wartość 0 zmiennej semaforowej wolne i tym samym uniemożliwia opuszczenie. W ten sposób producent blokowany jest w dostępie do bufora, co chroni bufor przed przepełnieniem. Semafor wolne zostanie podniesiony przez konsumenta, gdy zwolni on miejsce w buforze.
Jeśli producentowi uda się umieścić kolejny element w buforze, sygnalizuje to przez podniesienie semafora zajęte. Ile razy podniesie go producent, tyle razy będzie mógł go opuścić konsument.
Konsument działa symetrycznie w stosunku do producenta. Podobnie jak producent, utrzymuje on lokalną zmienną i, która wskazuje mu pozycję z kolejnym elementem do pobrania. Zmienna ta musiałaby być współdzielona w przypadku wielu konsumentów.
Przed uzyskaniem dostępu do bufora konsument wykonuje operację opuszczenia semafora zajęte, który zwiększa producent po umieszczeniu w buforze kolejnego elementu. Jeśli semafor zajęte jest równy 0, bufor jest pusty i konsument nie ma tam czego szukać. Utknie on zatem w operacji opuszczania.
Jeśli konsument uzyska dostęp do bufora, pobierze element i tym samym zwolni miejsce. Fakt ten zasygnalizuje poprzez podniesieni semafora wolne, co z kolei umożliwi wykonanie kolejnego kroku producentowi.
W problemie można rozważać dwa rodzaje użytkowników (procesów) — czytelników i pisarzy — lub użytkowników wcielających się w rolę czytelnika lub pisarza. Rozróżnienie takie jest o tyle istotne, że w niektórych rozwiązaniach (zwłaszcza w środowisku rozproszonym) przyjęcie stałej liczby czytelników i pisarzy ma istotny wpływ na konstrukcję protokołu synchronizacji.
Można rozważać dwa warianty problemu:
Zaprezentowane rozwiązanie faworyzuje czytelników, a dopuszcza głodzenie pisarzy. Synchronizacja opiera się na dwóch binarnych semaforach i współdzielonej zmiennej l_czyt (liczba czytelników w czytelni). Semafor mutex_r służy do synchronizacji dostępu do zmiennej l_czyt. Semafor mutex_w służy z kolei do blokowania pisarzy.
W prezentowanym rozwiązaniu czytelnik może wejść do czytelni zawsze, gdy nie ma w niej pisarza. Czytelnik zamyka zatem semafor mutex_r, chroniący zmienną l_czyt, po czym zwiększa ją o 1. Jeśli po zwiększeniu o 1 zmienna równa jest 1, to znaczy, że jest on pierwszym czytelnikiem, który zajął czytelnię. Musi on zatem zamknąć wejście pisarzom poprzez opuszczenie semafora mutex_w. Mogłoby się okazać jednak, że w czytelni nie było wprawdzie czytelników, ale był właśnie pisarz. Operacja opuszczenia semafora mutex_w powstrzyma czytelnika przed dostępem do czytelni do czasu wyjścia z niej pisarza (patrz następny slajd).
Jeśli do czytelni wchodzą kolejni czytelnicy, nie wykonują już operacji na semaforze mutex_w. Zamknął go już pierwszy czytelnik.
Przy wyjściu czytelnika z czytelni zmniejszana jest wartość zmiennej l_czyt. Operacja chroniona jest oczywiście przez semafor mutex_r, gwarantujący realizację w sekcji krytycznej. Gdyby po zmniejszeniu zmiennej l_czyt okazało się, że jest ona równa 0, to znaczy, że z czytelni wyszedł ostatni czytelnik i można dać szansę pisarzowi. Podnoszony jest zatem semafor mutex_w.
Może się jednak tak zdarzyć, że w czytelni zawsze będzie jakiś czytelnik. Zanim wyjdzie jeden czytelnik, następny może już wejść do czytelni. Można w ten sposób doprowadzić do głodzenia pisarzy.
Jednym zadaniem pisarza jest zakończyć sukcesem operację opuszczania semafora mutex_w. Jeśli pisarzowi się to uda, na czas pisania semafor będzie opuszczony. Kolejny pisarz utknie oczywiście na semaforze mutex_w. Pierwszy z czytelników, próbujących wejść do czytelni, również utknie na semaforze mutex_w. W wyniku zablokowania w opuszczaniu semafora mutex_w, do czasu odblokowania nie zostanie podniesiony semafor mutex_r, co spowoduje zablokowanie na nim pozostałych czytelników.
Synchronizacja w problemie pięciu filozofów odbywa się na dwóch poziomach:
Potrzeba synchronizacji na poziomie lokalnym wynika z faktu, że każdy widelec jest współwłasnością dwóch filozofów, a używany w danej chwili może być tylko przez co najwyżej jednego z nich. Globalna koordynacja z kolei jest wymagana, gdyż każdy filozof w celu przejścia do stanu „jedzenie” potrzebuje dwóch widelców. Uzyskanie tylko jednego z nich może oznaczać przetrzymywanie zasobu bez wyraźnej perspektywy zwolnienia go po osiągnięciu stanu „sytości”, do czego potrzeba drugiego.
Problem dostępu do widelców w synchronizacji pięciu filozofów można rozwiązać za pomocą tablicy semaforów binarnych — widelec . Semafor na każdej pozycji tablicy reprezentuje jeden widelec. Zmiana stanu z myślenia na jedzenie wymaga jednak dwóch widelców. Istnieje zatem ryzyko zakleszczenia lub uwięzienia, co jest istotą problemu pięciu filozofów. Problem zakleszczenia omawiany będzie w następnym module, ale uprzedzając całościowe omówienie zagadnień zakleszczenia, można powiedzieć, że najprostszym podejściem jest niedopuszczeni do powstania cyklu w oczekiwaniu na widelce. Można w tym celu stosować różne techniki:
W przedstawionym w dalszej części rozwiązaniu przyjęto pierwsze z wymienionych podejść, w związku z czym potrzebny jest semafor ogólny dopuść o wartości początkowej 4.
Przed podjęciem próby zdobycia widelców filozof opuszcza semafor dopuść . Jeśli byłby piątym procesem, dopuszczonym do rywalizacji, jest ryzyko powstania cyklu i zakleszczenia. Semafor dopuść dopuszcza jednak tylko czterech filozofów, w związku z czym nie ma ryzyka cyklu.
Fotel w salonie fryzjerskim jest stanowiskiem, obsługiwanym przez fryzjera. Zakłada się, że fryzjerów jest nie mniej niż foteli. W przypadku braku klienta fryzjer śpi. Jeśli jednak kolejka klientów nie jest pusta, fryzjerzy obsługują kolejnych klientów w miarę dostępnych foteli. Sama obsługa oznacza jednoczesną aktywność zarówno klienta, jak i fryzjera.
Problem można rozważać w kilku wariantach:
Rozwiązanie opiera się na jednym semaforze binarnym i trzech ogólnych. Poza tym, w zmiennej l_czek pamiętana jest liczba klientów oczekujących na obsługę i zajmujących miejsca w poczekalni. Semafor binarny mutex służy głównie do synchronizacji dostępu do zmiennej l_czek.
Klient zamyka semafor mutex w celu ochrony operacji na zmiennej l_czek, po czym sprawdza, czy jest wolne miejsce w poczekalni. Jeśli nie ma miejsca, otwiera semafor mutex i kończy niepowodzeniem próbę skorzystania z usługi. Jeśli natomiast jest wolne miejsce w poczekalni, to będąc cały czas w sekcji krytycznej, chronionej przez mutex, zmniejsza o 1 zmienną l_czek (zajmuje miejsce w poczekalni), podnosi semafor klient, dając w ten sposób sygnał fryzjerowi i opuszcza sekcję krytyczną. Po opuszczeniu sekcji krytycznej czeka na wolnego fryzjera na semaforze fryzjer — czeka na sygnał na tym semaforze, czyli na jego podniesienie. Kiedy pojawi się wolny fryzjer, podniesie on ten semafor i klient przejdzie do fazy strzyżenia.
Fryzjer czeka na klienta na semaforze klient, który jest podnoszony przez klienta po uzyskaniu miejsca w poczekalni. Po zakończeniu tej operacji fryzjer wie, że ma klienta więc czeka na wolny fotel opuszczając semafor fotel. Jeśli operacja się zakończy to jest fotel dla klienta i można przejść do obsługi. Najpierw zmniejszana jest zmienna l_czek, bo zwalnia się miejsce w poczekalni. Następnie poprzez podniesienie semafora fryzjer, przekazywany jest klientowi sygnał, że może wyjść ze stanu czekania i przejść do właściwej obsługi. Po zwolnieniu semafora mutex fryzjer też przechodzi do obsługi, po zakończeniu której zwalnia fotel (podnosi semafor fotel).
Zasada funkcjonowania monitora podobna jest do mechanizmów POSIX. Właściwie raczej mechanizmy POSIX wzorowane są na monitorach, gdyż koncepcja monitora została zaproponowana przez Hoare’a wcześniej, niż powstał standard POSIX.
Synchronizacja związana jest w tym przypadku z definicją określonej struktury, która (podobnie jak definicja klasy w podejściach obiektowych) obejmuje deklaracje zmiennych instancji oraz implementacje metod dostępu — wejść. Zmienne dostępne są tylko wewnątrz monitora, tzn. operacje na nich mogą być wykonywane tylko w ramach wejść. Wejścia z kolei stanowią publiczny interfejs dostępu do monitora. W ich implementacji można się odwoływać tylko do zmiennych monitora oraz parametrów.
Wejście wykonywane jest przy wyłącznym dostępie do monitora — wyklucza zatem aktywność jakiegokolwiek innego procesu wewnątrz monitora, czyli wyklucza możliwość współbieżnego wykonywana kodu monitora przez kilka procesów. Możliwe jest jednak udostępnienie monitora w przypadku, gdy proces wejdzie w stan oczekiwania na zmiennej warunkowej.
Częścią definicji monitora są zmienne warunkowe, na których proces może jawnie usnąć, a następnie zostać obudzony. Podobnie jak w przypadku mechanizmów POSIX, na czas uśpienia monitor jest zwalniany. W ten sposób uśpiony proces może kiedyś zostać obudzony przez inny proces, który wyśle sygnał na danej zmiennej. Warto jednak podkreślić, że zmienne warunkowe, jako wewnętrzne zmienne monitora, dostępne są tylko w ramach wejść. Zarówno usypianie jak i budzenie procesu jest częścią implementacji jakiegoś wejścia.
Każde wejście w definicji monitora może mieć parametry tak, jak normalna procedura. Wśród deklaracji zmiennych mogą się pojawić szczególne zmienne — warunkowe, na których w implementacji poszczególnych wejść można wykonywać operacja wait i signal . Podobnie jak w mechanizmach POSIX, wait powoduje uśpienie procesu w oczekiwaniu na sygnał i udostępnienie monitora innym procesom, a signal budzi jeden z procesów, śpiących na zmiennej warunkowej lub jest ignorowany, jeśli nie ma procesu do obudzenia.
Różnica w stosunku do mechanizmów standardu POSIX jest zatem taka, że zajęcie i zwolnienie zamaka wykonywane jest niejawnie. Sam zamek w związku z tym również nie jest jawnie deklarowany. W ten sposób można się ustrzec błędów związanych z pominięciem tego typu operacji synchronizującej. Należy jedynie zadbać o poprawność definicji struktury danych, a w zakresie tym można liczyć na wsparcie ze strony narzędzi programistycznych, np. kompilatora.
Podstawą rozwiązania problemu czytelników i pisarzy za pomocą monitora jest odpowiednio zdefiniowany bufor cykliczny. Bufor ten w prezentowanym rozwiązaniu chroniony jest przez monitor, tzn. właściwy bufor — określony jako pula miejsc — stanowi część monitora, w związku z czym dostępny jest bezpośrednio tylko w ramach wejść. Poza tym w monitorze zadeklarowane są zmienne na potrzeby obsługi dostępu do puli:
Synchronizacja dostępu wymaga jeszcze zmiennych warunkowych, na których byłyby usypiane procesy w przypadku zapełniania lub całkowitego opróżnienia bufora. W rozwiązaniu wykorzystano dwie zmienne warunkowe:
Wejście wstaw wywoływane jest przez producenta. Przed umieszczeniem elementu w puli danego bufora należy sprawdzić, czy jest wolne miejsce, czyli czy bieżące wypełnienie bufora — licz — nie jest takie, jak jego pojemność — n. Jeśli wartości są równe, bufor jest całkowicie zapełniony i proces producenta usypiany jest na zmiennej warunkowej pełny. Obudzony zostanie dopiero przez konsumenta po pobraniu elementu.
Jeśli w buforze jest wolne miejsce, na pozycji wskazanej przez zmienną wej umieszczany jest element, wstawiany przez producenta, po czym zmienna wej jest zwiększana cyklicznie o 1. Zwiększana jest też o 1 zmienna licz, gdyż przybył jeden element.
Na końcu wysyłany jest sygnał dla (być może) oczekującego konsumenta, że pojawiło się coś w buforze, co można skonsumować. Jeśli nikt nie czekan na zmiennej warunkowej pusty, sygnał zostanie zignorowany.
mplementacja wejścia pobierz jest analogiczna. Sprawdzane jest, czy bufor nie jest pusty, czyli czy liczba elementów — licz — nie jest równa 0. Jeśli licz jest równe 0, następuje uśpienie konsumenta.
Jeśli bufor nie jest pusty, konsument pobiera z pozycji, indeksowanej przez wyj element, który staje się wartością parametru wyjściowego. Zmienna wyj zwiększana jest cyklicznie, żeby wskazywała kolejny element, po czym następuje zmniejszenie zmiennej licz, gdyż w buforze zwolniła się miejsce po pobranym elemencie.
Na końcu wysyłany jest sygnał do producentów, którzy mogą czekać na zwolnienie miejsca w buforze.
Przyjmując, że początkowy stanu bufor jest pusty, w ramach inicjalizacji następuje wyzerowanie wszystkich zmiennych, związanych z kontrolą dostępu do puli.
Użycie monitora odpowiedzialnego za buforowanie w samym kodzie producenta lub konsumenta jest już bardzo proste. Wystarczy po wyprodukowaniu elementu wywołać odpowiednie wejście — wstaw, a chcąc skonsumować kolejny element, wywołać pobierz . Ponieważ bufor jest chroniony przez monitor, cała odpowiedzialność za synchronizację spoczywa na twórcy tego monitora, minimalizując ryzyko błędu w programie dla producenta i konsumenta.
W przedstawionym schemacie synchronizacji monitor czytelnia nie chroni czytelni. Monitor w tym przypadku pełni rolę koordynatora dostępu do czytelni. Jeśli w programie któregoś procesu przed wejściem do czytelni nie znalazłyby się operacje na monitorze, będące w rzeczywistości pytaniami o pozwolenie na wejście, to czytelnia i tak stałaby się dostępna, tylko w sposób nie skoordynowany, zatem z ryzykiem naruszeniem poprawności.
Gdyby czytelnia była chroniona wewnątrz monitora i dostępna byłaby poprzez wejścia typu: czytaj, pisz, to nadmiernie ograniczona byłaby współbieżność dostępu dla czytelników, gdyż wykluczaliby się oni wzajemnie.
W rozwiązaniu pominięto implementację monitora czytelnia. Implementację tę pozostawia się jako ćwiczenie.
shared czytelnia: Monitor;Przedstawiona definicja dotyczy właściwie warunkowego regionu krytycznego. Blokowanie i wznawianie procesów w przypadku regionów krytycznych odbywa się na podstawie warunku logicznego, w przeciwieństwie do monitora, gdzie jawnie wysyłany jest sygnał. Jeśli więc warunek nie jest spełniony, proces jest usypiany tak samo, jak przez jawne wywołanie wait w przypadku monitora. Również w przypadku, gdy warunek stanie się prawdziwy, proces zostanie obudzony. W przypadku monitora wymagane jest jawne wykonanie signal. Oczywiście w czasie oczekiwania na spełnienie warunku, podanego po frazie when, region krytyczny jest dostępny dla innych procesów.
shared v: T;
region v when B do S;
W przedstawionym rozwiązaniu buf jest zmienną typu rekord, obejmującą pulę pozycji i zmienne do jej obsługi (podobnie, jak w przypadku monitora). Na zmiennej buf będzie wykonywany region krytyczny.
Zasada działania tego rozwiązania jest zbliżona do monitora. Jak już wspomniano przy ogólnej definicji regionu krytycznego, różnicą jest tylko sposób opisu fragmentu kodu, wykonywanego w trybie wyłącznym oraz sposób blokowania producentów i konsumentów w dostępie do bufora.
Wzajemne wykluczanie dotyczy fragmentu kodu objętego konstrukcją region, zatem trzech operacji podstawienia, modyfikujących składowe rekordu buf. Takie same operacje w przypadku monitora znajdowały się w implementacji wejścia wstaw.
Usypianie i budzenie odbywa się niejawnie w zależności od wypełnienia bufora. Taki sam warunek sprawdzany był w przypadku monitora, ale usypianie a następnie budzenie wymagało jawnego użycia w kodzie instrukcji wait i signal .
Działanie konsumenta jest analogiczne. Warto zwrócić uwagę, że konsument wykonuje inny region krytyczny (z innym warunkiem i innym kodem wykonywanym w trybie wyłączny) na tej samej zmiennej — buf. Wykonywanie kodu konsumenta wyklucza zatem wykonywanie kodu producenta i odwrotnie.