Monitory

Monitory

Podstawową wadą semafora jest to, że nie jest to mechanizm strukturalny, przez co trudno jest analizować programy współbieżne i ogarnąć wszystkie możliwe przeploty. Dochodzą do tego częste błędy polegające chociażby na niezamierzonej zamianie operacji P i V ze sobą.

Monitor jako moduł programistyczny

Powyższych wad jest pozbawiony monitor, który stanowi połączenie modułu programistycznego z sekcją krytyczną. Monitor jest po prostu modułem zawierającym deklaracje stałych, zmiennych, funkcji i procedur. Wszystkie te obiekty, z wyjątkiem jawnie wskazanych funkcji i procedur są lokalne w monitorze i nie są widoczne na zewnątrz niego. Wskazane funkcje i procedury (tzw. eksportowane) są widoczne na zewnątrz monitora. Mogą je wywoływać procesy i za ich pośrednictwem manipulować danymi ukrytymi w monitorze. Monitor zawiera też kod, który służy do jego inicjacji, na przykład do ustawienia wartości początkowych zmiennych deklarowanych w monitorze.

Monitor będziemy definiować korzystając z następującej składni:

monitor Nazwa;
  definicje stałych i typów;
  deklaracje zmiennych lokalnych;
  deklaracje procedur i funkcji;
begin
  instrukcje inicjujące monitor;
end;

Definiując stałe, typy, zmienne i procedury będziemy stosować składnię Pascala z tym, że procedury i funkcje udostępniane na zewnątrz będziemy poprzedzać słowem kluczowym export.

Aby wywołać eksportowaną przez monitor M procedurę P w pewnym procesie użyjemy notacji:

 M.P (parametry)

Z powyższego opisu wynika, że monitor jest po prostu modułem, ukrywającym część informacji i udostępniającym na zewnątrz pewne funkcje i procedury. Ale to nie są jeszcze wszystkie własności monitora.

Monitor jako sekcja krytyczna

Monitor jest z definicji sekcją krytyczną. Co to oznacza? Otóż jednocześnie co najwyżej jeden proces może być w trakcie wykonania kodu znajdującego się w monitorze. Innymi słowy: jeśli jakiś proces wywoła procedurę eksportowaną przez monitor M i rozpocznie jej wykonanie, to do czasu powrotu z tej procedury żaden inny proces nie może rozpocząć wykonania tej ani żadnej innej procedury/ funkcji monitora. O procesie, który wywołał funkcję/procedurę monitora i nie zakończył jeszcze jej wykonania, będziemy mówić, że znajduje się w monitorze. Zatem jednocześnie w monitorze może przebywać co najwyżej jeden proces.

Taka definicja narzuca sposób naturalny sposób korzystania ze zmiennych współdzielonych przez procesy. Po prostu należy umieścić je w monitorze i dostęp do nich realizować za pomocą eksportowanych procedur i funkcji. Programista korzystający w taki właśnie sposób ze zmiennej dzielonej nie musi myśleć o zapewnianiu wyłączności w dostępie do niej --- robi to za niego automatycznie sam monitor.

Co się jednak dzieje, jeśli pewien proces wywoła procedurę monitora w chwili, gdy inny proces już się w nim znajduje? Otóż taki proces musi poczekać. Z każdym monitorem jest związana kolejka procesów oczekujących na "wejście" do niego. Jest to kolejka prosta: proces, który zgłosił się jako pierwszy i został wstrzymany przed wejściem do monitora, jako pierwszy zostanie wznowiony. Zaznaczmy, niezależnie od tego, którą procedurę czy funkcję monitora proces wywołał, zostanie on w razie konieczności wstrzymany i umieszczony w tej samej kolejce. Jest jedna kolejka procesów oczekujących na wejście do monitora, a nie tak jak w Adzie, osobne kolejki do poszczególnych procedur eksportowanych.

Gdy proces, który przebywał w monitorze, opuści go, czyli gdy następuje powrót z wywołanej funkcji/procedury monitora do procesu, pierwszy proces w kolejce procesów oczekujących na wejście do monitora jest automatycznie budzony. I znów dzieje się to automatycznie, programista nie musi się o to martwić.

