Monitoruj (synchronizacja)

W programowaniu współbieżnym monitor jest konstrukcją synchronizującą, która umożliwia wątkom zarówno wzajemne wykluczanie , jak i możliwość czekania (blokowania), aż określony warunek stanie się fałszywy. Monitory posiadają również mechanizm sygnalizowania innym wątkom, że ich warunek został spełniony. Monitor składa się z mutex (blokady) i zmiennych warunkowych . Zmienna warunkowa zasadniczo jest kontenerem wątków, które czekają na określony warunek. Monitory zapewniają mechanizm, dzięki któremu wątki tymczasowo rezygnują z wyłącznego dostępu, aby poczekać na spełnienie jakiegoś warunku, zanim odzyskają wyłączny dostęp i wznowią swoje zadanie.

Inną definicją monitora jest klasa , obiekt lub moduł bezpieczny dla wątków , które otaczają muteks , aby bezpiecznie umożliwić dostęp do metody lub zmiennej przez więcej niż jeden wątek . Charakterystyczną cechą monitora jest to, że jego metody są wykonywane z wzajemnym wykluczeniem : W każdym momencie co najwyżej jeden wątek może wykonywać dowolną ze swoich metod . Używając jednej lub więcej zmiennych warunkowych, może również zapewnić wątkom możliwość oczekiwania na określony warunek (używając w ten sposób powyższej definicji „monitora”). W pozostałej części tego artykułu to znaczenie „monitorowania” będzie określane jako „obiekt/klasa/moduł bezpieczny dla wątków”.

Monitory zostały wynalezione przez Pera Brincha Hansena i CAR Hoare'a i zostały po raz pierwszy zaimplementowane w języku Concurrent Pascal firmy Brinch Hansen .

Wzajemne wykluczenie

Jako prosty przykład rozważ obiekt bezpieczny dla wątków do wykonywania transakcji na koncie bankowym:

    klasa monitora  Konto  {  private  int  balance := 0  niezmienne  saldo >= 0  public method  boolean  wypłacić(  int  kwota)  warunek wstępny  kwota >= 0 {  if  saldo < kwota {  return false  }  else  { saldo := saldo - kwota  return true  } }  public metoda  depozytu (  kwota  int )  warunku wstępnego  >= 0 { saldo := saldo + kwota } }

Gdy wątek wykonuje metodę obiektu wątkowo-bezpiecznego, mówi się, że zajmuje obiekt, utrzymując jego mutex (blokadę) . Obiekty bezpieczne dla wątków są implementowane w celu wymuszenia , że ​​w każdym momencie obiekt może zajmować co najwyżej jeden wątek . Blokada, która jest początkowo odblokowana, jest blokowana na początku każdej metody publicznej i jest odblokowywana przy każdym powrocie z każdej metody publicznej.

Po wywołaniu jednej z metod wątek musi czekać, aż żaden inny wątek nie wykona żadnej z metod obiektu wątkowo-bezpiecznego, zanim rozpocznie wykonywanie swojej metody. Zauważ, że bez tego wzajemnego wykluczania się, w tym przykładzie dwa wątki mogą spowodować utratę lub zyskanie pieniędzy bez powodu. Na przykład dwa wątki pobierające 1000 z konta mogą zwrócić wartość true, jednocześnie powodując spadek salda tylko o 1000, w następujący sposób: najpierw oba wątki pobierają bieżące saldo, znajdują je większe niż 1000 i odejmują od niego 1000; następnie oba wątki przechowują saldo i wracają.

cukru składniowego w powyższym przykładzie implementuje następującą podstawową reprezentację kodu, zawijając wykonanie każdej funkcji w muteksy: 

     class  Konto  {  private  lock  myLock  private  int  balance := 0  niezmienne  saldo >= 0  public method  boolean  wypłacić(  int  kwota)  warunek wstępny  kwota >= 0 { myLock.acquire()  try  {  if  balance < kwota {  return false  }  else  { saldo : = saldo - kwota  return true  } }  ostatecznie  { myLock.release() } }  metoda publiczna  depozyt (  int  kwota)  warunek wstępny  kwota >= 0 { myLock.acquire()  try  { saldo := saldo + kwota }  ostatecznie  { myLock.release() } } }

Zmienne warunkowe

Oświadczenie o problemie

W przypadku wielu zastosowań wzajemne wykluczanie nie wystarcza. Wątki próbujące wykonać operację mogą potrzebować czekać, aż spełni się jakiś warunek P. Zajęta pętla oczekiwania 

  podczas  gdy  nie  (  P  )  pomiń

nie zadziała, ponieważ wzajemne wykluczanie zapobiegnie wejściu innego wątku do monitora w celu spełnienia warunku. Istnieją inne „rozwiązania”, takie jak pętla, która odblokowuje monitor, odczekuje określony czas, blokuje monitor i sprawdza warunek P . Teoretycznie działa i nie blokuje się, ale pojawiają się problemy. Trudno zdecydować się na odpowiednią ilość czasu oczekiwania: za mały i wątek obciąży procesor, za duży i będzie widocznie nie reagował. Potrzebny jest sposób sygnalizowania wątku, kiedy warunek P jest prawdziwy (lub może być prawdziwy).

Studium przypadku: klasyczny ograniczony problem producenta/konsumenta

Klasycznym problemem współbieżności jest problem ograniczonego producenta/konsumenta , w którym istnieje kolejka lub bufor pierścieniowy zadań o maksymalnym rozmiarze, przy czym jeden lub więcej wątków to wątki „producentów”, które dodają zadania do kolejki, a jeden lub więcej innych wątków to wątki „konsumentów”, które usuwają zadania z kolejki. Zakłada się, że kolejka sama w sobie nie jest bezpieczna wątkowo i może być pusta, pełna lub pomiędzy pustą a pełną. Ilekroć kolejka jest pełna zadań, potrzebujemy blokowania wątków producenta, dopóki nie będzie miejsca na zadania usuwające z kolejki wątków konsumenckich. Z drugiej strony, gdy kolejka jest pusta, potrzebujemy blokowania wątków konsumenckich, dopóki nie będzie dostępnych więcej zadań z powodu dodania ich przez wątki producenta.

Ponieważ kolejka jest współbieżnym obiektem współdzielonym między wątkami, dostęp do niej musi być atomowy , ponieważ kolejka może zostać wprowadzona w niespójny stan podczas dostępu do kolejki, który nigdy nie powinien być ujawniany między wątkami. Zatem każdy kod, który uzyskuje dostęp do kolejki, stanowi sekcję krytyczną , która musi być synchronizowana przez wzajemne wykluczanie. Jeśli instrukcje kodu i procesora w krytycznych sekcjach kodu, które uzyskują dostęp do kolejki, mogą być przeplatane przez dowolne przełączanie kontekstu między wątkami na tym samym procesorze lub przez jednocześnie działające wątki na wielu procesorach, istnieje ryzyko ujawnienia niespójnego stanu i spowodowania wyścigu .

Niepoprawnie bez synchronizacji

Naiwnym podejściem jest zaprojektowanie kodu z zajętym oczekiwaniem i bez synchronizacji, co powoduje, że kod podlega warunkom wyścigu: 

   


   
      
            
           
         globalna  kolejka  RingBuffer  ;  // Niebezpieczny dla wątków bufor pierścieniowy zadań.  // Metoda reprezentująca zachowanie każdego wątku producenta:  metoda  publiczna  producent  ()  {  while  (  true  )  {  task  myTask  =  ...;  // Producent tworzy nowe zadanie do dodania.  while  (  kolejka  .  isFull  ())  {}  // Busy-czekaj, aż kolejka się nie zapełni.  kolejka  .  kolejkować  (  
    



   
      
           
           
         mojeZadanie  );  // Dodaj zadanie do kolejki.  }  }  // Metoda reprezentująca zachowanie każdego wątku konsumenta:  public  method  consumer  ()  {  while  (  true  )  {  while  (  kolejka  .  isEmpty  ())  {}  // Busy-czekaj, aż kolejka nie będzie pusta.  mojeZadanie  =  kolejka  .  usuń z kolejki  ();  // Usuń zadanie z kolejki.  wykonaj  (  mojeZadanie  );  
    
 // Wyjdź i zrób coś z zadaniem.  }  }

Ten kod ma poważny problem polegający na tym, że dostęp do kolejki może zostać przerwany i przeplatany z dostępem innych wątków do kolejki. Metody kolejki.enqueue i kolejki.dequeue prawdopodobnie zawierają instrukcje aktualizujące zmienne składowe kolejki, takie jak jej rozmiar, pozycja początkowa i końcowa, przypisanie i alokacja elementów kolejki itp. Ponadto metody kolejki.isEmpty ( ) i kolejki.isFull () odczytują również ten udostępniony stan. Jeśli wątki producenta/konsumenta mogą być przeplatane podczas wywołań kolejkowania/usuwania z kolejki, wówczas niespójny stan kolejki może zostać ujawniony, co prowadzi do warunków wyścigu. Ponadto, jeśli jeden konsument opróżni kolejkę pomiędzy wyjściem innego konsumenta z zajętego oczekiwania i wywołaniem „usuń z kolejki”, wówczas drugi konsument spróbuje usunąć kolejkę z pustej kolejki, co doprowadzi do błędu. Podobnie, jeśli producent zapełni kolejkę pomiędzy wyjściem innego producenta z zajętego oczekiwania i wywołaniem „enqueue”, wówczas drugi producent spróbuje dodać do pełnej kolejki, co spowoduje błąd.

