Warum fünf Essensphilosophen?

18

Ich habe mich gefragt, warum das Problem der Essensphilosophen auf einem Fall mit fünf Philosophen beruht. Warum nicht vier?

Ich denke, wir können alle unangenehmen Probleme beobachten, die auftreten können, wenn wir beispielsweise fünf Philosophen diskutieren, auch wenn wir vier Denker haben. Ist es dann nur aus einem historischen Grund?

falconepl
quelle
1
Das ursprüngliche Problem wurde 1965 von Dijkstra beschrieben und als Dining Quintuple bezeichnet (siehe Anmerkungen oben auf Seite 3).
Ich erinnere mich an vier Essphilosophen ...
Michael Borgwardt
16
Es sind 5 Philosophen, weil er versucht hat zu sehen, ob jemals jemand das Offensichtliche bemerkt; 5 Philosophen unterhalten sich, bis das Restaurant sie rauswirft, sie holen nicht einmal ihr Besteck ab. Vielleicht unterbrechen sie das Gespräch so lange, bis sie anfangen zu essen. Bei 5 ist bereits eine in der Warteschlange, die darauf wartet, unterbrochen zu werden, um die Kontinuität zu gewährleisten.
Jimmy Hoffa
1
@ Jimmy Hoffa - + 1. Und warum antwortet das nicht?
SChepurin

Antworten:

17

Laut EWD310 "Hierarchical Ordering of Sequential Processes" ( Hierarchische Reihenfolge der sequentiellen Prozesse) wurde Nummer 5 für Bildungszwecke ausgewählt, um es den Schülern zu erleichtern, Algorithmen zu verstehen, mit denen die Lösung des Problems demonstriert werden soll.

Dieser Artikel stützt ferner die Idee, dass 5 für das allgemeine Problem nicht wirklich relevant ist, indem er zum einen explizit angibt, dass das Problem für 9 oder 25 Philosophen gestellt worden sein könnte, und zum anderen, indem er es in Form von zwei gleichzeitig operierenden Problemen darstellt Entitäten, "Klasse A und Klasse B, teilen sich die gleiche Ressource ..."

Die von Dijkstra verwendete Lösung führt drei "Zustände des Philosophen" ein: Denken, Essen, Hunger. Der zur Lösung des Problems vorgestellte Code verwaltet diese drei Zustände zusammen mit einer damit nicht verbundenen Anzahl von Philosophen.

Wenn der Autor die Anzahl der Philosophen 2, 3 oder 4 gewählt hat, kann dies zu Verwirrung bei den Schülern führen, die den Code lesen, unabhängig davon, ob die gewählte Anzahl mit der Anzahl der Zustände oder etwas anderem zusammenhängt. Dies kann leicht durch Versuch genannten Zahlen in der Beschreibung von EWD310 unten angegebenen getestet werden: Anmerkung zum Beispiel , wie sich dies ändern würde [0:4]auf [0:3], [0:2], [0:1]und Aussagen , welche mod.

Im Gegensatz dazu sieht Nummer 5 ziemlich unschuldig aus und ruft keine unnötigen Assoziationen hervor. Man kann sagen, dass es gewählt wurde, um besser zu veranschaulichen, dass die Anzahl der Philosophen willkürlich ist .


Der erwähnte Algorithmus wird in EWD310 wie folgt dargestellt:

... ordnen wir jedem Philosophen eine Zustandsvariable "C" zu, sagen wir, wo

C[i] = 0bedeutet: Philosoph idenkt

C[i] = 2bedeutet: Philosoph iisst.

...

Wir führen für den letzten Übergang einen Zwischenzustand ein

C[i] = 1bedeutet: Philosoph iist hungrig

Jetzt durchläuft jeder Philosoph zyklisch die Zustände 0, 1, 2, 0 ... Die nächste zu stellende Frage lautet: Wann muss der (gefährliche) Übergang von 1 zu 2 für den Philosophen stattfinden K?

...

Im Universum nehmen wir deklariert an

1) die semaphore mutex, anfangs = 1

2) die integer array C[0:4], mit anfangs allen element = 0

3) das semaphore array prisem[0:4]mit anfangs allen Elementen = 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;

(Diese Prozedur, die die Instabilität behebt, falls Kvorhanden, wird nur innerhalb eines kritischen Abschnitts aufgerufen.)

In diesem Universum kann das Leben des Philosophen wjetzt kodiert werden

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

Und das schließt die Lösung, die ich anstrebte ...

Mücke
quelle
2
Vielleicht bin ich dann kein Philosoph, weil ich gleichzeitig denken kann, wenn ich esse oder hungrig bin. Und mehr noch: keiner von ihnen trinkt oder redet.
ott--
5

Nur Dijkstra kann mit Sicherheit antworten, aber ich wäre zuversichtlich, dass es willkürlich ist.

"Es wurde ursprünglich 1965 von Edsger Dijkstra als Übung für eine Schülerprüfung formuliert, die sich mit Computern befasste, die um den Zugriff auf Bandlaufwerksperipheriegeräte konkurrierten. Kurz darauf gab Tony Hoare dem Problem seine derzeitige Formulierung."

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

Eoin Carroll
quelle
2
Betrachten Sie das Problem der vier Gäste im Vergleich zu fünf. Wie ändert sich das Problem? Ist es einfacher oder schwieriger? Dies war eine Prüfungsfrage - die schwierigere ist wahrscheinlich die, die gestellt werden soll.
2

Weil es seltsam ist, nicht gerade. Damit Sie nicht versuchen, einen Algorithmus zu entwickeln, der auf Symmetrie oder Paarbildung beruht, und erst viel später feststellen, dass er für den allgemeinen Fall nicht funktioniert.

Dies ist eine Meinung; Ich habe keine historischen Kenntnisse darüber, was dem Autor in den Sinn gekommen ist.

Emilio M Bumachar
quelle
Dieser Punkt ist entscheidend. Mit vier Philosophen konnten zwei Paare abwechselnd essen.
Aaron Brick