Zmienne warunkowe

Często oprócz zapewnienia wyłącznego dostępu do zmiennych dzielonych zachodzi także potrzeba synchronizacji procesów w inny sposób. Proces musi na przykład poczekać na dostępność pewnych zasobów lub zakończenie przetwarzania przez inne procesy. Aby realizować tego typu zadania, monitor oferuje specjalny typ danych, tzw. zmienne warunkowe.

Zmienne warunkowe deklarujemy jako zmienne typu condition. Mogą one wystepować jedynie wewnątrz moniora. Na zmiennej warunkowej c proces może wykonać następujące operacje:

1. wait (c). Powoduje wstrzymanie działania procesu, który ją wykonał. Proces opuszcza chwilowo monitor (tym samym może do niego wejść inny proces z kolejki procesów oczekujących na wejście) i zostaje wstrzymany w kolejce prostej związanej ze zmienną warunkową c.
2. empty(c). Jest to funkcja logiczna przekazująca w wyniku informacje, czy są procesy oczekujące na zmiennej warunkowej c.
3. signal(c). Powoduje obudzenie pierwszego procesu z kolejki procesów oczekujących na zmiennej warunkowej c. Jeśli kolejka jest pusta, to instrukcja nie daje żadnego efektu. Obudzony proces natychmiast wznawia swoje działanie w monitorze od kolejnej instrukcji za wait, w którym został wstrzymany.

Uproszczona semantyka instrukcji signal

Bliższa analiza działania operacji signal prowadzi do niepokojących spostrzeżeń. Zgodnie z powyższą semantyką signal (c) budzi pierwszy proces z kolejki procesów oczekujących w kolejce związaną ze zmienną c. Obudzony proces ma natychmiast wznowić działanie w monitorze. Ale przecież w monitorze jest już inny proces: ten, który wykonał signal. Mamy więc dwa procesy w monitorze, co przeczy temu, że monitor jest sekcją krytyczną.

Aby poradzić sobie z tym problemem przyjmijmy na razie, że signal musi być ostatnią instrukcją wykonywaną przez proces w monitorze. Wtedy proces po wykonaniu operacji signal wychodzi z monitora oddając go obudzonemu procesowi. Podkreślmy to raz jeszcze. Jeśli proces wykonuje signal na niepustej kolejce i wychodzi z monitora, to do monitora wróci obudzony proces przed jakimikolwiek procesami oczekującymi na wejście do monitora. Jest to bardzo ważna i pożyteczna cecha monitora.

Przykład. Wzajemne wykluczanie.

Popatrzmy teraz, jak zazwyczaj korzysta się z monitorów. W zasadzie każdy problem synchronizacyjny można przedstawić w postaci następującego schematu procesu:

process P;
begin
  repeat
    praca nie wymagająca synchronizacji;
    protokół wstępny;
    fragment wymagający synchronizacji;
    protokół końcowy
  until false;
end;

Protokoły wstępny i końcowy zazwyczaj wymagają wzajemnego wykluczania. Naturalnym podejściem jest zatem umieszczenie ich w monitorze w postaci eksportowanych procedur. Zmienne potrzebne do zapewnienia właściwej synchronizacji umieszczamy także w tym samym monitorze, jako zmienne lokalne.

Spójrzmy, jak takie podejście sprawdza się przy problemie dostępu do sekcji krytycznej. Przypuśćmy, że z sekcji krytycznej może jednocześnie korzystać co najwyżej k procesów. Kod procesu jest oczywisty:

process P;
begin
  repeat
    własne_sprawy;
    M.Chce;
    sekcja_krytyczna;
    M.Zwalniam; 
  until false;
end;
 

W monitorze M umieścimy zmienną zliczającą aktualną liczbę wolnych miejsc w sekcji krytycznej, zmienną warunkową czekaj służącą do wstrzymywania procesów, gdy nie ma dla nich miejsca w sekcji krytycznej:

monitor M; 
var
  wolnych: integer;
  czekaj: condition;