Czekanie na wirowanie

Jedno naiwne podejście do osiągnięcia synchronizacji, jak wspomniano powyżej, polega na użyciu „ oczekiwania na spin ”, w którym muteks jest używany do ochrony krytycznych sekcji kodu, a oczekiwanie na zajętość jest nadal używane, a blokada jest uzyskiwana i zwalniana w między każdym sprawdzeniem zajętości oczekiwania. 

   
   


   
      
            

         globalna  kolejka  RingBuffer  ;  // Niebezpieczny dla wątków bufor pierścieniowy zadań.  global  Blokada  kolejki Blokada  ;  // Muteks dla bufora pierścieniowego zadań.  // Metoda reprezentująca zachowanie każdego wątku producenta:  metoda  publiczna  producent  ()  {  while  (  true  )  {  task  myTask  =  ...;  // Producent tworzy nowe zadanie do dodania.  kolejkaBlokada  .  nabywać  ();  
           
            
            
            
             
        

         // Uzyskaj blokadę dla wstępnego sprawdzenia zajętości.  while  (  kolejka  .  isFull  ())  {  // Busy-poczekaj, aż kolejka się nie zapełni.  kolejkaBlokada  .  zwolnij  ();  // Tymczasowo usuń blokadę, aby dać szansę innym wątkom  // wymagającym uruchomienia funkcji QueueLock, aby konsument mógł podjąć się zadania.  kolejkaBlokada  .  nabywać  ();  // Ponownie uzyskaj blokadę dla następnego wywołania "queue.isFull()".  }  kolejka  .  wstaw do kolejki  (  moje zadanie  );  
         
    



   
      
         
           // Dodaj zadanie do kolejki.  kolejkaBlokada  .  zwolnij  ();  // Usuń blokadę kolejki, dopóki nie będziemy jej potrzebować ponownie, aby dodać następne zadanie.  }  }  // Metoda reprezentująca zachowanie każdego wątku konsumenta:  metoda  publiczna  consumer  ()  {  while  (  true  )  {  QueueLock  .  nabywać  ();  // Uzyskaj blokadę dla wstępnego sprawdzenia zajętości.  while  (  kolejka  .  isEmpty  ())  {  
            
            
            
             
        
           
         // Busy-czekaj, aż kolejka nie będzie pusta.  kolejkaBlokada  .  zwolnij  ();  // Tymczasowo usuń blokadę, aby dać szansę innym wątkom  // wymagającym uruchomienia funkcji queryLock, aby producent mógł dodać zadanie.  kolejkaBlokada  .  nabywać  ();  // Ponownie uzyskaj blokadę dla następnego wywołania "queue.isEmpty()".  }  mojeZadanie  =  kolejka  .  usuń z kolejki  ();  // Usuń zadanie z kolejki.  kolejkaBlokada  .  zwolnij  ();  
         
    
 // Usuń blokadę kolejki, dopóki nie będziemy jej potrzebować ponownie do wykonania następnego zadania.  wykonaj  (  mojeZadanie  );  // Wyjdź i zrób coś z zadaniem.  }  }

Ta metoda gwarantuje, że stan niespójności nie wystąpi, ale marnuje zasoby procesora z powodu niepotrzebnego czekania w ruchu. Nawet jeśli kolejka jest pusta, a wątki producenta od dawna nie mają nic do dodania, wątki konsumenckie są zawsze zajęte – niepotrzebnie czekają. Podobnie, nawet jeśli konsumenci są przez długi czas zablokowani w przetwarzaniu swoich bieżących zadań, a kolejka jest pełna, producenci są zawsze zajęci czekaniem. To marny mechanizm. Potrzebny jest sposób blokowania wątków producenta, dopóki kolejka się nie zapełni, oraz sposób blokowania wątków konsumenckich, dopóki kolejka nie będzie pusta.

(Uwaga: Muteksy same w sobie mogą być również spin-lockami , które wymagają zajętego oczekiwania w celu uzyskania blokady, ale aby rozwiązać ten problem zmarnowanych zasobów procesora, zakładamy, że kolejkaLock nie jest blokadą spinową i właściwie używa blokowania zablokuj samą kolejkę.)

Zmienne warunkowe

Rozwiązaniem jest użycie zmiennych warunkowych . Koncepcyjnie zmienna warunkowa to kolejka wątków powiązana z muteksem, w której wątek może czekać na spełnienie się jakiegoś warunku. Zatem każda zmienna warunkowa c jest powiązana z asercją P c . Gdy wątek oczekuje na zmienną warunkową, ten wątek nie zajmuje monitora, więc inne wątki mogą wejść do monitora, aby zmienić jego stan. W większości typów monitorów te inne wątki mogą sygnalizować zmienną warunkową c , aby wskazać, że twierdzenie P c jest prawdziwe w bieżącym stanie.

Tak więc istnieją trzy główne operacje na zmiennych warunkowych:

  • czekać c, m , gdzie c jest zmienną warunkową, a m jest muteksem (blokadą) powiązanym z monitorem. Ta operacja jest wywoływana przez wątek, który przed kontynuacją musi poczekać, aż stwierdzenie P c będzie prawdziwe. Gdy wątek czeka, nie zajmuje monitora. Funkcją i podstawowym kontraktem operacji „oczekiwania” jest wykonanie następujących kroków:
    1. Atomowo :
      1. zwolnij mutex m ,
      2. przenieś ten wątek z „działających” do „kolejki oczekiwania” c (znanej również jako „kolejka snu”) wątków i
      3. prześpij ten wątek. (Kontekst jest synchronicznie przekazywany do innego wątku).
    2. Gdy ten wątek zostanie następnie powiadomiony/zasygnalizowany (patrz poniżej) i wznowiony, automatycznie ponownie uzyska mutex m .
    Kroki 1a i 1b mogą występować w dowolnej kolejności, przy czym etap 1c zwykle występuje po nich. Gdy wątek jest uśpiony i znajduje się w c , następny licznik programu do wykonania jest w kroku 2, w środku funkcji/ podprogramu „oczekiwania” . W ten sposób wątek śpi, a później budzi się w środku operacji „oczekiwania”.
    Atomowość operacji w ramach kroku 1 jest ważna, aby uniknąć warunków wyścigu, które byłyby spowodowane wywłaszczającym przełączaniem wątków pomiędzy nimi. Jednym z trybów awarii, który mógłby wystąpić, gdyby nie były one atomowe, jest pominięte przebudzenie , w którym wątek mógł znajdować się w kolejce uśpienia c i zwolnić muteks, ale przed przejściem wątku w stan uśpienia nastąpiło wyprzedzające przełączenie wątku, a inny wątek zwany operacją sygnalizacyjną (patrz poniżej) na c przesunął pierwszy wątek wycofać się z kolejki c . Gdy tylko pierwszy omawiany wątek zostanie przełączony z powrotem, jego licznik programu znajdzie się w kroku 1c i przejdzie w stan uśpienia i nie będzie można go ponownie obudzić, naruszając niezmiennik, który powinien był być na c kolejki snu, kiedy spał. Inne warunki wyścigu zależą od kolejności kroków 1a i 1b oraz zależą od tego, gdzie następuje zmiana kontekstu.
  • sygnał c , znany również jako powiadomienie c , jest wywoływany przez wątek w celu wskazania, że ​​twierdzenie P c jest prawdziwe. W zależności od typu i implementacji monitora, przenosi to jeden lub więcej wątków z c do „gotowej kolejki” lub innej kolejki do wykonania. Zwykle uważa się, że najlepszą praktyką jest wykonanie operacji „sygnału” przed zwolnieniem muteksu m , który jest powiązany z c , ale dopóki kod jest odpowiednio zaprojektowany pod kątem współbieżności i w zależności od implementacji wątków, często dopuszczalne jest również zwolnienie blokady przed sygnalizacją. W zależności od implementacji wątków, kolejność tego może mieć wpływ na priorytety planowania. (Niektórzy autorzy [ kto? ] Zamiast tego opowiadają się za zwolnieniem blokady przed sygnalizacją.) Implementacja wątków powinna dokumentować wszelkie specjalne ograniczenia dotyczące tej kolejności.
  • broadcast c , znany również jako notifyAll c , to podobna operacja, która budzi wszystkie wątki w kolejce oczekiwania c. Spowoduje to opróżnienie kolejki oczekiwania. Ogólnie, gdy więcej niż jeden warunek predykatu jest powiązany z tą samą zmienną warunkową, aplikacja będzie wymagać rozgłaszania zamiast sygnału ponieważ wątek oczekujący na niewłaściwy warunek może zostać obudzony, a następnie natychmiast ponownie zasnąć bez budzenia wątku oczekującego na właściwy warunek, który właśnie stał się prawdziwy. W przeciwnym razie, jeśli warunek predykatu jest jeden do jednego z powiązaną z nim zmienną warunkową, wtedy sygnał może być bardziej wydajny niż rozgłaszanie .

