El problema del filòsof de menjador és el problema clàssic de sincronització que diu que Cinc filòsofs estan asseguts al voltant d'una taula circular i la seva feina és pensar i menjar alternativament. Al centre de la taula es col·loca un bol de fideus juntament amb cinc escuradents per a cadascun dels filòsofs. Per menjar un filòsof necessita tant el seu escuradents dret com un esquerre. Un filòsof només pot menjar si hi ha disponibles tant els escuradents esquerra com la dreta del filòsof. En cas que els escuradents del filòsof no estiguin disponibles, el filòsof deixa el seu escuradents (ja sigui esquerre o dret) i comença a pensar de nou.
El filòsof del menjador demostra una gran classe de problemes de control de concurrència, per tant, és un problema de sincronització clàssic.
Cinc filòsofs asseguts al voltant de la taula
Problema dels filòsofs de menjador - Entenem el problema dels filòsofs de menjador amb el codi següent, hem utilitzat la figura 1 com a referència per fer-vos entendre el problema exactament. Els cinc filòsofs estan representats com P0, P1, P2, P3 i P4 i cinc escuradents per 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 } } Parlem del codi anterior:
Suposem que el Filòsof P0 vol menjar, entrarà a la funció Philosopher() i s'executarà prendre_escuradents[i]; fent això aguanta Escuradents C0 després d'això s'executa pren_escuradents[ (i+1) % 5]; fent això aguanta Escuradents C1 ( ja que i = 0, per tant (0 + 1) % 5 = 1)
De la mateixa manera, suposem que ara el Filòsof P1 vol menjar, entrarà a la funció Philosopher() i executarà prendre_escuradents[i]; fent això aguanta Escuradents C1 després d'això s'executa pren_escuradents[ (i+1) % 5]; fent això aguanta Escuradents C2 ( ja que i = 1, per tant (1 + 1) % 5 = 2)
Però pràcticament Chopstick C1 no està disponible, ja que ja l'ha pres el filòsof P0, per tant, el codi anterior genera problemes i produeix condicions de carrera.
La solució del problema dels filòsofs de menjador
Utilitzem un semàfor per representar un escuradents i això realment actua com una solució del problema dels filòsofs de menjador. Les operacions d'espera i senyal s'utilitzaran per a la solució del problema dels filòsofs de menjador, per triar un escuradents es pot executar una operació d'espera mentre que per alliberar un escuradents es pot executar un semàfor de senyal.
Semàfor: un semàfor és una variable entera en S, a la qual només s'accedeix a la inicialització mitjançant dues operacions atòmiques estàndard: espera i senyal, les definicions de les quals són les següents:
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></=> Inicialment, cada element del semàfor C0, C1, C2, C3 i C4 s'inicialitza a 1 ja que els escuradents estan a la taula i no els recull cap filòsof.
Modifiquem el codi anterior del problema del filòsof de menjador utilitzant operacions de semàfor espera i senyal, el codi desitjat sembla
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 } } Al codi anterior, la primera operació d'espera es realitza a take_chopstickC[i] i take_chopstickC [(i+1)% 5]. Això mostra al filòsof que he agafat els escuradents d'esquerra i dreta. La funció de menjar es realitza després d'això.
En acabar de menjar pel filòsof i, l'operació de senyal es realitza a take_chopstickC[i] i take_chopstickC [(i+1) % 5]. Això demostra que el filòsof que he menjat i ha deixat els escuradents esquerre i dret. Finalment, el filòsof comença a pensar de nou.
Entenem com el codi anterior està donant una solució al problema del filòsof de menjador?
Sigui el valor de i = 0 (valor inicial), suposem que el filòsof P0 vol menjar, entrarà a la funció Philosopher() i executarà Espera (agafa_paletaC[i]); fent això aguanta Escuradents C0 i redueix el semàfor C0 a 0 , després d'això s'executa Espereu( preneu_bacsC[(i+1)% 5] ); fent això aguanta Escuradents C1 ( ja que i = 0, per tant (0 + 1) % 5 = 1) i redueix el semàfor C1 a 0
De la mateixa manera, suposem que ara el Filòsof P1 vol menjar, entrarà a la funció Philosopher() i executarà Espera (agafa_paletaC[i]); fent això intentarà aguantar Escuradents C1 però no ho podrà fer , com que el valor del semàfor C1 ja ha estat posat a 0 pel filòsof P0, per tant entrarà en un bucle infinit perquè el filòsof P1 no podrà agafar l'escuradents C1, mentre que si el filòsof P2 vol menjar, entrarà a Filòsof. () funcionar i executar Espera (agafa_paletaC[i]); fent això aguanta Escuradents C2 i redueix el semàfor C2 a 0, després d'això, s'executa Espereu( preneu_bacsC[(i+1)% 5] ); fent això aguanta Escuradents C3 (ja que i = 2, per tant (2 + 1) % 5 = 3) i redueix el semàfor C3 a 0.
Per tant, el codi anterior proporciona una solució al problema del filòsof de menjador, un filòsof només pot menjar si els escuradents del filòsof immediats i esquerres estan disponibles, sinó el filòsof ha d'esperar. També d'una vegada dos filòsofs independents poden menjar simultàniament (és a dir, un filòsof P0 i P2, P1 i P3 i P2 i P4 poden menjar simultàniament, ja que tots són processos independents i segueixen la restricció anterior del problema del filòsof de menjador)
L'inconvenient de la solució anterior del problema del filòsof de menjador
A partir de la solució anterior del problema del filòsof de menjador, hem demostrat que no hi ha dos filòsofs veïns que puguin menjar al mateix moment. L'inconvenient de la solució anterior és que aquesta solució pot conduir a una condició de bloqueig. Aquesta situació passa si tots els filòsofs trien el seu escuradents esquerre al mateix temps, la qual cosa porta a la condició d'impasse i cap dels filòsofs pot menjar.
Per evitar el bloqueig, algunes de les solucions són les següents:
- El nombre màxim de filòsofs a la taula no ha de ser superior a quatre, en aquest cas, l'escuradents C4 estarà disponible per al filòsof P3, de manera que P3 començarà a menjar i després d'acabar el procediment de menjar, deixarà els dos escuradents C3. i C4, és a dir, els semàfors C3 i C4 s'incrementaran ara a 1. Ara el filòsof P2 que sostenia l'escuradents C2 també tindrà disponible l'escuradents C3, per tant, de manera similar, deixarà el seu escuradents després de menjar i permetrà que altres filòsofs mengin.
- Un filòsof en una posició parell hauria de triar l'escuradents dret i després l'escuradents esquerre, mentre que un filòsof en una posició estranya hauria d'escollir l'escuradents esquerre i després l'escuradents dret.
- Només en cas que els dos escuradents (esquerra i dreta) estiguin disponibles al mateix temps, només llavors un filòsof hauria de poder triar els seus escuradents.
- Els quatre filòsofs inicials (P0, P1, P2 i P3) haurien de triar l'escuradents esquerre i després l'escuradents dret, mentre que l'últim filòsof P4 hauria de triar l'escuradents dret i després l'escuradents esquerre. Això obligarà a P4 a subjectar primer l'escuradents dret, ja que l'escuradents dret de P4 és C0, que ja està subjecte pel filòsof P0 i el seu valor s'estableix en 0, és a dir, C0 ja és 0, de manera que P4 quedarà atrapat en un infinit. bucle i escuradents C4 roman buit. Per tant, el filòsof P3 té disponibles els escuradents C3 esquerre i C4 dret, per tant començarà a menjar i deixarà els dos escuradents un cop hagi acabat i deixarà que els altres mengin, la qual cosa elimina el problema del bloqueig.
El disseny del problema va ser per il·lustrar els reptes d'evitar el bloqueig, un estat de bloqueig d'un sistema és un estat en el qual no és possible el progrés del sistema. Penseu en una proposta on cada filòsof tingui instruccions per comportar-se de la següent manera:
- Es demana al filòsof que pensi fins que la forquilla esquerra estigui disponible, quan estigui disponible, aguanteu-la.
- El filòsof rep instruccions per pensar fins que la forquilla adequada estigui disponible, quan estigui disponible, aguanteu-la.
- Es demana al filòsof que mengi quan les dues forquilles estiguin disponibles.
- després, baixeu primer la bifurcació dreta
- després, baixeu la bifurcació de l'esquerra
- repetir des del principi.