Problem obedovalnega filozofa je klasični problem sinhronizacije, ki pravi, da pet filozofov sedi za okroglo mizo in njihova naloga je, da razmišljajo in jedo izmenično. Na sredino mize je postavljena skleda rezancev skupaj s petimi palčkami za vsakega od filozofov. Da bi filozof jedel, potrebuje tako desno kot levo palčko. Filozof lahko jé le, če sta na voljo leva in desna palčka filozofa. V primeru, da tako leva kot desna paličica filozofa nista na voljo, filozof odloži svojo (bodisi levo ali desno) paličico in začne znova razmišljati.
Filozof obedovanja prikazuje velik razred problemov nadzora sočasnosti, zato gre za klasični problem sinhronizacije.
Pet filozofov sedi za mizo
Problem filozofov obedovanja - Razumejmo težavo Dining Philosophers s spodnjo kodo, sliko 1 smo uporabili kot referenco, da boste natančno razumeli težavo. Pet filozofov je predstavljenih kot P0, P1, P2, P3 in P4, pet palčk pa kot C0, C1, C2, C3 in 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 } } Pogovorimo se o zgornji kodi:
Recimo, da Philosopher P0 želi jesti, bo vstopil v funkcijo Philosopher() in izvedel vzemi_palčko[i]; s tem drži C0 palčka po tem se izvede vzemi_palčko[ (i+1) % 5]; s tem drži C1 palčka (ker je i =0, torej (0 + 1) % 5 = 1)
Podobno predpostavimo, da zdaj Philosopher P1 želi jesti, vstopil bo v funkcijo Philosopher() in izvedel vzemi_palčko[i]; s tem drži C1 palčka po tem se izvede vzemi_palčko[ (i+1) % 5]; s tem drži C2 palčka (ker je i =1, torej (1 + 1) % 5 = 2)
Vendar Practically Chopstick C1 ni na voljo, saj ga je že prevzel filozof P0, zato zgornja koda ustvarja težave in ustvarja stanje dirke.
Rešitev problema Dining Philosophers
Semafor uporabljamo za predstavitev jedilne palčke in to resnično deluje kot rešitev problema Dining Philosophers. Operaciji čakanja in signala bosta uporabljeni za rešitev problema Dining Philosophers, za izbiranje palčke je mogoče izvesti čakalno operacijo, medtem ko je za sprostitev palčke mogoče izvesti signalni semafor.
Semafor: Semafor je celoštevilska spremenljivka v S, do katere poleg inicializacije dostopata samo dve standardni atomski operaciji - čakanje in signal, katerih definiciji sta naslednji:
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></=> Na začetku se vsak element semaforja C0, C1, C2, C3 in C4 inicializira na 1, saj so palčke na mizi in jih nihče od filozofov ne vzame v roke.
Spremenimo zgornjo kodo problema Dining Philosopher z uporabo semaforskih operacij čakanja in signala, želena koda izgleda takole
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 } } V zgornji kodi se prva operacija čakanja izvede na take_chopstickC[i] in take_chopstickC [ (i+1) % 5]. To kaže, da sem filozof pobral palčke z leve in desne. Po tem se izvaja prehranjevalna funkcija.
Ko filozof i the zaključi s prehranjevanjem, se operacija signala izvede na take_chopstickC[i] in take_chopstickC [ (i+1) % 5]. To kaže, da je filozof i jedel in odložil levo in desno palčko. Končno začne filozof znova razmišljati.
Razumejmo, kako zgornja koda ponuja rešitev za problem filozofa obedovanja?
Naj bo vrednost i = 0 (začetna vrednost), Recimo, da Philosopher P0 želi jesti, bo vstopil v funkcijo Philosopher() in izvedel Počakaj( vzemi_palčkoC[i]); s tem drži C0 palčka in zmanjša semafor C0 na 0 , po tem se izvede Počakaj( vzemi_palčkoC[(i+1) % 5]); s tem drži C1 palčka ( ker je i =0, torej (0 + 1) % 5 = 1) in reducira semafor C1 na 0
Podobno, recimo, da zdaj Philosopher P1 želi jesti, bo vstopil v funkcijo Philosopher() in izvedel Počakaj( vzemi_palčkoC[i]); s tem bo poskušal zadržati C1 palčka vendar tega ne bo mogel storiti , ker je vrednost semaforja C1 filozof P0 že nastavil na 0, bo vstopil v neskončno zanko, zaradi katere filozof P1 ne bo mogel izbrati palčke C1, če pa bo filozof P2 hotel jesti, bo vstopil v filozofa () funkcijo in izvedite Počakaj( vzemi_palčkoC[i]); s tem drži C2 palčka in zmanjša semafor C2 na 0, po tem pa se izvede Počakaj( vzemi_palčkoC[(i+1) % 5]); s tem drži C3 palčka ( ker je i =2, torej (2 + 1) % 5 = 3) in reducira semafor C3 na 0.
Zato zgornja koda ponuja rešitev za problem filozofa obedovanja. Filozof lahko jé le, če sta na voljo leva in desna palčka filozofa, sicer mora filozof počakati. Tudi naenkrat lahko jesta dva neodvisna filozofa hkrati (tj. filozof P0 in P2, P1 in P3 & P2 in P4 lahko jedo hkrati, saj so vsi neodvisni procesi in sledijo zgornji omejitvi problema filozofa obedovanja)
Pomanjkljivost zgornje rešitve problema jedilničnega filozofa
Iz zgornje rešitve problema filozofa obedovanja smo dokazali, da dva sosednja filozofa ne moreta jesti v istem trenutku. Pomanjkljivost zgornje rešitve je, da lahko ta rešitev povzroči stanje zastoja. Ta situacija se zgodi, če vsi filozofi hkrati izberejo svojo levo palčko, kar vodi v stanje slepe ulice in nobeden od filozofov ne more jesti.
Da bi se izognili zastoju, so nekatere rešitve naslednje -
- Največje število filozofov na mizi ne sme biti večje od štirih, v tem primeru bo palčka C4 na voljo filozofu P3, tako da bo P3 začel jesti in po koncu postopka prehranjevanja bo odložil obe palčki C3. in C4, tj. semaforja C3 in C4 bosta zdaj povečana na 1. Zdaj bo imel filozof P2, ki je držal palčko C2, na voljo tudi palčko C3, zato bo podobno odložil svojo palčko po jedi in omogočil drugim filozofom, da jedo.
- Filozof na sodi poziciji naj izbere desno palčko in nato levo palčko, medtem ko mora filozof na lihi poziciji izbrati levo palčko in nato desno palčko.
- Samo v primeru, da sta obe palčki (leva in desna) na voljo hkrati, le takrat sme filozof izbrati svoje palčke.
- Vsi štirje začetni filozofi (P0, P1, P2 in P3) bi morali izbrati levo palčko in nato desno palčko, medtem ko bi moral zadnji filozof P4 izbrati desno palčko in nato levo palčko. To bo prisililo P4, da najprej drži svojo desno palčko, saj je desna palčka P4 C0, ki jo že drži filozof P0 in je njena vrednost nastavljena na 0, tj. C0 je že 0, zaradi česar bo P4 ujet v neskončno zanka in palčka C4 ostane prazna. Zato ima filozof P3 na voljo levo C3 in desno C4 palčko, zato bo začel jesti in bo odložil obe palčki, ko bo končal, ter pustil drugim jesti, kar odpravi problem zastoja.
Zasnova problema je bila ponazoriti izzive izogibanja zastoju, stanje zastoja sistema je stanje, v katerem napredek sistema ni mogoč. Razmislite o predlogu, kjer je vsakemu filozofu naročeno, naj se obnaša takole:
- Filozofu je naročeno, naj razmišlja, dokler leve vilice niso na voljo, ko so na voljo, jih drži.
- Filozofu je naročeno, naj razmišlja, dokler ni na voljo prava vilica, ko je na voljo, jo drži.
- Filozof dobi navodilo, naj jé, ko sta na voljo obe vilici.
- nato najprej odložite desne vilice
- nato odložite leve vilice
- ponovi od začetka.