Dlaczego pięciu filozofów kulinarnych?

18

Zastanawiałem się, dlaczego problem filozofów kulinarnych jest oparty na przypadku pięciu filozofów. Dlaczego nie cztery?

Wydaje mi się, że możemy obserwować wszystkie nieprzyjemne problemy, które mogą wystąpić podczas omawiania przykładu pięciu filozofów, także gdy mamy czterech myślicieli. Czy to tylko z powodów historycznych?

falconepl
źródło
1
Pierwotny problem został opisany przez Dijkstrę w 1965 roku i nazywał się Quintuple do jadalni (znaleziony w notatkach na górze strony 3).
Wydaje mi się, że pamiętam naukę czterech filozofów kulinarnych ...
Michael Borgwardt
16
To 5 filozofów, ponieważ próbował sprawdzić, czy ktokolwiek kiedykolwiek zauważy oczywistość; 5 filozofów będzie rozmawiać, dopóki restauracja ich nie wyrzuci, nigdy nawet nie podniosą srebrnego naczynia. 4 może mieć przerwę w rozmowie na tyle długo, aby mogli zacząć jeść. Przy 5, gdy tylko dwa zatrzymają się na chwilę, już jeden w kolejce czeka na interwencję, aby zapewnić ciągłość.
Jimmy Hoffa
1
@Jimmy Hoffa - + 1. A dlaczego to nie jest odpowiedź?
SChepurin

Odpowiedzi:

17

Zgodnie z tym, co napisano w EWD310 „Hierarchiczne porządkowanie procesów sekwencyjnych” , wygląda na to, że numer 5 został wybrany do celów edukacyjnych, aby ułatwić uczniom zrozumienie algorytmu zaprojektowanego w celu zademonstrowania rozwiązania problemu.

Ten sam artykuł dodatkowo popiera ideę, że 5 nie jest tak naprawdę istotny dla ogólnego problemu, po pierwsze, wyraźnie stwierdzając, że „problem mógł zostać postawiony dla 9 lub 25 filozofów ...”, a następnie, reprezentując go w kategoriach dwóch jednocześnie działających podmioty „klasy A i klasy B dzielące ten sam zasób ...”

Rozwiązanie zastosowane przez Dijkstrę wprowadza trzy „stany filozofa”: myślenie, jedzenie, głód. Kod przedstawiony w celu rozwiązania problemu obsługuje te trzy stany wraz z niepowiązaną z nim liczbą filozofów.

Gdyby autor wybrał liczbę filozofów 2, 3 lub 4, mogłoby to spowodować zamieszanie uczniów czytających kod, niezależnie od tego, czy wybrana liczba jest związana z ilością stanów, czy czymś innym. To może być łatwo testowane przez próby wymienione w opisie podane numery od EWD310 poniżej: uwaga na przykład jak by to zmienić [0:4], aby [0:3], [0:2], [0:1]i oświadczenia udziałem mod.

W przeciwieństwie do tego, numer 5 wygląda dość niewinnie i nie wywołuje niepotrzebnych skojarzeń. Można powiedzieć, że wybrano to, aby lepiej zilustrować, że liczba filozofów jest, cóż, arbitralna .


Wspomniany algorytm przedstawiono w EWD310 w następujący sposób:

... kojarzymy z każdym filozofem zmienną stanu, powiedzmy „C”, gdzie

C[i] = 0oznacza: filozof imyśli

C[i] = 2oznacza: filozof ije.

...

dla ostatniego przejścia wprowadzamy stan pośredni

C[i] = 1oznacza: filozof ijest głodny

Teraz każdy filozof będzie cyklicznie przechodził przez stany 0, 1, 2, 0 ...... Następnym pytaniem jest: kiedy (niebezpieczne) przejście od 1 do 2 nastąpi dla filozofa K?

...

We wszechświecie zakładamy, że jest zadeklarowany

1) semaphore mutexpoczątkowo = 1

2) integer array C[0:4]początkowo wszystkie elementy = 0

3) semaphore array prisem[0:4]z początkowo wszystkimi elementami = 0

4) procedure test (integer value K);

if C[(K-1) mod 5] ≠ 2 and C[K]= 1
    and C[(K+1) mod 5] ≠ 2 do
      begin C[K]:= 2; V(prisem[K]) end;

(Ta procedura, która rozwiązuje niestabilność, Kgdy jest obecna, będzie wywoływana tylko z sekcji krytycznej).

W tym wszechświecie wmożna teraz zakodować życie filozofa

cycle begin think;
            P (mutex);
               C[w]:= 1; test (w);
            V(mutex);
            P(prisem[w]); eat
            P(mutex);
               C[w]:= 0; test [(w+l) mod 5];
               test [(w-1) mod 5];
            V(mutex)
      end

I na tym kończy się rozwiązanie, do którego dążyłem ...

komar
źródło
2
Może nie jestem wtedy filozofem, ponieważ mogę jednocześnie myśleć, jedząc lub będąc głodnym. I jeszcze więcej: żaden z nich nie pije ani nawet nie mówi.
ott--
5

Tylko Dijkstra może na pewno odpowiedzieć, ale byłbym pewien, że jest to arbitralne.

„Został on pierwotnie sformułowany w 1965 roku przez Edsger Dijkstra jako ćwiczenie egzaminacyjne dla studentów, przedstawione w kategoriach komputerów konkurujących o dostęp do urządzeń peryferyjnych napędu taśmowego. Wkrótce potem Tony Hoare podał problemowi swoją obecną formułę”.

http://en.wikipedia.org/wiki/Dining_philosophers_problem

Eoin Carroll
źródło
2
Rozważ problem czterech gości w porównaniu do pięciu. Jak zmienia się problem? Czy to jest łatwiejsze czy trudniejsze? To było pytanie egzaminacyjne - trudniejsze jest prawdopodobnie pytanie, które należy zadać.
2

Bo to dziwne, nawet nie. Abyś nie próbował opracować algorytmu, który opiera się na symetrii lub tworzeniu par, i dopiero znacznie później zdajesz sobie sprawę, że to nie działa w ogólnym przypadku.

To jest opinia; Nie mam historycznej wiedzy o tym, co przyszło na myśl autorowi.

Emilio M. Bumachar
źródło
Ten punkt jest kluczowy. Dzięki czterem filozofom dwie pary mogły na zmianę jeść.
Aaron Brick