Wykład składa się z trzech części. Pierwsza obejmuje semafory, ich abstrakcyjną definicję, klasyfikację oraz sposoby implementacji. Druga dotyczy mechanizmów standardu POSIX i sposobu ich użycia w synchronizacji. Ostatnia z zasadniczych części wykładu obejmuje klasyczne problemy synchronizacji procesów — producenta i konsumenta, czytelników i pisarzy, pięciu filozofów oraz śpiących fryzjerów. Przedstawione zostaną rozwiązania tych problemów z użyciem semaforów. Na koniec pojawi się krótka wzmianka o strukturalnych mechanizmach synchronizacji.

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.

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 .

Dla semafora dwustronnie ograniczonego definiuje się górne ograniczenie, po osiągnięciu którego następuje blokowanie procesu również w operacji podnoszenia.

W celu wyeksponowania przepływu sterowania i wskazania instrukcji, które muszą być wykonane niepodzielnie, implementację operacji P można przedstawić następująco:

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.

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:

• wartość dodatnia oznacza, że semafor jest podniesiony i przy takim stanie proces nie jest blokowany w operacji opuszczania,
• wartość ujemna oznacza, że semafor jest opuszczony, są procesy oczekujące na podniesienie semafora, a ich liczba jest równa wartości bezwzględnej pola wartość,
• wartość 0 oznacza, że semafor jest opuszczony ale nie ma procesów oczekujących na jego podniesienie (jest to szczególny przypadek poprzedniego punktu).

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:

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:

• zwiększanie przepustowości i budzenie procesów, dla których zmienna semaforowa osiągnęła wystarczającą wartość, nawet jeśli nie znajdują się na czele kolejki (ryzyko głodzenia procesów, które chcą opuścić semafor o relatywnie dużą wartość),
• zachowanie sprawiedliwości i budzenie procesów w kolejności ich kolejkowania.

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.

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

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.

• do wszystkich operacji jest przekazywana przez wskaźnik,
• przed użyciem powinna zostać zainicjalizowana (przez podstawienie właściwej stałej lub użycie odpowiedniej funkcji).
• 
  

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.

1. Wejście w stan oczekiwania po wywołaniu funkcji pthread_cond_wait jest bezwarunkowe.
2. Opuszczenie funkcji pthread_cond_wait zależy od możliwości zajęcia zamka. Po otrzymaniu sygnału wątek zachowuje się tak, jak w przypadku wywołania funkcji pthread_mutex_lock. Wybór następnego wątku do zajęcia zamka po jego zwolnieniu w innym wątku (w wyniku wywołania pthread_mutex_unlock lub pthread_cond_wait) zależy od polityki szeregowania.

Dział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ć.

• schemat 1 — tylko wątek oczekujący wie, na jaki stan czeka, a wątek sygnalizujący budzi go w przypadku każdej zmiany tego stanu,
• schemat 2 — zarówno wątek oczekujący jak i sygnalizujący wiedzą, jaki stan jest oczekiwany, w związku z czym możliwa jest optymalizacja — wątek sygnalizujący budzi wątek oczekujący dopiero po osiągnięciu tego stanu.
• 
  

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.

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.

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.

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.

Można rozważać dwa warianty problemu:

• czytelnia ma nieograniczoną pojemność, co oznacza, że może z niej jednocześnie (współbieżnie) korzystać nieograniczona liczba czytelników,
• czytelnia ma tylko n miejsc, co oznacza, że liczba jednocześnie korzystających czytelników nie może być większa niż n .

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.

• lokalnym — synchronizacja dostępu do konkretnego widelca,
• globalnym — koordynacja działań wszystkich pięciu filozofów w taki sposób, aby nie dopuścić do zakleszczenie, uwięzienia lub zagłodzenia któregoś z filozofów.

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.

• dopuścić do rywalizacji o widelce w danej chwili co najwyżej 4 procesy,
• stosować różną kolejność uzyskiwania widelców — np. filozof o numerze parzystym bierze najpierw lewy, a później prawy widelec, natomiast filozof o numerze nieparzystym bierze najpierw lewy widelec,
• stosować podejście priorytetowe, oparte np. na liczbie już zjedzonych posiłków — im więcej posiłków tym mniejszy priorytet.

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.

Problem można rozważać w kilku wariantach:

• grupa „jednorodnych” fryzjerów,
• kilka grup fryzjerów specjalistów — klient (klientka) zgłasza się do specjalisty od danego rodzaju usługi (np. modelowanie, farbowanie, pasemka itp.),
• fryzjerzy indywidualni — klient zgłasza się do konkretnego fryzjera.

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

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.

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.

• wej — indeks pozycji w puli, na której umieszczony zostanie kolejny wstawiany element,
• wyj — indeks pozycji w puli, z której pobierany będzie kolejny element,
• licz — liczba elementów w buforze.

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:

• pusty — do usypiania konsumentów, gdy bufor jest pusty,
• pełny — do usypiania producentów, gdy bufor jest w całości wypełniony.

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.

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.

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.

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.

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 .