Spisefilosofens problem er det klassiske synkroniseringsproblemet som sier at Fem filosofer sitter rundt et sirkulært bord og deres jobb er å tenke og spise alternativt. En bolle med nudler er plassert i midten av bordet sammen med fem spisepinner for hver av filosofene. For å spise trenger en filosof både høyre og venstre spisepinne. En filosof kan bare spise hvis både venstre og høyre spisepinner av filosofen er tilgjengelig. I tilfelle hvis både umiddelbare venstre og høyre spisepinnene til filosofen ikke er tilgjengelige, legger filosofen fra seg spisepinnen (enten venstre eller høyre) og begynner å tenke på nytt.
Spisefilosofen demonstrerer en stor klasse med samtidighetskontrollproblemer, derfor er det et klassisk synkroniseringsproblem.
Fem filosofer sitter rundt bordet
Problem med middagsfilosofer - La oss forstå Dining Philosophers Problem med koden nedenfor, vi har brukt fig 1 som referanse for å få deg til å forstå problemet nøyaktig. De fem filosofene er representert som P0, P1, P2, P3 og P4 og fem spisepinner av C0, C1, C2, C3 og C4.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } La oss diskutere koden ovenfor:
Anta at Philosopher P0 vil spise, vil den gå inn i Philosopher()-funksjonen og utføre take_chopstick[i]; ved å gjøre dette holder det C0 spisepinne etter at det utføres take_chopstick[ (i+1) % 5]; ved å gjøre dette holder det C1 spisepinne (siden i =0, derfor (0 + 1) % 5 = 1)
Anta på samme måte at nå Philosopher P1 vil spise, vil den gå inn i Philosopher()-funksjonen og kjøre take_chopstick[i]; ved å gjøre dette holder det C1 spisepinne etter at det utføres take_chopstick[ (i+1) % 5]; ved å gjøre dette holder det C2 spisepinne (siden i =1, derfor (1 + 1) % 5 = 2)
numpy meshgrid
Men praktisk talt Chopstick C1 er ikke tilgjengelig ettersom den allerede er tatt av filosof P0, derfor genererer koden ovenfor problemer og produserer rasetilstand.
Løsningen på Dining Philosophers Problem
Vi bruker en semafor for å representere en spisepinne, og dette fungerer virkelig som en løsning på Dining Philosophers Problem. Vente- og signaloperasjoner vil bli brukt for løsningen av Dining Philosophers-problemet, for å velge en spisepinne kan venteoperasjonen utføres mens for å slippe ut en spisepinnesignal kan semafor utføres.
Semafor: En semafor er en heltallsvariabel i S, som bortsett fra initialisering er tilgjengelig av bare to standard atomoperasjoner - vent og signal, hvis definisjoner er som følger:
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></=> Til å begynne med initialiseres hvert element i semaforen C0, C1, C2, C3 og C4 til 1 ettersom spisepinnene ligger på bordet og ikke plukkes opp av noen av filosofene.
La oss modifisere koden ovenfor for Dining Philosopher Problem ved å bruke semaforoperasjoner vent og signal, den ønskede koden ser ut som
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 koden ovenfor utføres den første venteoperasjonen på take_chopstickC[i] og take_chopstickC [(i+1) % 5]. Dette viser filosofen jeg har plukket opp spisepinnene fra venstre og høyre. Spisefunksjonen utføres etter det.
Etter fullført spising av filosof i the, utføres signaloperasjon på take_chopstickC[i] og take_chopstickC [(i+1) % 5]. Dette viser at filosofen jeg har spist og lagt ned både venstre og høyre spisepinnen. Endelig begynner filosofen å tenke igjen.
La oss forstå hvordan koden ovenfor gir en løsning på spisefilosofproblemet?
La verdien av i = 0( startverdi ), anta at filosof P0 vil spise, den vil gå inn i Philosopher()-funksjonen og kjøre Vent( take_chopstickC[i] ); ved å gjøre dette holder det C0 spisepinne og reduserer semaforen C0 til 0 , etter at det utføres Vent( take_chopstickC[(i+1) % 5] ); ved å gjøre dette holder det C1 spisepinne ( siden i =0, derfor (0 + 1) % 5 = 1) og reduserer semaforen C1 til 0
På samme måte, anta at nå Philosopher P1 vil spise, vil den gå inn i Philosopher()-funksjonen og kjøre Vent( take_chopstickC[i] ); ved å gjøre dette vil den prøve å holde C1 spisepinne men vil ikke klare det , siden verdien av semaforen C1 allerede er satt til 0 av filosof P0, vil den derfor gå inn i en uendelig løkke på grunn av hvilken filosof P1 ikke vil være i stand til å velge spisepinnen C1, mens hvis filosof P2 vil spise, vil den gå inn i Philosopher () funksjon, og utfør Vent( take_chopstickC[i] ); ved å gjøre dette holder det C2 spisepinne og reduserer semaforen C2 til 0, deretter kjøres den Vent( take_chopstickC[(i+1) % 5] ); ved å gjøre dette holder det C3 spisepinne ( siden i =2, derfor (2 + 1) % 5 = 3) og reduserer semaforen C3 til 0.
groovy dataspråk
Derfor gir koden ovenfor en løsning på spisefilosofproblemet, en filosof kan bare spise hvis både umiddelbare venstre og høyre spisepinner til filosofen er tilgjengelige, ellers må filosofen vente. Også på en gang kan to uavhengige filosofer spise samtidig (dvs. en filosof P0 og P2, P1 og P3 & P2 og P4 kan spise samtidig, da alle er de uavhengige prosessene og de følger begrensningen ovenfor for spisefilosofproblem)
Ulempen med løsningen ovenfor av spisefilosofproblemet
Fra løsningen ovenfor av spisefilosofproblemet har vi bevist at ingen to nabofilosofer kan spise på samme tidspunkt. Ulempen med løsningen ovenfor er at denne løsningen kan føre til en fastlåst tilstand. Denne situasjonen oppstår hvis alle filosofene plukker den venstre spisepinnen sin samtidig, noe som fører til tilstanden dødlås og ingen av filosofene kan spise.
For å unngå dødlås er noen av løsningene som følger -
- Maksimalt antall filosofer på bordet bør ikke være mer enn fire, i dette tilfellet vil spisepinnen C4 være tilgjengelig for filosof P3, så P3 vil begynne å spise og etter endt spiseprosedyre vil han legge fra seg både spisepinnen C3 og C4, dvs. semaforen C3 og C4 vil nå økes til 1. Nå vil filosof P2 som holdt spisepinnen C2 også ha spisepinnen C3 tilgjengelig, og på samme måte vil han legge fra seg spisepinnen etter å ha spist og gjøre det mulig for andre filosofer å spise.
- En filosof i en jevn posisjon bør velge den høyre spisepinnen og deretter den venstre spisepinnen, mens en filosof i en odde posisjon bør velge den venstre spisepinnen og deretter den høyre.
- Bare i tilfelle hvis begge spisepinnene (venstre og høyre) er tilgjengelige samtidig, bare da bør en filosof få lov til å plukke spisepinnene sine
- Alle de fire startfilosofene (P0, P1, P2 og P3) bør velge den venstre spisepinnen og deretter den høyre spisepinnen, mens den siste filosofen P4 bør velge den høyre spisepinnen og deretter den venstre spisepinnen. Dette vil tvinge P4 til å holde den høyre spisepinnen først siden den høyre spisepinnen til P4 er C0, som allerede holdes av filosof P0 og verdien er satt til 0, dvs. C0 er allerede 0, på grunn av dette vil P4 bli fanget i en uendelig løkke og spisepinnen C4 forblir ledig. Derfor har filosof P3 både venstre C3 og høyre C4 spisepinne tilgjengelig, derfor vil den begynne å spise og vil legge fra seg begge spisepinnene når de er ferdige og la andre spise, noe som fjerner problemet med vranglås.
Utformingen av problemet var å illustrere utfordringene med å unngå dødlås, en dødlåstilstand i et system er en tilstand der ingen fremdrift av systemet er mulig. Vurder et forslag der hver filosof blir bedt om å oppføre seg som følger:
- Filosofen blir bedt om å tenke til venstre gaffel er tilgjengelig, når den er tilgjengelig, hold den.
- Filosofen blir bedt om å tenke til den rette gaffelen er tilgjengelig, når den er tilgjengelig, hold den.
- Filosofen blir bedt om å spise når begge gaflene er tilgjengelige.
- sett deretter ned den høyre gaffelen først
- deretter, sett venstre gaffel ned neste
- gjenta fra begynnelsen.