Monitor (programowanie współbieżne)

Monitor – obiekt, który może być bezpiecznie używany przez kilka wątków. Metody monitora chronione są przez muteksy, przez co w dowolnym momencie czasowym z dowolnej metody może korzystać tylko jeden wątek naraz. Upraszcza to budowę obiektów, zwalniając programistę z konieczności implementacji skomplikowanych wykluczeń.

Monitory umożliwiają także wątkom czasowe zwolnienie wyłącznego dostępu podczas oczekiwania na spełnienie jakiegoś warunku. W tym czasie inny wątek może bezpiecznie wykonać swoje zadanie, a gdy warunek zostanie spełniony, poprzedni wątek z powrotem przejmie wyłączną kontrolę i dokończy pracę. Dwa wątki mogą także sygnalizować sobie, że warunek został spełniony.

Monitory zostały wynalezione przez C.A.R. Hoare’a[1] oraz Pera Brinch Hansena[2] i zostały po raz pierwszy zaimplementowane w języku Concurrent Pascal.

Wzajemne wykluczanie

Klasa obsługująca konto bankowe:

monitor class Konto {
  private int stan := 0
  invariant stan >= 0

  public method boolean pobierz(int kwota)
  {
    if kwota < 0 then error "Kwota nie może być ujemna"
    else if stan < kwota then return false
    else { stan := stan - kwota ; return true }
  }

  public method wplac(int kwota) {
    if kwota < 0 then error "Kwota nie może być ujemna"
    else stan := stan + kwota
  }
}

O wątku wykonującym metodę monitora mówimy, że zajmuje on monitor. Monitory projektowane są w taki sposób, aby w dowolnej chwili co najwyżej jeden wątek mógł je zajmować. Zapewnia to właściwość wzajemnego wykluczania.

Gdy wątek próbuje wywołać metodę monitora, musi zaczekać, dopóki inny wątek nie skończy swojej pracy na obiekcie. Zauważmy, że gdyby w podanym przykładzie zezwolić dwóm wątkom na jednoczesne wykonywanie pobierz(), aby pobrać kwotę 1000 zł, właściciel konta mógłby zyskać pieniądze bez żadnego powodu. Każdy z wątków pobrałby najpierw aktualny stan konta, zmniejszył go o 1000 zł, a następnie zapisał z powrotem do pola kwota, nie wiedząc, że dokładnie w tym samym czasie drugi zrobił identyczną operację. Ostatecznie pomimo pobrania łącznie 2000 złotych na koncie stwierdzilibyśmy ubytek połowy tej sumy.

W najprostszej implementacji wzajemne wykluczanie musi być zapewnione przez kompilator, co sprowadza się zazwyczaj do dodania do każdego obiektu monitora semafora, który początkowo jest podniesiony. Program opuszcza go automatycznie, gdy jakiś wątek próbuje wywołać metodę i podnosi z powrotem, gdy z metody wychodzi.

Oczekiwanie na warunki

W wielu sytuacjach wzajemne wykluczanie nie wystarcza. Wątki próbujące wykonać pewną operację mogą wymagać zaczekania na spełnienie określonego warunku aby móc kontynuować. Zwykłe aktywne czekanie przy pomocy pętli nie wystarcza:

while not (P) do pomiń

Wątek w dalszym ciągu zajmuje monitor, przez co nikt inny nie ma szans na zmianę jego stanu i spełnienie warunku. Rozwiązaniem są zmienne warunkowe. Zmienna warunkowa jest kolejką wątków przypisaną do monitora, które oczekują na jakiś skojarzony z nią przez programistę warunek Uznaje się, że wątki znajdujące się w kolejce nie zajmują monitora, dzięki czemu inny wątek może wykonać na nim operację, dzięki której stanie się prawdziwe. W większości implementacji ma on dodatkowo możliwość powiadomienia wątków z kolejki, że warunek został spełniony i mogą one wznowić swoje wykonywanie.

Zmienne warunkowe muszą udostępniać dwie podstawowe operacje:

  • czekaj na c (ang. wait) – wywoływana przez wątek, który chce zaczekać na spełnienie warunku W trakcie oczekiwania nie zajmuje on monitora i nazywany jest wątkiem oczekującym.
  • powiadom c (ang. signal lub notify) – wywoływana przez wątek, aby powiadomić czekające wątki, że został spełniony. Nazywamy go wątkiem powiadamiającym.

Zmienne warunkowe z blokowaniem

Oryginalne prace C.A.R. Hoare’a oraz Pera Brinch Hansena proponowały zmienne warunkowe z blokowaniem. Monitory pracujące w ten sposób są często nazywane monitorami Hoare’a.

W zmiennych warunkowych z blokowaniem wątek powiadamiający jest blokowany do czasu, aż powiadomiony wątek oczekujący nie opuści monitora lub nie zatrzyma się w ponownym oczekiwaniu na warunek.

Zakładamy, że występują dwie główne kolejki wątków:

  • e jest kolejką wejściową.
  • s jest kolejką wątków powiadamiających.

