Valgomojo filosofo problema yra klasikinė sinchronizacijos problema, kuri teigia, kad aplink apskritą stalą sėdi penki filosofai ir jų darbas yra mąstyti ir valgyti alternatyviai. Stalo centre dedamas dubuo su makaronais ir po penkias lazdeles kiekvienam filosofui. Kad filosofas valgytų, jam reikia ir dešinės, ir kairės lazdelės. Filosofas gali valgyti tik tada, kai turi tiek dešiniąją, tiek kairę filosofo lazdeles. Tuo atveju, jei filosofui nėra tiek tiesioginės kairės, tiek dešinės lazdelės, tada filosofas padeda savo (kairę arba dešinę) lazdelę ir vėl pradeda mąstyti.

Valgomojo filosofas demonstruoja didelę lygiagrečio valdymo problemų klasę, todėl tai yra klasikinė sinchronizavimo problema.

Aplink stalą sėdi penki filosofai

Valgymo filosofų problema - Supraskime valgymo filosofų problemą naudodami toliau pateiktą kodą, 1 pav. naudojome kaip nuorodą, kad tiksliai suprastumėte problemą. Penki filosofai vaizduojami kaip P0, P1, P2, P3 ir P4, o penkios lazdelės – C0, C1, C2, C3 ir C4.

kiek miestų yra pas mus

 Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } 

Aptarkime aukščiau pateiktą kodą:

Tarkime, kad filosofas P0 nori valgyti, jis įeis į Philosopher() funkciją ir vykdys paimti_lazdelę[i]; tai darydamas jis laikosi C0 lazdelės po to jis vykdomas paimti_lazdelę[ (i+1) % 5]; tai darydamas jis laikosi C1 pagaliukas ( kadangi i = 0, todėl (0 + 1) % 5 = 1)

Panašiai tarkime, kad dabar Filosofas P1 nori valgyti, jis įeis į Filosofas() funkciją ir vykdys paimti_lazdelę[i]; tai darydamas jis laikosi C1 pagaliukas po to jis vykdomas paimti_lazdelę[ (i+1) % 5]; tai darydamas jis laikosi C2 lazdelė ( kadangi i = 1, todėl (1 + 1) % 5 = 2)

Tačiau praktiškai Chopstick C1 nėra, nes jį jau paėmė filosofas P0, todėl aukščiau pateiktas kodas sukuria problemų ir sukuria lenktynių sąlygas.

teksto įvynioklis css

Valgymo filosofų problemos sprendimas

Mes naudojame semaforą, kad pavaizduotume lazdelę, ir tai tikrai veikia kaip valgymo filosofų problemos sprendimas. Valgymo filosofų problemos sprendimui bus naudojamos laukimo ir signalo operacijos, o lazdelės paėmimui galima atlikti laukimo operaciją, o lazdelės atleidimui – semaforą.

Semaforas: semaforas yra sveikasis S kintamasis, kuris, be inicijavimo, pasiekiamas tik dviem standartinėmis atominėmis operacijomis - laukimu ir signalu, kurių apibrėžimai yra tokie:

 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&apos;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&apos;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 &amp; 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></=>

Iš pradžių kiekvienas semaforo elementas C0, C1, C2, C3 ir C4 inicijuojamas į 1, nes lazdelės yra ant stalo ir jų nepaima nė vienas filosofas.

Modifikuokime aukščiau pateiktą valgymo filosofo problemos kodą naudodami semaforo operacijas laukti ir signalizuoti, norimas kodas atrodo taip

 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 } } 

Aukščiau pateiktame kode pirmoji laukimo operacija atliekama take_chopstickC[i] ir take_chopstickC [ (i+1) % 5]. Tai rodo, kad filosofas aš paėmiau lazdeles iš kairės ir dešinės. Valgymo funkcija atliekama po to.

pirminio rakto sudėtinis raktas

Filosofui baigus valgyti, signalo operacija atliekama take_chopstickC[i] ir take_chopstickC [ (i+1) % 5]. Tai rodo, kad filosofas aš pavalgiau ir padėjo ir kairę, ir dešinę lazdeles. Galiausiai filosofas vėl pradeda mąstyti.

Supraskime, kaip aukščiau pateiktas kodas išsprendžia valgymo filosofo problemą?

Tegul i reikšmė = 0 (pradinė reikšmė), tarkime, kad filosofas P0 nori valgyti, jis įves į Filosofo () funkciją ir vykdys Palauk( take_chopsticckC[i] ); tai darydamas jis laikosi C0 lazdelės ir sumažina semaforą C0 iki 0 , po to jis vykdomas Palaukite( take_chopsticckC[(i+1) % 5] ); tai darydamas jis laikosi C1 pagaliukas ( kadangi i =0, todėl (0 + 1) % 5 = 1) ir sumažina semaforą C1 iki 0

