Synchronizacja procesów

Streszczenie

W niniejszym wykładzie zajmujemy się problemem synchronizacji współpracujących ze sobą procesów współbieżnych. Poznamy mechanizmy i techniki programistyczne służące do synchronizowania procesów.

Na początku przedstawiamy sam problem synchronizacji procesów. Dalej próbujemy rozwiązać go przy użyciu klasycznych konstrukcji programistycznych. Jest to możliwe, lecz bardzo skomplikowane i nieefektywne. Dalej poznajemy typowe mechanizmy synchronizacji procesów udostępniane przez systemy operacyjne. Ich wykorzystanie prześledzimy na typowych przykładach.

Wprowadzenie

Problem synchronizacji procesów pojawia się wszędzie tam, gdzie mamy do czynienia ze współpracującymi ze sobą współbieżnymi procesami. Oto najczęściej spotykane przyczyny, dla których konieczna jest synchronizacja współpracujących procesów:

Procesy współdzielą pewną strukturę danych -- Zwykle wykonania operacji na tej strukturze danych nie mogą dowolnie przeplatać się współbieżnie ze sobą. Pojedyncze operacje muszą być "zatomizowane", tzn. tylko jeden proces może na raz modyfikować współdzieloną strukturę danych, stąd konieczność synchronizacji procesów przy dostępie do struktury danych. Jest to przykład tzw. problemu sekcji krytycznej.
Wyniki działania jednego procesu stanowią dane dla innego procesu. Oczywiście drugi z procesów może przetwarzać dane dopiero wówczas, gdy zostaną one obliczone przez pierwszy z procesów, stąd konieczność synchronizacji działań obydwu procesów. Dodatkowo, jeżeli dane zajmują dużo pamięci i są obliczane stopniowo, to drugi z procesów może informować pierwszy, które dane zostały "zużyte" i można wykorzystać zajmowaną przez nie pamięć. Przykładem takiego współdziałania procesów jest problem producenta-konsumenta.
Procesy korzystają z pewnej wspólnej puli zasobów, które pobierają i zwalniają wedle potrzeb. Oczekiwanie na zasoby i przydzielanie ich wymaga również synchronizacji między procesami. Przykładem dobrze ilustrującym taki rodzaj synchronizacji jest problem pięciu filozofów.

Zrealizowanie synchronizacji między procesami wymaga pewnych narzędzi i technik programistycznych, opisanych w niniejszym wykładzie. Na pierwszy rzut oka problem może się wydawać trywialny. Okazuje się jednak, że programowanie procesów współbieżnych jest bardzo trudne. Liczba zależności między procesami jest trudna do ogarnięcia.

Analizując programy współbieżne zakładamy, że współbieżne wykonanie procesów może polegać na dowolnym przepleceniu wykonań poszczególnych procesów. Dodatkowo musimy pamiętać, że przeplatane nie są instrukcje języka programowania wysokiego poziomu, lecz instrukcje procesora w skompilowanym programie. Jeśli nasz program jest poprawny przy takim założeniu, to mamy pewność, że będzie działał poprawnie (niezależnie od realizacji systemu operacyjnego, parametrów technicznych komputera, zachodzących przerwań i innych procesów działających w systemie).

W przypadku programów współbieżnych testowanie programów ma bardzo ograniczone zastosowanie. Nie jesteśmy w stanie przetestować wszystkich możliwych przeplotów wykonań procesów. Siłą rzeczy testy są przeprowadzane na konkretnej platformie i konkretnym komputerze. Tak więc pomyślne wyniki testów wcale nie gwarantują, że program będzie działał poprawnie na innej platformie, czy np. na szybszym komputerze. Jesteśmy więc skazani na weryfikowanie poprawności programów współbieżnych. Już w przypadku programów sekwencyjnych jest to trudne zadanie, a w przypadku programów współbieżnych jest to bardzo trudne.

Synchronizacja procesów za pomocą wspólnych zmiennych

Zanim poznamy wyspecjalizowane narzędzia programistyczne służące do synchronizacji procesów, spróbujmy rozwiązać problem synchronizacji procesów używając zwykłych konstrukcji programistycznych. Procesy mogą synchronizować swoje działania modyfikując współdzielone zmienne. Spróbujemy rozwiązać problem synchronizacji procesów na przykładzie problemu producenta-konsumenta i sekcji krytycznej.

Problem producenta-konsumenta

Rozważmy następujący problem. Mamy dane dwa procesy: producenta i konsumenta. Oba procesy działają w nieskończonej pętli. Producent wytwarza jednostki jakiegoś produktu, a konsument konsumuje je. Jednostki wyprodukowane, ale jeszcze nie skonsumowane są umieszczane w buforze. Bufor może pomieścić maksymalnie n jednostek produktu. Jeżeli bufor jest pusty, to konsument musi zaczekać, aż producent wyprodukuje kolejną jednostkę produktu. Jeżeli bufor jest pełny, to producent musi zaczekać, aż konsument pobierze jednostkę produktu z bufora.

Nie jest to problem akademicki, lecz bardzo często spotykany w systemach operacyjnych. Choćby buforowanie znaków naciskanych na klawiaturze, czy wysyłanie wydruków na drukarkę to przykłady problemu producent-konsument.

Procesy producenta i konsumenta mają podobny schemat:

producent:

  repeat
    wyprodukuj jednostkę produktu;
    wstaw wyprodukowaną jednostkę do bufora
  until false

konsument:

  repeat
    pobierz z bufora jednostkę produktu;
    skonsumuj pobraną jednostkę
  until false

Bufor służący do przechowywania jednostek produktu może być zrealizowany za pomocą następujących zmiennych:

  var
    bufor: array [0..n-1] of produkt;
    pierwszy: 0..n-1;
    licznik: 0..n;

Początkowo zmienna pierwszy może mieć dowolną wartość (z zakresu), a zmienna licznik powinna być równa 0. Wstawianie i pobieranie jednostek produktu z bufora można zaimplementować następująco:

