El problema del filósofo que come es el problema clásico de la sincronización, que dice que cinco filósofos están sentados alrededor de una mesa circular y su trabajo es pensar y comer alternativamente. En el centro de la mesa se coloca un plato de fideos junto con cinco palillos para cada uno de los filósofos. Para comerse un filósofo necesita tanto el palillo derecho como el izquierdo. Un filósofo sólo puede comer si tiene disponibles los palillos izquierdo y derecho inmediatos del filósofo. En caso de que los palillos izquierdo y derecho del filósofo no estén disponibles, entonces el filósofo deja su palillo (ya sea el izquierdo o el derecho) y comienza a pensar de nuevo.
El filósofo del comedor demuestra una gran clase de problemas de control de concurrencia, por lo que es un problema de sincronización clásico.
Cinco filósofos sentados alrededor de la mesa
El problema de los filósofos al cenar - Comprendamos el problema de los filósofos gastronómicos con el siguiente código. Hemos utilizado la figura 1 como referencia para que comprenda el problema exactamente. Los cinco filósofos están representados por P0, P1, P2, P3 y P4 y los cinco palillos por C0, C1, C2, C3 y 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 } } Analicemos el código anterior:
Supongamos que el Filósofo P0 quiere comer, ingresará en la función Filósofo() y ejecutará tomar_palillo[i]; al hacer esto se mantiene palillo C0 después de eso se ejecuta tomar_palillo[ (i+1) % 5]; al hacer esto se mantiene palillo C1 (ya que i =0, por lo tanto (0 + 1) % 5 = 1)
De manera similar, supongamos que ahora el Filósofo P1 quiere comer, ingresará en la función Filósofo() y ejecutará tomar_palillo[i]; al hacer esto se mantiene palillo C1 después de eso se ejecuta tomar_palillo[ (i+1) % 5]; al hacer esto se mantiene palillo C2 (ya que i =1, por lo tanto (1 + 1) % 5 = 2)
Pero Practically Chopstick C1 no está disponible porque ya lo tomó el filósofo P0, por lo que el código anterior genera problemas y produce una condición de carrera.
La solución al problema de los filósofos que cenan
Usamos un semáforo para representar un palillo y esto realmente actúa como una solución al problema de los filósofos gastronómicos. Las operaciones de espera y señal se utilizarán para la solución del problema de los filósofos del comedor; para recoger un palillo se puede ejecutar la operación de espera mientras que para soltar una señal de palillo se puede ejecutar el semáforo.
Semáforo: un semáforo es una variable entera en S, a la que, además de la inicialización, solo se accede mediante dos operaciones atómicas estándar: esperar y señalar, cuyas definiciones son las siguientes:
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></=> Inicialmente, cada elemento del semáforo C0, C1, C2, C3 y C4 se inicializa a 1 cuando los palillos están sobre la mesa y ninguno de los filósofos los recoge.
Modifiquemos el código anterior del Problema del Filósofo Comedor usando operaciones de semáforo de espera y señal, el código deseado se ve así
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 } } En el código anterior, la primera operación de espera se realiza en take_chopstickC[i] y take_chopstickC [(i+1) % 5]. Esto muestra al filósofo que he cogido los palillos de izquierda a derecha. Después de eso se realiza la función de comer.
Al finalizar la comida del filósofo i, la operación de señal se realiza en take_chopstickC[i] y take_chopstickC [(i+1) % 5]. Esto muestra que el filósofo comí y dejé los palillos izquierdo y derecho. Finalmente, el filósofo vuelve a pensar.
Entendamos cómo el código anterior ofrece una solución al problema del filósofo gastronómico.
Sea el valor de i = 0 (valor inicial), supongamos que el Filósofo P0 quiere comer, ingresará en la función Filósofo () y ejecutará. Espere (take_chopstickC[i]); al hacer esto se mantiene palillo C0 y reduce el semáforo C0 a 0 , después de eso se ejecuta Espera( take_chopstickC[(i+1) % 5] ); al hacer esto se mantiene palillo C1 (ya que i =0, por lo tanto (0 + 1) % 5 = 1) y reduce el semáforo C1 a 0
De manera similar, supongamos que ahora el Filósofo P1 quiere comer, ingresará a la función Filósofo() y ejecutará Espere (take_chopstickC[i]); al hacer esto intentará retener palillo C1 pero no podré hacer eso , Dado que el valor del semáforo C1 ya ha sido establecido en 0 por el filósofo P0, entrará en un bucle infinito por lo que el filósofo P1 no podrá coger el palillo C1, mientras que si el filósofo P2 quiere comer, entrará en el filósofo. () función y ejecutar Espere (take_chopstickC[i]); al hacer esto se mantiene palillo C2 y reduce el semáforo C2 a 0, después de eso, ejecuta Espera( take_chopstickC[(i+1) % 5] ); al hacer esto se mantiene palillo c3 (ya que i =2, por lo tanto (2 + 1) % 5 = 3) y reduce el semáforo C3 a 0.
Por lo tanto, el código anterior proporciona una solución al problema del filósofo que come. Un filósofo solo puede comer si los palillos izquierdo y derecho del filósofo están disponibles; de lo contrario, el filósofo debe esperar. Además, de una vez, dos filósofos independientes pueden comer simultáneamente (es decir, un filósofo P0 y P2, P1 y P3 y P2 y P4 puede comer simultáneamente ya que todos son procesos independientes y siguen la restricción anterior del problema del filósofo de la comida)
El inconveniente de la solución anterior del problema del filósofo del comedor.
A partir de la solución anterior del problema del filósofo comensal, hemos demostrado que no hay dos filósofos vecinos que puedan comer al mismo tiempo. El inconveniente de la solución anterior es que puede conducir a una condición de punto muerto. Esta situación ocurre si todos los filósofos toman su palillo izquierdo al mismo tiempo, lo que lleva a la condición de punto muerto y ninguno de los filósofos puede comer.
Para evitar un punto muerto, algunas de las soluciones son las siguientes:
- El número máximo de filósofos en la mesa no debe ser más de cuatro, en este caso, el palillo C4 estará disponible para el filósofo P3, por lo que P3 comenzará a comer y una vez finalizado su procedimiento de alimentación, dejará ambos palillos C3. y C4, es decir, el semáforo C3 y C4 ahora se incrementarán a 1. Ahora el filósofo P2 que sostenía el palillo C2 también tendrá el palillo C3 disponible, por lo tanto, de manera similar, dejará su palillo después de comer y permitirá que otros filósofos coman.
- Un filósofo en una posición par debe tomar el palillo derecho y luego el izquierdo, mientras que un filósofo en una posición impar debe tomar el palillo izquierdo y luego el derecho.
- Solo en el caso de que ambos palillos (izquierdo y derecho) estén disponibles al mismo tiempo, solo entonces se le debería permitir al filósofo recoger sus palillos.
- Los cuatro filósofos iniciales (P0, P1, P2 y P3) deben elegir el palillo izquierdo y luego el derecho, mientras que el último filósofo P4 debe elegir el palillo derecho y luego el izquierdo. Esto obligará a P4 a sostener primero su palillo derecho, ya que el palillo derecho de P4 es C0, que ya lo sostiene el filósofo P0 y su valor se establece en 0, es decir, C0 ya es 0, por lo que P4 quedará atrapado en un infinito. El bucle y el palillo C4 permanecen vacíos. Por lo tanto, el filósofo P3 tiene disponibles los palillos izquierdo C3 y derecho C4, por lo tanto, comenzará a comer y dejará ambos palillos una vez que termine y dejará que otros coman, lo que elimina el problema del punto muerto.
El diseño del problema fue ilustrar los desafíos de evitar el punto muerto, un estado de punto muerto de un sistema es un estado en el que no es posible ningún progreso del sistema. Considere una propuesta en la que a cada filósofo se le instruye a comportarse de la siguiente manera:
- Se le indica al filósofo que piense hasta que la bifurcación izquierda esté disponible, cuando esté disponible, manténgala presionada.
- El filósofo recibe instrucciones de pensar hasta que esté disponible la bifurcación correcta y, cuando esté disponible, sostenerla.
- El filósofo recibe instrucciones de comer cuando ambos tenedores estén disponibles.
- luego, baje primero el tenedor derecho
- luego, baje la bifurcación izquierda a continuación
- repetir desde el principio.