Ruokailufilosofin ongelma on klassinen synkronointiongelma, joka sanoo, että viisi filosofia istuu pyöreän pöydän ympärillä ja heidän tehtävänsä on ajatella ja syödä vaihtoehtoisesti. Kulhollinen nuudeleita asetetaan pöydän keskelle ja viisi syömäpuikkoa kullekin filosofille. Syödäkseen filosofi tarvitsee sekä oikean että vasemman syömäpuikon. Filosofi voi syödä vain, jos filosofin vasen ja oikea syömäpuikot ovat käytettävissä. Jos filosofin sekä vasen että oikea syömäpuikko eivät ole saatavilla, filosofi laskee (joko vasemman tai oikean) syömäpuikon alas ja alkaa ajatella uudelleen.
Ruokailufilosofi esittelee suuren luokan samanaikaisuuden ohjausongelmia, joten se on klassinen synkronointiongelma.
Viisi filosofia istuu pöydän ympärillä
Ruokailufilosofien ongelma - Ymmärretään Dining Philosophers -ongelma alla olevalla koodilla, olemme käyttäneet kuvaa 1 viitteenä saadaksesi sinut ymmärtämään ongelman tarkasti. Viittä filosofia edustavat P0, P1, P2, P3 ja P4 ja viisi syömäpuikkoa C0, C1, C2, C3 ja 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 } } Keskustellaan yllä olevasta koodista:
Oletetaan, että Filosofi P0 haluaa syödä, se tulee Philosopher()-funktioon ja suorittaa take_chopsticck[i]; näin tekemällä se kestää C0 syömäpuikko sen jälkeen se suoritetaan ota_syömäpuikko[ (i+1) % 5]; näin tekemällä se kestää C1 syömäpuikko ( koska i = 0, siis (0 + 1) % 5 = 1)
Samoin oletetaan nyt, että Philosopher P1 haluaa syödä, se tulee Philosopher()-funktioon ja suorittaa take_chopsticck[i]; näin tekemällä se kestää C1 syömäpuikko sen jälkeen se suoritetaan ota_syömäpuikko[ (i+1) % 5]; näin tekemällä se kestää C2 syömäpuikko ( koska i = 1, siis (1 + 1) % 5 = 2)
Mutta Käytännössä Chopstick C1 ei ole saatavilla, koska filosofi P0 on jo ottanut sen, joten yllä oleva koodi tuottaa ongelmia ja tuottaa kilpailutilanteen.
Ruokailufilosofi-ongelman ratkaisu
Käytämme semaforia edustamaan syömäpuikkoa, ja tämä todella toimii ratkaisuna ruokailufilosofien ongelmaan. Dining Philosophers -ongelman ratkaisuun käytetään Wait and Signal -operaatioita, syömäpuikon poiminta varten voidaan suorittaa odotustoiminto ja syömäpuikon vapauttamiseksi voidaan suorittaa semafori.
Semafori: Semafori on S:ssä oleva kokonaislukumuuttuja, johon alustuksen lisäksi päästään vain kahdella standardinmukaisella atomioperaatiolla - odotus ja signaali, joiden määritelmät ovat seuraavat:
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></=> Aluksi semaforin C0, C1, C2, C3 ja C4 kukin elementti alustetaan 1:ksi, kun syömäpuikot ovat pöydällä, eikä kukaan filosofeista ole poiminut niitä.
Muokataan yllä olevaa Ruokailufilosofi-ongelman koodia semaforioperaatioilla odota ja signaali, haluttu koodi näyttää tältä
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 } } Yllä olevassa koodissa ensimmäinen odotustoiminto suoritetaan kohteille take_chopstickC[i] ja take_chopstickC [ (i+1) % 5]. Tämä osoittaa, että filosofi olen poiminut syömäpuikot sen vasemmalta ja oikealta. Syömistoiminto suoritetaan sen jälkeen.
Kun filosofi on syönyt loppuun, signaalioperaatio suoritetaan kohteille take_chopstickC[i] ja take_chopstickC [ (i+1) % 5]. Tämä osoittaa, että filosofi olen syönyt ja laskenut sekä vasemman että oikean syömäpuikon. Lopulta filosofi alkaa ajatella uudelleen.
Ymmärretään, kuinka yllä oleva koodi antaa ratkaisun ruokailufilosofi-ongelmaan?
Olkoon i = 0(alkuarvo) arvo, oletetaan, että filosofi P0 haluaa syödä, se tulee Philosopher()-funktioon ja suorittaa Odota( take_chopsticckC[i] ); näin tekemällä se kestää C0 syömäpuikko ja pienentää semaforin C0 nollaan , sen jälkeen se suoritetaan Odota( ota_ syömäpuikkoC[(i+1) % 5] ); näin tekemällä se kestää C1 syömäpuikko ( koska i = 0, siksi (0 + 1) % 5 = 1) ja pienentää semaforin C1 arvoon 0
Samoin oletetaan nyt, että Philosopher P1 haluaa syödä, se tulee Philosopher()-funktioon ja suorittaa Odota( take_chopsticckC[i] ); tekemällä tämän se yrittää pitää C1 syömäpuikko mutta ei pysty siihen , koska filosofi P0 on jo asettanut semaforin C1 arvon 0:ksi, se menee siis äärettömään silmukkaan, jonka vuoksi filosofi P1 ei voi poimia syömäpuikkoa C1, kun taas jos filosofi P2 haluaa syödä, se astuu Filosofiin ()-toiminto ja suorita Odota( take_chopsticckC[i] ); näin tekemällä se kestää C2 syömäpuikko ja pienentää semaforin C2 arvoon 0, jonka jälkeen se suorittaa Odota( ota_ syömäpuikkoC[(i+1) % 5] ); näin tekemällä se kestää C3 syömäpuikko ( koska i =2, siksi (2 + 1) % 5 = 3) ja pienentää semaforin C3 arvoon 0.
Siksi yllä oleva koodi tarjoaa ratkaisun ruokailufilosofi-ongelmaan. Filosofi voi syödä vain, jos filosofin sekä vasen että oikea syömäpuikot ovat käytettävissä, muuten filosofin on odotettava. Myös kaksi itsenäistä filosofia voi kerralla syödä samanaikaisesti (eli filosofi P0 ja P2, P1 ja P3 & P2 ja P4 voivat syödä samanaikaisesti, koska kaikki ovat itsenäisiä prosesseja ja ne noudattavat yllä olevaa ruokailufilosofiongelman rajoitusta)
Yllä olevan ruokailufilosofi-ongelman ratkaisun haittapuoli
Yllä olevasta ruokailufilosofi-ongelman ratkaisusta olemme osoittaneet, että kaksi vierekkäistä filosofia ei voi syödä samaan aikaan. Yllä olevan ratkaisun haittana on, että tämä ratkaisu voi johtaa lukkiutumiseen. Tämä tilanne tapahtuu, jos kaikki filosofit poimivat vasemman syömäpuikon yhtä aikaa, mikä johtaa umpikujaan eikä kukaan filosofeista voi syödä.
Lukituksen välttämiseksi jotkut ratkaisuista ovat seuraavat:
- Filosofien enimmäismäärä pöydällä ei saa olla enempää kuin neljä, tässä tapauksessa syömäpuikko C4 on saatavilla filosofille P3, joten P3 aloittaa syömisen ja syömistoimenpiteensä päätyttyä laskee molemmat syömäpuikon C3 alas. ja C4, eli semafori C3 ja C4 kasvatetaan nyt 1:ksi. Nyt filosofilla P2, joka piti syömäpuikkoa C2, on myös syömäpuikko C3 saatavilla, joten samalla tavalla hän laskee syömäpuikon syömisen jälkeen ja antaa muille filosofeille mahdollisuuden syödä.
- Parillisessa asennossa olevan filosofin tulee valita oikea syömäpuikko ja sitten vasen syömäpuikko, kun taas parittomassa asemassa olevan filosofin tulee valita vasen syömäpuikko ja sitten oikea syömäpuikko.
- Vain siinä tapauksessa, että molemmat syömäpuikot (vasen ja oikea) ovat saatavilla samanaikaisesti, vain silloin filosofin tulisi antaa poimia syömäpuikot
- Kaikkien neljän aloittavan filosofin (P0, P1, P2 ja P3) tulee valita vasen syömäpuikko ja sitten oikea syömäpuikko, kun taas viimeisen filosofin P4 tulisi valita oikea syömäpuikko ja sitten vasen syömäpuikko. Tämä pakottaa P4:n pitelemään ensin oikeaa syömäpuikkoaan, koska P4:n oikea syömäpuikko on C0, joka on jo filosofin P0 hallussa ja sen arvoksi on asetettu 0, eli C0 on jo 0, minkä vuoksi P4 jää loukkuun äärettömään. silmukka ja syömäpuikko C4 jäävät tyhjiksi. Tästä syystä filosofilla P3:lla on käytettävissä sekä vasen C3 että oikea C4 syömäpuikko, joten se alkaa syödä ja laskee molemmat syömäpuikot alas, kun se on valmis, ja antaa muiden syödä, mikä poistaa umpikujan ongelman.
Ongelman tarkoituksena oli havainnollistaa umpikujan välttämisen haasteita, järjestelmän umpikujatila on tila, jossa järjestelmän eteneminen ei ole mahdollista. Harkitse ehdotusta, jossa jokaista filosofia neuvotaan käyttäytymään seuraavasti:
- Filosofia ohjataan ajattelemaan, kunnes vasen haarukka on käytettävissä, kun se on käytettävissä, pidä sitä.
- Filosofia ohjataan ajattelemaan, kunnes oikea haarukka on saatavilla, kun se on saatavilla, pidä sitä kiinni.
- Filosofia neuvotaan syömään, kun molemmat haarukat ovat saatavilla.
- laske sitten oikea haarukka ensin alas
- laske sitten vasen haarukka seuraavaksi alas
- toista alusta.