producent:

  repeat
    wyprodukuj jednostkę produktu;
    while licznik = n do;
    bufor [(pierwszy+licznik) mod n] := wyprodukowana jednostka;
    licznik := licznik + 1
  until false

konsument:

  repeat
    while licznik = 0 do;
    pobrana jednostka := bufor [pierwszy];
    pierwszy := (pierwszy + 1) mod n;
    licznik := licznik - 1;
    skonsumuj pobraną jednostkę
  until false

Oglądane z osobna, oba procesy wydają się poprawne. Jeśli jednak uruchomimy je współbieżnie, mogą one działać niepoprawnie. Błąd tkwi w instrukcjach licznik := licznik + 1 i licznik := licznik - 1. Instrukcje te mogą być zaimplementowane w języku maszynowym, na przykład, w następujący sposób:

  rejestr1 := licznik;
  rejestr1 := rejestr1 + 1;
  licznik := rejestr1

  rejestr2 := licznik;
  rejestr2 := rejestr2 - 1;
  licznik := rejestr2

Załóżmy, że w buforze są trzy jednostki produktu, czyli licznik = 3. Współbieżnie wkładamy i pobieramy po jednej jednostce produktu do/z bufora. W rezultacie w buforze nadal powinny być trzy jednostki produktu. Jeżeli instrukcje obu procesów przeplotą się w następujący sposób:

  rejestr1 := licznik;
  rejestr2 := licznik;
  rejestr2 := rejestr2 - 1;
  licznik := rejestr2
  rejestr1 := rejestr1 + 1;
  licznik := rejestr1

to zmienna licznik będzie równa 4!

Rozwiązaniem problemu jest "zatomizowanie" operacji pobierania i wkładania jednostek produktu z i do bufora. Należy zapewnić, aby w trakcie gdy jeden proces zmienia zawartość bufora drugi nie mógł robić tego równocześnie. Inaczej mówiąc, operacje wkładania i wyjmowania z bufora (z wyjątkiem pętli oczekujących) powinny tworzyć tzw. sekcję krytyczną.

Problem sekcji krytycznej

Sekcja krytyczna, to fragment(y) kodu lub operacje, które nie mogą być wykonywane współbieżnie. Sekcja krytyczna jest otoczona dodatkowym kodem synchronizującym przebywanie procesów wejściowych -- przed wejściem do sekcji krytycznej każdy proces musi przejść przez sekcję wejściową, a wychodząc przechodzi przez sekcję wyjściową. Dopóki jakiś proces przebywający w sekcji krytycznej nie opuści jej, inne procesy chcące wejść do sekcji krytycznej są wstrzymywane w sekcji wejściowej. Przechodząc przez sekcję wyjściową, proces opuszczający sekcję krytyczną wpuszcza jeden z procesów oczekujących (jeśli takowe są). Zakładamy tutaj, że każdy proces, który wejdzie do sekcji krytycznej kiedyś ją opuści.

Podstawowa własność, jaką powinna spełniać sekcja krytyczna, to wzajemne wykluczanie: tylko jeden proces na raz może przebywać w sekcji krytycznej. Gdyby było to jedyne wymaganie wobec sekcji krytycznej, to można by ją bardzo prosto zaimplementować: nie wpuszczać żadnych procesów do sekcji krytycznej. Oczywiście nie o to chodzi! Stąd też druga wymagana własność, to wykorzystanie sekcji krytycznej: jeśli jakiś proces chce wejść do sekcji krytycznej, to nie może ona pozostawać pusta.

Jeśli wiele procesów oczekuje na wejście do sekcji krytycznej, to nie jest określone w jakiej kolejności wejdą one do niej. Nie ma tu jednak zupełnej dowolności. Przyjęto najmniejsze wymagania zapewniające sensowne działanie sekcji krytycznej, brak zagłodzenia oczekujących procesów: każdy proces, który chce wejść do sekcji krytycznej ma gwarancję, że kiedyś do niej wejdzie.

Rozwiązanie problemu sekcji krytycznej polega na podaniu implementacji sekcji wejściowej i wyjściowej. Mając dane takie implementacje, moglibyśmy np. rozwiązań problem producenta-konsumenta w następujący sposób:

producent:

  repeat
    wyprodukuj jednostkę produktu;
    while licznik = n do;
    sekcja wejściowa;
    bufor [(pierwszy+licznik) mod n] := wyprodukowana jednostka;
    licznik := licznik + 1;
    sekcja wyjściowa
  until false

konsument:

  repeat
    while licznik = 0 do;
    sekcja wejściowa;
    pobrana jednostka := bufor [pierwszy];
    pierwszy := (pierwszy + 1) mod n;
    licznik := licznik - 1;
    sekcja wyjściowa;
    skonsumuj pobraną jednostkę
  until false

Algorytm Dekkera

Algorytm Dekkera to implementacja sekcji krytycznej dla dwóch procesów korzystająca ze zmiennych współdzielonych przez te procesy. Algorytm ten wykorzystuje trzy zmienne:

  var
    k: array [1..2] of 0..1;
    czyja_kolej: 1..2;

Początkowo komórki tablicy k są równe 1. Każdy z procesów kontroluje jedną komórkę tej tablicy. Gdy proces chce wejść do sekcji krytycznej, to ustawia komórkę na 0, aż do chwili wyjścia z sekcji krytycznej.

Zmienna czyja_kolej jest początkowo równa 1. Łamie ona symetrię między procesami. W sytuacji, gdy obydwa procesy chcą wejść do sekcji krytycznej zmienna ta rozstrzyga, który powinien ustąpić drugiemu.

Zakładamy, że procesy mają numery 1 i 2, i każdy proces pamięta swój numer na zmiennej lokalnej p.

