Problem ucztujących filozofów
Problem ucztujących filozofów (znany też jako problem pięciu filozofów) – przykład klasycznego dla informatyki zadania synchronizacji procesów.
W 1965 roku E. Dijkstra wymyślił zadanie egzaminacyjne dotyczące sytuacji, w której 5 komputerów próbuje uzyskać dostęp do 5 współdzielonych napędów dysków. Niedługo potem problem został przedstawiony na nowo przez Ch. Hoare’a jako problem ucztujących filozofów. Jest to teoretyczne wyjaśnienie zakleszczenia i uniemożliwienia innym jednostkom korzystania z zasobów poprzez założenie, że każdy z filozofów bierze po jednym widelcu, a dopiero potem próbuje zdobyć drugi.
Problem ucztujących filozofów jest prezentacją problemu synchronizacji pracujących współbieżnie procesów. Istnieje kilka możliwych rozwiązań tego problemu, między innymi wykorzystujące arbitrów lub grupy semaforów.
Problem
Pięciu filozofów siedzi przy stole i każdy wykonuje jedną z dwóch czynności – albo je, albo rozmyśla. Stół jest okrągły, przed każdym z nich znajduje się miska ze spaghetti, a pomiędzy każdą sąsiadującą parą filozofów leży widelec, a więc każda osoba ma przy sobie dwie sztuki – po swojej lewej i prawej stronie. Ponieważ jedzenie potrawy jest trudne przy użyciu jednego widelca, zakłada się, że każdy filozof korzysta z dwóch. Dodatkowo nie ma możliwości skorzystania z widelca, który nie znajduje się bezpośrednio przed daną osobą. Problem ucztujących filozofów jest czasami przedstawiany przy użyciu ryżu, który musi być jedzony dwiema pałeczkami, co lepiej obrazuje sytuację.
Filozofowie nigdy nie rozmawiają ze sobą, co stwarza zagrożenie zakleszczenia w sytuacji, gdy każdy z nich zabierze lewy widelec i będzie czekał na prawy (lub na odwrót).
Aby zilustrować problem zakleszczenia możemy przyjąć, że opisany system wchodzi w stan zakleszczenia w przypadku, gdy wystąpi „krąg nieuprawnionych zgłoszeń”. W takiej sytuacji filozof P1 czeka na widelec zabrany przez filozofa P2, który czeka na widelec filozofa P3 itd. tworząc cykliczny łańcuch.
Głodzenie (zamierzona gra słów w oryginalnym opisie problemu) może także wystąpić niezależnie od zakleszczenia w sytuacji, gdy zostanie wzięta pod uwagę kwestia czasu oczekiwania filozofa na dwa wolne widelce.
Przykładowo, może zostać wprowadzona reguła, że filozof czeka pięć minut z widelcem w ręku, aż drugi widelec będzie dostępny. W sytuacji, gdy nie otrzyma kompletu, odkłada go i czeka kolejne pięć minut przed podjęciem kolejnej próby zdobycia pary sztućców. Taki schemat eliminuje możliwość zakleszczenia (system może zmieniać swój stan) jednak dalej jest podatny na problem livelock. Jeśli wszyscy filozofowie wejdą do jadalni jednocześnie, następnie dokładnie w tym samym czasie chwycą za swój lewy widelec, to po pięciu minutach wszyscy go odłożą, poczekają pięć minut, znowu go zabiorą itd.
Brak dostępnych widelców jest analogią braku dostępu do współdzielonych zasobów w rzeczywistym programowaniu komputerów, w sytuacji zwanej współbieżnością. Blokowanie zasobów jest powszechną techniką zapewniania wyłącznego dostępu do zasobu przez jeden program lub moduł kodu. Gdy zasób zostaje zajęty przez program, każdy następny „zainteresowany” nim program jest blokowany do czasu zwolnienia zasobu. Zależnie od okoliczności, jeśli kilka programów bierze udział w blokowaniu zasobu, możliwe jest zakleszczenie.
Na przykład: jeden program potrzebuje dwóch plików do działania, więc jeśli uruchomimy dwa takie programy i zablokują one po jednym pliku, to oba programy będą czekały na zwolnienie drugiego pliku, co nigdy nie nastąpi.
Problem ucztujących filozofów jest uogólnionym i abstrakcyjnym problemem używanym do tłumaczenia różnych zagadnień powstających wokół problemów dotyczących wzajemnego wykluczania. W powyższym przypadku problem zakleszczenia jest zilustrowany przy jego pomocy.
Rozwiązania
Rozwiązanie przy pomocy kelnera
Relatywnie prostym rozwiązaniem jest wprowadzenie kelnera. Filozofowie będą pytać go o pozwolenie przed wzięciem widelca. Ponieważ kelner jest świadomy, które widelce są aktualnie w użyciu, może nimi rozporządzać zapobiegając zakleszczeniom.
Gdy cztery widelce są w użyciu, następny filozof (chcący uzyskać możliwość jedzenia) będzie musiał czekać na pozwolenie kelnera. Pozwolenie nie zostanie udzielone do czasu zwolnienia widelca przez jednego z jedzących. Logika zostanie zachowana jeśli założymy, że filozofowie w pierwszej kolejności sięgają po widelec leżący po ich lewej stronie, a następnie po prawy (lub na odwrót).
Aby zilustrować jak to działa, oznaczmy filozofów literami od A do E (zgodnie z ruchem wskazówek zegara). Jeśli A i C jedzą, cztery widelce są w użyciu. B siedzi między A i C, więc nie ma w jego sąsiedztwie żadnego widelca, podczas gdy D i E mają jeden nieużywany widelec między sobą. Przypuśćmy, że D chciałby coś zjeść. Gdyby podniósł piąty widelec, zaistniałoby prawdopodobieństwo zakleszczenia. Gdyby natomiast spytał kelnera o widelec, dostałby od niego polecenie czekania, a po zwolnieniu widelców D byłby pierwszym, który dostanie komplet sztućców. Dzięki takiemu podejściu zostało wyeliminowane zagrożenie zakleszczenia.
Rozwiązanie przy użyciu hierarchii zasobów
Inne proste rozwiązanie jest osiągalne poprzez częściowe uporządkowanie lub ustalenie hierarchii dla zasobów (w tym wypadku widelców) i wprowadzenie zasady, że kolejność dostępu do zasobów jest ustalona przez ów porządek, a ich zwalnianie następuje w odwrotnej kolejności, oraz że dwa zasoby niepowiązane relacją porządku nie mogą zostać użyte przez jedną jednostkę w tym samym czasie.
W tym przykładzie oznaczmy zasoby (widelce) numerami od 1 do 5 – w ustalonym porządku – oraz ustalmy, że jednostki (filozofowie) zawsze najpierw podnoszą widelec oznaczony niższym numerem, a dopiero potem ten oznaczony wyższym. Następnie, zwracając widelce, najpierw oddają widelec z wyższym numerem, a potem z niższym. W tym wypadku, jeśli czterech filozofów jednocześnie podniesie swoje widelce z niższymi numerami, na stole pozostanie widelec z najwyższym numerem, przez co piąty filozof nie będzie mógł podnieść żadnego. Ponadto tylko jeden filozof ma dostęp do widelca z najwyższym numerem, więc będzie on mógł jeść dwoma widelcami. Gdy skończy, najpierw odłoży widelec z najwyższym numerem, a następnie z niższym, umożliwiając kolejnemu filozofowi zabranie drugiego sztućca.
Właśnie takie rozwiązanie swojego zadania proponował Dijkstra.
Pomimo że rozwiązanie hierarchii zasobów zapobiega zakleszczeniom, nie zawsze jest ono praktyczne, zwłaszcza gdy lista wymaganych zasobów nie jest z góry znana. Na przykład jeśli jednostka zajmuje zasoby 3 i 5, po czym stwierdza, że potrzebuje zasobu 2, musi zwolnić 5, a następnie 3, aby zająć 2, a następnie ponownie zająć 3 i 5 (w tej kolejności). Programy komputerowe, które uzyskują dostęp do dużej liczby rekordów w bazie danych, nie działałyby wydajnie, gdyby przed uzyskaniem dostępu do nowego wiersza musiały zwalniać dostęp do wierszy z wyższymi numerami, przez co metoda jest niepraktyczna dla takiego zastosowania.
Jest to często najbardziej praktyczne rozwiązanie dla rzeczywistych problemów informatyki; poprzez ustalenie stałej hierarchii blokad oraz wymuszanie porządku nabywania blokad, można zapobiec temu problemowi.
Rozwiązanie Chandy/Misra
W 1984, K. Mani Chandy i J. Misra zaproponowali inny sposób rozwiązania problemu ucztujących filozofów, aby pozwolić dowolnym agentom (ponumerowanym P1,...,Pn) ubiegać się o dostęp do dowolnej liczby zasobów, w przeciwieństwie do rozwiązania Dijkstry. Rozwiązanie to jest także kompletnie rozproszone i nie wymaga centralnego zarządzania po inicjalizacji.
- Dla każdej pary filozofów ubiegającej się o dostęp do zasobu stwórz widelec i wręcz go filozofowi z niższym identyfikatorem (ID). Każdy widelec może być brudny lub czysty. Na początku wszystkie widelce są brudne.
- Gdy filozof chce użyć zbioru zasobów (tj. jeść), musi uzyskać widelec od konkurujących z nim sąsiadów. Dla każdego widelca, który nie jest w jego posiadaniu, wysyła żądanie w celu jego uzyskania.
- Gdy filozof z widelcem otrzymuje żądanie, zatrzymuje widelec, jeśli jest on czysty, jeśli natomiast jest brudny, to go przekazuje, uprzednio myjąc.
- Gdy filozof kończy jedzenie, wszystkie jego widelce stają się brudne. Jeśli podczas jedzenia przyszło żądanie od innego filozofa, wtedy po skończeniu jedzenia, przekazywany jest czysty widelec.
To rozwiązanie pozwala na duży stopień współbieżności rozwiązując dowolnie duży problem.
Zobacz też
Bibliografia
- Silberschatz, Abraham; Peterson, James L. Operating Systems Concepts. Addison-Wesley. 1988.
- Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems.
- Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115-138.
- Lehmann, D. J., Rabin M. O, (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pages 133-138.
Linki zewnętrzne
Media użyte na tej stronie
(c) Benjamin D. Esham / Wikimedia Commons, CC BY-SA 3.0
An illustration of the dining philosophers problem.