Zgodnie z regułą projektową, wiele zmiennych warunkowych może być powiązanych z tym samym muteksem, ale nie odwrotnie. (Jest to jeden-do-wielu .) Wynika to z faktu, że predykat Pc mogą jest taki sam dla wszystkich wątków korzystających z monitora i musi być chroniony przez wzajemne wykluczanie wszystkich innych wątków, które mogą spowodować zmianę warunku lub które przeczytaj go, podczas gdy dany wątek powoduje jego zmianę, ale mogą istnieć różne wątki, które chcą czekać na inny warunek dla tej samej zmiennej wymagającej użycia tego samego muteksu. W opisanym powyżej przykładzie producent-konsument , kolejka musi być chroniona przez unikalny obiekt mutex, m . Wątki „producenta” będą chciały czekać na monitorze za pomocą blokady zmiennej warunkowej dopóki kolejka nie będzie pełna Wątki „konsumenckie” będą chciały czekać na innym monitorze przy użyciu tego samego muteksu m , ale innej zmiennej warunkowej który blokuje się, dopóki kolejka nie będzie pusta. (Zwykle) nigdy nie miałoby sensu mieć różnych muteksów dla tej samej zmiennej warunkowej, ale ten klasyczny przykład pokazuje, dlaczego często ma sens posiadanie wielu zmiennych warunkowych używających tego samego muteksa. Muteks używany przez jedną lub więcej zmiennych warunkowych (jeden lub więcej monitorów) może być również współdzielony z kodem, który nie używa zmiennych warunkowych (i który po prostu uzyskuje/zwalnia je bez żadnych operacji oczekiwania/sygnału), jeśli te krytyczne sekcje nie występują wymagać oczekiwania na określony warunek na współbieżnych danych.

Monitoruj użycie

Prawidłowe podstawowe użycie monitora to:

 
   
	  


 
             
 nabywać  (  m  );  // Uzyskaj blokadę tego monitora.  while  (  !  p  )  {  // Podczas gdy warunek/predykat/twierdzenie, na które czekamy, nie jest prawdziwe...  czekaj  (  m  ,  cv  );  // Poczekaj na blokadę i zmienną warunkową tego monitora.  }  // ... Krytyczna sekcja kodu znajduje się tutaj ...  signal  (  cv2  );  // Lub: transmisja (cv2);  // cv2 może być taki sam jak cv lub inny.  uwolnić  (   m  );  // Zwolnij blokadę tego monitora.

