Problem śpiącego golibrody

Problem śpiącego golibrody (ang. sleeping barber problem) – klasyczny informatyczny problem komunikacji i synchronizacji pomiędzy kilkoma procesami. Można go przedstawić za pomocą analogii do pracy golibrody, który odpoczywa w gabinecie, gdy nie ma klientów, i obsługuje ich, gdy się pojawiają.

Problem

Analogia bazuje na hipotetycznym gabinecie z jednym golibrodą. Golibroda ma jedno krzesło w swoim gabinecie, a obok znajduje się poczekalnia z pewną liczbą krzeseł dla klientów. Gdy golibroda kończy golić brodę klienta, pozwala mu opuścić gabinet, po czym idzie do poczekalni sprawdzić, czy jakiś klient tam czeka. Jeśli tak, przyprowadza go do gabinetu, sadza na krześle i goli jego brodę. Jeśli jednak nikt nie czeka w poczekalni, golibroda wraca do gabinetu i zasypia na swoim krześle.

Przychodzący klient sprawdza najpierw, co robi golibroda. Jeśli golibroda śpi, klient budzi go i siada na jego krześle, gdzie jest obsługiwany. Jeśli golibroda aktualnie pracuje, klient wchodzi do poczekalni. Jeśli w poczekalni jest wolne krzesło, klient siada na nim i czeka na swoją kolej, jeśli natomiast nie ma wolnego krzesła, klient wychodzi. Z prostej analizy powyższego opisu można wysnuć wniosek, że gabinet będzie funkcjonował poprawnie: golibroda będzie obsługiwał każdego chętnego klienta, a gdy ich zabraknie, będzie spał, dopóki nie zjawi się kolejny. W praktyce może pojawić się wiele problemów, które dobrze ilustrują potencjalne trudności w komunikacji międzyprocesowej.

Wszystkie te problemy wynikają z faktu, że działania wykonywane przez golibrodę jak i klienta (sprawdzanie stanu poczekalni, wchodzenie do gabinetu, zajmowanie krzesła w poczekalni, itd.) zajmują nieznaną ilość czasu. Klient może po wejściu zobaczyć, że golibroda jest zajęty. Zdecyduje w takim razie, że powinien udać się do poczekalni. Podczas gdy klient jest w drodze, golibroda kończy obsługiwać poprzedniego klienta i również idzie do poczekalni, by sprawdzić, czy jest tam kolejny klient. Nie ma tam jednak nikogo (bo nowy klient jeszcze tam nie dotarł), więc golibroda wraca do gabinetu i zasypia. Następnie nowy klient zajmuje miejsce w poczekalni. W takiej sytuacji golibroda czeka na klienta, podczas gdy ten sam klient czeka w poczekalni na golibrodę. Innym przykładem może być sytuacja, w której dwóch klientów przychodzi do golibrody w tym samym czasie, podczas gdy w poczekalni jest jedno wolne miejsce. Obaj zauważają, że golibroda jest zajęty, po czym idą do poczekalni i próbują zająć to samo krzesło.

Wymyślenie tej analogii jest często przypisywane Edsgerowi Dijkstrze, jednemu z pionierów informatyki.

Rozwiązanie

Istnieje wiele rozwiązań tego problemu. Kluczowym elementem każdego z nich jest tzw. mutex (blokada), który sprawia, że tylko jeden proces naraz może zmieniać stan systemu. Golibroda musi uzyskać dla siebie blokadę, zanim sprawdzi liczbę klientów, i zwolnić ją, gdy zasypia lub zaczyna obsługiwać klienta. Klient musi uzyskać blokadę, zanim wejdzie do gabinetu, i zwolnić ją, gdy tylko usiądzie w poczekalni lub na krześle golibrody. Zabieg ten eliminuje oba problemy opisane w poprzedniej sekcji. Potrzebna jest także pewna liczba semaforów do przechowywania stanu systemu, na przykład liczby osób w poczekalni.

Zobacz też

• problem ucztujących filozofów
• problem producenta i konsumenta

Bibliografia

• Andrew S. Tanenbaum: Modern Operating Systems (2nd Edition). Upper Saddle River, N.J.: Prentice Hall, 2001. ISBN 0-13-031358-0.brak strony w książce
• Allen B. Downey: The Little Book of Semaphores. 2008, s. 127–131. [dostęp 2012-02-10].
• Edsger W. Dijkstra: Cooperating sequential processes, Technical Report EWD-123. Technological University, Eindhoven, The Netherlands: 1965. [dostęp 2012-02-10].brak strony w książce