Sekcja wejściowa:

  k [p] := 0;
  while k [3 - p] = 0 do begin
    if czyja_kolej ≠ p then begin
      (* Ustąp drugiemu procesowi. *)
      k [p] := 1;
      while czyja_kolej ≠ p do;
      k [p] := 0
    end
  end

Sekcja wyjściowa:
```
  k [p] := 1;
  czyja_kolej := 3 - p;
```

Rozwiązanie to jest poprawne, jednak ma pewne wady:

jest ograniczone do dwóch procesów,
proces oczekujący oczekuje aktywnie, tzn. czekając na jakieś zdarzenie sprawdza ciągle warunek określający, czy dane zdarzenie już zaszło.

Pierwszą z tych wad można usunąć -- za chwilę zobaczymy jak. Druga wada jest jednak poważna. Oczekiwanie aktywne oznacza niepotrzebne zużycie czasu procesora. Nie można jej usunąć bez wprowadzenia dodatkowych mechanizmów programistycznych. Mechanizmy takie poznamy dalej.

Algorytm piekarniany

Algorytm piekarniany stanowi rozwiązanie problemu sekcji krytycznej dla n procesów. W polskich realiach algorytm ten mógłby nazywać się pocztowy, gdyż przypomina system numerków wydawanych oczekującym klientom w urzędach pocztowych. Algorytm ten korzysta z następujących zmiennych współdzielonych:

  var
    wybieranie: array [1..n] of boolean;
    numerek: arrzy [0..n-1] of integer;

Początkowo elementy tych tablic są równe odpowiednio false i 0. Procesy są ponumerowane od 1 do n. Zakładamy, że każdy proces pamięta swój numer na zmiennej lokalnej p.

Procesy chcące wejść do sekcji krytycznej "pobierają numerki". W tablicy wybieranie proces zaznacza, iż jest właśnie w trakcie pobierania numerka, a pobrany numerek zapamiętuje w tablicy numerek. Proces wchodzi do sekcji krytycznej, gdy upewni się, że jest pierwszy w kolejce. Po wyjściu z sekcji krytycznej proces "wyrzuca numerek", tzn. zapisuje w tablicy numerek wartość 0.

Jest pewna różnica między algorytmem piekarnianym, a systemem numerków stosowanym w urzędach pocztowych. Może się zdarzyć, że dwa procesy otrzymają ten sam numerek. Mamy gwarancję, że kolejne numerki tworzą ciąg niemalejący, możliwe są w nim jednak powtórzenia. Jeżeli dwa procesy otrzymają ten sam numerek, to pierwszeństwo ma proces o niższym numerze (p). Możemy więc powiedzieć, że procesy wchodzą do sekcji krytycznej w porządku leksykograficznym par (numerek, numer procesu). (Para (a, b) poprzedza w porządku leksykograficznym parę (c, d), co oznaczamy przez (a, b) < (c, d), gdy a < c, lub a = c oraz b < d.)

Sekcja wejściowa:

  wybieranie [p] := true;
  numerek [p] := max (numerek [1], numerek [2], ..., numerek [n]) + 1;
  wybieranie [p] := false;
  for j := 1 to n do begin 
    while wybieranie [j] do;
    while numerek [j] ≠ 0 and (numerek [j], j) < (numerek [p], p) do;
  end

Sekcja wyjściowa:
```
  numerek [p] := 0;
```

Proces czekający na wejście do sekcji krytycznej z każdym krokiem pętli for upewnia się/czeka aż proces nr j nie stoi przed nim w kolejce do sekcji krytycznej.

Algorytm piekarniany jest bardziej ogólny niż algorytm Dekkera, lecz również nie jest wolny od wad: nadal mamy do czynienia z aktywnym oczekiwaniem, ponadto liczba procesów jest ograniczona przez stałą n. W kolejnym punkcie dowiemy się, jak pozbyć się aktywnego oczekiwania.

Mechanizmy synchronizacji

W punkcie tym przedstawimy wybrane najważniejsze mechanizmy synchronizacji realizowane przez systemy operacyjne i/lub języki programowania.

Semafory

Nazwa dobrze oddaje naturę semaforów -- jest to mechanizm synchronizacji idealnie pasujący do rozwiązywania problemu sekcji krytycznej, a jego działanie przypomina działanie semafora kolejowego. Wyobraźmy sobie wielotorową magistralę kolejową, która na pewnym odcinku zwęża się do k torów. Pociągi jeżdżące magistralą to procesy. Zwężenie to uogólnienie sekcji krytycznej. Na zwężonym odcinku może znajdować się na raz maksymalnie k pociągów, każdy na oddzielnym torze. Podobnie jak w przypadku sekcji krytycznej, każdy oczekujący pociąg powinien kiedyś przejechać i żaden pociąg nie powinien stać, jeżeli jest wolny tor. Semafor to specjalna zmienna całkowita, początkowo równa k. Specjalna, ponieważ (po zainicjowaniu) można na niej wykonywać tylko dwie operacje:

P -- Jeżeli semafor jest równy 0 (semafor jest opuszczony), to proces wykonujący tę operację zostaje wstrzymany, dopóki wartość semafora nie zwiększy się (nie zostanie on podniesiony). Gdy wartość semafora jest dodatnia (semafor jest podniesiony), to zmniejsza się o 1 (pociąg zajmuje jeden z k wolnych torów).
V -- Wartość semafora jest zwiększana o 1 (podniesienie semafora). Jeżeli jakiś proces oczekuje na podniesienie semafora, to jest on wznawiany, a semafor natychmiast jest zmniejszany.

Istotną cechą operacji na semaforach jest ich niepodzielność. Jeżeli jeden z procesów wykonuje operację na semaforze, to (z wyjątkiem wstrzymania procesu, gdy semafor jest opuszczony) żaden inny proces nie wykonuje w tym samym czasie operacji na danym semaforze. Aby zapewnić taką niepodzielność, potrzebne jest specjalne wsparcie systemowe lub sprzętowe.

