Solución Dining-Philosophers usando monitores

Requisito previo: Monitor , Sincronización de procesos

Problema comedor-filósofos: N filósofos sentados alrededor de una mesa circular

• Hay un palillo entre cada filósofo
• Un filósofo debe recoger sus dos palillos más cercanos para poder comer
• Un filósofo debe tomar primero un palillo, luego el segundo, no los dos a la vez.

Necesitamos un algoritmo para asignar estos recursos limitados (palillos) entre varios procesos (filósofos) de modo que la solución esté libre de bloqueos y de inanición.

Existe algún algoritmo para resolver Comedor – Problema del filósofo, pero pueden tener una situación de punto muerto. Además, una solución libre de interbloqueos no está necesariamente libre de hambre. Los semáforos pueden provocar interbloqueos debido a errores de programación. Los monitores por sí solos no son suficientes para resolver esto, necesitamos monitores con variables de condición

Solución basada en monitor para los filósofos de la comida

Ilustramos los conceptos de monitor presentando una solución libre de puntos muertos para el problema de los filósofos comedores. Monitor se utiliza para controlar el acceso a variables de estado y variables de condición. Solo indica cuándo entrar y salir del segmento. Esta solución impone la restricción de que un filósofo puede tomar sus palillos solo si ambos están disponibles.

Para codificar esta solución, necesitamos distinguir entre tres estados en los que podemos encontrar a un filósofo. Para ello, introducimos la siguiente estructura de datos:

PENSAMIENTO – Cuando el filósofo no quiere acceder a ninguna de las dos bifurcaciones.

HAMBRE – Cuando el filósofo quiere entrar en la sección crítica.

COMER – Cuando el filósofo tiene los dos tenedores, es decir, ha entrado en la sección.

La filósofa puedo establecer la variable estado[i] = COMIENDO solo si sus dos vecinos no están comiendo
(estado[(i+4) % 5] != COMIENDO) y (estado[(i+1) % 5] != COMIENDO ).

// Dining-Philosophers Solution Using Monitors
monitor DP
{
    status state[5];
    condition self[5];
  
    // Pickup chopsticks
    Pickup(int i)
    {
        // indicate that I’m hungry
        state[i] = hungry;
  
        // set state to eating in test()
        // only if my left and right neighbors 
        // are not eating
        test(i);
  
        // if unable to eat, wait to be signaled
        if (state[i] != eating)
            self[i].wait;
    }
  
    // Put down chopsticks
    Putdown(int i)
    {
  
        // indicate that I’m thinking
        state[i] = thinking;
  
        // if right neighbor R=(i+1)%5 is hungry and
        // both of R’s neighbors are not eating,
        // set R’s state to eating and wake it up by 
        // signaling R’s CV
        test((i + 1) % 5);
        test((i + 4) % 5);
    }
  
    test(int i)
    {
  
        if (state[(i + 1) % 5] != eating
            && state[(i + 4) % 5] != eating
            && state[i] == hungry) {
  
            // indicate that I’m eating
            state[i] = eating;
  
            // signal() has no effect during Pickup(),
            // but is important to wake up waiting
            // hungry philosophers during Putdown()
            self[i].signal();
        }
    }
  
    init()
    {
  
        // Execution of Pickup(), Putdown() and test()
        // are all mutually exclusive,
        // i.e. only one at a time can be executing
for
    i = 0 to 4
  
        // Verify that this monitor-based solution is
        // deadlock free and mutually exclusive in that
        // no 2 neighbors can eat simultaneously
        state[i] = thinking;
    }
} // end of monitor

El programa anterior es una solución de monitor para el problema del comedor-filósofo.

También tenemos que declarar

condition self[5];

Esto le permite a la filósofa i retrasarse cuando tiene hambre pero no puede obtener los palillos que necesita. Ahora estamos en posición de describir nuestra solución al problema de los filósofos comedores. La distribución de los palillos está controlada por el monitor Dining Philosophers. Cada filósofo, antes de empezar a comer, debe invocar la operación recoger(). Este acto puede dar lugar a la suspensión del proceso filosófico. Después de completar con éxito la operación, el filósofo puede comer. Después de esto, el filósofo invoca la operación putdown(). Por lo tanto, filósofo i debo invocar las operaciones recoger() y poner() en la siguiente secuencia:

DiningPhilosophers.pickup(i);
              ...
              eat
              ...
DiningPhilosophers.putdown(i);

Es fácil demostrar que esta solución asegura que no haya dos vecinos comiendo simultáneamente y que no se produzcan interbloqueos. Notamos, sin embargo, que es posible que un filósofo muera de hambre.

Este artículo es una contribución de Mayank Rana . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.