Ponadto każda zmienna warunkowa posiada własną kolejkę wątków oczekujących na spełnienie warunku. Zazwyczaj gwarantuje się uczciwość obu kolejek (tzn. wchodzący do nich wątek nie będzie wybierany w nieskończoność, co głodziłoby pozostałe).

Poniżej przedstawione są implementacje poszczególnych operacji monitora. Zakładamy, że są one wykonywane atomowo:

wejście do monitora:
  wejdź do metody
  jeśli monitor jest zajęty
     dodaj obecny wątek do 
  w przeciwnym wypadku
     zajmij monitor
opuszczenie monitora:
 przełącz
 opuść metodę
czekaj na 
  dodaj obecny wątek do 
  przełącz
  zablokuj obecny wątek
powiadom 
  jeśli jest wątek czekający w 
     wybierz i usuń z kolejki dowolny wątek 
     dodaj obecny wątek do 
     odblokuj 
     zablokuj obecny wątek

Komenda przełącz wybiera z kolejki następny wątek, który zajmie monitor, a jeśli jest ona pusta, odblokowuje go:

przełącz:
  jeśli jest wątek w kolejce 
     wybierz ten wątek, usuń go z kolejki i odblokuj
  jeśli jest wątek w kolejce 
     wybierz ten wątek, usuń go z kolejki i odblokuj
  w przeciwnym wypadku
     zwolnij monitor

W powyższej implementacji każdy wątek powiadamiający natychmiast się zatrzymuje, lecz ma gwarantowany priorytet przy przełączaniu. Alternatywne podejście zakłada brak kolejki i oczekiwanie w po wysłaniu powiadomienia.

Czasami stosuje się także dodatkową operację powiadom i zakończ, aby nie blokować niepotrzebnie wątku, który nie ma w monitorze już nic do zrobienia i pozostaje mu tylko wyjść. Łączy ona powiadamianie oraz wyjście z metody monitora.

Zmienne warunkowe bez blokowania

W zmiennych warunkowych bez blokowania operacja powiadom nie powoduje opuszczenia monitora. Zamiast tego wątek oczekujący jest przenoszony do kolejki aby zaczekać, aż wątek powiadamiający zakończy swoje zadanie. Kolejka jest niepotrzebna. Czasami dodaje się dodatkową operację powiadom wszystkie, która przenosi wszystkie oczekujące wątki do

Poniżej przedstawione są implementacje poszczególnych operacji monitora. Zakładamy, że są one wykonywane atomowo:

wejście do monitora:
  wejdź do metody
  jeśli monitor jest zajęty
     dodaj obecny wątek do 
  w przeciwnym wypadku
     zajmij monitor
opuszczenie monitora:
  przełącz
  opuść metodę
czekaj na 
  dodaj obecny wątek do 
  przełącz
  zablokuj obecny wątek
powiadom 
  jeśli jest wątek czekający w 
     wybierz i usuń z kolejki dowolny wątek 
     dodaj  do kolejki
powiadom wszystkie 
  przenieś wszystkie wątki z  do kolejki
przełącz:
  jeśli jest wątek w kolejce 
     wybierz ten wątek, usuń go z kolejki i odblokuj
  w przeciwnym wypadku
     zwolnij monitor

Jako modyfikację proponuje się utworzenie kolejki do której przenoszone są wątki w ramach operacji powiadom i powiadom wszystkie i która ma zagwarantowane pierwszeństwo przed [3][4].

Monitory z niejawnym warunkiem

W języku Java każdy obiekt może stać się monitorem, przy czym metody, których dotyczy wykluczanie, muszą być oznaczone modyfikatorem synchronized. Zamiast udostępniać jawne zmienne warunkowe, każdy monitor wyposażony jest w pojedynczą kolejkę obok kolejki wejściowej. Wszystkie operacje dotyczą tej jednej kolejki, co pozwala skojarzyć z monitorem co najwyżej jeden warunek. Aby zastosować więcej zmiennych warunkowych, należy ręcznie dodać do klasy obiekt Lock i przy jego pomocy utworzyć odpowiednią liczbę zmiennych. Programista musi wtedy samodzielnie zajmować się wywołaniem odpowiednich operacji przy wchodzeniu i opuszczaniu monitora.

Identyczne podejście zostało zaimplementowane także w innych językach, jak np. C#.

Przypisy

  1. ↑ C.A.R. Hoare. Monitors: an operating system structuring concept. „Communications of the ACM”. 17 (10), s. 589–597, 1974. DOI: 10.1145/355620.361161. ISSN 0001-0782. 
  2. ↑ P. Brinch Hansen. The programming language Concurrent Pascal. „IEEE Transactions on Software Engineering”. 2, s. 199–206, 1975. 
  3. ↑ John Howard. Signaling in monitors. „Proceedings of the 2nd International Conference on Software Engineering”, s. 47–52, 1976. 
  4. ↑ P.H Buhr, M. Fortier, M.H. Coffin. Monitor classification. „ACM Computing Surveys rok = 1995”. 17 (1). s. 63–107. DOI: 10.1145/214037.214100. ISSN 0360-0300.