Rozwiązanie problemu sekcji krytycznej za pomocą semaforów jest banalnie proste. Wystarczy dla każdej sekcji krytycznej utworzyć odrębny semafor, nadać mu na początku wartość 1, w sekcji wejściowej każdy proces wykonuje na semaforze operację P, a w sekcji wyjściowej operację V. Wymaga to jednak od programisty pewnej dyscypliny: Każdej operacji P musi odpowiadać operacja V i to na tym samym semaforze. Pomyłka może spowodować złe działanie sekcji krytycznej.

Jeżeli procesy mogą przebywać na raz więcej niż w jednej sekcji krytycznej, to musimy zwrócić uwagę na możliwość zakleszczenia. Problem zakleszczenia jest omówiony szczegółowo w następnym wykładzie. Wyobraźmy sobie, że mamy dwa semafory: S i Q, każdy związany z jedną sekcją krytyczną. Mamy też dwa procesy: P1 i P2 -- każdy z nich chce wejść równocześnie do obydwu sekcji krytycznych. Jeżeli są one zaimplementowane następująco:

P1:

  P(S);
  P(Q);
  Sekcje krytyczne
  V(Q);
  V(S);

P2:

  P(Q);
  P(S);
  Sekcje krytyczne
  V(S);
  V(Q);

to możliwy jest następujący scenariusz. Proces P1 opuszcza semafor S, po czym proces P2 opuszcza semafor Q. Wówczas proces P1 czeka w nieskończoność na podniesienie semafora Q, a proces P2 na podniesienie semafora S. Sytuację taką nazywamy właśnie zakleszczeniem. W przedstawionym przykładzie rozwiązaniem jest opuszczanie semaforów w obu procesach w tej samej kolejności.

Semafory są tak często stosowane do rozwiązywania problemu sekcji krytycznej, że spotyka się ich uproszczoną wersję: semafory binarne. Semafor binarny, to taki semafor, który może przyjmować tylko dwie wartości: 0 i 1. Próba podniesienia semafora równego 1, w zależności od implementacji, nie zmienia jego wartości lub powoduje błąd.

Zastosowanie semaforów nie ogranicza się do problemu sekcji krytycznej. Operacje P i V nie muszą być wykonywane zgodnie z podanym wyżej schematem. Przykładem innego zastosowania semaforów będzie podane niżej rozwiązanie problemu producenta-konsumenta.

Kolejki komunikatów

Kolejki komunikatów przypominają uporządkowane skrzynki na listy. Podstawowe dwie operacje, jakie można wykonywać na kolejce, to wkładanie i wyjmowanie komunikatów (pakietów informacji) z kolejki. Komunikaty są uporządkowane w kolejce na zasadzie FIFO (ang. first in, first out). Włożenie powoduje dołączenie komunikatu na koniec kolejki, a pobranie powoduje wyjęcie pierwszego komunikatu z kolejki. Jeżeli kolejka jest pusta, to próba pobrania komunikatu powoduje wstrzymanie procesu w oczekiwaniu na komunikat.

Możliwych jest wiele różnych implementacji kolejek komunikatów, różniących się zestawem dostępnych operacji i ew. ograniczeniami implementacyjnymi. Pojemność kolejki może być ograniczona. Wówczas próba włożenia komunikatu do kolejki powoduje wstrzymanie procesu w oczekiwaniu na pobranie komunikatów. Niektóre implementacje mogą udostępniać nieblokujące operacje wkładania/pobierania komunikatów -- wówczas zamiast wstrzymywania procesu przekazywana jest informacja o niemożności natychmiastowego wykonania operacji. Możliwe jest też selektywne pobieranie komunikatów z kolejki.

Kolejki komunikatów są równie silnym mechanizmem synchronizacji, co semafory. Mając do dyspozycji semafory można zaimplementować kolejki komunikatów -- przekonanie się o tym pozostawiamy jako ćwiczenie dla czytelnika. Odwrotna konstrukcja jest również możliwa. Rozważmy kolejkę komunikatów, do której wkładamy tylko puste, nic nie znaczące komunikaty. Wówczas kolejka taka będzie zachowywać się jak semafor. Chcąc zainicjować ją na określoną wartość, należy na początku włożyć do niej określoną ilość pustych komunikatów.

Monitory

Monitory to przykład strukturalnego mechanizmu synchronizacji wbudowanego w języki programowania wysokiego poziomu. Monitor to rodzaj klasy, której metody stanowią sekcję krytyczną. (Mówiąc o klasach, pomijamy tutaj zjawisko dziedziczenia.) Atrybuty monitora są dostępne jedynie wewnątrz (metod) monitora. Konstrukcja monitora zapewnia, że tylko jeden proces na raz może znajdować się w monitorze. Pozostałe procesy oczekują w kolejce (FIFO). Jeśli jakiś proces chce wejść do monitora, który jest właśnie zajęty, to jest on wstawiany na koniec kolejki procesów oczekujących na wejście do monitora. Jeśli proces opuszcza monitor, a inne procesy czekają w kolejce na wejście do monitora, to pierwszy proces z kolejki wchodzi do monitora.

Monitory stanowią wygodniejsze rozwiązanie problemu sekcji krytycznej niż semafory, ze względu na ich strukturalny charakter. Stosując semafory można popełnić szereg błędów programistycznych: zapomnieć o podniesieniu czy opuszczeniu semafora, pomylić semafory, czy np. pomylić operacje P i V. W przypadku monitorów odpowiednie instrukcje synchronizujące są realizowane przez język programowania.

Monitory nie sprowadzają się tylko do strukturalnej sekcji krytycznej. Udostępniają one dodatkowo kolejki procesów typu condition. Kolejki takie mogą być używane tylko wewnątrz monitorów. Są to kolejki FIFO. Kolejki condition udostępniają dwie operacje:

