Problem filozofa koji jede je klasični problem sinkronizacije koji kaže da pet filozofa sjedi oko okruglog stola i njihov je posao naizmjenično razmišljati i jesti. Zdjela s rezancima stavlja se na sredinu stola zajedno s pet štapića za jelo za svakog od filozofa. Da bi jeo, filozofu su potrebni i desni i lijevi štapić. Filozof može jesti samo ako su mu dostupni i lijevi i desni štapići za jelo. U slučaju da neposredni lijevi i desni štapić za jelo filozofa nisu dostupni, filozof odlaže svoj (bilo lijevi ili desni) štapić i ponovno počinje razmišljati.
Filozof objedovanja demonstrira veliku klasu problema kontrole istovremenosti, stoga je to klasični problem sinkronizacije.
Pet filozofa sjedi oko stola
Problem filozofa blagovanja - Hajdemo razumjeti problem Dining Philosophers s donjim kodom, upotrijebili smo sliku 1 kao referencu da biste točno razumjeli problem. Pet filozofa predstavljeno je kao P0, P1, P2, P3 i P4, a pet štapića za jelo kao C0, C1, C2, C3 i 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 } } Raspravljajmo o gornjem kodu:
Pretpostavimo da Philosopher P0 želi jesti, ući će u funkciju Philosopher() i izvršiti uzmi_štapić[i]; čineći ovo drži C0 štapić za jelo nakon toga izvršiti uzmi_štapić [ (i+1) % 5]; čineći ovo drži C1 štapić za jelo ( budući da je i =0, dakle (0 + 1) % 5 = 1)
Slično pretpostavimo da sada Philosopher P1 želi jesti, ući će u funkciju Philosopher() i izvršiti uzmi_štapić[i]; čineći ovo drži C1 štapić za jelo nakon toga izvršiti uzmi_štapić [ (i+1) % 5]; čineći ovo drži C2 štapić za jelo ( budući da je i =1, dakle (1 + 1) % 5 = 2)
Ali Praktički Chopstick C1 nije dostupan jer ga je već uzeo filozof P0, stoga gornji kod stvara probleme i proizvodi stanje utrke.
Rješenje problema filozofa blagovanja
Koristimo semafor za predstavljanje štapića za jelo i ovo doista djeluje kao rješenje problema filozofa objedovanja. Operacije čekanja i signala koristit će se za rješavanje problema Dining Philosophers, za odabir štapića može se izvršiti operacija čekanja dok se za puštanje štapića može izvršiti signalni semafor.
Semafor: Semafor je cjelobrojna varijabla u S, kojoj osim inicijalizacije pristupaju samo dvije standardne atomske operacije - čekanje i signal, čije definicije su sljedeće:
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></=> U početku se svaki element semafora C0, C1, C2, C3 i C4 inicijalizira na 1 jer su štapići na stolu i nitko ih od filozofa ne uzima u ruke.
Modificirajmo gornji kod problema Dining Philosopher korištenjem semaforskih operacija čekanja i signala, željeni kod izgleda ovako
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 } } U gornjem kodu, prva operacija čekanja izvodi se na take_chopstickC[i] i take_chopstickC [ (i+1) % 5]. Ovo pokazuje da sam filozof pokupio štapiće s lijeve i desne strane. Nakon toga se izvodi funkcija prehrane.
Po završetku jedenja od strane filozofa i the, operacija signala se izvodi na take_chopstickC[i] i take_chopstickC [ (i+1) % 5]. Ovo pokazuje da je filozof kojeg sam jeo i spustio i lijevi i desni štapić. Konačno, filozof ponovno počinje razmišljati.
Shvatimo kako gornji kod daje rješenje za problem filozofa blagovanja?
Neka je vrijednost i = 0 (početna vrijednost), pretpostavimo da Filozof P0 želi jesti, ući će u funkciju Filozof() i izvršiti Čekaj( uzmi_štapićC[i]); čineći ovo drži C0 štapić za jelo i reducira semafor C0 na 0 , nakon toga izvršiti Čekaj( uzmi_štapićC[(i+1) % 5] ); čineći ovo drži C1 štapić za jelo ( budući da je i =0, dakle (0 + 1) % 5 = 1) i reducira semafor C1 na 0
Slično tome, pretpostavimo da sada Philosopher P1 želi jesti, ući će u funkciju Philosopher() i izvršiti Čekaj( uzmi_štapićC[i]); čineći to pokušat će se zadržati C1 štapić za jelo ali to neće moći učiniti , budući da je vrijednost semafora C1 već postavljena na 0 od strane filozofa P0, stoga će ući u beskonačnu petlju zbog koje filozof P1 neće moći odabrati štapić C1, dok ako filozof P2 želi jesti, ući će u filozofa () funkcija i izvršavanje Čekaj( uzmi_štapićC[i]); čineći ovo drži C2 štapić za jelo i reducira semafor C2 na 0, nakon toga se izvršava Čekaj( uzmi_štapićC[(i+1) % 5] ); čineći ovo drži C3 štapić za jelo ( budući da je i =2, dakle (2 + 1) % 5 = 3) i reducira semafor C3 na 0.
Stoga gornji kod nudi rješenje za problem filozofa u blagovanju. Filozof može jesti samo ako su odmah dostupni i lijevi i desni štapići filozofa, inače filozof mora pričekati. Također, dva nezavisna filozofa mogu jesti istovremeno (tj. filozof P0 i P2, P1 i P3 & P2 i P4 mogu jesti istovremeno jer su svi neovisni procesi i slijede gornje ograničenje problema filozofa blagovanja)
Nedostatak gornjeg rješenja problema filozofa blagovanja
Iz gornjeg rješenja problema filozofa objedovanja, dokazali smo da dva susjedna filozofa ne mogu jesti u istom trenutku u vremenu. Nedostatak gornjeg rješenja je da ovo rješenje može dovesti do stanja zastoja. Ova situacija se događa ako svi filozofi istovremeno uzmu svoj lijevi štapić, što dovodi do stanja mrtve točke i nitko od filozofa ne može jesti.
Da biste izbjegli zastoj, neka od rješenja su sljedeća -
- Maksimalan broj filozofa na stolu ne smije biti veći od četiri, u ovom slučaju, štapić C4 će biti dostupan filozofu P3, tako da će P3 početi jesti i nakon završetka svoje procedure jedenja, spustit će oba štapića C3 i C4, tj. semafor C3 i C4 sada će se povećati na 1. Sada će filozof P2 koji je držao štapić C2 također imati štapić C3 na raspolaganju, stoga će slično odložiti svoj štapić nakon jela i omogućiti drugim filozofima da jedu.
- Filozof na parnoj poziciji treba odabrati desni štapić, a zatim lijevi štapić, dok bi filozof na neparnoj poziciji trebao odabrati lijevi štapić, a zatim desni štapić.
- Samo u slučaju da su oba štapića (lijevi i desni) dostupni u isto vrijeme, samo tada filozofu treba dopustiti da bira svoje štapiće
- Sva četiri početna filozofa (P0, P1, P2 i P3) trebaju odabrati lijevi štapić, a zatim desni štapić, dok posljednji filozof P4 treba odabrati desni štapić, a zatim lijevi štapić. Ovo će prisiliti P4 da prvi drži svoj desni štapić jer je desni štapić od P4 C0, kojeg već drži filozof P0 i njegova vrijednost je postavljena na 0, tj. C0 je već 0, zbog čega će P4 biti zarobljen u beskonačnom petlja i štapić C4 ostaju prazni. Stoga filozof P3 ima na raspolaganju i lijevi C3 i desni C4 štapić, stoga će početi jesti i spustit će svoja oba štapića kada završi i pustiti druge da jedu što uklanja problem zastoja.
Dizajn problema trebao je ilustrirati izazove izbjegavanja zastoja, stanje zastoja sustava je stanje u kojem nije moguć napredak sustava. Razmotrite prijedlog u kojem se svakom filozofu nalaže da se ponaša kako slijedi:
- Filozof je upućen da razmišlja dok lijeva vilica ne bude dostupna, kada je dostupna, drži je.
- Filozof je upućen da razmišlja dok desna vilica ne bude dostupna, kada je dostupna, drži je.
- Filozof je upućen da jede kada su obje vilice dostupne.
- zatim prvo spustite desnu vilicu
- zatim spustite lijevu vilicu
- ponovite ispočetka.