Mówiąc dokładniej, jest to ten sam pseudokod, ale z bardziej szczegółowymi komentarzami, aby lepiej wyjaśnić, co się dzieje:











 // ... (poprzedni kod)  // O wejściu do monitora.  // Uzyskaj doradczy muteks (blokadę) powiązany z współbieżnymi  // danymi, które są współdzielone między wątkami,  // aby zapewnić, że żadne dwa wątki nie będą mogły być zapobiegawczo przeplatane lub  // uruchamiane jednocześnie na różnych rdzeniach podczas wykonywania w krytycznych  // sekcjach, które odczytywać lub zapisywać te same współbieżne dane. Jeśli inny   // wątek przetrzymuje ten muteks, to ten wątek zostanie uśpiony  // (zablokowany) i umieszczony w kolejce uśpienia m. (Mutex "m" nie będzie   // spin-lockiem.)  nabyć  (  m 







  	
		
		
		 );  // Teraz trzymamy zamek i możemy sprawdzić stan  // po raz pierwszy.  // Gdy po raz pierwszy wykonujemy warunek pętli while po powyższym  // „acquire”, pytamy: „Czy warunek/predykat/twierdzenie  // na które czekamy, już jest prawdziwy?”  while  (  !  p  ())  // "p" jest dowolnym wyrażeniem (np. zmienną lub  // wywołaniem funkcji), które sprawdza warunek i  // zwraca wartość logiczną. To samo w sobie jest krytyczną   // sekcją, więc *MUSISZ* trzymać blokadę, kiedy 
		
				






 // wykonanie tego warunku pętli „while”!  // Jeśli nie jest to pierwszy raz sprawdzany warunek „while”,  // to zadajemy pytanie: „Teraz, gdy inny wątek korzystający z tego  // monitora powiadomił mnie i obudził mnie, a ja zostałem kontekstowo przełączony  // z powrotem, czy warunek/predykat/twierdzenie, na które czekamy, pozostał  // prawdziwy między momentem, w którym się obudziłem, a czasem, w którym ponownie nabyłem  // zamek wewnątrz wywołania „wait” w ostatnim iteracja tej pętli lub  // jakiś inny wątek spowodował, że warunek ponownie stał się fałszywy w pliku 



	
	
	
	
	

	 
		
		
		 // w międzyczasie czyniąc to fałszywym przebudzeniem?  {  // Jeśli jest to pierwsza iteracja pętli, odpowiedź brzmi  // „nie” — warunek nie jest jeszcze gotowy. W przeciwnym razie odpowiedź brzmi:   // to drugie. To było fałszywe przebudzenie, jakiś inny wątek pojawił się   // jako pierwszy i spowodował, że warunek ponownie stał się fałszywy, i musimy  // znowu czekać.  czekaj  (  m  ,  cv  );  // Tymczasowo uniemożliwić innym wątkom na dowolnym rdzeniu wykonywanie  // operacji na m lub cv.  // release(m) // Atomowo zwolnij blokadę "m" tak inną 
		
		
		
		
		
		
		
		
		
		
		
		
		 // // kod korzystający z tych współbieżnych danych  // // może działać, przenieś ten wątek do // // kolejki oczekiwania cv  , aby został powiadomiony  // // kiedyś, gdy warunek stanie się  // // prawdziwy, i prześpij ten wątek. Ponownie włącz   // // inne wątki i rdzenie do wykonywania  // // operacji na m i cv.  //  // Na tym rdzeniu następuje zmiana kontekstu.  //  // W pewnym momencie w przyszłości warunek, na który czekamy, staje się  // prawdziwy, a inny wątek korzystający z tego monitora (m, cv) wysyła albo  // sygnał, który budzi ten wątek, albo 
		
		
		
		
		
		
		
		
		
		
		
	
	
	


 // transmisja, która nas budzi, co oznacza, że ​​zostaliśmy wyjęci  // z kolejki oczekiwania cv.  //  // W tym czasie inne wątki mogą spowodować, że warunek  ponownie stanie się fałszywy // lub warunek może się przełączyć raz lub więcej  // lub może się zdarzyć, że pozostanie prawdziwy.  //  // Ten wątek jest przełączony z powrotem na jakiś rdzeń.  //  // przejmij(m) // Blokada "m" zostaje ponownie przejęta.  // Zakończ tę iterację pętli i ponownie sprawdź warunek pętli „while”, // aby upewnić się, że  predykat jest nadal prawdziwy.  }  // Warunek, na który czekamy, jest prawdziwy! 












   // Nadal trzymamy blokadę, albo sprzed wejścia do monitora, albo od  // ostatniego wykonania "wait".  // Tutaj znajduje się krytyczna sekcja kodu, która ma warunek wstępny, że nasz predykat  // musi być prawdziwy.  // Ten kod może sprawić, że warunek cv będzie fałszywy i/lub że inne  // predykaty innych zmiennych warunkowych staną się prawdziwe.  // Sygnał wywołania lub rozgłaszanie, w zależności od  // predykatów zmiennych warunkowych (które współdzielą mutex m) stały się prawdziwe lub mogły stać się prawdziwe,  // oraz używanego typu semantycznego monitora.  dla  (  cv_x  w   
	 






 cvs_to_signal  )  {  sygnał  (  cv_x  );  // Lub: transmisja (cv_x);  }  // Jeden lub więcej wątków zostało obudzonych, ale zostaną one zablokowane, gdy tylko spróbują  // uzyskać m.  // Zwolnij muteks, aby powiadomione wątki i inne osoby mogły wejść do swoich  sekcji krytycznych //.  uwolnienie  (  m  );

Rozwiązanie problemu ograniczonego producenta/konsumenta

Wprowadziwszy użycie zmiennych warunkowych, użyjmy go do ponownego przyjrzenia się i rozwiązania klasycznego ograniczonego problemu producent/konsument. Klasycznym rozwiązaniem jest użycie dwóch monitorów, zawierających dwie zmienne warunkowe współdzielące jedną blokadę w kolejce:

    
   
   
				        
    globalna  ulotna  kolejka  RingBuffer  ;  // Niebezpieczny dla wątków bufor pierścieniowy zadań.  global  Blokada  kolejki Blokada  ;  // Muteks dla bufora pierścieniowego zadań. (Nie spin-lock.)   globalna  kolejka  CVEmptyCV  ;  // Zmienna warunkowa dla wątków konsumenckich oczekujących, // aby kolejka  stała się niepusta. Powiązana z nią blokada to „queueLock”.   globalna  kolejka  CVPełneCV  ;  // Zmienna warunkowa dla wątków producenta oczekujących na kolejkę 
				       


   
      
        
           

        
        

        
          // staną się niepełne. Powiązana z nią blokada to także „queueLock”.   // Metoda reprezentująca zachowanie każdego wątku producenta:  metoda  publiczna  producent  ()  {  while  (  true  )  {  // Producent tworzy nowe zadanie do dodania.  zadanie  mojeZadanie  =  ...;  // Uzyskaj „queueLock” do wstępnego sprawdzenia predykatu.  kolejkaBlokada  .  nabywać  ();  // Sekcja krytyczna, która sprawdza, czy kolejka nie jest pełna.  podczas  (  kolejka  
            
             
            
        

        
        

         .  isFull  ())  {  // Zwolnij "queueLock", dodaj ten wątek do "queueFullCV" i uśpij ten wątek.  czekać  (  kolejkaLock  ,  kolejkaPełneCV  );  // Gdy ten wątek zostanie obudzony, ponownie pobierz „queueLock” do następnego sprawdzenia predykatu.  }  // Sekcja krytyczna dodająca zadanie do kolejki (zauważ, że trzymamy "queueLock").  kolejka  .  wstaw do kolejki  (  moje zadanie  );  // Obudź jeden lub wszystkie wątki konsumentów, które czekają, aż kolejka nie będzie pusta 
        
         
        

        
        
    



   
       // teraz, gdy jest to gwarantowane, wątek konsumencki przejmie to zadanie.  sygnał  (  kolejkaPusteCV  );  // Lub: broadcast(queueEmptyCV);  // Koniec sekcji krytycznych.  // Zwolnij „queueLock”, dopóki nie będziemy go potrzebować ponownie, aby dodać następne zadanie.  kolejkaBlokada  .  zwolnij  ();  }  }  // Metoda reprezentująca zachowanie każdego wątku konsumenta:  metoda  publiczna  consumer  ()  {  while  (  true  )  { 
        
        

        
          
            
             
            
         // Uzyskaj „queueLock” do wstępnego sprawdzenia predykatu.  kolejkaBlokada  .  nabywać  ();  // Sekcja krytyczna, która sprawdza, czy kolejka nie jest pusta.  while  (  kolejka  .  isEmpty  ())  {  // Zwolnij "queueLock", dodaj ten wątek do "queueEmptyCV" i uśpij ten wątek.  czekać  (  kolejkaLock  ,  kolejkaEmptyCV  );  // Gdy ten wątek zostanie obudzony, ponownie pobierz „queueLock” do następnego sprawdzenia predykatu.  } 

        
          

        
        
         
        

        
         // Sekcja krytyczna, która usuwa zadanie z kolejki (pamiętaj, że trzymamy „queueLock”).  mojeZadanie  =  kolejka  .  usuń z kolejki  ();  // Obudź jeden lub wszystkie wątki producenta, które czekają na niepełną kolejkę  // teraz, gdy jest to gwarantowane, aby wątek producenta dodał zadanie.  sygnał  (  kolejkaPełneCV  );  // Lub: broadcast(queueFullCV);  // Koniec sekcji krytycznych.  // Zwolnij „queueLock”, dopóki nie będziemy go potrzebować ponownie do wykonania następnego zadania.  kolejkaBlokada  .  zwolnij  (); 

        
        
    
 // Wyjdź i zrób coś z zadaniem.  wykonaj  (  mojeZadanie  );  }  }

Zapewnia to współbieżność między wątkami producenta i konsumenta współużytkującymi kolejkę zadań i blokuje wątki, które nie mają nic do roboty, a nie są zajęte czekaniem, jak pokazano we wspomnianym podejściu z wykorzystaniem spin-locków.

Wariant tego rozwiązania mógłby wykorzystywać pojedynczą zmienną warunku zarówno dla producentów, jak i konsumentów, na przykład o nazwie „queueFullOrEmptyCV” lub „queueSizeChangedCV”. W tym przypadku więcej niż jeden warunek jest powiązany ze zmienną warunku, tak że zmienna warunku reprezentuje słabszy warunek niż warunki sprawdzane przez poszczególne wątki. Zmienna warunkowa reprezentuje wątki, które czekają, aż kolejka nie będzie pełna , oraz wątki, które czekają, aż nie będzie pusta. Jednak wykonanie tego wymagałoby użycia rozgłaszania we wszystkich wątkach przy użyciu zmiennej warunkowej i nie można użyć zwykłego sygnał . Dzieje się tak, ponieważ zwykły sygnał może obudzić wątek niewłaściwego typu, którego warunek nie został jeszcze spełniony, a wątek ten wróciłby do stanu uśpienia bez zasygnalizowania wątku prawidłowego typu. Na przykład producent może zapełnić kolejkę i obudzić innego producenta zamiast konsumenta, a obudzony producent ponownie zasnął. W komplementarnym przypadku konsument mógłby opróżnić kolejkę i zamiast producenta obudzić innego konsumenta, a konsument ponownie zasnąłby. Korzystanie z transmisji zapewnia, że ​​niektóre wątki odpowiedniego typu będą przebiegać zgodnie z oczekiwaniami zawartymi w opisie problemu.

Oto wariant wykorzystujący tylko jedną zmienną warunkową i rozgłoszenie:

    
   
   
                              
                              
                               globalna  ulotna  kolejka  RingBuffer  ;  // Niebezpieczny dla wątków bufor pierścieniowy zadań.  global  Blokada  kolejki Blokada  ;  // Muteks dla bufora pierścieniowego zadań. (Nie spin-lock.)   globalna  kolejka  CVFullOrEmptyCV  ;  // Pojedyncza zmienna warunkowa dla sytuacji, gdy kolejka nie jest gotowa na żaden wątek  // tj. dla wątków producentów oczekujących na niepełną kolejkę  // oraz dla wątków konsumenckich oczekujących na opróżnienie kolejki.  // Powiązana blokada to „queueLock”. 
                              
                              


   
      
        
           

        
         // Używanie zwykłego „sygnału” nie jest bezpieczne, ponieważ jest powiązane z  // wieloma warunkami predykatu (twierdzeniami).  // Metoda reprezentująca zachowanie każdego wątku producenta:  metoda  publiczna  producent  ()  {  while  (  true  )  {  // Producent tworzy nowe zadanie do dodania.  zadanie  mojeZadanie  =  ...;  // Uzyskaj „queueLock” do wstępnego sprawdzenia predykatu.  kolejkaBlokada  .  nabywać  (); 

        
          
            
             
            
        

        
         // Sekcja krytyczna, która sprawdza, czy kolejka nie jest pełna.  while  (  kolejka  .  isFull  ())  {  // Zwolnij „queueLock”, dodaj ten wątek do kolejki „queueFullOrEmptyCV” i uśpij ten wątek.  czekaj  (  kolejkaLock  ,  kolejkaPełnaLubPustaCV  );  // Gdy ten wątek zostanie obudzony, ponownie pobierz „queueLock” do następnego sprawdzenia predykatu.  }  // Sekcja krytyczna dodająca zadanie do kolejki (zauważ, że trzymamy "queueLock").  kolejka  .  kolejkować  ( 

        
        
         
        

        
        
    
 mojeZadanie  );  // Obudź wszystkie wątki producenta i konsumenta, które czekają, aż kolejka będzie odpowiednio  // niepełna i niepusta, teraz, gdy ta ostatnia jest gwarantowana, aby wątek konsumenta przejął zadanie.  rozgłaszaj  (  kolejkaPełnaOrEmptyCV  );  // Nie używaj "sygnału" (ponieważ może to obudzić tylko inny wątek producenta).  // Koniec sekcji krytycznych.  // Zwolnij „queueLock”, dopóki nie będziemy go potrzebować ponownie, aby dodać następne zadanie.  kolejkaBlokada  .  zwolnij  ();  }  } 


   
      
        
        

        
          
            
             // Metoda reprezentująca zachowanie każdego wątku konsumenta:  public  method  consumer  ()  {  while  (  true  )  {  // Uzyskaj „queueLock” do wstępnego sprawdzenia predykatu.  kolejkaBlokada  .  nabywać  ();  // Sekcja krytyczna, która sprawdza, czy kolejka nie jest pusta.  while  (  kolejka  .  isEmpty  ())  {  // Zwolnij „queueLock”, dodaj ten wątek do kolejki „queueFullOrEmptyCV” i uśpij ten wątek.  Czekać  
            
        

        
          

        
        
         (  kolejkaLock  ,  kolejkaPełnaOrEmptyCV  );  // Gdy ten wątek zostanie obudzony, ponownie pobierz „queueLock” do następnego sprawdzenia predykatu.  }  // Sekcja krytyczna, która usuwa zadanie z kolejki (pamiętaj, że trzymamy "queueLock").  mojeZadanie  =  kolejka  .  usuń z kolejki  ();  // Obudź wszystkie wątki producenta i konsumenta, które czekają, aż kolejka będzie odpowiednio  // niepełna i niepusta teraz, gdy ta pierwsza jest gwarantowana, więc wątek producenta doda zadanie.  transmisja  (  
        

        
        

        
        
    
 kolejkaPełneLubPusteCV  );  // Nie używaj „sygnału” (ponieważ może to obudzić tylko inny wątek konsumencki).  // Koniec sekcji krytycznych.  // Zwolnij „queueLock”, dopóki nie będziemy go potrzebować ponownie do wykonania następnego zadania.  kolejkaBlokada  .  zwolnij  ();  // Wyjdź i zrób coś z zadaniem.  wykonaj  (  mojeZadanie  );  }  }

