Het probleem van de eetfilosoof is het klassieke synchronisatieprobleem, dat zegt dat vijf filosofen rond een ronde tafel zitten en het hun taak is om afwisselend te denken en te eten. Voor elk van de filosofen wordt een kom noedels in het midden van de tafel geplaatst, samen met vijf eetstokjes. Om te eten heeft een filosoof zowel zijn rechter als zijn linker eetstokje nodig. Een filosoof kan alleen eten als zowel de directe linker- als de rechter eetstokjes van de filosoof beschikbaar zijn. In het geval dat zowel de onmiddellijke linker als de rechter eetstokjes van de filosoof niet beschikbaar zijn, legt de filosoof zijn (linker of rechter) eetstokje neer en begint opnieuw na te denken.
De eetfilosoof demonstreert een grote groep gelijktijdigheidscontroleproblemen en is daarom een klassiek synchronisatieprobleem.
Vijf filosofen zitten rond de tafel
Eetfilosofen Probleem - Laten we het probleem van de eetfilosofen met de onderstaande code begrijpen. We hebben figuur 1 als referentie gebruikt om u het probleem precies te laten begrijpen. De vijf filosofen worden weergegeven als P0, P1, P2, P3 en P4 en de vijf eetstokjes als C0, C1, C2, C3 en C4.
generieke Java-geneesmiddelen
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Laten we de bovenstaande code bespreken:
Stel dat Filosoof P0 wil eten, dan zal hij de functie Filosoof() invoeren en uitvoeren take_chopstick[i]; door dit te doen blijft het bestaan C0 eetstokje daarna wordt het uitgevoerd neem eetstokje[ (i+1) % 5]; door dit te doen blijft het bestaan C1 eetstokje ( aangezien i =0, dus (0 + 1) % 5 = 1)
Stel dat Filosoof P1 nu wil eten, dan zal hij de functie Filosoof() invoeren en uitvoeren take_chopstick[i]; door dit te doen blijft het bestaan C1 eetstokje daarna wordt het uitgevoerd neem eetstokje[ (i+1) % 5]; door dit te doen blijft het bestaan C2 eetstokje ( aangezien i =1, dus (1 + 1) % 5 = 2)
Maar praktisch gezien is Chopstick C1 niet beschikbaar omdat deze al is gebruikt door filosoof P0, vandaar dat de bovenstaande code problemen genereert en een raceconditie veroorzaakt.
Linux-host
De oplossing van het probleem van de eetfilosofen
We gebruiken een seinpaal om een eetstokje voor te stellen en dit fungeert echt als een oplossing voor het probleem van de eetfilosofen. Wacht- en signaaloperaties zullen worden gebruikt voor de oplossing van het Dining Philosophers-probleem. Voor het kiezen van een eetstokje kan een wachtoperatie worden uitgevoerd, terwijl voor het loslaten van een eetstokje-signaal een semafoor kan worden uitgevoerd.
Semafoor: Een semafoor is een geheel getalvariabele in S, die, afgezien van initialisatie, toegankelijk is via slechts twee standaard atomaire bewerkingen: wachten en signaleren, waarvan de definities als volgt zijn:
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></=> Aanvankelijk wordt elk element van de semafoor C0, C1, C2, C3 en C4 geïnitialiseerd op 1, aangezien de eetstokjes op tafel liggen en door geen van de filosofen worden opgepakt.
Laten we de bovenstaande code van het Dining Philosopher-probleem aanpassen door gebruik te maken van semafoorbewerkingen, wait and signal, de gewenste code ziet er als volgt uit
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 } } In de bovenstaande code wordt de eerste wachtbewerking uitgevoerd op take_chopstickC[i] en take_chopstickC [(i+1) % 5]. Dit laat de filosoof zien dat ik de eetstokjes links en rechts heb opgepakt. Daarna wordt de eetfunctie uitgevoerd.
bouwer ontwerppatroon
Na voltooiing van het eten door filosoof i wordt de signaalbewerking uitgevoerd op take_chopstickC[i] en take_chopstickC [(i+1) % 5]. Hieruit blijkt dat de filosoof ik heb gegeten en zowel de linker als de rechter eetstokjes heb neergelegd. Eindelijk begint de filosoof weer na te denken.
Laten we eens kijken hoe de bovenstaande code een oplossing biedt voor het probleem van de eetfilosoof?
Stel dat de waarde van i = 0(beginwaarde), stel dat Filosoof P0 wil eten, dan zal hij de functie Filosoof() invoeren en uitvoeren Wacht( take_chopstickC[i] ); door dit te doen blijft het bestaan C0 eetstokje en reduceert semafoor C0 tot 0 , daarna wordt het uitgevoerd Wacht( take_chopstickC[(i+1) % 5] ); door dit te doen blijft het bestaan C1 eetstokje ( aangezien i =0, dus (0 + 1) % 5 = 1) en reduceert semafoor C1 tot 0
Stel dat Filosoof P1 nu wil eten, dan zal hij de functie Filosoof() invoeren en uitvoeren Wacht( take_chopstickC[i] ); Door dit te doen zal het proberen vast te houden C1 eetstokje maar dat zal niet lukken , aangezien de waarde van semafoor C1 al door filosoof P0 op 0 is ingesteld, zal deze in een oneindige lus terechtkomen waardoor filosoof P1 eetstokje C1 niet kan kiezen, terwijl als filosoof P2 wil eten, hij in Filosoof terechtkomt () functie en uitvoeren Wacht( take_chopstickC[i] ); door dit te doen blijft het bestaan C2 eetstokje en reduceert semafoor C2 naar 0, daarna wordt het uitgevoerd Wacht( take_chopstickC[(i+1) % 5] ); door dit te doen blijft het bestaan C3 eetstokje (aangezien i =2, dus (2 + 1) % 5 = 3) en reduceert semafoor C3 tot 0.
Daarom biedt de bovenstaande code een oplossing voor het probleem van de eetfilosoof. Een filosoof kan alleen eten als zowel de onmiddellijke linker- als de rechter eetstokjes van de filosoof beschikbaar zijn, anders moet de filosoof wachten. Ook kunnen in één keer twee onafhankelijke filosofen tegelijkertijd eten (d.w.z. filosoof P0 en P2, P1 en P3 & P2 en P4 kunnen tegelijkertijd eten, omdat het allemaal onafhankelijke processen zijn en ze de bovenstaande beperking van het eetfilosoofprobleem volgen)
np.random.rand
Het nadeel van de bovenstaande oplossing van het eetfilosoofprobleem
Met de bovenstaande oplossing van het eetfilosoofprobleem hebben we bewezen dat geen twee naburige filosofen op hetzelfde tijdstip kunnen eten. Het nadeel van bovenstaande oplossing is dat deze oplossing tot een impasse kan leiden. Deze situatie doet zich voor als alle filosofen tegelijkertijd hun linker eetstokje pakken, wat leidt tot een impasse en geen van de filosofen kan eten.
Om een impasse te voorkomen, zijn enkele oplossingen als volgt:
- Het maximale aantal filosofen op tafel mag niet meer dan vier zijn. In dit geval zal eetstokje C4 beschikbaar zijn voor filosoof P3, dus P3 zal beginnen met eten en na het einde van zijn eetprocedure zal hij zijn beide eetstokjes C3 neerleggen. en C4, d.w.z. semafoor C3 en C4 worden nu verhoogd naar 1. Nu zal filosoof P2, die eetstokje C2 vasthield, ook eetstokje C3 beschikbaar hebben, dus op dezelfde manier zal hij zijn eetstokje neerleggen na het eten en andere filosofen in staat stellen te eten.
- Een filosoof op een even positie moet het rechter eetstokje en vervolgens het linker eetstokje kiezen, terwijl een filosoof op een oneven positie het linker eetstokje en vervolgens het rechter eetstokje moet kiezen.
- Alleen als beide eetstokjes (links en rechts) tegelijkertijd beschikbaar zijn, alleen dan zou een filosoof zijn eetstokjes mogen plukken
- Alle vier de beginnende filosofen (P0, P1, P2 en P3) moeten het linker eetstokje en vervolgens het rechter eetstokje kiezen, terwijl de laatste filosoof P4 het rechter eetstokje en vervolgens het linker eetstokje moet kiezen. Dit zal P4 dwingen om eerst zijn rechter eetstokje vast te houden, aangezien het rechter eetstokje van P4 C0 is, dat al in handen is van filosoof P0 en de waarde ervan is ingesteld op 0, dat wil zeggen dat C0 al 0 is, waardoor P4 vast komt te zitten in een oneindige situatie. lus en eetstokje C4 blijft leeg. Daarom heeft filosoof P3 zowel het linker C3- als het rechter C4-eetstokje beschikbaar, daarom zal hij beginnen met eten en zal hij zijn beide eetstokjes neerleggen zodra hij klaar is en anderen laten eten, waardoor het probleem van de impasse wordt weggenomen.
Het ontwerp van het probleem was om de uitdagingen te illustreren die gepaard gaan met het vermijden van een impasse; een impasse van een systeem is een toestand waarin geen vooruitgang van het systeem mogelijk is. Beschouw een voorstel waarbij elke filosoof wordt opgedragen zich als volgt te gedragen:
- De filosoof krijgt de opdracht om na te denken totdat de linkervork beschikbaar is, en als deze beschikbaar is, houdt u deze vast.
- De filosoof krijgt de opdracht om na te denken totdat de juiste vork beschikbaar is, en als deze beschikbaar is, houd hem dan vast.
- De filosoof krijgt de opdracht om te eten als beide vorken beschikbaar zijn.
- Plaats vervolgens eerst de rechtervork
- Plaats vervolgens de linkervork naar beneden
- herhaal vanaf het begin.