Przechodzimy teraz do mechanizmów synchronizacji w systemach ze wspólną pamięcią. Model ten różni się od dotychczasowych przede wszystkim tym, że można stosować zmienne współdzielone, czyli dostępne dla wielu procesów, i za ich pomocą wymieniać informacje.
Korzystanie ze zmiennych współdzielonych wymaga jednak dużej ostrożności, jak widzieliśmy to podczas pierwszego wykładu. Niekontrolowane niczym modyfikowanie takich zmiennych w wielu procesach jednocześnie może dawać niedające się przewidzieć efekty. Z tego powodu większość z omawianych w dalszym ciągu mechanizmów gwarantuje atomowość lub niepodzielność pewnych operacji.
W dalszej części wykładu omówimy szczegółowo dwie metody synchronizacji procesów w środowisku scentralizowanym: semafory i monitory. Wspomnimy także o mechanizmie zamków (muteksów). Zanim jednak to nastąpi na przykładzie wzajemnego wykluczania wspomnijmy o dwóch innych metodach synchronizacji.
Pierwsza z tym metod jest stosowana wtedy, gdy nie dysponujemy żadnym wsparciem ani ze strony sprzętu ani oprogramowania. Korzystając jedynie z wysokopoziomowych instrukcji języka programowania można zapewnić wzajemne wykluczanie w dostępie do sekcji krytycznej za pomocą m.in. algorytmu Petersona. Jego dokładne omówienie znalazło się w materiałach dotyczących pierwszych ćwiczeń. Przypomijmy jego wady: statycznie znana liczba procesów, koszt, a przede wszystkim aktywne oczekiwanie.
Czasem możemy liczyć na wsparcie sprzętowe. Może to być na przykład specjalny rozkaz maszynowy realizujący niepodzielny zapis i odczyt. Rozpatrzmy dla przykładu rozkaz Test_and_Set, który odczytuje pewien bit G i ustawia go na jeden. Działanie takiego rozkazu można by zapisać w wysokopoziomowym języku następująco:
procedure Test_and_Set (var L: 0..1);
{ Ta procedura jest atomowa! }
begin
L := G;
G := 1;
end
Problem wzajemnego wykluczania można wówczas rozwiązać następująco:
var wolny: 0..1 := 0;
process P;
var
i: 0..1;
begin
repeat
własne_sprawy;
repeat
Test_and_Set (i);
until i = 0;
sekcja_krytyczna;
wolny := 0;
until false
end;
To rozwiązanie także nie jest pozbawione wad. Pierwszą z nich jest oczywiście aktywne oczekiwanie, drugą możliwość zagłodzenia procesu.
Omówienie mechanizmów udostępnianych programowo rozpoczniemy od semaforów. Semafor jest to abstrakcyjny typ danych, na którym można wykonywać jedynie dwie operacje:
Powyższe operacje są niepodzielne i wzajemnie się wykluczają. Ponadto semafor można raz, poza procesami, zainicjować na dowolną wartość nieujemną.
O semaforze myślimy jak o pewnej zmiennej całkowitej o wartościach nieujemnych. Programista nie ma jednak dostępu do wartości tej zmiennej (poza początkową inicjacją), a operacje na niej wykonuje za pomocą operacji P i V. Ich działanie można zdefiniować na dwa sposoby.
Klasyczna definicja semafora definiuje semantykę operacji P następująco:
P(S): zaczekaj aż wartość semafora S będzie dodatnia; zmniejsz S o 1
Jeśli semafor S ma od razu wartość większą niż 0, to operacja P nie wstrzymuje wywołującego ją procesu. Jeśli S ma wartość równą 0, to proces wykonujący P jest wstrzymywany w sposób nieangażujący procesora. W czasie, gdy proces oczekuje inne procesy mogą rozpocząć wykonanie operacji P (i zostaną także wstrzymane) lub też wykonać operację V (co, jak za chwilę zobaczymy, powoduje zwiększenie wartości zmiennej semaforowej i w konsekwencji może doprowadzić do obudzenia jednego z oczekujących na operacji P procesów).
Operację V definiuje się po prostu tak:
V(S): S := S + 1
Powyższe definicje wymagają kilku wyjaśnień. Niepodzielność instrukcji V jest zrozumiała: zwiększenie semafora ma się po prostu odbyć w jednym kroku. Co jednak oznacza niepodzielność instrukcji P? Jeśli proces rozpoczyna wykonanie tej operacji i zastaje dodatnią wartość semafora, to zmniejsza jego wartość o 1, a niepodzielność gwarantuje, że operacja ta zostanie wykonana w całości zanim inny proces rozpocznie wykonanie V lub P. Jeśli jednak proces zastanie semafor równy zero to jest wstrzymany. Niepodzielność P nie gwarantuje zatem tego, że proces, który rozpoczął jej wykonanie zakończy je bez wstrzymania swojego działania. Jednak proces wstrzymany oddaje dostęp do operacji P i V, dzięki czemu inny proces może zwiększyć semafor. Któryś z oczekujących procesów (jeden z nich) może "zauważyć" tę zmianę (nie zajmujemy się sposobem implementacji tego mechanizmu) i wznowić wykonanie operacji P. I tutaj ponownie korzystamy z niepodzielności, która gwarantuje, że proces zmniejszy wartość semafora zanim ktokolwiek inny rozpocznie wykonanie P lub V.
Podkreślmy raz jeszcze: P i V to jedyne operacje na semaforze. W szczególności nie ma możliwości sprawdzenia wartości zmiennej semaforowej!.
Operacja V może spowodować obudzenie jednego spośród procesów oczekujących na semaforze. Definicja nie precyzuje jednak, który to będzie proces. Nie można w szczególności założyć, że procesy oczekują na semaforze w kolejce. Aby zapewnić żywotność programów korzystających z semaforów przyjmuje się jednak pewne założenie dotyczące oczekiwania: jest ono sprawiedliwe. Każdy proces oczekujący zostanie w skończonym czasie obudzony, jeśli tylko semafor zostanie podniesiony dostatecznie dużo razy.
W dalszym ciągu wykładu będziemy mówić, że semafor jest zamknięty, jeśli wartość zmiennej semaforowej wynosi 0, w przeciwnym razie semafor będziemy nazywać otwartym. Sformułowanie przejść pod semaforem będzie oznaczać zakończenie wykonania operacji P, a podniesienie semafora to wykonanie na nim operacji V.
Czasem wpowadza się nieco inną definicję operacji P i V:
P(S): jeśli S > 0, to S := S - 1, w przeciwnym razie wstrzymaj działanie
V(s): jeśli są procesy oczekujące na S, to obudź jeden z nich, w przeciwnym razie S := S + 1
Podstawowa różnica polega na tym, że w definicji uproszczonej nie podnosi się semafora, jeśli są procesy oczekujące. Zamiast tego proces wykonujący operację V budzi jeden z nich. Semafor zostanie podniesiony jedynie wówczas, gdy nikt pod nim nie czeka. Pozostałe założenia dotyczące niepodzielności, atomowości i sprawiedliwości operacji semaforowej pozostają w mocy.
Nazwy operacji semaforowych pochodzą z języka holenderskiego:
Pojawiające się w literaturze nazwu wait i signal rezerwujemy dla operacji na zmiennych warunkowych.
Szczególnym przypadkiem semafora jest semafor binarny. Przyjmuje on jedynie wartość 0 lub 1 (zamknięty lub otwarty), a operacje na nim wykonuje się następująco:
P(S): jeśli S > 0, to S := 0, w przeciwnym razie wstrzymaj działanie
V(S): jeśli są procesy oczekujące na S, to obudź jeden z nich, w przeciwnym razie S := 1
Semafor binarny jest oszczędniejszy pamięciowo niż semafor ogólny, gdyż wymaga tylko jednego bitu.
Zauważmy, że powyższa definicja semafora binarnego powoduje, że otwarcie otwartego semafora binarnego nie ma żadnego efektu. Może to prowadzić do subtelnych błędów w programach. Dlatego też niektórzy przyjmują, że operacja V na otwartym semaforze binarnym powoduje błąd.
Semafory będziemy deklarować używając typu semaphore lub binary semaphore. Deklaracje będziemy umieszczać poza procesami. Semafory będą inicjowane od razu w miejscu deklaracji.
Rozwiązanie problemu wzajemnego wykluczania jest bardzo proste:
mutex: binary semaphore := 1;
process P;
begin
repeat
własne_sprawy;
P (mutex);
sekcja_krytyczna;
V (mutex)
until false
end
Jeśli dostęp do sekcji krytycznej może uzyskać jednocześnie co najwyżej k procesów (dla k > 1), zastosujemy semafory ogólne:
mutex: semaphore := k;
process P;
begin
repeat
własne_sprawy;
P (mutex);
sekcja_krytyczna;
V (mutex)
until false
end
Przypuśćmy, że mamy typ danych Bufor z operacjami Wstaw i Pobierz, implementujący bufor o pojemności N. Chcemy za pomocą semaforów rozwiązać problem wielu producentów i wielu konsumentów dbając o właściwą synchronizację dostępu do bufora.
W tym celu wprowadzimy trzy semafory. Semafor mutex będzie dbać o wzajemne wykluczanie operacji na buforze (nie można jednocześnie wstawiać danych do bufora, żeby dane nie trafiły na to samo miejsce). Oprócz tego za pomocą semafora wolne będziemy "zliczać" wolne miejsca w buforze, a za pomocą semafora zajęte --- będziemy zliczać zajęte miejsca. Przyjmijmy, że bufor jest początkowo pusty. Naturalnym sposobem inicjacji semaforów jest:
mutex: binary semaphore := 1; wolne: semaphore := N; zajete: semaphore := 0; b: Buffer;
Producent przed wstawieniem danych do bufora musi się upewnić, że w buforze jest miejsce. Jeśli tak, to liczba wolnych miejsc się zmniejszy, a zwiększy się liczba miejsc zajętych. Naturalne jest więc zaimplementowanie producenta w następujący sposób:
process Producent;
var
x: integer;
begin
repeat
produkuj (x);
P (wolne);
P (mutex);
wstaw (b, x);
V (mutex);
V (zajete)
until false;
end
Proces konsumenta jest symetryczny:
process Konsument;
var
x: integer;
begin
repeat
P (zajete);
P (mutex);
x := pobierz (b);
V (mutex);
V (wolne)
until false;
end
W dotychczasowych rozważaniach wprowadziliśmy semafory ogólne i binarne. Powstaje naturalne pytanie, który z tych mechanizmów ma większą siłę wyrazu. Czy program zapisany z wykorzystaniem semaforów binarnych daje się zapisać korzystając jedynie z semaforów ogólnych (i być może dodatkowych "zwykłych" zmiennych) i na odwrót.
Ponieważ każdy semafor binarny jest zarazem semaforem ogólny, więc zamiast semaforów binarnych można zawsze użyć semaforów ogólnych (zakładamy, że nie dochodzi do próby otwarcia otwartego semafora binarnego). Również program korzystający z semaforów ogólnych daje się napisać z użyciem semaforów ogólnych i pewnych dodatkowych zmiennych, jednak stwierdzenie tego faktu nie jest już tak oczywiste.
Aby się o tym przekonać dokonajmy "symulacji" semafora ogólnego S za pomocą zmiennej całkowitej N oraz dwóch semaforów binarnych mutex i delay. Symulacja polega na zaimplementowaniu operacji P(S) oraz V (S) za pomocą operacji na semaforach mutex i delay i zmiennej całkowitej N.
Aby zaimplementować operację P(S) musimy umieć odczytać wartość zmiennej semaforowej. To jednak jest niemożliwe. Dlatego też wartość tę będziemy pamiętać na zmiennej N. Tak naprawdę zmienna ta będzie pełnić dwie funkcje. Jeśli jest dodatnia, to zapamiętuje wartość zmiennej semaforowej, jeśli jest ujemna, to jej wartość bezwzględna oznacza liczbę procesów oczekujących pod semaforem N.
Początkowe wartości poszczególnych zmiennych są następujące:
var mutex: binary semaphore := 1; delay: binary semaphore := 0; N := początkowa wartość symulowanego semafora S
Operację P(S) implementujemy następująco:
P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end else V (mutex);
Przyjrzyjmy się tej procedurze. Opuszczenie semafora ogólnego S ma być atomowe i wykluczać się z innymi operacjami na tym semaforze. Procedura zaczyna się więc od zamknięcia semafora mutex, gwarantującego wzajemne wykluczania. Następnie jest zmniejszana zmienna N. Jeśli na skutek tego zmniejszenia otrzyma ona wartość ujemną, to znaczy, że semafor jest zamknięty. Zgodnie z przedstawionymi intuicjami wartość -N oznacza wtedy liczbę procesów oczekujących, więc zmniejszenie N jest uzasadnione. W takiej sytuacji proces musi jednak poczekać. W tym celu wykonuje operację P na zamkniętym semaforze delay. Ale zanim to uczyni musi podnieść semafor mutex, aby otworzyć dostęp do operacji P(S) i V(S) dla innych procesów (gdybyśmy nie podnieśli semafora mutex doszłoby do zakleszczenia)!
Jeśli semafor był otwarty, to proces kontynuuje swoje działanie bez oczekiwania, więc nie wykonuje operacji P(delay) a jedynie V(mutex).
Operacja V(S) wygląda następująco:
P (mutex); N := N + 1; if N <= 0 then V (delay); V (mutex);
I znów semafor mutex dba o wzajemne wykluczanie i niepodzielność. Zwiększenie zmiennej N jest potrzebne niezależnie od tego czy przed semaforem nikt nie czekał (N >= 0) i w związku z tym trzeba zwiększyć wartość zmiennej semaforowej (czyli zwiększyć N), czy też były procesy oczekujące (N < 0) i jeden z nich należy obudzić, czyli zmniejszyć wartość -N (zwiększając N). Jeśli jednak N było początkowo mniejsze niż zero, to trzeba obudzić jeden z procesów oczekujących na semaforze delay --- stąd operacja V(delay).
Ta z pozoru sensowna symulacja zawiera jednak pewien subtelny błąd. Aby go znaleźć prześledźmy symulację następującego programu:
var S: semaphore := 2;
proces P(i: 1..4);
begin
własne_sprawy;
P (S);
sekcja_krytyczna;
V (S)
end
Widzimy, że jest to rozwiązanie problemu wzajemnego wykluczania, przy czym w sekcji krytycznej mogą przebywać jednocześnie co najwyżej dwa procesy.
Przepiszmy powyższy program zastępując operacje na semaforze S ich implementacją:
var N: integer := 2; mutex : binary semaphore := 1; delay : binary semaphore := 0;
proces P(i: 1..4);
begin
własne_sprawy;
P (mutex);
N := N - 1;
if N <= -1 then
begin
V (mutex);
P (delay) {*}
end else
V (mutex);
sekcja_krytyczna;
P (mutex);
N := N + 1;
if N <= 0 then V (delay);
V (mutex);
end
Przypuśćmy, że do sekcji krytycznej usiłują wejść dwa procesy: P(1) i P(2). Oczywiście udaje im się to. Zmienna N zostaje zmniejszona o 2 ma więc wartość 0, semafor delay jest nadal zamknięty, a mutex otwarty. Popatrzmy, co się stanie, jeśli proces P(3) będzie usiłował wejść do sekcji krytycznej. Zamyka on semafor mutex, zmniejsza N o 1 stwierdza, że N = -1 więc podnosi semafor mutex i ma się zawiesić na semaforze delay. Jest to zgodne z oczekiwaniami, gdyż sekcja krytyczna jest już zajęta przez dwa procesy. Przypuśmy jednak, że zanim proces zawiesi się w wierszu oznaczonym * analogiczny ciąg instrukcji wykona proces P(4). Mamy wówczas następującą sytuację:
Procesy P(1) i P(2) są w sekcji krytycznej. Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość -2. Semafor mutex jest otwarty. Semafor delay jest zamknięty.
Przypuśmy, że teraz procesy P(1) i P(2) po kolei wychodzą z sekcji krytycznej. Proces P(1) zamyka semafor mutex , zwiększa N o jeden na -1, wykonuje operację V (delay) i V(mutex). Sytuacja jest następująca:
Proces P(2) jest w sekcji krytycznej. Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość -1. Semafor mutex jest otwarty. Semafor delay jest otwarty.
Teraz proces P(2) wykonuje analogiczny fragment kodu: zamyka semafor mutex, zwiększa N o 1 i ... podnosi semafor delay! Ale semafor ten jest już otwarty. W zależności od semantyki powoduje to błąd lub nie daje efektu. Przypuśćmy, że nic się nie zmienia. Proces P(2) kontynuuje otwierając semafor mutex, co prowadzi do:
Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość 0. Semafor mutex jest otwarty. Semafor delay jest otwarty.
Teraz swoje działanie kontynuuje proces P(3). Wykonuje operację P (delay) i wchodzi do sekcji krytycznej:
Proces P(3) jest w sekcji krytycznej. Proces P(4) jest tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość 0. Semafor mutex jest otwarty. Semafor delay jest zamknięty.
Gdy proces P(4) spróbuje kontynuować swoje działanie, to wykona operację P(delay) i zostanie wstrzymany, mimo że w sekcji krytycznej jest jeszcze miejsce!. Pokazaliśmy zatem scenariusz ilustrujący błędne (to znaczy niezgodne z oryginalnym programem) działanie symulacji.
Opisaną powyżej symulację na szczęście można łatwo poprawić. Zaskakujący jest przy tym sposób ---- z pozoru bezsensowny, a w rzeczywistości prowadzący do ważnej techniki konstruowania programów wykorzystujących semafory.
Zestawmy dotychczasową implementację operacji P(S) i V(S) z nową, poprawną wersją:
własne_sprawy; P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end else V (mutex); sekcja_krytyczna; P (mutex); N := N + 1; if N <= 0 then V (delay); V (mutex); |
własne_sprawy; P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end; V (mutex); sekcja_krytyczna; P (mutex); N := N + 1; if N <= 0 then V (delay) else V (mutex); |
Przyjrzyjmy się implementacji operacji P(S):
P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end; V (mutex);
Jeśli warunek jest spełniony, to semafor mutex jest zamykany raz a otwierany dwukrotnie! Analogicznie w V(S):
P (mutex); N := N + 1; if N <= 0 then V (delay) else V (mutex);
może się zdarzyć opuszczenie semafora mutex bez jego podniesienia!
Pomimo tego implementacja jest poprawna. Przyjrzyjmy się bliżej zastosowanemu trikowi, który polega na założeniu, że proces budzony z semafora delay zastanie zamknięty semafor mutex. Przy takim założeniu jasna staje się konieczność bezwarunkowego podniesienia semafora mutex na końcu operacji P(S). Z drugiej strony w kodzie operacji V(S) należy zagwarantować, że obudzony proces faktycznie zastanie opuszczony semafor mutex. Aby to zapewnić w implementacji V(S) mutex jest podnoszony jedynie wówczas, gdy nikogo nie budzimy. Jeśli jednak podnosimy semafor delay, to mutex pozostaje zamknięty --- właśnie po to aby proces obudzony z semafora delay zastał zamknięty semafor mutex.
Co daje taka technika? Wyjaśnijmy to na przykładzie scenariusza, który prowadził do błędnego działania poprzedniej symulacji. Zacznijmy od sytuacji, w której procesy P(1) i P(2) są już w sekcji krytycznej, a P(3) i P(4) tuż przed zawieszeniem się na operacji P(delay). Semafor mutex jest otwarty, a semafor delay --- zamknięty. Zmienna N ma wartość -2. Przypuśćmy, że proces P(1) wychodzi teraz z sekcji krytycznej. Zamyka semafor mutex, zwiększa zmienną N na -1 i podnosi semafor delay. Ale mutex pozostaje zamknięty! Z tego powodu zanim proces P(2) będzie mógł rozpocząć wykonanie kodu za swoją sekcją krytyczną, któryś z procesów P(3) lub P(4) (albo oba) muszą wykonać operację V(delay). Ponieważ delay jest w tym momencie otwarty, więc jeden z procesów przejdzie przez niego, zamykając go za sobą i wykona operację V(mutex). Dopiero wtedy dostęp do fragmentów kodu chronionych semaforem mutex staje się otwarty, a scenariusz powodujący błędne działanie poprzedniej symulacji nie jest już możliwy.
Opisaną technikę w ogólności można ująć w następujący schemat. Zawieszanie procesu realizujemy w następujący sposób (dodatkowa zmienna ile_czeka zlicza ile procesów oczekuje na początkowo zamkniętym semaforze sem:
P(mutex);
...
if warunek then
begin
ile_czeka := ile_czeka + 1;
V(mutex);
P(sem); { obudzony proces zastanie zamknięty mutex }
ile_czeka := ile_czeka -1
...
end;
...
V(mutex)
Budzenie procesu realizujemy następująco:
P(mutex) ... if ile_czeka > 0 then V (sem) else V (mutex)
Opisana technika nosi nazwę dziedziczenia sekcji krytycznej, bo budzony z semafora sem proces dziedziczy wyłączny dostęp do sekcji krytycznej chronionej semaforem mutex po procesie budzącym. Umiejętne stosowanie tej techniki pozwala ograniczyć liczbę możliwych przeplotów i uniknąć wielu błędów synchronizacyjnych poprzez wymuszenie niepodzielności akcji budzenia i wznowienia działania przez proces obudzony.