Matfilosofens problem är det klassiska synkroniseringsproblemet som säger att Fem filosofer sitter runt ett runt bord och deras uppgift är att tänka och äta alternativt. En skål med nudlar placeras i mitten av bordet tillsammans med fem ätpinnar för var och en av filosoferna. För att äta behöver en filosof både sin högra och en vänstra ätpinne. En filosof kan bara äta om både vänster och höger ätpinnar av filosofen är tillgängliga. Om filosofens omedelbara vänstra och högra ätpinne inte är tillgängliga, lägger filosofen ner sin (antingen vänster eller höger) ätpinne och börjar tänka igen.
Matfilosofen demonstrerar en stor klass av problem med samtidighetskontroll, så det är ett klassiskt synkroniseringsproblem.
Fem filosofer sitter runt bordet
Dining Philosophers Problem - Låt oss förstå Dining Philosophers Problem med koden nedan, vi har använt fig 1 som en referens för att få dig att förstå problemet exakt. De fem filosoferna representeras som P0, P1, P2, P3 och P4 och fem ätpinnar av C0, C1, C2, C3 och C4.
dhanashree verma
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Låt oss diskutera ovanstående kod:
Anta att Philosopher P0 vill äta, kommer den att gå in i Philosopher()-funktionen och köra take_chopstick[i]; genom att göra detta håller det C0 ätpinne efter att det körs take_chopstick[ (i+1) % 5]; genom att göra detta håller det C1 ätpinne (eftersom i =0, därför (0 + 1) % 5 = 1)
Anta på samma sätt att nu Philosopher P1 vill äta, kommer den att gå in i Philosopher()-funktionen och köra take_chopstick[i]; genom att göra detta håller det C1 ätpinne efter att det körs take_chopstick[ (i+1) % 5]; genom att göra detta håller det C2 ätpinne (eftersom i =1, därför (1 + 1) % 5 = 2)
Men praktiskt taget Chopstick C1 är inte tillgänglig eftersom den redan har tagits av filosofen P0, därför genererar ovanstående kod problem och skapar raskondition.
maskinspråk
Lösningen på Dining Philosophers Problem
Vi använder en semafor för att representera en ätpinne och detta fungerar verkligen som en lösning på Dining Philosophers Problem. Vänta och signaloperationer kommer att användas för lösningen av Dining Philosophers Problem, för att välja en chopstick kan vänta operation utföras medan en chopstick signal semafor kan utföras för att släppa.
Semafor: En semafor är en heltalsvariabel i S, som förutom initialisering endast nås av två standard atomoperationer - vänta och signal, vars definitioner är följande:
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></=> Inledningsvis initieras varje element i semaforen C0, C1, C2, C3 och C4 till 1 eftersom ätpinnarna ligger på bordet och inte plockas upp av någon av filosoferna.
Låt oss modifiera ovanstående kod för Dining Philosopher Problem genom att använda semaforoperationer vänta och signalera, den önskade koden ser ut
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 } } I ovanstående kod utförs den första vänteoperationen på take_chopstickC[i] och take_chopstickC [(i+1) % 5]. Detta visar filosofen jag har plockat upp ätpinnarna från vänster och höger. Ätfunktionen utförs efter det.
sharwanand
Efter avslutad ätning av filosofen i the, utförs signaloperation på take_chopstickC[i] och take_chopstickC [(i+1) % 5]. Detta visar att filosofen jag har ätit och lagt ner både vänster och höger ätpinnar. Äntligen börjar filosofen tänka igen.
Låt oss förstå hur ovanstående kod ger en lösning på middagsfilosofproblemet?
Låt värdet på i = 0( initialvärde ), anta att filosof P0 vill äta, kommer den att gå in i Philosopher()-funktionen och köra Vänta( take_chopstickC[i] ); genom att göra detta håller det C0 ätpinne och reducerar semaforen C0 till 0 , efter att det körs Vänta( take_chopstickC[(i+1) % 5] ); genom att göra detta håller det C1 ätpinne (eftersom i =0, därför (0 + 1) % 5 = 1) och reducerar semaforen C1 till 0
På samma sätt, anta att nu Philosopher P1 vill äta, kommer den att gå in i Philosopher()-funktionen och köra Vänta( take_chopstickC[i] ); genom att göra detta kommer den att försöka hålla C1 ätpinne men kommer inte att kunna göra det , eftersom värdet på semafor C1 redan har satts till 0 av filosof P0, kommer den därför att gå in i en oändlig slinga på grund av vilken filosof P1 inte kommer att kunna välja ätpinne C1 medan om filosof P2 vill äta, kommer den att gå in i Philosopher () funktion och exekvera Vänta( take_chopstickC[i] ); genom att göra detta håller det C2 ätpinne och reducerar semaforen C2 till 0, efter det körs den Vänta( take_chopstickC[(i+1) % 5] ); genom att göra detta håller det C3 ätpinne (eftersom i =2, därför (2 + 1) % 5 = 3) och reducerar semaforen C3 till 0.
Därför tillhandahåller ovanstående kod en lösning på middagsfilosofproblemet, en filosof kan bara äta om både omedelbara vänster och höger ätpinnar av filosofen finns tillgängliga, annars behöver filosofen vänta. Också på en gång kan två oberoende filosofer äta samtidigt (d.v.s. filosofen P0 och P2, P1 och P3 & P2 och P4 kan äta samtidigt eftersom alla är de oberoende processerna och de följer ovanstående begränsning av matfilosofiska problem)
array lista java
Nackdelen med ovanstående lösning av middagsfilosofproblemet
Från ovanstående lösning av middagsfilosofproblemet har vi bevisat att inga två närliggande filosofer kan äta vid samma tidpunkt. Nackdelen med ovanstående lösning är att denna lösning kan leda till ett dödläge. Denna situation inträffar om alla filosofer plockar sin vänstra ätpinne samtidigt, vilket leder till ett dödläge och ingen av filosoferna kan äta.
För att undvika dödläge är några av lösningarna som följer -
- Maximalt antal filosofer på bordet bör inte vara fler än fyra, i det här fallet kommer ätpinne C4 att vara tillgänglig för filosof P3, så P3 kommer att börja äta och efter avslutad ätprocedur kommer han att lägga ner både ätpinnen C3 och C4, dvs semaforen C3 och C4 kommer nu att ökas till 1. Nu kommer filosof P2 som höll i ätpinne C2 också att ha ätpinne C3 tillgänglig, därför kommer han på samma sätt att lägga ner sin ätpinne efter att ha ätit och göra det möjligt för andra filosofer att äta.
- En filosof i en jämn position bör välja den högra ätpinnen och sedan den vänstra ätpinnen medan en filosof i en udda position bör välja den vänstra ätpinnen och sedan den högra ätpinnen.
- Endast om båda ätpinnarna (vänster och höger) är tillgängliga samtidigt, bara då bör en filosof få välja sina ätpinnar
- Alla fyra startfilosoferna (P0, P1, P2 och P3) ska välja den vänstra ätpinnen och sedan den högra ätpinnen, medan den sista filosofen P4 ska välja den högra ätpinnen och sedan den vänstra ätpinnen. Detta kommer att tvinga P4 att hålla sin högra ätpinne först eftersom den högra ätpinne i P4 är C0, som redan hålls av filosofen P0 och dess värde är satt till 0, dvs C0 är redan 0, på grund av vilket P4 kommer att fångas in i en oändlig slinga och ätpinne C4 förblir lediga. Därför har filosof P3 både vänster C3 och höger C4 ätpinne tillgänglig, därför kommer den att börja äta och kommer att lägga ifrån sig båda ätpinnarna när de är klara och låta andra äta vilket tar bort problemet med dödläge.
Utformningen av problemet var att illustrera utmaningarna med att undvika dödläge, ett dödläge för ett system är ett tillstånd där ingen framsteg av systemet är möjlig. Överväg ett förslag där varje filosof instrueras att bete sig enligt följande:
- Filosofen instrueras att tänka tills vänster gaffel är tillgänglig, när den är tillgänglig, håll den.
- Filosofen instrueras att tänka tills rätt gaffel är tillgänglig, när den är tillgänglig, håll den.
- Filosofen instrueras att äta när båda gafflarna är tillgängliga.
- sätt sedan ner höger gaffel först
- Lägg sedan ner vänster gaffel
- upprepa från början.