Prymitywy synchronizacji

Implementacja muteksów i zmiennych warunkowych wymaga pewnego rodzaju prymitywu synchronizacji zapewnianego przez wsparcie sprzętowe, które zapewnia niepodzielność . Blokady i zmienne warunkowe są abstrakcjami wyższego poziomu w stosunku do tych prymitywów synchronizacji. W przypadku procesora jednoprocesorowego wyłączanie i włączanie przerwań jest sposobem implementacji monitorów poprzez zapobieganie przełączaniu kontekstu podczas krytycznych sekcji blokad i zmiennych warunkowych, ale to nie wystarcza w przypadku procesora wieloprocesorowego. Na wieloprocesorze zwykle specjalne atomowe odczytu, modyfikacji i zapisu w pamięci, takie jak testowanie i ustawianie , porównywanie i zamiana itp. są używane, w zależności od tego, co zapewnia architektura zestawu instrukcji . Zwykle wymagają one odroczenia blokady wirowania dla samego stanu blokady wewnętrznej, ale ta blokada jest bardzo krótka. W zależności od implementacji, atomowe instrukcje odczytu, modyfikacji i zapisu mogą blokować magistralę przed dostępem innych rdzeni i/lub uniemożliwiać zmianę kolejności instrukcji w procesorze. Oto przykładowa implementacja pseudokodu części systemu wątków i muteksów oraz zmiennych warunkowych w stylu Mesa, przy użyciu testu i ustawienia oraz zasada „kto pierwszy, ten lepszy”. To wyjaśnia większość sposobu działania systemu wątków, ale pokazuje części istotne dla muteksów i zmiennych warunkowych:

Przykładowa implementacja Mesa-monitora z Test-and-Set 



    
     



 // Podstawowe części systemu wątków:  // Załóżmy, że „ThreadQueue” obsługuje swobodny dostęp.  public  volatile  ThreadQueue  readyQueue  ;  // Niebezpieczna dla wątków kolejka gotowych wątków. Elementy to (wątek*).   publiczny  ulotny  wątek  globalny  *  currentThread  ;  // Załóżmy, że ta zmienna dotyczy rdzenia. (Inne są udostępniane.)   // Implementuje blokadę obrotu tylko na zsynchronizowanym stanie samego systemu wątków.  // To jest używane z test-and-set jako prymityw synchronizacji.  publiczny       



   
      
         
    

     ulotne  globalne  wątki  boolSystemBusy  =  false  ;  // Procedura obsługi przerwań przełączania kontekstu (ISR):  // Na bieżącym rdzeniu procesora zapobiegawczo przełącz się na inny wątek.  metoda  publiczna  contextSwitchISR  ()  {  if  (  testAndSet  (  threadingSystemBusy  ))  {  return  ;  // Nie można teraz przełączyć kontekstu.  }  // Upewnij się, że to przerwanie nie może się powtórzyć, co spowodowałoby zafałszowanie przełączania kontekstu: 
    

    
    
    
    
       
     systemCall_disableInterrupts  ();  // Pobierz wszystkie rejestry aktualnie uruchomionego procesu.  // W przypadku licznika programów (PC) będziemy potrzebować lokalizacji instrukcji  // etykiety „resume” poniżej. Pobieranie wartości rejestru jest zależne od platformy i może wymagać   // odczytania aktualnej ramki stosu, instrukcji JMP/CALL itp. (Szczegóły wykraczają poza ten zakres.)  currentThread  ->  registers  =  getAllRegisters  ();  // Zapisz rejestry w obiekcie „currentThread” w pamięci.  bieżący wątek  ->    

     
    
        
    
       rejestry  .  komputer  =  wznów  ;  // W tej metodzie ustaw następny komputer na etykietę „wznowienia” poniżej.  kolejka gotowa  .  wstawiaj do kolejki  (  bieżący wątek  );  // Umieść ten wątek z powrotem w kolejce gotowych do późniejszego wykonania.  Wątek  *  inny wątek  =  kolejka gotowa  .  usuń z kolejki  ();  // Usuń i uruchom następny wątek z kolejki gotowych.  bieżący wątek  =  inny wątek  ;  

    
    
    

    

     // Zastąp wartość globalnego wskaźnika bieżącego wątku, aby był gotowy na następny wątek.  // Przywróć rejestry z currentThread/otherThread, włączając skok do zapisanego PC innego wątku  // (w "resume" poniżej). Ponownie, szczegóły tego, jak to się robi, wykraczają poza ten zakres.   restoreRegisters  (  inny wątek  .  rejestry  );  // *** Teraz działa „otherThread” (który jest teraz „currentThread”)! Oryginalny wątek jest teraz „uśpiony”.  ***   CV  :  

    

       
     




 // To jest miejsce, w którym inne wywołanie contextSwitch() musi ustawić komputer PC podczas przełączania kontekstu z powrotem tutaj.  // Powrót do miejsca, w którym inny wątek został przerwany.  ThreadingSystemBusy  =  false  ;  // Musi być przypisaniem atomowym.  systemCall_enableInterrupts  ();  // Ponownie włącz przełączanie z wywłaszczaniem na tym rdzeniu.  }  // Metoda uśpienia wątku:  // Na bieżącym rdzeniu procesora następuje synchroniczne przełączenie kontekstu na inny wątek bez umieszczania  // bieżącego wątku w kolejce gotowych. 



   
    
    
     // Musi być wstrzymywane "threadingSystemBusy" i wyłączone przerwania, aby ta metoda  // nie była przerywana przez licznik czasu przełączania wątków, który wywołałby contextSwitchISR().  // Po powrocie z tej metody należy wyczyścić „threadingSystemBusy”.  public  method  threadSleep  ()  {  // Pobierz wszystkie rejestry aktualnie uruchomionego procesu.  // W przypadku licznika programów (PC) będziemy potrzebować lokalizacji instrukcji  // etykiety „resume” poniżej. Pobieranie wartości rejestru jest zależne od platformy i może obejmować  
    
       
       

     // odczytywanie aktualnej ramki stosu, instrukcji JMP/CALL itp. (Szczegóły wykraczają poza ten zakres.)  currentThread  ->  registers  =  getAllRegisters  ();  // Zapisz rejestry w obiekcie „currentThread” w pamięci.  currentThread  ->  rejestry  .  komputer  =  wznów  ;  // W tej metodzie ustaw następny komputer na etykietę „wznowienia” poniżej.  // W przeciwieństwie do contextSwitchISR(), nie umieścimy currentThread z powrotem w readyQueue. 
    
    
        
    
       

     // Zamiast tego został już umieszczony w kolejce muteksu lub zmiennej warunkowej.  Wątek  *  inny wątek  =  kolejka gotowa  .  usuń z kolejki  ();  // Usuń i uruchom następny wątek z kolejki gotowych.  bieżący wątek  =  inny wątek  ;  // Zastąp wartość globalnego wskaźnika bieżącego wątku, aby był gotowy na następny wątek.  // Odtwórz rejestry z currentThread/otherThread, w tym skok do zapisanego komputera innego wątku 
    
    

    

     

    


    // (w sekcji „wznowienie” poniżej). Ponownie, szczegóły tego, jak to się robi, wykraczają poza ten zakres.   restoreRegisters  (  inny wątek  .  rejestry  );  // *** Teraz działa „otherThread” (który jest teraz „currentThread”)! Oryginalny wątek jest teraz „uśpiony”.  ***   wznowienie  :  // To jest miejsce, w którym inne wywołanie contextSwitch() musi ustawić komputer PC podczas przełączania kontekstu z powrotem tutaj.  // Powrót do miejsca, w którym inny wątek został przerwany.  }  publiczna  metoda  oczekiwania  (  Mutex  m  ,    
    
    
      
    
    
    
     ConditionVariable  c  )  {  // Wewnętrzna blokada spinu, podczas gdy inne wątki dowolnego rdzenia uzyskują dostęp do  // „wstrzymanych” i „kolejki wątków” lub „kolejki gotowej” tego obiektu.  while  (  testAndSet  (  threadingSystemBusy  ))  {}  // Uwaga: „threadingSystemBusy” ma teraz wartość true.  // Wywołanie systemowe wyłączające przerwania w tym rdzeniu, aby funkcja threadSleep() nie była przerywana przez  // licznik czasu przełączania wątków w tym rdzeniu, który wywołałby contextSwitchISR(). 
    
    
    
 
      
    
    
    
    
    
    
     // Wykonywane poza threadSleep() w celu zwiększenia wydajności, tak aby ten wątek był uśpiony  // zaraz po przejściu do kolejki zmiennej warunkowej.  systemCall_disableInterrupts  ();  twierdzić  m  .  trzymane  ;  // (Konkretnie, ten wątek musi być tym, który go trzyma.)  m  .  zwolnij  ();  do  .  oczekujące wątki  .  wstawiaj do kolejki  (  bieżący wątek  );  wątekUśpij  ();  // Wątek śpi... Wątek zostaje wybudzony z sygnału/transmisji. 
    
       
     
    
    
    
    
    


    
     ThreadingSystemBusy  =  false  ;  // Musi być przypisaniem atomowym.  systemCall_enableInterrupts  ();  // Ponownie włącz przełączanie z wywłaszczaniem na tym rdzeniu.  // Styl Mesa:  // W tym miejscu mogą teraz wystąpić przełączenia kontekstu, powodujące, że predykat wywołującego klienta będzie fałszywy.  m  .  nabywać  ();  }  sygnał  metody  publicznej  (  ConditionVariable  c  )  {  // Wewnętrzna blokada spinu, podczas gdy inne wątki dowolnego rdzenia uzyskują dostęp do obiektu 
    
      
    
    
    
    
    
    
     // "wstrzymane" i "kolejka wątków" lub "kolejka gotowa".  while  (  testAndSet  (  threadingSystemBusy  ))  {}  // Uwaga: „threadingSystemBusy” ma teraz wartość true.  // Wywołanie systemowe wyłączające przerwania w tym rdzeniu, aby funkcja threadSleep() nie była przerywana przez  // licznik czasu przełączania wątków w tym rdzeniu, który wywołałby contextSwitchISR().  // Wykonywane poza threadSleep() dla większej wydajności, tak aby ten wątek był uśpiony  // zaraz po wejściu do kolejki zmiennej warunkowej.  systemCall_disableInterrupts  (); 
    
      
          
        
    
    
       
     
    
     if  (  !  c  .  Wątki oczekujące  .  isEmpty  ())  {  Wątek obudzony  =  c  .  oczekujące wątki  .  usuń z kolejki  ();  kolejka gotowa  .  wstawiaj do kolejki  (  obudziony wątek  );  }  ThreadingSystemBusy  =  false  ;  // Musi być przypisaniem atomowym.  systemCall_enableInterrupts  ();  // Ponownie włącz przełączanie z wywłaszczaniem na tym rdzeniu.  // Styl mesy: 
    


    
    
    
      
    
    
     // Wątek obudzony nie ma żadnego priorytetu.  }  public  method  broadcast  (  ConditionVariable  c  )  {  // Wewnętrzna blokada spinu, podczas gdy inne wątki dowolnego rdzenia uzyskują dostęp do  // obiektów „holdy” i „threadQueue” lub „readyQueue”.  while  (  testAndSet  (  threadingSystemBusy  ))  {}  // Uwaga: „threadingSystemBusy” ma teraz wartość true.  // Wywołanie systemowe wyłączające przerwania w tym rdzeniu, aby funkcja threadSleep() nie była przerywana przez 
    
    
    
    
    
      
          
         // licznik czasu przełączania wątków na tym rdzeniu, który wywołałby contextSwitchISR().  // Wykonywane poza threadSleep() w celu zwiększenia wydajności, tak aby ten wątek był uśpiony  // zaraz po przejściu do kolejki zmiennej warunkowej.  systemCall_disableInterrupts  ();  while  (  !  c  .  Oczekiwanie wątków  .  isEmpty  ())  {  obudzony wątek  =  c  .  oczekujące wątki  .  usuń z kolejki  ();  kolejka gotowa  .  w kolejce  (  obudzony wątek 
    
    
       
     
    
    
    


  
         
        );  }  ThreadingSystemBusy  =  false  ;  // Musi być przypisaniem atomowym.  systemCall_enableInterrupts  ();  // Ponownie włącz przełączanie z wywłaszczaniem na tym rdzeniu.  // Styl Mesa:  // Obudzone wątki nie mają żadnego priorytetu.  }  class  Mutex  {  chroniony  lotny  bool  przechowywany  =  fałsz  ;  private  volatile  ThreadQueue  blockingThreads  ;  
    
       
        
        
          
        
        
         // Niebezpieczna dla wątków kolejka zablokowanych wątków. Elementy to (wątek*).   metoda  publiczna  nabycia  ()  {  // Wewnętrzna blokada spinu, podczas gdy inne wątki dowolnego rdzenia uzyskują dostęp do // obiektów  „wstrzymanych” i „kolejki wątków” lub „kolejki gotowej”.  while  (  testAndSet  (  threadingSystemBusy  ))  {}  // Uwaga: „threadingSystemBusy” ma teraz wartość true.  // Wywołanie systemowe wyłączające przerwania w tym rdzeniu, aby funkcja threadSleep() nie była przerywana przez 
        
        
        
        

         

          
            
             // licznik czasu przełączania wątków na tym rdzeniu, który wywołałby contextSwitchISR().  // Wykonywane poza threadSleep() dla większej wydajności, tak aby ten wątek był uśpiony  // zaraz po przejściu do kolejki blokowania.  systemCall_disableInterrupts  ();  twierdzić  !  blokowanie wątków  .  zawiera  (  bieżący wątek  );  if  (  hold  )  {  // Umieść „bieżący wątek” w kolejce tej blokady, aby // został  uznany za „uśpiony” w tej blokadzie. 
            
            
            
            
            
            
             
             
        
        
           // Zauważ, że „currentThread” nadal wymaga obsługi przez threadSleep().  kolejka gotowa  .  usuń  (  bieżący wątek  );  blokowanie wątków  .  wstawiaj do kolejki  (  bieżący wątek  );  wątekUśpij  ();  // Teraz jesteśmy obudzeni, co musi być spowodowane tym, że "wstrzymane" stało się fałszywe.  twierdzić  !  trzymane  ;  twierdzić  !  blokowanie wątków  .  zawiera  (  bieżący wątek  );  }  wstrzymane  =  prawda 
        
           
         
            
        
       
        
        
           ;  ThreadingSystemBusy  =  false  ;  // Musi być przypisaniem atomowym.  systemCall_enableInterrupts  ();  // Ponownie włącz przełączanie z wywłaszczaniem na tym rdzeniu.  }  public  method  release  ()  {  // Wewnętrzna blokada spinu, podczas gdy inne wątki dowolnego rdzenia uzyskują dostęp do // obiektów  „holded” i „threadQueue” lub „readyQueue”.  while  (  testAndSet  (  ThreadingSystemBusy  ))  {} 
        
        
        
        
        
          

          
        
          
               
             // Uwaga: „threadingSystemBusy” ma teraz wartość true.  // Wywołanie systemowe do wyłączenia przerwań na tym rdzeniu w celu zwiększenia wydajności.  systemCall_disableInterrupts  ();  twierdzić  , że  ;  // (Zwolnienie powinno być wykonane tylko wtedy, gdy blokada jest wciśnięta.)  hold  =  false  ;  if  (  !  blockingThreads  .  isEmpty  ())  {  Wątek  *  unblockedThread  =  blockingThreads  .  usuń z kolejki  ();  kolejka gotowa  . 
        
        
           
         
    


  
      
 w kolejce  (  odblokowany wątek  );  }  ThreadingSystemBusy  =  false  ;  // Musi być przypisaniem atomowym.  systemCall_enableInterrupts  ();  // Ponownie włącz przełączanie z wywłaszczaniem na tym rdzeniu.  }  }  struct  ConditionVariable  {  volatile  ThreadQueue  oczekujące wątki  ;  }

