Problem ze śpiącym fryzjerem

W informatyce problem śpiącego fryzjera jest klasycznym problemem komunikacji i synchronizacji między procesami , który ilustruje złożoność pojawiającą się, gdy istnieje wiele procesów systemu operacyjnego .

Problem został pierwotnie zaproponowany w 1965 roku przez pioniera informatyki Edsgera Dijkstrę , który użył go, aby podkreślić, że semafory ogólne są często zbędne.

Oświadczenie o problemie

Wyobraź sobie hipotetyczny zakład fryzjerski z jednym fryzjerem, jednym fotelem fryzjerskim i poczekalnią z n krzesłami ( n może wynosić 0) dla oczekujących klientów. Obowiązują następujące zasady:

  • Jeśli nie ma klientów, fryzjer zasypia na krześle
  • Klient musi obudzić fryzjera, jeśli ten śpi
  • Jeśli klient przychodzi, gdy fryzjer pracuje, wychodzi, jeśli wszystkie krzesła są zajęte i siada na pustym krześle, jeśli jest dostępne
  • Kiedy fryzjer kończy strzyżenie, sprawdza poczekalnię, czy nie ma oczekujących klientów i zasypia, jeśli ich nie ma

Istnieją dwie główne komplikacje. Po pierwsze, istnieje ryzyko, że sytuacja wyścigowa , w której fryzjer śpi, podczas gdy klient czeka, aż fryzjer zabierze go na strzyżenie, powstaje, ponieważ wszystkie czynności — sprawdzenie poczekalni, wejście do sklepu, zajęcie fotela w poczekalni — poświęcić określoną ilość czasu. Konkretnie, klient może przyjść, aby znaleźć fryzjera strzyżącego włosy, więc wraca do poczekalni, aby zająć miejsce, ale wracając do poczekalni, fryzjer kończy strzyżenie i idzie do poczekalni, którą zastaje pustą (ponieważ klient chodzi wolno lub idzie do toalety) i tym samym zasypia w fotelu fryzjerskim. Po drugie, inny problem może wystąpić, gdy dwóch klientów przychodzi w tym samym czasie, gdy w poczekalni jest tylko jedno wolne miejsce i obaj próbują usiąść na jednym krześle; tylko pierwsza osoba, która dotrze do krzesła, będzie mogła usiąść.

Problem wielu śpiących fryzjerów ma dodatkową złożoność polegającą na koordynowaniu kilku fryzjerów wśród oczekujących klientów.

Rozwiązania

Istnieje kilka możliwych rozwiązań, ale wszystkie rozwiązania wymagają muteksu , który gwarantuje, że tylko jeden z uczestników może zmienić stan jednocześnie. Fryzjer musi uzyskać muteks stanu pokoju przed sprawdzeniem klientów i zwolnić go, gdy zaczną spać lub ścinać włosy; klient musi go nabyć przed wejściem do sklepu i wydać po zajęciu miejsca w poczekalni lub fotelu fryzjerskim, a także przy wyjściu ze sklepu z powodu braku wolnych miejsc. Rozwiązałoby to oba wyżej wymienione problemy. Szereg semaforów wymagane jest również wskazanie stanu systemu. Na przykład można zapisać liczbę osób w poczekalni.

Realizacja

Poniższy pseudokod gwarantuje synchronizację między fryzjerem a klientem i jest wolny od zakleszczeń , ale może doprowadzić do zagłodzenia klienta. Problem głodu można rozwiązać za pomocą kolejki „ pierwsze weszło, pierwsze wyszło” (FIFO) . Semafor zapewniałby dwie funkcje: wait() i signal() , które pod względem kodu C odpowiadałyby odpowiednio P () i V() . [ potrzebne źródło ] 


   0
        
   0         
        

 
                       # Pierwsze dwa to muteksy (możliwe tylko 0 lub 1)  Semaphore  barberReady  =  Semaphore  accessWRSeats  =  1  # jeśli 1, liczba miejsc w poczekalni może być zwiększana lub zmniejszana  Semaphore  custReady  =  # liczba klientów aktualnie przebywających w poczekalni , gotowe do obsłużenia  int  numberOfFreeWRSeats  =  N  # całkowita liczba miejsc w poczekalni  def  Barber  ():  while  true  :  # Uruchom w nieskończonej pętli. 
                 
             
          
             
           
    

  wait  (  custReady  )  # Spróbuj pozyskać klienta - jeśli żaden nie jest dostępny, idź spać.  wait  (  accessWRSeats  )  # Awake - spróbuj uzyskać dostęp do modyfikacji # dostępnych miejsc, w przeciwnym razie śpij.  numberOfFreeWRSeats  +=  1  # Jedno krzesło w poczekalni staje się wolne.  signal  (  barberReady  )  # Jestem gotowy do cięcia.  signal  (  accessWRSeats  )  # Nie potrzebujesz już zamka na krzesłach.  # (Obetnij tutaj włosy.)  Def  Customer 
                      
             
       0 
          
               
       ():  while  true  :  # Uruchom w nieskończonej pętli, aby zasymulować wielu klientów.  wait  (  accessWRSeats  )  # Spróbuj uzyskać dostęp do krzeseł w poczekalni.  if  numberOfFreeWRSeats  >  :  # Jeśli są wolne miejsca:  numberOfFreeWRSeats  -=  1  # usiądź na krześle  sygnał  (  custReady  )  # powiadom fryzjera, który czeka na  sygnał klienta   (  accessWRSeats  )      
               
      
                           
           
       # nie trzeba już zamykać krzeseł,  czekać  (  barberReady  )  # czekać, aż fryzjer będzie gotowy  # (Tutaj należy obciąć włosy.)  else  :  # w przeciwnym razie nie ma wolnych miejsc; pech --   sygnał  (  accessWRSeats  )  # ale nie zapomnij zwolnić blokady siedzeń!  # (Wyjdź bez strzyżenia.)

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Sleeping_barber_problem&oldid=1098544845 ”