wait -- powoduje wstrzymanie procesu i wstawienie go na koniec kolejki,
signal -- powoduje wznowienie pierwszego procesu z kolejki, o ile kolejka nie jest pusta.

Jeżeli w momencie wstrzymania procesu znajdującego się w monitorze jakiekolwiek procesy oczekują na wejście do monitora, to pierwszy z oczekujących procesów wchodzi do monitora. W momencie, gdy proces znajdujący się w monitorze wykona operację signal na (niepustej) kolejce, to nagle w monitorze mamy dwa procesy. Z drugiej strony, w monitorze może przebywać tylko jeden proces na raz. Istnieją dwa rozwiązania tego problemu:

Operacja signal może być wykonywana tylko jako ostatnia w monitorze. Po jej wykonaniu proces natychmiast opuszcza monitor. Rozwiązanie to jest o tyle ograniczone, że jeden proces może wznowić tylko jeden inny proces.
Wznawiany proces "wypycha" z monitora proces, który wykonał operację signal. Jednak wypychany proces jest wstawiany na początek kolejki procesów oczekujących na wejście do monitora. Dzięki temu jesteśmy w stanie prześledzić co się będzie działo w monitorze do momentu ponownego wejścia wypchniętego procesu.

Synchronizacja wątków w Javie

Przypomnijmy, że w wykładzie poświęconym procesom poznaliśmy pojęcie wątku, sposób tworzenia wątków w Javie oraz podstawowe operacje na wątkach. Teraz zajmiemy się synchronizacją wątków.

W Javie zaimplementowano uproszczony mechanizm monitorów. Każdy obiekt może być monitorem. W tym celu, wszystkie udostępniane metody należy zadeklarować jako synchronized. Efekt jest taki, że tylko jeden wątek na raz może wykonywać takie metody obiektu. Każdy kolejny wątek zostanie wstrzymany i będzie oczekiwał w kolejce, aż wątek wykonujący jedną z tych metod opuści obiekt. Natomiast wątek, który już wykonuje metodę synchronized może bez przeszkód wywołać kolejną taką metodę danego obiektu. Obiekt zostanie zwolniony, gdy zakończy wykonywanie wszystkich tych metod.

Jeżeli tworzymy klasę monitorów, to dobrym zwyczajem jest, aby atrybuty obiektów nie były bezpośrednio dostępne. Zamiast tego możemy udostępnić metody służące do ich modyfikowania i badania ich wartości. Ponadto, wszystkie udostępniane metody najlepiej zadeklarować jako synchronized. W ten sposób mamy gwarancję że tylko jeden wątek na raz będzie wykonywał metody obiektu, a dodatkowo żaden inny wątek nie będzie w tym samym czasie modyfikował wartości atrybutów. Oto prosty przykład:

  public class Counter { 
    private int c = 0; 
    public synchronized void inc() { 
      c++; 
    } 
    public synchronized void dec() { 
      c--; 
    } 
    public synchronized int val() {
      return c; 
    } 
  }

Jeżeli nie chcemy tworzyć monitora, a chcemy na chwilę uzyskać wyłączny dostęp do jakiegoś obiektu, to możemy skorzystać z instrukcji synchronized. Jej składnia jest następująca: synchronized (wyrażenie) instrukcja. Wynikiem wyrażenia jest obiekt (referencja do obiektu), który zajmujemy na wyłączność, na czas wykonania (bloku) instrukcji. Oto prosty przykład pokazujący tę konstrukcję. Zachęcamy do przetestowania jej w podanej postaci, oraz z usuniętym synchronized.

  import java.util.Random;

  public class Sync extends Thread {
    static Object sekcja = new Object(); 
    static int n = 0;
    Random gen = new Random();
    
    public void run() {
      int r;

      for (int i = 1; i <= 12; i++) {
        synchronized (sekcja) {
          // Opóźnienie, w trakcie którego zmienia się wartość n
          r = gen.nextInt(100000);
          for (int j = 1; j <= r; j++) { n = n + i * j;}
          for (int j = 1; j <= r; j++) { n = n - i * j;}

          n = n+1;        
          System.out.println(n);
        }
      }
    }
    
    public static void main(String args[])
    {
      new Sync().start();
      new Sync().start();
    }
  }

Java implementuje uproszczone monitory, ponieważ mamy do dyspozycji tylko jedną (niejawną) kolejkę typu condition w obiekcie. Jeżeli wątek wykona operację wait(), to zostaje zawieszony i umieszczony w tej kolejce. Gdy inny wątek wykona operację notify(), to wątek, który najdłużej czeka budzi się. Jest też dostępna operacja notifyAll(), która budzi wszystkie czekające wątki. Jeśli żaden wątek nie czeka na obudzenie, to te dwie operacje nie przynoszą żadnych skutków. Zwykle wątek wykonuje wait(), gdy czeka na spełnienie jakiegoś warunku, a notify() lub notifyAll(), gdy warunek, na który ktoś może czekać mógł się stać się prawdziwy.

W momencie gdy jakiś wątek wykona notify() lub notifyAll() mamy potencjalnie trzy grupy procesów, które mogą chcieć wejść do monitora:

wątek, który wykonał tę operację,
wątki, które zostały obudzone, oraz
wątki, które czekają na wejście do monitora.

Rozwiązanie przyjęte w Javie odbiega od klasycznych monitorów. Po pierwsze, wątek, który wykonał notify() lub notifyAll() pozostaje w monitorze. Po drugie, wątki obudzone i czekające na wejście do monitora konkurują na równych prawach o wejście do monitora. W praktyce oznacza to, że nie mamy żadnej gwarancji, że obudzony wątek wejdzie do monitora bezpośrednio po opuszczeniu go przez wątek, który go obudził. Może się zdarzyć, że między nie "wciśnie się" wątek, który jeszcze nie wszedł do monitora.