Semafor

Jako przykład rozważmy klasę wątkowo bezpieczną, która implementuje semafor . Istnieją metody zwiększania (V) i zmniejszania (P) prywatnej liczby całkowitej s . Jednak liczba całkowita nigdy nie może być zmniejszana poniżej 0; dlatego wątek, który próbuje zmniejszyć, musi czekać, aż liczba całkowita będzie dodatnia. Używamy zmiennej warunkowej sIsPositive z powiązanym twierdzeniem . 

   

     monitor class  Semaphore  {  private  int  s := 0  niezmienny  s >= 0  private  Warunek  sIsPositive  /*  powiązany z  s > 0 */  public method  P() {  while  s = 0:  wait  sIsPositive  assert  s > 0 s := s - 1 }  metoda publiczna  V() { s := s + 1  załóż  s > 0  sygnał  sIsPositive } }

Zaimplementowano pokazywanie całej synchronizacji (usuwając założenie klasy bezpiecznej dla wątków i pokazując muteks):

    
     

     class  Semaphore  {  private  volatile  int  s := 0  invariant  s >= 0  private  ConditionVariable  sIsPositive  /*  powiązane z  s > 0 */  private  Mutex  myLock  /* Blokada na "s" */  public method  P() { myLock.acquire()  while  s = 0:  czekaj  (myLock, sIsPositive)  assert  s > 0 s := s - 1 myLock.release() }  metoda publiczna  V() { myLock.acquire() s := s + 1  assert  s > 0  sygnał  sIsPositive myLock.release() } }

Monitor realizowany za pomocą semaforów

I odwrotnie, blokady i zmienne warunkowe można również wyprowadzić z semaforów, dzięki czemu monitory i semafory można zredukować do siebie:

