Solución del problema de la cena de los filósofos

Problema de la cena de los filósofos[pic 2]

Este, también conocido como el “problema de los filósofos cenando”, es un problema clásico de las ciencias de computación el cual fue propuesto por Edsger Dijkstra en 1965 para representar el problema encontrado en la sincronización de procesos en un sistema operativo.

Su interpretación está basado en pensadores chinos, quienes comían con dos palillos, donde es más lógico que se necesite el del comensal que se siente al lado para poder comer, a pesar de esto en el lado occidental se tiende a cambiar estos palillos por tenedores.

Enunciado 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. Para comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su izquierda y derecha. Si cualquier filósofo toma un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda tomar 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 toman 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 interbloqueo o deadlock.

El problema consiste en encontrar un algoritmo que permita que los filósofos nunca se mueran de hambre.

Contamos con:

• 5 filósofos (procesos).
• 5 tenedores (recursos).
• 1 mesa redonda en la que todos están sentados.

Posible solución[pic 3]

Contando con un total de 5 filósofos, 1 tenedor por cada uno localizado a su derecha, y una mesa redonda; podríamos aplicar una condición de espera circular, donde aplicándoles un turno cíclico, la misma prioridad para comer y el mismo tiempo para utilizar los tenedores, estos podrían ir comiendo uno por uno de manera cíclica, volviendo a comer tan pronto se complete el ciclo, además de poseer tiempo para pensar mientras no se encuentran en turno.

[pic 4]

Ejemplificación

Luego de asignados los turnos:

1. El filósofo #1 tomaría el tenedor a su derecha y el tenedor a su izquierda (perteneciente al filósofo 5, pero libre o en desuso), comería 1 vez, y a continuación procedería a liberar los tenedores en los respectivos lugares de donde los tomo.
2. El filósofo #2 tomaría el tenedor a su derecha y el tenedor a su izquierda (perteneciente al filósofo 1, pero libre o en desuso), comería 1 vez, y a continuación procedería a liberar los tenedores en los respectivos lugares de donde los tomo.
3. El filósofo #3 tomaría el tenedor a su derecha y el tenedor a su izquierda (perteneciente al filósofo 2, pero libre o en desuso), comería 1 vez, y a continuación procedería a liberar los tenedores en los respectivos lugares de donde los tomo.
4. El filósofo #4 tomaría el tenedor a su derecha y el tenedor a su izquierda (perteneciente al filósofo 3, pero libre o en desuso), comería 1 vez, y a continuación procedería a liberar los tenedores en los respectivos lugares de donde los tomo.
5. El filósofo #5 tomaría el tenedor a su derecha y el tenedor a su izquierda (perteneciente al filósofo 4, pero libre o en desuso), comería 1 vez, y a continuación procedería a liberar los tenedores en los respectivos lugares de donde los tomo.

Ya completado el ciclo, el filoso #1 tendría la oportunidad de comer nuevamente siguiendo los parámetros establecidos, y así continuaría el ciclo hasta estos acabar con sus respectivos platos de fideos, y de igual modo tendrían tiempo para pensar sin morir de hambre. Los parámetros a seguir fueron:

...