Das Problem der Essphilosophen in Java

1. Einleitung

Das Dining Philosophers-Problem ist eines der klassischen Probleme, mit denen Synchronisationsprobleme in einer Umgebung mit mehreren Threads beschrieben und Techniken zu ihrer Lösung veranschaulicht werden . Dijkstra formulierte dieses Problem zunächst und stellte es in Bezug auf Computer vor, die auf Peripheriegeräte für Bandlaufwerke zugreifen.

Die vorliegende Formulierung wurde von Tony Hoare gegeben, der auch dafür bekannt ist, den Quicksort-Sortieralgorithmus zu erfinden. In diesem Artikel analysieren wir dieses bekannte Problem und codieren eine beliebte Lösung.

2. Das Problem

Das obige Diagramm zeigt das Problem. An einem runden Tisch sitzen fünf stille Philosophen (P1 - P5), die ihr Leben mit Essen und Denken verbringen.

Es gibt fünf Gabeln, die sie teilen können (1 - 5), und um essen zu können, muss ein Philosoph Gabeln in beiden Händen haben. Nach dem Essen legt er beide ab und dann können sie von einem anderen Philosophen ausgewählt werden, der denselben Zyklus wiederholt.

Das Ziel ist es, ein Schema / Protokoll zu entwickeln, das den Philosophen hilft, ihr Ziel zu erreichen, zu essen und zu denken, ohne zu verhungern.

3. Eine Lösung

Eine erste Lösung wäre, jeden der Philosophen dazu zu bringen, das folgende Protokoll zu befolgen:

