Problem Restauratorów Filozofów: Zamknięcie, Głodowanie i Jak Je Unikać

Delikatnie zaprojektowane zapętle (deadlock)

Edsger Dijkstra sformułował problem pięciu filozofów w 1965 roku (początkowo dotyczący napędowych taśm; późniejsze, popularne framing z filozofami zostało wprowadzone przez Tony'ego Hoare), aby zilustrować zapętle i głodowanie przy użyciu najprostszej możliwej konfiguracji: pięciu filozofów siedzi wokół okrągłego stołu, pomiędzy każdą sąsiednią parą znajduje się pojedynczy widelec, a każdy filozof potrzebuje obu sąsiadujących wideł do jedzenia. Każdy filozof na przemian myśli i je, a widelec może być trzymany przez jednego filozofa jednocześnie – jest to zasób z wykluczeniem współbieżnym, dokładnie jak blokada, wiersz bazy danych lub bufor pamięci współdzielonej w rzeczywistym systemie współbieznym.

Prawidłowe, naiwne rozwiązanie

Oczywiste implementacja zakłada, że każdy filozof wybiera lejek, następnie prawy lejek, je i odkłada oba. Jeśli wszyscy filozofowie chwycą lejek po lewej stronie w tym samym momencie, wszystkie pięć lejki są teraz trzymane, a każdy filozof czeka na wieczność na prawy lejek, który nigdy nie zostanie zwolniony – zablokowanie (deadlock). Jest to klasyczne przedstawienie czterech warunków Coffmana, które muszą zachodzić jednocześnie, aby wystąpiło zablokowanie: wykluczenie wzajemne (lejek służy jednemu filozofowi), trzymanie i oczekiwanie (trzymanie lejka po lewej stronie podczas czekania na prawy), brak przejęcia (nikt nie może zmusić lejka do oddania filozofu) i oczekiwanie okrężne (każdy filozof czeka na sąsiada po prawej stronie, tworząc cykl).

// naiwne: zablokowanie występuje, gdy każdy filozof chwyta lejek jednocześnie pickUp(lejek_po_lewej_stronie); pickUp(lejek_po_prawej_stronie); // blokuje na zawsze, jeśli trzymacz lejka po prawej stronie jest // sam w stanie oczekiwania na SWÓJ prawy lejek (cykl) eat(); putDown(lejek_po_lewej_stronie); putDown(lejek_po_prawej_stronie)

// naive: deadlocks if every philosopher grabs left simultaneously
pickUp(leftFork);
pickUp(rightFork);   // blocks forever if right fork's holder is
                      // itself waiting on ITS right fork (a cycle)
eat();
putDown(leftFork);
putDown(rightFork);

Uporządkowanie zasobów przerywa pętlę oczekiwania

Najtańsze rozwiązanie bezpośrednio łamie pętlę oczekiwania: numeruj widełki od 0 do 4 i wymagaj, aby każdy filozof najpierw chwycił widełko o niższym numerze, niezależnie od tego, po której stronie jest. W ten sposób filozof między widełkami 4 i 0 chwyta widełko 0 pierwszy, a nie widełko 4 – to jedyna asymetria potrzebna do uniemożliwienia powstania wzoru cyklicznego oczekiwania. Jest to dokładnie technika stosowana w rzeczywistych silnikach baz danych i menedżerach bloków: zawsze odnajmuj bloki w ustalonym globalnym porządku, a pętla oczekiwania nie może powstać niezależnie od tego, ile wątków konkuruje.

// resource (fork) ordering — breaks circular wait
const [first, second] = leftFork.id < rightFork.id
  ? [leftFork, rightFork] : [rightFork, leftFork];
pickUp(first);
pickUp(second);
eat();
putDown(second);
putDown(first);

Sędzia i ograniczenie współbieżności

Drugie klasyczne rozwiązanie eliminuje sytuację hold-and-wait: wprowadza się sędziego (czeka, jak w opowieści), którego filozof musi poprosić o pozwolenie przed podniesieniem jakiejkolwiek gałki. Sędzia przyznaje pozwolenie tylko wtedy, gdy obie gałki są wolne, a proces ten odbywa się atomowo. W rezultacie żaden filozof nie trzyma jednej gałki podczas czekania na drugą, co uniemożliwia strukturalnie zablokowanie – kosztem pojedynczego punktu synchronizacji globalnej, który może stać się wąskim gardłem przy dużym obciążeniu, co stanowi klasyczny kompromis związany z blokadami centralnymi.

Trzecie rozwiązanie ogranicza współbieżność bezpośrednio: pozwala siedzieć maksymalnie czterem spośród pięciu filozofów naraz. Dzięki czterom kandydatom na cztery gałki, co najmniej jeden filozof ma gwarantowane, że obie sąsiednie gałki są wolne, co eliminuje zablokowanie bez potrzeby sędziego ani ustalania kolejności gałek – jest to analogia teorii współbieżności kontroli dostępu.

Zamknięcie (Deadlock) vs. głodowanie (Starvation) vs. życie w kółko (Livelock)

Są to trzy odrębne rodzaje błędów, które warto rozróżnić. Zamknięcie (deadlock) występuje wtedy, gdy zbiór procesów trwale czeka na siebie nawzajem w cyklu – nic nie postępuje. Głodowanie to sytuacja, w której proces jest stale pozbawiany zasobu, którego potrzebuje, nawet jeśli system jako całość nadal się rozwija, np. jeśli polityka planowania zawsze faworyzuje filozofów sąsiadujących z danym filozofem. Życie w kółko (livelock) występuje wtedy, gdy procesy aktywnie zmieniają stan w odpowiedzi na siebie, ale nadal nie dokonują żadnogo realnego postępu – dwa filozofowie powtarzają czynności podnoszenia i opuszczania widelców, by być uprzejmym wobec siebie nawzajem, w nieskończoność. Poprawnie rozwiązanie problemu filozofów z jedzeniem powinno wyeliminować wszystkie trzy sytuacje, a nie tylko zamknięcie. Kolejność zasobów oraz arbitrum to właśnie to robią, ale naiwna polityka priorytetów może wyeliminować zamknięcie, jednocześnie pozwalając jednej, nieprzewidzianej sytuacji na głodowanie.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Dining Philosophers i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.