Utrudnia to wnioskowanie o kolejności, w jakiej wątki wchodzą do monitora. W praktyce oznacza to, że czekając na spełnienie jakiegoś warunku, zamiast prostej konstrukcji:

  if (...) wait();

należy raczej stosować konstrukcję:

  while (...) wait();

W ten sposób, nawet jeśli między wykonaniem notify(), a wejściem obudzonego wątku do monitora, dany warunek przestanie być prawdziwy, to wątek ponownie zacznie oczekiwać na jego spełnienie. Biorąc pod uwagę, że każdy obiekt dysponuje tylko jedną (niejawną) kolejką typu condition, obudzony wątek i tak powinien się upewnić, czy to akurat on powinien być obudzony.

Mimo wszystkich odstępstw od klasycznych monitorów, przedstawione mechanizmy synchronizacji wątków wystarczają do rozwiązania wielu mniej skomplikowanych zadań. Czytelników zainteresowanych bardziej zaawansowanymi mechanizmami synchronizacji w Javie odsyłamy do pakietu java.util.concurrent.

Sprzętowe mechanizmy synchronizacji

Jak wspomnieliśmy wcześniej, za pomocą klasycznych narzędzi programistycznych nie da się wyeliminować aktywnego oczekiwania. Z drugiej strony, przedstawione w tym punkcie mechanizmy synchronizacji są pozbawione tej wady. Tak więc ich implementacja wymaga wsparcia sprzętowego. W przypadku komputera jednoprocesorowego, takiego wsparcia dostarcza np. blokowanie przerwań. Ponieważ przełączenie kontekstu może nastąpić tylko na skutek wykonania przez proces operacji systemowej, lub na skutek przerwania sprzętowego, więc zablokowanie przerwań powoduje, że ciąg instrukcji jest wykonywany niepodzielnie. Należy jednak pamiętać, że przerwania nie powinny być blokowane na zbyt długo, gdyż może to mieć zły wpływ np. na zegar systemowy.

W przypadku komputerów wieloprocesorowych blokowanie przerwań jest niewystarczające. Nawet przy zablokowanych przerwaniach kilka procesów może działać równolegle. Potrzebne jest wówczas inne wsparcie sprzętowe.

Przykładem takiego wsparcia może być instrukcja procesora test-and-set (testuj i ustaw). Działaniu tej instrukcji odpowiada następująca funkcja:

  function TestAndSet (var x: boolean): boolean;
  begin
    TestAndSet := x;
    x := true
  end;

W wyniku jej wykonania zmienna x uzyskuje wartość true, a wynikiem funkcji jest poprzednia wartość zmiennej x. Znaczenie tej instrukcji polega na tym, że jest ona wykonywana w sposób niepodzielny, atomowy. Między pobraniem wartości x, a ustawieniem jej na true żaden inny proces nie ma dostępu do zmiennej x.

Korzystając z instrukcji TestAndSet możemy rozwiązać problem sekcji krytycznej:

Sekcja wejściowa:
```
  while TestAndSet (S) do;
```
Sekcja wyjściowa:
```
  S := false; 
```

Chcąc unikać aktywnego oczekiwania nie stosujemy powyższej implementacji bezpośrednio do ochrony sekcji krytycznych procesów, lecz używamy jej np. do ochrony niepodzielności operacji na semaforach.

Istnieją również inne instrukcje, równoważne TestAndSet, np. instrukcja exchange (zamień). Powoduje ona, że dwie podane komórki pamięci zamieniają się wartościami. Ponownie, istotne jest to, że operacja zamiany jest wykonywana w sposób niepodzielny.

Klasyczne problemy synchronizacji

W punkcie tym przedstawimy kilka klasycznych problemów synchronizacji procesów. Choć niektóre z nich mogą się wydawać akademickie, to stanowią one bardzo dobry "poligon" dla różnych technik synchronizacji procesów.

Problem producenta-konsumenta c.d.

Problem producenta-konsumenta przedstawiliśmy już na początku tego wykładu. Zastanówmy się, jak można wykorzystać poznane mechanizmy synchronizacji procesów do rozwiązania tego problemu. Najpierw rozwiążemy ten problem stosując semafory.

Przyjmijmy, że struktura danych reprezentująca bufor jest taka jak poprzednio.

  var
    bufor: array [0..n-1] of produkt;
    pierwszy: 0..n-1;
    licznik: 0..n;

Możemy użyć semafora (S) do stworzenia sekcji krytycznej, w której umieścimy operacje wkładania i wyjmowania jednostek produktu z bufora. Nie wyeliminuje to jednak aktywnego oczekiwania na produkt lub puste miejsce w buforze. Aktywne oczekiwanie możemy wyeliminować używając dwóch dodatkowych semaforów: jeden (pełne) będzie równy liczbie jednostek produktu znajdujących się w buforze, a drugi (puste) będzie równy liczbie pustych miejsc w buforze. Początkowo semafor S jest równy 1, pełne jest równy 0, a puste jest równy n. Procesy producenta i konsumenta wyglądają wówczas następująco:

Producent:

  repeat
    wyprodukuj jednostkę produktu;
    P(puste);
    P(S);
    bufor [(pierwszy+licznik) mod n] := wyprodukowana jednostka;
    licznik := licznik + 1;
    V(S);
    V(pełne)
  until false

Konsument:

  repeat
    P(pełne);
    P(S);
    pobrana jednostka := bufor [pierwszy];
    pierwszy := (pierwszy + 1) mod n;
    licznik := licznik - 1;
    V(S);
    V(puste);
    skonsumuj pobraną jednostkę
  until false

Zwróćmy uwagę na użycie semaforów pełne i puste. Nie tworzą one sekcji krytycznych, lecz synchronizują pobieranie i wstawianie elementów do bufora. Widać na tym przykładzie, że semafory mają szersze zastosowanie, niż tylko tworzenie sekcji krytycznych. Rozwiązanie to ma jeszcze jedną zaletę. Nawet jeżeli uruchomimy kilku producentów i konsumentów, to będą oni poprawnie korzystać ze wspólnego bufora. Uczciwość kolejności w jakiej budzone są procesy oczekujące na podniesienie semafora gwarantuje, że nie wystąpi zagłodzenie.