while(true) { // Initially, thinking about life, universe, and everything think(); // Take a break from thinking, hungry now pick_up_left_fork(); pick_up_right_fork(); eat(); put_down_right_fork(); put_down_left_fork(); // Not hungry anymore. Back to thinking! } 

Wie der obige Pseudocode beschreibt, denkt jeder Philosoph zunächst. Nach einer gewissen Zeit bekommt der Philosoph Hunger und möchte essen.

An diesem Punkt greift er nach den Gabeln auf beiden Seiten und fährt mit dem Essen fort, sobald er beide hat . Sobald das Essen fertig ist, legt der Philosoph die Gabeln ab, damit sie für seinen Nachbarn verfügbar sind.

4. Implementierung

Wir modellieren jeden unserer Philosophen als Klassen, die die Runnable- Schnittstelle implementieren , damit wir sie als separate Threads ausführen können. Jeder Philosoph hat Zugang zu zwei Gabeln auf seiner linken und rechten Seite:

public class Philosopher implements Runnable { // The forks on either side of this Philosopher private Object leftFork; private Object rightFork; public Philosopher(Object leftFork, Object rightFork) { this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run() { // Yet to populate this method } }

Wir haben auch eine Methode, die einen Philosophen anweist , eine Aktion auszuführen - essen, denken oder Gabeln erwerben, um sich auf das Essen vorzubereiten:

public class Philosopher implements Runnable { // Member variables, standard constructor private void doAction(String action) throws InterruptedException { System.out.println( Thread.currentThread().getName() + " " + action); Thread.sleep(((int) (Math.random() * 100))); } // Rest of the methods written earlier }

Wie im obigen Code gezeigt, wird jede Aktion simuliert, indem der aufrufende Thread für eine zufällige Zeitspanne angehalten wird, sodass die Ausführungsreihenfolge nicht allein durch die Zeit erzwungen wird.

Lassen Sie uns nun die Kernlogik eines Philosophen implementieren .

Um den Erwerb einer Gabel zu simulieren, müssen wir sie sperren, damit keine zwei Philosophen- Threads sie gleichzeitig erwerben.

Um dies zu erreichen, verwenden wir das synchronisierte Schlüsselwort, um den internen Monitor des Fork-Objekts abzurufen und zu verhindern, dass andere Threads dasselbe tun. Eine Anleitung zum synchronisierten Schlüsselwort in Java finden Sie hier. Wir implementieren nun die run () -Methode in der Philosopher- Klasse:

public class Philosopher implements Runnable { // Member variables, methods defined earlier @Override public void run() { try { while (true) { // thinking doAction(System.nanoTime() + ": Thinking"); synchronized (leftFork) { doAction( System.nanoTime() + ": Picked up left fork"); synchronized (rightFork) { // eating doAction( System.nanoTime() + ": Picked up right fork - eating"); doAction( System.nanoTime() + ": Put down right fork"); } // Back to thinking doAction( System.nanoTime() + ": Put down left fork. Back to thinking"); } } } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } } 

Dieses Schema implementiert genau das zuvor beschriebene: Ein Philosoph denkt eine Weile nach und beschließt dann zu essen.

Danach erwirbt er die Gabeln links und rechts und beginnt zu essen. Wenn er fertig ist, legt er die Gabeln ab. Außerdem fügen wir jeder Aktion Zeitstempel hinzu, um die Reihenfolge zu verstehen, in der Ereignisse auftreten.

Um den gesamten Prozess zu starten, schreiben wir einen Client, der 5 Philosophen als Threads erstellt und alle startet:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; philosophers[i] = new Philosopher(leftFork, rightFork); Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } }

Wir modellieren jede der Gabeln als generische Java-Objekte und stellen so viele davon her, wie es Philosophen gibt. Wir übergeben jedem Philosophen seine linken und rechten Gabeln, die er mit dem synchronisierten Schlüsselwort zu sperren versucht .

Das Ausführen dieses Codes führt zu einer Ausgabe ähnlich der folgenden. Ihre Ausgabe unterscheidet sich höchstwahrscheinlich von der unten angegebenen, hauptsächlich weil die sleep () -Methode für ein anderes Intervall aufgerufen wird:

Philosopher 1 8038014601251: Thinking Philosopher 2 8038014828862: Thinking Philosopher 3 8038015066722: Thinking Philosopher 4 8038015284511: Thinking Philosopher 5 8038015468564: Thinking Philosopher 1 8038016857288: Picked up left fork Philosopher 1 8038022332758: Picked up right fork - eating Philosopher 3 8038028886069: Picked up left fork Philosopher 4 8038063952219: Picked up left fork Philosopher 1 8038067505168: Put down right fork Philosopher 2 8038089505264: Picked up left fork Philosopher 1 8038089505264: Put down left fork. Back to thinking Philosopher 5 8038111040317: Picked up left fork

Alle Philosophen fangen anfangs an zu denken, und wir sehen, dass Philosoph 1 die linke und rechte Gabel aufnimmt, dann beide isst und sie ablegt, wonach "Philosoph 5" sie aufnimmt.

5. Das Problem mit der Lösung: Deadlock

Obwohl es so aussieht, als ob die obige Lösung korrekt ist, tritt ein Deadlock auf.

Ein Deadlock ist eine Situation, in der der Fortschritt eines Systems angehalten wird, während jeder Prozess darauf wartet, eine Ressource zu erhalten, die von einem anderen Prozess gehalten wird.

Wir können dasselbe bestätigen, indem wir den obigen Code einige Male ausführen und überprüfen, ob der Code manchmal nur hängt. Hier ist eine Beispielausgabe, die das oben genannte Problem demonstriert:

Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: Picked up left fork Philosopher 1 8487596641267: Picked up left fork Philosopher 5 8487597646086: Picked up left fork Philosopher 4 8487617680958: Picked up left fork Philosopher 2 8487631148853: Picked up left fork

In dieser Situation hat jeder Philosoph seine linke Gabel erworben, kann aber seine rechte Gabel nicht erwerben, da sein Nachbar sie bereits erworben hat. Diese Situation wird allgemein als zirkuläres Warten bezeichnet und ist eine der Bedingungen, die zu einem Deadlock führen und den Fortschritt des Systems verhindern.

6. Beheben des Deadlocks

Wie wir oben gesehen haben, ist der Hauptgrund für einen Deadlock die zirkuläre Wartebedingung, bei der jeder Prozess auf eine Ressource wartet, die von einem anderen Prozess gehalten wird. Um eine Deadlock-Situation zu vermeiden, müssen wir daher sicherstellen, dass die zirkuläre Wartebedingung nicht erfüllt ist. Es gibt verschiedene Möglichkeiten, dies zu erreichen. Die einfachste ist die folgende:

Alle Philosophen greifen zuerst nach ihrer linken Gabel, außer einer, der zuerst nach seiner rechten Gabel greift.

Wir implementieren dies in unseren vorhandenen Code, indem wir eine relativ geringfügige Änderung am Code vornehmen:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { final Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; if (i == philosophers.length - 1) { // The last philosopher picks up the right fork first philosophers[i] = new Philosopher(rightFork, leftFork); } else { philosophers[i] = new Philosopher(leftFork, rightFork); } Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } } 

Die Änderung erfolgt in den Zeilen 17 bis 19 des obigen Codes, in denen wir die Bedingung einführen, dass der letzte Philosoph zuerst nach seiner rechten Gabel greift und nicht nach der linken. Dies unterbricht die zirkuläre Wartebedingung und wir können den Deadlock verhindern.

Die folgende Ausgabe zeigt einen der Fälle, in denen alle Philosophen die Möglichkeit haben, nachzudenken und zu essen, ohne einen Stillstand zu verursachen:

Philosopher 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosopher 3 88519864404195: Picked up left fork Philosopher 5 88519871990082: Picked up left fork Philosopher 4 88519874059504: Picked up left fork Philosopher 5 88519876989405: Picked up right fork - eating Philosopher 2 88519935045524: Picked up left fork Philosopher 5 88519951109805: Put down right fork Philosopher 4 88519997119634: Picked up right fork - eating Philosopher 5 88519997113229: Put down left fork. Back to thinking Philosopher 5 88520011135846: Thinking Philosopher 1 88520011129013: Picked up left fork Philosopher 4 88520028194269: Put down right fork Philosopher 4 88520057160194: Put down left fork. Back to thinking Philosopher 3 88520067162257: Picked up right fork - eating Philosopher 4 88520067158414: Thinking Philosopher 3 88520160247801: Put down right fork Philosopher 4 88520249049308: Picked up left fork Philosopher 3 88520249119769: Put down left fork. Back to thinking 

Durch mehrmaliges Ausführen des Codes kann überprüft werden, ob das System frei von der zuvor aufgetretenen Deadlock-Situation ist.

7. Fazit

In diesem Artikel haben wir das berühmte Problem der Dining Philosophers und die Konzepte des zirkulären Wartens und Stillstands untersucht . Wir haben eine einfache Lösung codiert, die einen Deadlock verursacht hat, und eine einfache Änderung vorgenommen, um das zirkuläre Warten zu unterbrechen und einen Deadlock zu vermeiden. Dies ist nur ein Anfang, und es gibt anspruchsvollere Lösungen.

Den Code für diesen Artikel finden Sie auf GitHub.