Das Problem des Essensphilosophen ist das klassische Problem der Synchronisation, das besagt, dass fünf Philosophen an einem runden Tisch sitzen und ihre Aufgabe darin besteht, abwechselnd zu denken und zu essen. Eine Schüssel Nudeln wird in die Mitte des Tisches gestellt, zusammen mit fünf Essstäbchen für jeden Philosophen. Um zu essen, braucht ein Philosoph sowohl sein rechtes als auch sein linkes Essstäbchen. Ein Philosoph kann nur dann essen, wenn sowohl das linke als auch das rechte Stäbchen des Philosophen verfügbar sind. Falls nicht sowohl das linke als auch das rechte Essstäbchen des Philosophen unmittelbar verfügbar sind, legt der Philosoph sein (entweder linkes oder rechtes) Essstäbchen weg und beginnt erneut zu denken.
Der Speisephilosoph demonstriert eine große Klasse von Problemen bei der Parallelitätskontrolle, daher handelt es sich um ein klassisches Synchronisationsproblem.
Fünf Philosophen sitzen am Tisch
Problem der Essphilosophen - Lassen Sie uns das Dining Philosophers-Problem mit dem folgenden Code verstehen. Wir haben Abb. 1 als Referenz verwendet, damit Sie das Problem genau verstehen. Die fünf Philosophen werden durch P0, P1, P2, P3 und P4 und die fünf Essstäbchen durch C0, C1, C2, C3 und C4 dargestellt.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Lassen Sie uns den obigen Code besprechen:
Angenommen, Philosoph P0 möchte essen, er wird die Funktion Philosopher() eingeben und ausführen take_chopstick[i]; dadurch gilt es C0-Essstäbchen Danach wird es ausgeführt take_chopstick[ (i+1) % 5]; dadurch gilt es C1-Essstäbchen (da i =0, also (0 + 1) % 5 = 1)
Negation diskrete Mathematik
Angenommen, Philosoph P1 möchte nun etwas essen, er wird die Funktion Philosopher() aufrufen und ausführen take_chopstick[i]; dadurch gilt es C1-Essstäbchen Danach wird es ausgeführt take_chopstick[ (i+1) % 5]; dadurch gilt es C2-Essstäbchen (da i =1, also (1 + 1) % 5 = 2)
Aber praktisch ist Chopstick C1 nicht verfügbar, da es bereits vom Philosophen P0 übernommen wurde, weshalb der obige Code Probleme erzeugt und eine Rennbedingung erzeugt.
Karte im Typoskript
Die Lösung des Problems der Essphilosophen
Wir verwenden ein Semaphor, um ein Essstäbchen darzustellen, und dies ist tatsächlich eine Lösung des Problems der Speisephilosophen. Zur Lösung des Dining Philosophers-Problems werden Warte- und Signaloperationen verwendet. Zum Auswählen eines Essstäbchens kann eine Warteoperation ausgeführt werden, während zum Loslassen eines Essstäbchensignals ein Semaphor ausgeführt werden kann.
Semaphor: Ein Semaphor ist eine ganzzahlige Variable in S, auf die abgesehen von der Initialisierung nur durch zwei standardmäßige atomare Operationen zugegriffen wird – Warten und Signal, deren Definitionen wie folgt lauten:
1. wait( S ) { while( S <= 0) ; s--; } 2. signal( s ) { s++; < pre> <p>From the above definitions of wait, it is clear that if the value of S <= 0 then it will enter into an infinite loop(because of the semicolon; after while loop). whereas job signal is to increment value s.< p> <p>The structure of the chopstick is an array of a semaphore which is represented as shown below -</p> <pre> semaphore C[5]; </pre> <p>Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized to 1 as the chopsticks are on the table and not picked up by any of the philosophers.</p> <p>Let's modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal, the desired code looks like</p> <pre> void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } </pre> <p>In the above code, first wait operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows philosopher i have picked up the chopsticks from its left and right. The eating function is performed after that.</p> <p>On completion of eating by philosopher i the, signal operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows that the philosopher i have eaten and put down both the left and right chopsticks. Finally, the philosopher starts thinking again.</p> <h3>Let's understand how the above code is giving a solution to the dining philosopher problem?</h3> <p>Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C0 chopstick</strong> and reduces semaphore C0 to 0 <strong>,</strong> after that it execute <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C1 chopstick</strong> ( since i =0, therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0</p> <p>Similarly, suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it will try to hold <strong>C1 chopstick</strong> but will not be able to do that <strong>,</strong> since the value of semaphore C1 has already been set to 0 by philosopher P0, therefore it will enter into an infinite loop because of which philosopher P1 will not be able to pick chopstick C1 whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C2 chopstick</strong> and reduces semaphore C2 to 0, after that, it executes <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C3 chopstick</strong> ( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0.</p> <p>Hence the above code is providing a solution to the dining philosopher problem, A philosopher can only eat if both immediate left and right chopsticks of the philosopher are available else philosopher needs to wait. Also at one go two independent philosophers can eat simultaneously (i.e., philosopher <strong>P0 and P2, P1 and P3 & P2 and P4</strong> can eat simultaneously as all are the independent processes and they are following the above constraint of dining philosopher problem)</p> <h3>The drawback of the above solution of the dining philosopher problem</h3> <p>From the above solution of the dining philosopher problem, we have proved that no two neighboring philosophers can eat at the same point in time. The drawback of the above solution is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time, which leads to the condition of deadlock and none of the philosophers can eat.</p> <p>To avoid deadlock, some of the solutions are as follows -</p> <ul> <li>Maximum number of philosophers on the table should not be more than four, in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat.</li> <li>A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.</li> <li>Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks</li> <li>All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.</li> </ul> <p>The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock state of a system is a state in which no progress of system is possible. Consider a proposal where each philosopher is instructed to behave as follows:</p> <ul> <li>The philosopher is instructed to think till the left fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to think till the right fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to eat when both forks are available.</li> <li>then, put the right fork down first</li> <li>then, put the left fork down next</li> <li>repeat from the beginning.</li> </ul> <hr></=></p></=> Zunächst wird jedes Element des Semaphors C0, C1, C2, C3 und C4 auf 1 initialisiert, da die Stäbchen auf dem Tisch liegen und von keinem der Philosophen in die Hand genommen werden.
Ändern wir den obigen Code des Dining Philosopher Problems, indem wir die Semaphoroperationen „wait“ und „signal“ verwenden, so sieht der gewünschte Code aus
void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } Im obigen Code wird die erste Warteoperation für take_chopstickC[i] und take_chopstickC [ (i+1) % 5] ausgeführt. Das zeigt, dass ich die Stäbchen von links und rechts aufgenommen habe. Danach wird die Essfunktion ausgeführt.
Nach Abschluss des Essens durch Philosoph i wird die Signaloperation an take_chopstickC[i] und take_chopstickC [(i+1) % 5] ausgeführt. Dies zeigt, dass der Philosoph, den ich gegessen habe, sowohl das linke als auch das rechte Stäbchen weggelegt hat. Schließlich beginnt der Philosoph erneut nachzudenken.
Lassen Sie uns verstehen, wie der obige Code eine Lösung für das Problem des Essensphilosophen bietet.
Sei der Wert von i = 0 (Anfangswert). Angenommen, Philosoph P0 möchte essen, er wird in die Funktion Philosopher() eingegeben und ausgeführt Wait( take_chopstickC[i] ); dadurch gilt es C0-Essstäbchen und reduziert Semaphor C0 auf 0 , Danach wird es ausgeführt Wait( take_chopstickC[(i+1) % 5] ); dadurch gilt es C1-Essstäbchen (da i =0, also (0 + 1) % 5 = 1) und reduziert Semaphor C1 auf 0
So initialisieren Sie ein Array in Java
Angenommen, Philosoph P1 möchte nun etwas essen, er wird die Funktion Philosopher() aufrufen und ausführen Wait( take_chopstickC[i] ); Dadurch wird es versuchen zu halten C1-Essstäbchen aber das werde ich nicht schaffen , Da der Wert des Semaphors C1 bereits vom Philosophen P0 auf 0 gesetzt wurde, gerät er in eine Endlosschleife, wodurch Philosoph P1 nicht in der Lage sein wird, das Essstäbchen C1 auszuwählen, wohingegen Philosoph P2, wenn er essen möchte, in Philosopher eintreten wird ()-Funktion ausführen und ausführen Wait( take_chopstickC[i] ); dadurch gilt es C2-Essstäbchen und reduziert Semaphor C2 auf 0, danach wird es ausgeführt Wait( take_chopstickC[(i+1) % 5] ); dadurch gilt es C3-Essstäbchen (da i =2, also (2 + 1) % 5 = 3) und reduziert Semaphor C3 auf 0.
Daher bietet der obige Code eine Lösung für das Problem des Essensphilosophen. Ein Philosoph kann nur essen, wenn sowohl die linken als auch die rechten Essstäbchen des Philosophen unmittelbar verfügbar sind, andernfalls muss der Philosoph warten. Auch können gleichzeitig zwei unabhängige Philosophen gleichzeitig essen (d. h. Philosoph P0 und P2, P1 und P3 & P2 und P4 kann gleichzeitig essen, da es sich bei allen um unabhängige Prozesse handelt und sie der oben genannten Einschränkung des Essphilosophenproblems folgen)
Der Nachteil der oben genannten Lösung des Speisephilosophenproblems
Mit der obigen Lösung des Essensphilosophenproblems haben wir bewiesen, dass keine zwei benachbarten Philosophen gleichzeitig essen können. Der Nachteil der oben genannten Lösung besteht darin, dass diese Lösung zu einem Deadlock-Zustand führen kann. Diese Situation tritt auf, wenn alle Philosophen gleichzeitig ihr linkes Essstäbchen auswählen, was zu einem Stillstand führt und keiner der Philosophen essen kann.
Um einen Deadlock zu vermeiden, gibt es einige Lösungen wie folgt:
- Die maximale Anzahl der Philosophen auf dem Tisch sollte nicht mehr als vier betragen. In diesem Fall steht das Essstäbchen C4 für den Philosophen P3 zur Verfügung, sodass P3 mit dem Essen beginnt und nach Abschluss seines Essvorgangs seine beiden Essstäbchen C3 ablegen wird und C4, d. h. die Semaphoren C3 und C4 werden nun auf 1 erhöht. Nun steht dem Philosophen P2, der das Essstäbchen C2 hielt, auch das Essstäbchen C3 zur Verfügung, sodass er in ähnlicher Weise nach dem Essen sein Essstäbchen weglegen und anderen Philosophen das Essen ermöglichen wird.
- Ein Philosoph an einer geraden Position sollte das rechte Essstäbchen und dann das linke Essstäbchen auswählen, während ein Philosoph an einer ungeraden Position das linke Essstäbchen und dann das rechte Essstäbchen auswählen sollte.
- Nur wenn beide Stäbchen (links und rechts) gleichzeitig verfügbar sind, darf ein Philosoph nur dann seine Stäbchen auswählen
- Alle vier Startphilosophen (P0, P1, P2 und P3) sollten das linke und dann das rechte Essstäbchen auswählen, während der letzte Philosoph P4 das rechte und dann das linke Essstäbchen auswählen sollte. Dadurch wird P4 gezwungen, zuerst sein rechtes Essstäbchen zu halten, da das rechte Essstäbchen von P4 C0 ist, das bereits vom Philosophen P0 gehalten wird und dessen Wert auf 0 gesetzt ist, d. h. C0 ist bereits 0, wodurch P4 im Unendlichen gefangen wird Schleife und Stäbchen C4 bleiben frei. Daher hat Philosoph P3 sowohl das linke C3- als auch das rechte C4-Essstäbchen zur Verfügung, daher beginnt er mit dem Essen und legt beide Essstäbchen weg, sobald es fertig ist, und lässt andere essen, was das Problem des Stillstands beseitigt.
Der Entwurf des Problems bestand darin, die Herausforderungen bei der Vermeidung von Deadlocks zu veranschaulichen. Ein Deadlock-Zustand eines Systems ist ein Zustand, in dem kein Fortschritt des Systems möglich ist. Stellen Sie sich einen Vorschlag vor, bei dem jeder Philosoph angewiesen wird, sich wie folgt zu verhalten:
- Der Philosoph wird angewiesen, so lange zu denken, bis die linke Gabelung verfügbar ist. Wenn sie verfügbar ist, halten Sie sie fest.
- Der Philosoph wird angewiesen, so lange zu denken, bis die richtige Gabelung verfügbar ist. Wenn sie verfügbar ist, halten Sie sie fest.
- Der Philosoph wird angewiesen zu essen, wenn beide Gabeln verfügbar sind.
- Setzen Sie dann zuerst die rechte Gabel ab
- Dann legen Sie als nächstes die linke Gabel nach unten
- von Anfang an wiederholen.