Następnie implementujemy procedurę Chce. Przygotowując procedury monitorowe, a zwłaszcza protokoły wstępne, dobrze jest wychwycić warunek na wstrzymanie procesu i zastosować instrukcję warunkową, która przy prawdziwym warunku powoduje zawieszenie procesu. Dalsze czynności wykonywane przez proces w protokole wstępnym często nie zależą od tego, czy proces czekał, czy nie. Z technicznego punktu widzenia oznacza to, że we wspomnianej instrukcji warunkowej najczęściej nie jest potrzebna część po else.

W omawianym przekładzie proces powinien poczekać, jeśli nie ma wolnych miejsc. Gdy będą już wolne miejsca, to należy zmniejszyć ich liczbę i wyjść z monitora:

export procedure Chce;
begin
  if wolnych = 0 then
    wait (czekaj);
  wolnych := wolnych - 1
end;

Protokół końcowy zwalnia jedno miejsce i budzi proces oczekujący na wejście do sekcji krytycznej:

export procedure Zwalniam;
begin
  wolnych := wolnych + 1;
  signal (czekaj)
end;

Monitor wymaga również zainicjowania zmiennych:

 begin
   wolnych := k
 end.

Zwróćmy uwagę, że w procedurze Zwalniam sygnał jest wysyłany bezwarunkowo. Jeśli nikt nie czekał na warunku czekaj, to nie stanie się nic złego, gdyż taki sygnał nie powoduje żadnego efektu.

Przykład. Czytelnicy i pisarze

Przeanalizujmy jeszcze rozwiązanie problemu czytelników i pisarzy. Tak jak w poprzednim przykładzie, protokoły wstępne i końcowe czytelnika i pisarza umieścimy w monitorze, co prowadzi do następującego kodu procesów:

proces Czytelnik;
begin
  repeat
    własne_sprawy;
    Czytelnia.ChceCzytać;
    czytanie;
    Czytelnia.KoniecCzytania;
  until false;
end;

proces Pisarz;
begin
  repeat
    własne_sprawy;
    Czytelnia.ChcePisać;
    pisanie;
    Czytelnia.KoniecPisania;
  until false;
end;

Monitor Czytelnia zwiera dwie zmienne warunkowe: do wstrzymywania czytelników i pisarzy. Oprócz tego jest potrzebna zmienna pamiętająca ilu czytelników czyta i ilu pisarzy pisze. Ta druga zmienna mogłaby być zmienną logiczną, ale dla symetrii niech obie zmienne będą zmiennymi całkowitymi:

monitor Czytelnia;
var
  iluczyta: integer;
  ilupisze: integer;
  czytelnicy: condition;
  pisarze: condition;

Rozpocznijmy od protokołu wstępnego pisarza. Pisarz musi czekać, jeśli ktokolwiek jest w czytelni:

export procedure ChcePisać;
begin
  if iluczyta+ilupisze> 0 then
    wait (pisarze);
  ilupisze := ilupisze + 1
end;

Protokół wstępny czytelnika jest podobny. Czytelnik musi poczekać, jeśli ktoś pisze lub --- aby nie zagłodzić pisarzy --- są pisarze oczekujący na pisanie. Instrukcję oznaczoną gwiazdką wyjaśnimy nieco później:

export procedure ChceCzytać;
begin
  if (ilupisze > 0) or not empty (pisarze) then
    wait (czytelnicy);
  iluczyta := iluczyta + 1;
  signal (czytelnicy)   {*}
end;

Protokół końcowy czytelnik jest prosty. Jeśli jest on ostatnim wychodzącym z czytelni, to budzi pisarza:

export procedure KoniecCzytania;
begin
  iluczyta := iluczyta - 1;
  if iluczyta = 0 then
    signal (pisarze)   
end;