Panašiai, tarkime, kad dabar Filosofas P1 nori valgyti, jis įeis į Filosofas() funkciją ir vykdys Palauk( take_chopsticckC[i] ); tai darydamas jis bandys išlaikyti C1 pagaliukas bet negalės to padaryti , kadangi semaforo C1 reikšmę filosofas P0 jau nustatė į 0, todėl jis pateks į begalinę kilpą, dėl kurios filosofas P1 negalės paimti lazdelės C1, o jei filosofas P2 nori valgyti, jis įeis į Filosofą () funkciją ir vykdyti Palaukite( take_chopsticckC[i] ); tai darydamas jis laikosi C2 lazdelė ir sumažina semaforą C2 iki 0, po to jis įvykdo Palaukite( take_chopsticckC[(i+1) % 5] ); tai darydamas jis laikosi C3 pagaliukas ( kadangi i = 2, todėl (2 + 1) % 5 = 3) ir sumažina semaforą C3 iki 0.

Taigi aukščiau pateiktas kodas yra valgomojo filosofo problemos sprendimas. Filosofas gali valgyti tik tada, kai yra prieinamos tiek dešinės, tiek kairiosios filosofo lazdelės, kitaip filosofas turi palaukti. Taip pat vienu metu du nepriklausomi filosofai gali valgyti vienu metu (t. y. filosofas P0 ir P2, P1 ir P3 ir P2 ir P4 gali valgyti vienu metu, nes visi yra nepriklausomi procesai ir jie laikosi aukščiau pateikto valgymo filosofo problemos apribojimo)

charakteris.palyginti java

Aukščiau pateikto valgymo filosofo problemos sprendimo trūkumas

Iš aukščiau pateikto valgymo filosofo problemos sprendimo mes įrodėme, kad du kaimyniniai filosofai negali valgyti tuo pačiu metu. Aukščiau pateikto sprendimo trūkumas yra tas, kad šis sprendimas gali sukelti aklavietę. Tokia situacija atsitinka, jei visi filosofai vienu metu renkasi kairę lazdelę, o tai veda į aklavietę ir nė vienas iš filosofų negali valgyti.

Siekiant išvengti aklavietės, kai kurie sprendimai yra tokie:

• Maksimalus filosofų skaičius ant stalo turi būti ne daugiau kaip keturi, tokiu atveju filosofas P3 turės lazdelę C4, taigi P3 pradės valgyti ir baigęs valgymo procedūrą nudės abi lazdelę C3. ir C4, t. y. semaforas C3 ir C4, dabar bus padidintas iki 1. Dabar filosofas P2, kuris laikė lazdelę C2, taip pat turės lazdelę C3, taigi, panašiai, po valgio jis nudės lazdelę ir leis valgyti kitiems filosofams.
• Filosofas, esantis lygioje padėtyje, turėtų pasirinkti dešinę ir tada kairę lazdelę, o nelyginėje padėtyje esantis filosofas turėtų pasirinkti kairę ir tada dešinę.
• Tik tuo atveju, jei abi lazdelės (kairė ir dešinė) yra prieinamos vienu metu, tik tada filosofui turėtų būti leista išsirinkti savo lazdeles.
• Visi keturi pradedantieji filosofai (P0, P1, P2 ir P3) turėtų pasirinkti kairįjį ir tada dešinįjį lazdelę, o paskutinis filosofas P4 turėtų pasirinkti dešinę ir tada kairę. Tai privers P4 pirmiausia laikyti dešinę lazdelę, nes dešinioji P4 lazdelė yra C0, kurią jau laiko filosofas P0 ir jos reikšmė nustatyta į 0, ty C0 jau yra 0, dėl to P4 įstrigo į begalybę. kilpa ir lazdelė C4 lieka laisva. Vadinasi, filosofas P3 turi ir kairę C3, ir dešiniąją C4 lazdelę, todėl pradės valgyti, o baigęs nudės abi lazdeles ir leis valgyti kitiems, o tai pašalina aklavietės problemą.

Problemos dizainas buvo skirtas iliustruoti iššūkius, kaip išvengti aklavietės, sistemos aklavietės būsena yra būsena, kai neįmanoma sistemos progreso. Apsvarstykite pasiūlymą, kuriame kiekvienam filosofui būtų nurodyta elgtis taip:

• Filosofui nurodoma mąstyti tol, kol bus pasiekiama kairioji šakutė, o kai yra, laikykite ją.
• Filosofui nurodoma mąstyti tol, kol atsiras tinkama šakutė, o kai ji yra, laikykite ją.
• Filosofui nurodoma valgyti, kai yra abi šakutės.
• tada pirmiausia nuleiskite dešinę šakę
• tada nuleiskite kairę šakę
• pakartokite nuo pradžių.