Rozwiążemy teraz problem producenta-konsumenta za pomocą monitorów. Monitor będzie udostępniał dwie operacje:wstaw i pobierz. Użyjemy takiej samej struktury danych do zaimplementowania bufora. Dodatkowo potrzebne będą nam dwie kolejki procesów: pełne -- oczekujących na produkty i puste -- oczekujących na puste miejsca w buforze.

  monitor producent_konsument;
    var
      bufor: array [0..n-1] of produkt;
      pierwszy: 0..n-1;
      licznik: 0..n; 
      pełne, puste: condition;
    
    procedure wstaw(p: produkt);
    begin
      if licznik = n then wait(puste);
      bufor [(pierwszy+licznik) mod n] := p;
      licznik := licznik + 1;
      signal(pełne)
    end;

    function pobierz: produkt;
    begin
      if licznik = 0 then wait(pełne);
      pobierz := bufor [pierwszy];
      pierwszy := (pierwszy + 1) mod n;
      licznik := licznik - 1;
      signal(puste)
    end;

  begin
    pierwszy := 0;
    licznik := 0
  end;

Problem czytelników i pisarzy

W problemie czytelników i pisarzy mamy dwie grupy procesów (czytelników i pisarzy) współzawodniczących o dostęp do pewnej sekcji krytycznej, którą będziemy nazywać biblioteką. Biblioteka jest o tyle specyficzną sekcją krytyczną, że może w niej przebywać równocześnie wielu czytelników. Jeżeli natomiast znajduje się w niej pisarz, to nie może w niej być nikogo innego. Powstaje pytanie, w jakiej kolejności możemy wpuszczać do biblioteki czytelników i pisarzy tak, aby nie było możliwości zagłodzenia? Przyjmiemy następujące rozwiązanie: Jeżeli czytelnik chce wejść do biblioteki, a nie ma w niej pisarzy, ani też żaden pisarz nie czeka na wejście do biblioteki, to po prostu do niej wchodzi. W przeciwnym przypadku staje w kolejce oczekujących na wejście do biblioteki. Jeżeli pisarz chce wejść do biblioteki, a nie jest ona pusta lub ktoś już czeka na wejście do niej, to staje w kolejce oczekujących na wejście do biblioteki. Gdy pisarz opuszcza bibliotekę, to wchodzą do niej wszyscy oczekujący czytelnicy, lub jeśli ich brak, to pierwszy pisarz z kolejki. Gdy ostatni czytelnik wychodzi z biblioteki, to wchodzi do niej pierwszy pisarz z kolejki (o ile taki jest). W ten sposób, nawet jeżeli cały czas będą pojawiać się pisarze i czytelnicy chętni do skorzystania z biblioteki, to wchodzić do niej będą na zmianę: grupa czytelników, pisarz, grupa czytelników, pisarz itd., co gwarantuje, że nie nastąpi zagłodzenie.

Oto rozwiązanie za pomocą monitorów. Używamy w nim dwóch kolejek procesów: czytelnicy, to czytelnicy oczekujący na wejście do biblioteki, a pisarze, to pisarze oczekujący na wejście do biblioteki. Dodatkowo zmienna licznik jest równa liczbie czytelników w bibliotece, lub -1, gdy jest w niej pisarz. Monitor udostępnia cztery procedury, wejście i wyjście z biblioteki odpowiednio dla czytelników i pisarzy.

  monitor czytelnicy_i_pisarze;
    var
      licznik: integer;
      czytelnicy, pisarze: condition;

    procedure wejście_czytelnika;
    begin
      if (licznik = -1) or not empty(pisarze) then wait(czytelnicy);
      licznik := licznik + 1;
      signal(czytelnicy)
    end;

    procedure wyjście_czytelnika;
    begin
      licznik := licznik - 1;
      if licznik = 0 then signal(pisarze)
    end;

    procedure wejście_pisarza;
    begin
      if licznik ≠ 0 then wait(pisarze);
      licznik := -1
    end;

    procedure wyjście_pisarza;
    begin
      licznik := 0;
      if empty(czytelnicy) then signal(pisarze) else signal(czytelnicy)
    end;

  begin
    licznik := 0;
  end;

Zwróćmy uwagę, w jaki sposób wszyscy oczekujący czytelnicy wchodzą do biblioteki po wyjściu pisarza. Pisarz budzi pierwszego oczekującego czytelnika, ten budzi drugiego, który budzi trzeciego itd.

Problem pięciu filozofów

Problem pięciu filozofów, to akademicki problem synchronizacji, który okazał się bardzo dobrym sprawdzianem dla różnych metod synchronizacji. Mamy pięciu filozofów. Każdy z nich rozmyśla. Gdy zgłodnieje, to idzie jeść, a gdy się naje, to kontynuuje rozmyślania, aż znowu nie zgłodnieje itd. Filozofowie jedzą przy okrągłym stole przedstawionym na poniższym rysunku, przy czym każdy z nich ma swoje miejsce. Każdy z nich najpierw nakłada sobie jedzenie z miski stojącej na środku stołu, bierze dwie pałeczki leżące po lewej i prawej stronie talerza i je. Po zjedzeniu odkłada pałeczki na miejsce. Rzecz w tym, że na stole jest tylko pięć pałeczek, po jednej między dwoma sąsiednimi talerzami. Problem polega na takim zsynchronizowaniu poczynań filozofów, aby wykluczyć możliwość blokady i zagłodzenia.

