Spisefilosoffens problem er det klassiske problem med synkronisering, som siger, at Fem filosoffer sidder omkring et cirkulært bord, og deres opgave er at tænke og spise alternativt. En skål nudler er placeret i midten af bordet sammen med fem spisepinde til hver af filosofferne. For at spise har en filosof brug for både deres højre og venstre spisepind. En filosof kan kun spise, hvis både venstre og højre spisepinde af filosoffen er tilgængelig. Hvis filosoffens umiddelbare venstre og højre spisepinde ikke er tilgængelige, sætter filosoffen deres (enten venstre eller højre) spisepind fra sig og begynder at tænke igen.
Spisefilosoffen demonstrerer en stor klasse af samtidighedskontrolproblemer, derfor er det et klassisk synkroniseringsproblem.
Fem filosoffer sidder rundt om bordet
Spisefilosoffer problem - Lad os forstå Dining Philosophers-problemet med nedenstående kode, vi har brugt fig. 1 som reference for at få dig til at forstå problemet nøjagtigt. De fem filosoffer er repræsenteret som P0, P1, P2, P3 og P4 og fem spisepinde af 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 } } Lad os diskutere ovenstående kode:
Antag at Philosopher P0 vil spise, vil den gå ind i Philosopher()-funktionen og udføre take_chopstick[i]; ved at gøre dette holder det C0 spisepind efter at det udføres take_chopstick[ (i+1) % 5]; ved at gøre dette holder det C1 spisepind (da i =0, derfor (0 + 1) % 5 = 1)
Antag på samme måde, at nu Philosopher P1 vil spise, vil den gå ind i Philosopher()-funktionen og udføre take_chopstick[i]; ved at gøre dette holder det C1 spisepind efter at det udføres take_chopstick[ (i+1) % 5]; ved at gøre dette holder det C2 spisepind (da i =1, derfor (1 + 1) % 5 = 2)
mamta kulkarni
Men praktisk talt er Chopstick C1 ikke tilgængelig, da den allerede er blevet taget af filosof P0, hvorfor ovenstående kode genererer problemer og producerer racetilstand.
Løsningen af Spisefilosoffer-problemet
Vi bruger en semafor til at repræsentere en spisepind, og dette fungerer virkelig som en løsning på Dining Philosophers Problem. Vente- og signaloperationer vil blive brugt til løsningen af Spisefilosoffer-problemet, for at vælge en spisepind kan venteoperation udføres, mens en spisepindsignalsemafor kan udføres for at frigive.
Semafor: En semafor er en heltalsvariabel i S, som bortset fra initialisering kun tilgås af to standard atomoperationer - vent og signal, hvis definitioner 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></=> Indledningsvis initialiseres hvert element i semaforen C0, C1, C2, C3 og C4 til 1, da spisepindene er på bordet og ikke opfanges af nogen af filosofferne.
Lad os ændre ovenstående kode for Dining Philosopher Problemet ved at bruge semaforoperationer vent og signal, den ønskede kode ser ud
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 ovenstående kode udføres den første venteoperation på take_chopstickC[i] og take_chopstickC [(i+1) % 5]. Dette viser filosof, jeg har samlet spisepindene op fra venstre og højre. Derefter udføres spisefunktionen.
Efter at filosoffen er færdig med at spise, udføres signaloperation på take_chopstickC[i] og take_chopstickC [(i+1) % 5]. Dette viser, at filosoffen jeg har spist og lagt både venstre og højre spisepinde. Endelig begynder filosoffen at tænke igen.
Lad os forstå, hvordan ovenstående kode giver en løsning på spisefilosofproblemet?
Lad værdien af i = 0( begyndelsesværdi ), antag at filosof P0 vil spise, vil den gå ind i funktionen Philosopher() og udføre Vent( take_chopstickC[i] ); ved at gøre dette holder det C0 spisepind og reducerer semaforen C0 til 0 , efter at det udføres Vent( take_chopstickC[(i+1) % 5] ); ved at gøre dette holder det C1 spisepind (da i =0, derfor (0 + 1) % 5 = 1) og reducerer semaforen C1 til 0
På samme måde, antag nu, at Philosopher P1 vil spise, vil den gå ind i Philosopher()-funktionen og udføre Vent( take_chopstickC[i] ); ved at gøre dette vil den forsøge at holde C1 spisepind men vil ikke kunne gøre det , da værdien af semafor C1 allerede er blevet sat til 0 af filosof P0, vil den derfor indgå i en uendelig løkke på grund af hvilken filosof P1 ikke vil være i stand til at vælge spisepind C1, mens hvis filosof P2 vil spise, vil den gå ind i Philosopher () funktion og udfør Vent( take_chopstickC[i] ); ved at gøre dette holder det C2 spisepind og reducerer semaforen C2 til 0, hvorefter den udføres Vent( take_chopstickC[(i+1) % 5] ); ved at gøre dette holder det C3 spisepind (da i =2, derfor (2 + 1) % 5 = 3) og reducerer semaforen C3 til 0.
scanner scan java
Derfor giver ovenstående kode en løsning på spisefilosofproblemet. En filosof kan kun spise, hvis både den umiddelbare venstre og højre spisepinde af filosoffen er tilgængelige, ellers skal filosoffen vente. Også på én gang kan to uafhængige filosoffer spise samtidigt (dvs. P0 og P2, P1 og P3 & P2 og P4 kan spise samtidigt, da alle er de uafhængige processer, og de følger ovenstående begrænsning af spisefilosofproblem)
Ulempen ved ovenstående løsning af spisefilosofproblemet
Fra ovenstående løsning af spisefilosofproblemet har vi bevist, at ingen to nabofilosoffer kan spise på samme tidspunkt. Ulempen ved ovenstående løsning er, at denne løsning kan føre til en dødvandetilstand. Denne situation opstår, hvis alle filosofferne plukker deres venstre spisepind på samme tid, hvilket fører til tilstanden dødvande, og ingen af filosofferne kan spise.
For at undgå dødvande er nogle af løsningerne som følger -
- Det maksimale antal filosoffer på bordet bør ikke være mere end fire, i dette tilfælde vil spisepind C4 være tilgængelig for filosof P3, så P3 begynder at spise, og efter afslutningen af hans spiseprocedure, vil han lægge både spisepinden C3 fra sig. og C4, dvs. semaforen C3 og C4 vil nu blive øget til 1. Nu vil filosof P2, som holdt spisepinden C2, også have spisepinden C3 tilgængelig, derfor vil han på samme måde lægge sin spisepind fra sig efter at have spist og gøre det muligt for andre filosoffer at spise.
- En filosof i en lige position bør vælge den højre spisepind og derefter den venstre spisepind, mens en filosof i en ulige position bør vælge den venstre spisepind og derefter den højre.
- Kun hvis begge spisepinde (venstre og højre) er tilgængelige på samme tid, skal en filosof først have lov til at vælge deres spisepinde
- Alle de fire startfilosoffer (P0, P1, P2 og P3) skal vælge den venstre spisepind og derefter den højre spisepind, hvorimod den sidste filosof P4 skal vælge den højre spisepind og derefter den venstre spisepind. Dette vil tvinge P4 til at holde sin højre spisepind først, da den højre spisepind i P4 er C0, som allerede holdes af filosoffen P0, og dens værdi er sat til 0, dvs. C0 er allerede 0, på grund af hvilket P4 vil blive fanget i en uendelig løkke og spisepind C4 forbliver ledig. Derfor har filosof P3 både venstre C3 og højre C4 spisepind til rådighed, derfor vil den begynde at spise og vil lægge sine begge spisepinde fra sig, når den er færdig og lade andre spise, hvilket fjerner problemet med dødvande.
Designet af problemet var at illustrere udfordringerne ved at undgå dødvande, en dødvandstilstand i et system er en tilstand, hvor ingen fremskridt i systemet er mulig. Overvej et forslag, hvor hver filosof bliver instrueret i at opføre sig som følger:
- Filosoffen bliver bedt om at tænke, indtil venstre gaffel er tilgængelig, når den er tilgængelig, hold den.
- Filosoffen bliver bedt om at tænke, indtil den rigtige gaffel er tilgængelig, når den er tilgængelig, hold den.
- Filosoffen bliver bedt om at spise, når begge gafler er tilgængelige.
- sæt derefter den højre gaffel ned først
- sæt derefter venstre gaffel ned
- gentag fra begyndelsen.