Podana tutaj implementacja jest niepoprawna. Jeśli wątek wywoła funkcję wait() po wywołaniu funkcji broadcast(), pierwotny wątek może utknąć na czas nieokreślony, ponieważ funkcja broadcast() zwiększa semafor tylko tyle razy, ile wątków już czeka.

      
     

    
    
    
     
     metoda  publiczna  czekać  (  Mutex  m  ,  ConditionVariable  c  )  {  assert  m  .  trzymane  ;  do  .  wewnętrznyMutex  .  nabywać  ();  do  .  liczba Kelnerzy  ++  ;  m  .  zwolnij  ();  // Może przejść przed/po sąsiednich liniach.  do  .  wewnętrznyMutex  .  zwolnij  (); 

    
    
    
     
    
     


    
    
     // Inny wątek mógłby zasygnalizować tutaj, ale to jest OK ze względu na  // sposób liczenia semaforów. Jeśli liczba c.sem stanie się 1, nie będziemy mieli   // czasu oczekiwania.  do  .  sem  .  nabywać  ();  // Zablokuj w CV.  // Obudzony  m  .  nabywać  ();  // Ponowne pobranie muteksu.  }  sygnał  metody  publicznej  (  ConditionVariable  c  )  {  c  .  wewnętrznyMutex  .  nabywać  ();  Jeśli    0 
        
         
    
    


    
     (  do  .  num Kelnerzy  >  )  {  do  .  liczba Kelnerzy  --  ;  do  .  sem  .  zwolnij  ();  // (Nie musi być chroniony przez c.internalMutex.)  }  c  .  wewnętrznyMutex  .  zwolnij  ();  }  rozgłaszanie  metodą  publiczną  (  zmiennawarunkowa  c  )  {  c  .  wewnętrznyMutex  .  nabywać  (); 
       0 
        
         
    
    


  
         while  (  do  .  num Kelnerzy  >  )  {  do  .  liczba Kelnerzy  --  ;  do  .  sem  .  zwolnij  ();  // (Nie musi być chroniony przez c.internalMutex.)  }  c  .  wewnętrznyMutex  .  zwolnij  ();  }  class  Mutex  {  chronione  wartości logiczne  przechowywane  =  false  ;  
         
                                          

       
        
         
          
    
    
       
         // Tylko dla asercji, aby upewnić się, że liczba sem nigdy nie zostanie przekroczona > 1.  protected  Semaphore  sem  =  Semaphore  (  1  );  // Liczba zawsze będzie wynosić co najwyżej 1.  // Brak posiadania <--> 1; posiadane <--> 0.   metoda  publiczna  nabycia  ()  {  sem  .  nabywać  ();  twierdzić  !  trzymane  ;  trzymane  =  prawda  ;  }  wydanie  metody  publicznej  ()  {  assert   
          
        
    


  
        0 
                                
        0  trzymane  ;  // Upewnij się, że nigdy nie otrzymamy sem powyżej 1. To byłoby złe.  trzymane  =  fałsz  ;  sem  .  zwolnij  ();  }  }  class  ConditionVariable  {  protected  int  numWaiters  =  ;  // Z grubsza śledzi liczbę kelnerów zablokowanych w sem.  // (Wewnętrzny stan semafora jest koniecznie prywatny.)  protected  Semaphore  sem  =  Semaphore  (  );  // Udostępnia kolejkę oczekiwania. 
       
 chroniony  Mutex  wewnętrznyMutex  ;  // (Naprawdę kolejny semafor. Chroni "numWaiters".)  }

Kiedy sygnał pojawia się na zmiennej warunkowej, na którą czeka co najmniej jeden inny wątek, są co najmniej dwa wątki, które mogą wtedy zająć monitor: wątek, który sygnalizuje, i dowolny z wątków oczekujących. Aby za każdym razem monitor zajmował co najwyżej jeden wątek, należy dokonać wyboru. Istnieją dwie szkoły myślenia o tym, jak najlepiej rozwiązać ten wybór. Prowadzi to do dwóch rodzajów zmiennych warunkowych, które zostaną zbadane w następnej kolejności:

  • Zmienne warunku blokowania nadają priorytet sygnalizowanemu wątkowi.
  • Nieblokujące zmienne warunkowe dają pierwszeństwo wątkowi sygnalizacyjnemu.

Blokowanie zmiennych warunkowych

Oryginalne propozycje CAR Hoare'a i Pera Brincha Hansena dotyczyły blokowania zmiennych warunkowych . W przypadku zmiennej warunku blokującego wątek sygnalizacyjny musi czekać poza monitorem (co najmniej), dopóki sygnalizowany wątek nie zrezygnuje z zajętości monitora przez powrót lub ponowne oczekiwanie na zmienną warunkową. Monitory wykorzystujące zmienne warunków blokowania są często nazywane typu Hoare lub monitorami sygnału i pilnego oczekiwania .

Monitor typu Hoare z dwiema zmiennymi warunkowymi a i b . Po tym, jak Buhr i in.

Zakładamy, że z każdym monitorowanym obiektem powiązane są dwie kolejki wątków

  • e to kolejka wejściowa
  • s to kolejka wątków, które zostały zasygnalizowane.

Dodatkowo zakładamy, że dla każdej zmiennej warunkowej c istnieje kolejka

  • c .q , która jest kolejką wątków oczekujących na zmienną warunkową c

Wszystkie kolejki są zwykle gwarantowane jako uczciwe , aw niektórych implementacjach może być zagwarantowane, że pierwsze weszło, pierwsze wyszło .

Realizacja każdej operacji jest następująca. (Zakładamy, że każda operacja jest wykonywana we wzajemnym wykluczaniu innych; w związku z tym zrestartowane wątki nie rozpoczynają wykonywania, dopóki operacja nie zostanie zakończona).

   wejdź do monitora: wprowadź metodę,  jeśli  monitor jest zablokowany dodaj ten wątek do e zablokuj ten wątek  w przeciwnym razie  zablokuj monitor opuść monitor: zaplanuj  powrót  z metody  czekaj  c  : dodaj ten wątek do  c  .q harmonogram zablokuj ten wątek  sygnał  c  :  jeśli  istnieje wątek oczekujący na  c  .q wybierz i usuń jeden taki wątek t z  c  .q (t nazywa się „sygnalizowanym wątkiem”) dodaj ten wątek do s restart t (aby t zajął monitor jako następny) zablokuj ten harmonogram wątków: jeśli jest  wątek  na s wybierz i usuń jeden wątek z s i zrestartuj go (ten wątek zajmie monitor jako następny)  w przeciwnym razie, jeśli  jest wątek na e, wybierz i usuń jeden wątek z e i zrestartuj go (ten wątek zajmie monitor jako następny) w  przeciwnym razie  odblokuj monitor (monitor stanie się pusty)

Procedura planowania wybiera następny wątek do zajęcia monitora lub, w przypadku braku wątków kandydujących, odblokowuje monitor.

Wynikowa dyscyplina sygnalizacyjna jest znana jako „sygnał i pilne oczekiwanie”, ponieważ sygnalizator musi czekać, ale ma pierwszeństwo przed wątkami w kolejce wejściowej. Alternatywą jest „sygnalizuj i czekaj”, w której nie ma kolejki s , a zamiast tego sygnalizator czeka na kolejce e .

Niektóre implementacje zapewniają operację sygnału i powrotu , która łączy sygnalizację z powrotem z procedury. 

   zasygnalizuj  c  i wróć  :  jeśli  wątek czeka na  c  .q wybierz i usuń jeden taki wątek t z  c  .q (t nazywa się „sygnalizowanym wątkiem”) uruchom ponownie t (aby t zajął monitor jako następny)  w przeciwnym razie  zaplanuj  powrót  od metody

W obu przypadkach („sygnał i pilne oczekiwanie” lub „sygnał i oczekiwanie”), gdy sygnalizowana jest zmienna warunkowa i co najmniej jeden wątek czeka na zmienną warunkową, wątek sygnalizacyjny bezproblemowo przekazuje zajętość sygnalizowanemu wątkowi, więc że żadna inna nić nie może zająć miejsca pomiędzy. Jeżeli Pc operacji jest prawdą na początku każdej operacji c na sygnale , to będzie prawdą na końcu każdej oczekiwania c . Podsumowano to w następujących umowach . W tych umowach ja jestem monitorem niezmienny . 

  

  
       

    
     

   wejdź do monitora:  warunek końcowy  wychodzę  z  monitora: warunek wstępny   czekam  c  :  warunek wstępny  I  modyfikuje  stan monitora  warunek końcowy  P  c  i  sygnał  I  c  :  warunek  wstępny  P  c  i  I  modyfikuję  stan monitora  warunek końcowy  I  sygnał  c  i powrót  :  warunek wstępny   Pc  _  i  I

W umowach tych zakłada się, że I i P c nie zależą od zawartości ani długości kolejek.

(Gdy można zapytać zmienną warunkową o liczbę wątków oczekujących w jej kolejce, można podać bardziej wyrafinowane kontrakty. Na przykład użyteczną parą kontraktów, umożliwiającą przekazanie obłożenia bez ustalania niezmiennika, jest:

  
     

 
        czekaj  c  :  warunek wstępny  I  modyfikuje  stan warunku  końcowego monitora   P  c  warunek wstępny  sygnału  c  (  niepusty  (  c  )  i  P  c  )  lub  (pusty (  c  )  i  I  )  modyfikuje  stan warunku  końcowego  I monitora

(Zobacz Howard i Buhr i in., aby uzyskać więcej informacji).

Należy tutaj zauważyć, że twierdzenie P c zależy wyłącznie od programisty; on lub ona po prostu musi być konsekwentny w tym, co to jest.

Kończymy tę sekcję przykładem klasy bezpiecznej wątkowo, używającej monitora blokującego, który implementuje ograniczony, bezpieczny wątkowo stos . 

    
      klasa monitora  SharedStack  {  private const  pojemność := 10  private  int  [pojemność] A  private  int  size := 0  niezmienna  0 <= rozmiar  i  rozmiar <= pojemność  private  Warunek blokowania  theStackIsNotEmpty  /*  powiązane z  0 < rozmiar  i  rozmiar <= pojemność */  private  Warunek blokowania  theStackIsNotFull 

       /*  powiązany z  0 <= rozmiar  i  rozmiar <pojemność */  metoda publiczna  push( wartość   int  ) {  if  rozmiar =pojemność  to  poczekaj  theStackIsNotFull  assert  0 <= rozmiar  i  rozmiar <pojemność A[rozmiar] := wartość ; rozmiar := rozmiar + 1   assert  0 < rozmiar  i  rozmiar <= pojemność  sygnał  theStackIsNotEmpty  i powrót  }  metoda publiczna  int  pop() {  if   size = 0  następnie  poczekaj  theStackIsNotEmpty  assert  0 < size  and  size <= pojemność size := size - 1 ;  assert  0 <= rozmiar  i  rozmiar < pojemność  sygnał  theStackIsNotFull  i zwróć  A[size] } }

Zauważ, że w tym przykładzie stos wątkowo-bezpieczny wewnętrznie zapewnia muteks, który, podobnie jak we wcześniejszym przykładzie producent/konsument, jest współdzielony przez obie zmienne warunkowe, które sprawdzają różne warunki na tych samych współbieżnych danych. Jedyna różnica polega na tym, że przykład producenta/konsumenta zakładał zwykłą kolejkę, która nie jest bezpieczna dla wątków i używał samodzielnego muteksu i zmiennych warunkowych, bez abstrakcji tych szczegółów monitora, jak ma to miejsce w tym przypadku. W tym przykładzie, gdy wywoływana jest operacja „wait”, musi ona w jakiś sposób zostać dostarczona z muteksem stosu bezpiecznego dla wątków, na przykład jeśli operacja „wait” jest zintegrowaną częścią „klasy monitora”. Oprócz tego rodzaju abstrakcyjnej funkcjonalności, gdy używany jest „surowy” monitor, tak będzie zawsze muszą zawierać muteks i zmienną warunku, z unikalnym muteksem dla każdej zmiennej warunku.

Nieblokujące zmienne warunkowe

W przypadku nieblokujących zmiennych warunkowych (zwanych również zmiennymi warunkowymi typu „Mesa” lub zmiennymi warunkowymi „sygnalizuj i kontynuuj” ) sygnalizacja nie powoduje utraty zajętości monitora przez wątek sygnalizacyjny. Zamiast tego sygnalizowane wątki są przenoszone do e . Nie ma potrzeby kolejki s .

Monitor w stylu Mesa z dwiema zmiennymi warunkowymi a i b

W przypadku nieblokujących zmiennych warunkowych operacja na sygnale jest często nazywana powiadamianiem — terminologii, której będziemy się tutaj trzymać. Powszechne jest również dostarczanie powiadamiania wszystkich , która przenosi wszystkie wątki oczekujące na zmienną warunkową do kolejki e .

Znaczenie różnych operacji podano tutaj. (Zakładamy, że każda operacja jest wykonywana we wzajemnym wykluczaniu innych; w związku z tym zrestartowane wątki nie rozpoczynają wykonywania, dopóki operacja nie zostanie zakończona).

   wejdź do monitora: wprowadź metodę,  jeśli  monitor jest zablokowany dodaj ten wątek do e zablokuj ten wątek  w przeciwnym razie  zablokuj monitor opuść monitor: zaplanuj  powrót  z metody  czekaj  c  : dodaj ten wątek do  c  .q harmonogram zablokuj ten wątek  powiadom  c  : jeśli istnieje wątek oczekujący na  c  .q wybierz i usuń jeden wątek t z  c  .q (t nazywa się „zgłoszonym wątkiem”) przenieś t do e   powiadom wszystkich  c  : przenieś wszystkie wątki oczekujące na  c  .q do harmonogramu e :  jeśli  jest wątek na e wybierz i usuń jeden wątek z e i zrestartuj go  w przeciwnym razie  odblokuj monitor

Jako odmiana tego schematu, zgłoszony wątek może zostać przeniesiony do kolejki o nazwie w , która ma pierwszeństwo przed e . Patrz Howard i Buhr i in. do dalszej dyskusji.

Możliwe jest powiązanie twierdzenia P c z każdą zmienną warunkową c w taki sposób, że P c z pewnością będzie prawdziwe po powrocie z oczekiwania c . Należy jednak upewnić się, że P c jest zachowane od czasu, gdy powiadamiający wątek zrezygnuje z zajętości, aż do momentu, gdy powiadomiony wątek zostanie wybrany do ponownego wejścia do monitora. Pomiędzy tymi godzinami może być aktywność innych mieszkańców. Dlatego często zdarza się, że Pc jest po prostu prawdziwe .

Z tego powodu zwykle konieczne jest zamknięcie każdej operacji oczekiwania w takiej pętli 

 
     podczas  gdy  nie  (  P  )  czekaj  c

gdzie P jest pewnym warunkiem silniejszym niż P c . Operacje powiadamiania c i powiadamiania wszystkich c są traktowane jako „wskazówki”, że P może być prawdziwe dla jakiegoś oczekującego wątku. Każda iteracja takiej pętli poza pierwszą oznacza utratę powiadomienia; dlatego w przypadku monitorów nieblokujących należy uważać, aby nie można było utracić zbyt wielu powiadomień.

Jako przykład „podpowiedzi” rozważ konto bankowe, na którym wątek wypłaty będzie czekał, aż na koncie będzie wystarczająca ilość środków, zanim przejdzie dalej

     monitor class  Account  {  private  int  balance := 0  niezmienne  saldo >= 0  private  NonblockingCondition  balanceMayBeBigEnough  metoda publiczna  wypłacić(  int  kwota)  warunek  wstępny  kwota >= 0 {  while  balance < kwota  czekać  saldoMayBeBigEnough  potwierdzić  saldo >= kwota saldo := saldo - kwota } depozyt   metodą publiczną  (  int  kwota)  warunek wstępny  kwota >= 0 { saldo := saldo + kwota  powiadom wszystkich  saldoMayBeBigEnough } }

W tym przykładzie oczekiwany warunek jest funkcją kwoty do wypłaty, więc wątek deponujący nie może wiedzieć, że spełnił taki warunek. W tym przypadku sensowne jest wpuszczenie każdego oczekującego wątku do monitora (pojedynczo), aby sprawdzić, czy jego asercja jest prawdziwa.

Niejawne monitory zmiennych warunków

Monitor w stylu Java

W języku Java każdy obiekt może służyć jako monitor. Metody wymagające wzajemnego wykluczania muszą być wyraźnie oznaczone słowem synchronized . Bloki kodu mogą być również oznaczone zsynchronizowanymi plikami .

Zamiast mieć jawne zmienne warunkowe, każdy monitor (tj. obiekt) jest wyposażony w pojedynczą kolejkę oczekiwania oprócz kolejki wejściowej. Wszystkie operacje oczekiwania są wykonywane w tej pojedynczej kolejce oczekiwania, a wszystkie powiadamiania i powiadamiania o wszystkim mają zastosowanie do tej kolejki. Podejście to zostało przyjęte w innych językach, na przykład C# .

Niejawna sygnalizacja

Innym podejściem do sygnalizacji jest pominięcie operacji sygnalizacji . Za każdym razem, gdy wątek opuszcza monitor (poprzez powrót lub oczekiwanie), twierdzenia wszystkich oczekujących wątków są oceniane, dopóki jeden z nich nie zostanie uznany za prawdziwy. W takim systemie zmienne warunkowe nie są potrzebne, ale asercje muszą być jawnie zakodowane. Umowa na czekanie jest 

  
        czekaj  P  :  warunek wstępny  I  modyfikuje  stan  warunku końcowego  P  i  I monitora

Historia

Brinch Hansen i Hoare opracowali koncepcję monitora na początku lat 70., opierając się na wcześniejszych pomysłach własnych i Edsgera Dijkstry . Brinch Hansen opublikował pierwszą notację monitora, przyjmując klas z Simula 67 i wynalazł mechanizm kolejkowania. Hoare dopracował zasady wznowienia procesu. Brinch Hansen stworzył pierwszą implementację monitorów w Concurrent Pascal . Hoare wykazał ich równoważność z semaforami .

Monitory (i Concurrent Pascal) zostały wkrótce użyte do uporządkowania synchronizacji procesów w systemie operacyjnym Solo.

Języki programowania obsługujące monitory obejmują:

Napisano wiele bibliotek, które umożliwiają konstruowanie monitorów w językach, które nie obsługują ich natywnie. Gdy używane są wywołania bibliotek, programista musi wyraźnie zaznaczyć początek i koniec wykonywanego kodu z wzajemnym wykluczeniem. Pthreads jest jedną z takich bibliotek.

Zobacz też

Notatki

Dalsza lektura

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Monitor_(synchronizacja)&oldid=1122802829 ”