El problema de la cena de los filósofos

También conocido como «El problema de los filósofos cenando» o «El problema de los filósofos comensales», es un problema clásico de las ciencias de la computación propuesto por el cientí­fico Edsger Dijkstra* para representar los inconvenientes que plantea la sincronización de procesos en un sistema operativo.

Independientemente de tenedores o palillos (yo optaré por estos últimos), el enunciado serí­a el siguiente:

Hay cinco filósofos sentados alrededor de una mesa que pasan su vida cenando y pensando. Cada uno dispone de un plato de arroz y un palillo a la izquierda de su plato, pero para comer son necesarios dos palillos y cada filósofo sólo puede coger el que está a su izquierda o el que hay a su derecha. Con un solo palillo en la mano no tienen más remedio que esperar hasta que atrapen otro y puedan seguir comiendo.

Si dos filósofos adyacentes intentan tomar el mismo palillo a la vez se produce una condición de carrera: ambos compiten por lo mismo pero uno se queda sin comer.

Si todos los filósofos cogen el palillo de su derecha al mismo tiempo, todos se quedarán esperando eternamente porque alguien debe liberar el palillo que les falta, cosa que nadie hará porque todos se encuentran en la misma situación (esperando que alguno deje su palillo). Llegado esto, los filósofos se morirán de hambre. A este bloqueo mutuo se le denomina interbloqueo o deadlock.

El objetivo consiste en encontrar un recurso que permita que los filósofos nunca se mueran de hambre. Porque:

– Dos filósofos contiguos no pueden comer a la vez (exclusión mutua).

– Si un filósofo está comiendo, los contiguos no pueden hacerlo hasta que aquél termine (sincronización).

– El filósofo que termina de comer debe ceder los palillos para su posterior utilización (interbloqueo).

Este sencillo planteamiento resulta muy útil para los que estudian informática porque ayuda a pensar en los sistemas que tienen recursos limitados (en el ejemplo anterior los palillos son limitados) y en los clientes (programas y usuarios): hay que darles servicio (comida) a todos en un tiempo razonable.

Se trata de que los recursos sean utilizados de la manera más eficiente por todos los procesos implicados. Hay algoritmos para solucionarlo pero todos los métodos pasan por asignar prioridades y/o tiempos máximos de uso de los recursos.

La finalidad es demostrar que se presentarán problemas ante la falta de una apropiada sincronización y evitar la peligrosa condición de carrera.

Condición de carrera es una expresión que proviene del inglés «race condition», si bien serí­a mejor hablar de «estado de carrera», igual que se habla de estado de espera. Una condición de carrera describe el error que se produce en programas o circuitos lógicos cuando no han sido diseñados adecuadamente para su ejecución simultánea con otros.

Y el ejemplo tí­pico de interbloqueo se produce cuando dos procesos están esperando a que el otro realice una acción: ninguno llega a realizar la acción por estar a la espera del otro. Este tipo de errores de programación pueden ser aprovechados por exploits locales para vulnerar los sistemas.

*Edsger Wybe Dijkstra nació en Rotterdam (Holanda) en 1930. Estudió Fí­sica Teórica, trabajó en el Centro Matemático de Amsterdam y finalmente se entregó al estudio de la Programación (uno de los problemas con que se encontró es que ser programador no estaba oficialmente reconocido como profesión por aquel entonces).

A principios de los 70 aceptó un puesto como desarrollador en Estados Unidos, paí­s en el que permaneció hasta su muerte en 2002. Fueron numerosas sus contribuciones al avance de la programación informática.

Fuente principal | wikipedia