Z protokołem końcowym pisarza jest jednak pewien problem. Umówiliśmy się, że operacja signal jest ostatnią operacją wykonywaną w monitorze. Tymczasem pisarz powinien wpuścić wszystkich oczekujących czytelników, o ile są jacyś, lub jednego pisarza, jeśli nie czekają czytelnicy. Wpuszczenie wszystkich oczekujących czytelników wymagałoby wykonanie operacji signal w pętli, a to powoduje, że signal nie jest ostatnią operacją monitora. Spróbujmy zastosować inne rozwiązanie. Niech pisarz budzi jednego czytelnika, o ile są oczekujący czytelnicy. Zauważmy, że obudzony czytelnik, dzięki dodanej do protokołu wstępnego instrukcji oznaczonej {*} obudzi kolejnego czytelnika, ten kolejny czytelnik obudzi następnego itd. aż do obudzenia wszystkich. Taką technikę będziemy nazywać kaskadowym zwalnianiem:

export procedure KoniecPisania;
begin
  ilupisze := ilupisze - 1;
  if not empty (czytelnicy) then
    signal (czytelnicy) 
  else
    signal (pisarze)   
end;
  

Pozostała jeszcze część inicjująca monitor:

begin
  iluczyta := 0; ilupisze := 0;
end.

Pełna semantyka instrukcji signal

Umieszczenie operacji signal na końcu kodu procesu nie jest jednak zawsze możliwe. Aby móc stosować signal także wewnątrz procedury monitora trzeba uściślić semantykę operacji signal w następujący sposób. Signal(c) powoduje obudzenie pierwszego procesu z kolejki procesów oczekujących na zmiennej warunkowej c. Jeśli kolejka jest pusta, to instrukcja nie daje żadnego efektu. W przeciwnym razie obudzony proces natychmiast wznawia swoje działanie w monitorze od kolejnej instrukcji za wait, w którym został wstrzymany, a proces wykonujący operację signal opuszcza tymczasowo monitor i zostaje umieszczony na początku kolejki procesów oczekujących na wejście do monitora.

Dzięki temu, że proces budzący opuszcza monitor, proces obudzony może wznowić swoje działanie bez obawy, że nie będzie jedynym procesem w monitorze. Z drugiej strony, umieszczenie budzącego na początku kolejki na wejściu do monitora zapewnia, że zostanie on wznowiony przed procesami oczekującymi na wejście do monitora, gdy tylko obudzony przez niego proces wyjdzie z niego.

Taka semantyka powoduje jednak pewne problemy. Kolejność instrukcji w, z pozoru niepodzielnej procedurze monitora, zaczyna mieć istotne znaczenie. Aby to zilustrować przyjrzyjmy się następującemu rozwiązaniu problemu wzajemnego wykluczania (z jednym procesem w sekcji krytycznej):

monitor M;
var
  wolne: boolean; 
  czekaj: condition;

export procedure Chce;
begin
  if not wolne then
    wait (czekaj);
  wolne := false
end;

export procedure Zwalniam;
begin
  wolne := true;
  signal (czekaj)
end;

begin
  wolne := true
end.

Powyższe rozwiązanie jest poprawne. Zamieńmy jednak kolejność instrukcji w procedurze Zwalniam:

export procedure Zwalniam;
begin
  signal (czekaj);
  wolne := true
end;

Program przestał być poprawny! Przypuśćmy, że proces P(1) wykona procedurę Chce. Spowoduje to ustawienie zmiennej wolne na false, a proces P(1) kończy wykonanie procedury Chce i wchodzi do sekcji krytycznej. Jeśli teraz proces P(2) wywoła procedurę Chce, to zostanie wstrzymany na zmiennej czekaj. Niech proces P(1) opuści teraz sekcję krytyczną. Wywoła wówczas procedurę Zwalniam. Pierwszą instrukcją jest signal. Zatem proces P(1) wyjdzie na chwilę z monitora, a obudzony zostanie proces P(2), który wznowi swoje działanie w procedurze Chce i ustawi zmienną wolne na true, po czym wyjdzie z monitora i przejdzie do sekcji krytycznej. Ponieważ monitor jest pusty, więc wraca do niego proces P(1), który wykona wolne := true. Efekt: proces P(2) jest w sekcji krytycznej, a zmienna wolne ma wartość true. Jeśli teraz proces P(1) ponownie wywoła procedurę Chce, to zostanie wpuszczony do sekcji krytycznej, mimo że przebywa tam już inny proces.