Czy to faktycznie jest problem? Czy nie wystarczy, aby każdy filozof siadał na swoim miejscu, brał do ręki jedną pałeczkę (np. lewą), potem drugą i jadł? Oczywiście jeżeli z którejś pałeczki korzysta akurat jego kolega, to z filozoficznym spokojem poczeka aż on zje. Okazuje się, że przy takim rozwiązaniu możliwa jest blokada. Przypuśćmy, że wszyscy filozofowie robią dokładnie to samo. Wszyscy na raz siadają przy stole, biorą do ręki pałeczkę z lewej strony i ... mamy blokadę. Każdy z nich czeka na pałeczkę leżącą z prawej strony, ale nigdy się jej nie doczeka.

Czy można by uniknąć blokady, gdyby filozofowie brali pałeczki tylko po dwie naraz? Jeżeli jedna z pałeczek jest używana przez innego filozofa, to czeka on, aż obydwie będą leżeć na stole. Okazuje się, że wówczas możliwe jest zagłodzenie. Przypuśćmy, że jeden z filozofów siada do stołu i czeka na pałeczkę z prawej strony. W tym czasie z jego lewej strony siada jego kolega i zaczyna jeść, zabierając pałeczkę z lewej strony. Po chwili filozof z prawej strony odkłada pałeczkę, ale nasz filozof nie może jej wziąć, bo brak pałeczki po lewej stronie. Po chwili filozof z prawej strony wraca i zaczyna jeść, zabierając pałeczkę z prawej strony. Filozof z lewej strony kończy jeść i odkłada pałeczkę, ale teraz nie ma pałeczki z prawej strony, itd. Widzimy, że nasz filozof będzie czekał raz na pałeczkę z lewej, raz prawej strony, ulegając (dosłownie) zagłodzeniu.

Istnieje wiele rozwiązań tego problemu. Jedno z nich polega na ograniczeniu liczby równocześnie jedzących filozofów do 4. Powiedzmy, że każdy z filozofów zanim usiądzie, bierze talerz. Wystarczy, że w jadalni będą tylko 4 talerze. Każdą pałeczkę reprezentujemy jako semafor, początkowo równy 1. Wzięcie pałeczki, to opuszczenie semafora, a jej odłożenie, to podniesienie semafora. Talerzom odpowiada semafor, którego początkowa wartość, to 4. Podobnie, wzięcie talerza, to opuszczenie semafora, a odłożenie, to podniesienie semafora. Przyjmujemy, że filozofowie i pałeczki są ponumerowani od 0 do 4.

  var
    paleczki: array [0..4] of semaphore;
    talerze: semaphore;

  procedure filozof(i: 0..4);
  begin
    repeat
      myśl;
      P(talerz);
      P(paleczki[i]);
      P(paleczki[(i + 1) mod 5]);
      jedz;
      V(paleczki[i]);
      V(paleczki[(i + 1) mod 5]);
      V(talerz);
    until false
  end;

Podsumowanie

Programowanie współbieżne jest niezwykle trudne, ze względu na wielość możliwych przebiegów obliczeń. Synchronizując problemy musimy nie tylko zapewnić poprawność interakcji między procesami, ale również wykluczyć możliwość wystąpienia blokady, czy zagłodzenia.

W niniejszym wykładzie przedstawiliśmy problematykę synchronizacji procesów współbieżnych, oraz podstawowe mechanizmy synchronizacji: semafory, kolejki komunikatów i monitory. Ich użycie zostało zilustrowane na klasycznych przykładach.

Słownik

aktywne oczekiwanie

proces czekając na jakieś zdarzenie sprawdza ciągle warunek określający, czy dane zdarzenie już zaszło; jest to zjawisko niepożądane ze względu na niepotrzebne zużycie czasu procesora.

algorytm Dekkera

implementacja sekcji krytycznej za pomocą wspólnych zmiennych dla dwóch współbieżnych procesów.

algorytm piekarniany

implementacja sekcji krytycznej za pomocą wspólnych zmiennych dla n współbieżnych procesów.

exchange

instrukcja procesora wykorzystywana przy implementacji mechanizmów synchronizacji procesów.

kolejka komunikatów

mechanizm synchronizacji procesów; kolejka FIFO pakietów informacji (komunikatów) z dwiema podstawowymi operacjami: dołączeniem komunikatu na koniec kolejki i pobraniem komunikatu z początku kolejki.

kolejka procesów typu condition

mechanizm synchronizacji procesów dostępny w ramach monitorów.

monitor

strukturalny mechanizm synchronizacji; monitor to rodzaj klasy, której metody stanowią sekcję krytyczną, plus kolejki procesów.

sekcja krytyczna

fragmenty kodu lub operacje, których wykonywanie przez procesy współbieżne podlega synchronizacji zgodnie z następującymi zasadami:

wzajemne wykluczanie -- tylko jeden proces może na raz przebywać w sekcji krytycznej, dopóki proces przebywający w sekcji krytycznej nie opuści jej inne procesy nie mogą wejść do niej,
wykorzystanie -- jeśli jakiś proces chce wejść do sekcji krytycznej, to nie może ona pozostawać pusta,
brak zagłodzenia -- każdy proces, który chce wejść do sekcji krytycznej ma gwarancję, że kiedyś do niej wejdzie.

semafor

mechanizm synchronizacji procesów; semafor to specjalna zmienna całkowita, na której można wykonywać tylko dwa rodzaje operacji: opuszczanie (P) i podnoszenie (V).

semafor binarny

szczególny rodzaj semafora, który może przyjmować tylko dwie wartości: 0 i 1.

test-and-set

instrukcja procesora wykorzystywana przy implementacji mechanizmów synchronizacji procesów.

Zadania

(5p.) Co by było, gdyby w problemie producenta-konsumenta pętle oczekujące, aż bufor nie będzie pusty/pełny umieścić również w sekcji krytycznej?
(5p.) Rozwiąż problem sekcji krytycznej za pomocą instrukcji exchange.

Strona przygotowana przez Marcina Kubicę i Krzysztofa Stencla.