El problema de los filósofos (I)

Por todos es conocido el problema de los filósofos. Un problema clásico de la informática propuesto por Edsger Dijkstra para representar el problema de la sincronización de procesos en un sistema operativo. Este problema tiene multiples soluciones pero hoy voy a proponer una en concreto. Solución del problema sólo con semáforos binarios. Para ello vamos, primero, a recordar el planteamiento del problema.

 

Cinco filósofos se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Pero para comer los fideos son necesarios dos tenedores y cada filósofo puede tomar el tenedor que esté a su izquierda o derecha, uno por vez (o sea, no puede tomar los dos al mismo tiempo, pero puede tomar uno y después el otro). Si cualquier filósofo coge un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger el otro tenedor, para luego empezar a comer. Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.
Si todos los filósofos cogen el tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en la misma situación (esperando que alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este bloqueo mutuo se denomina deadlock.

Para implementar la solución al problema de los filósofos sólo con semáforos binarios tendremos que hacer que uno de ellos tenga código ligéramente diferente a los demás. Si tenemos n filósofos, en nuestro caso 5, n-1 (4) tendrán el mismo código i el n-ésimo (el quinto) ligéramente diferente. De este modo conseguimos que todos soliciten el tenedor en el mismo orden (primero el que tenga el índice menor). Así se rompe la espera circular y se evita el deadlock.

Filósofos del primero al n-1:

filosofo {
  for ( ; ; ) {
     pensar();
     wait(i);
     wait(i+1);
     comer();
     signal(i+1);
     signal(i);
  }
}

Filósofo n-ésimo:

filosofo {
  for ( ; ; ) {
     pensar();
     wait(i+1 mod n);
     wait(i);
     comer();
     signal(i);
     signal(i+1 mod n);
  }
}

6 respuestas a El problema de los filósofos (I)

  1. Alais dice:

    walaaaaa pero com es pot ser tant friki!!! xD

  2. alcojol dice:

    Cambiame el link al nuevo blog😉 Ahora no estoy seguro pero creo que esa solución (o una parecida) podía provocar deadlock, nosotros en S.O. usabamos una variante donde cada filósofo una vez que acababa de comer despertaba a sus dos compañeros laterales😛

  3. leibvitz dice:

    Habría deadlock si el último filósofo cogiera primero el quinto tenedor y después el primero, pero no es así. De la forma como está, el último filósofo quiere coger el primer tenedor primero y se queda bloqueado por que lo está usando el primer filósofo. Siempre se coge el tenedor con menor índice primero, así se evita el deadlock.

  4. […] filósofos (y II) Esta vez quiero colgar dos soluciones concretas al problema basándome en la explicación que hice hace algun tiempo. Para hacerlo he elegido dos lenguajes de programación que usan modelos de […]

  5. carlos dice:

    y como seria la solucion de este problem utilizando sockets de java???

  6. leibvitz dice:

    Hola. Tendríamos que especificar qué quiere decir “utilizando sockets”, mandando mensajes de coger y soltar los cubiertos?

    Saludos!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: