El Blog de Leibvitz Ssariews

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);
  }
}

This entry was posted on jueves, 26 de octubre de 2006 at 19:19 and is filed under Informàtica. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.