Contenidos:
Aplicación de solución al problema
Manual de Desarrollo de la aplicación
Pruebas realizadas para ver su correcto funcionamiento
La Cena de los Filósofos
Solución al problema La Cena de los Filósofos.
Presentación del problema:
He creado una aplicación que resuelve el problema de ‘La cena de los filósofos’ de una manera gráfica y mostrando los suficientes datos para ver como los filósofos (procesos) cenan y piensan. Esta aplicación se ejecuta infinitamente sin entrar en bloqueo o inanición de los procesos. Los procesos trabajan de manera justa obteniendo todos un número igual aproximado de veces de acceso a los recursos del sistema.
Al final de este artículo tienes el acceso al código
Enunciado del problema:
Cinco filósofos están sentados 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 el tenedor que está a su izquierda y el de su 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. El resto de filósofos que no está ni comiendo ni con un tenedor en la mano está pensando.
El problema consiste en inventar un algoritmo que permita comer a los filósofos.
Información sobre el problema:
A mí personalmente algo que hacía que no entendiera el problema era que para comer necesitaran dos tenedores, nadie come con dos tenedores, hasta que buscando información resulta que los filósofos son pensadores orientales y lo que realmente tienen que obtener no son tenedores sino palillos, de ahí que sean necesarios dos palillos para poder comer!
El problema de la cena de los filósofos o problema de los filósofos cenando (dining philosophers problem) es un problema clásico de las ciencias de la computación propuesto por Edsger Dijkstra en 1965 para representar el problema de la sincronización de procesos en un sistema operativo. Se trata de lanzar cinco procesos (filósofos) y ponerles a competir por obtener unos recursos. La solución consiste en configurar para que estos procesos (filósofos) puedan acceder a los recursos (dos tenedores) y desarrollar el trabajo (puedan comer). El problema es que el algoritmo de solución debe ser justo y no debe permitir que uno de ellos ocupe todo el sistema y no deje comer a los demás o que entre ellos se bloqueen y ninguno pueda tener acceso paralizando todo el trabajo.
Solución al problema:
Lógicamente si son cinco filósofos y hay cinco tenedores el algoritmo debe permitir que la mayor parte del tiempo haya dos filósofos comiendo y uno pensando. Pero además se deben tomar en cuenta diferentes factores:
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.
Resumiendo: El problema consiste en encontrar un algoritmo que permita que los filósofos nunca se mueran de hambre y que el comedor esté dando de comer constantemente y de una manera lo más eficiente posible.
Aplicación de solución al problema:
Una vez abierto, el programa presenta este aspecto:
La parte más alta llamada La Cena de los Filósofos es donde se va a representar la ejecución del programa. Contiene la información del código de colores empleado.
La parte central llamada Log es la encargada de mostrar la información referente al uso del programa y su ejecución. Si se selecciona el Checkbox de ‘Crear un log’ se ira mostrando la información de la ejecución en el Área de Texto. Además contamos con unos contadores de las veces que han comido cada uno de los filósofos muy útil para comprobar que se ejecuta de una manera justa.
La parte de abajo es la referente a los controles.
Podemos iniciar la ejecución simplemente pulsando el botón de Iniciar. También Pausar y podemos reanudar pulsando de nuevo en Iniciar. Además resetear en Reset. Tenemos la ventana de Créditos de la aplicación y el botón de Salir.
También tenemos la opción de generar un log activando el Checkbox:
Esta opción crea un nuevo recurso a compartir entre los hilos de ejecución al cual solo puede acceder uno. Solo puede escribir un hilo lo que hace cada vez, por tanto es mejor utilizarlo para estudiar el algoritmo y para una ejecución normal ejecutarlo sin seleccionar.
En la foto de arriba podemos ver al Log trabajando, los contadores de Cuántas veces han comido, podemos ver que el Filósofo 1 y Filósofo 3 están comiendo, que tiene los tenedores cogidos (tenedores en azul), que el Filósofo 4 acaba de entrar como comensal y que el Filósofo 5 y el Filósofo 2 están pensando.
La aplicación se ejecuta de continuo hasta que el usuario decide pararla pulsando Pausar.
No entra en bloqueo o inanición y casi siempre están comiendo dos filósofos.
Manual de Desarrollo de la aplicación:
Para esta aplicación tenía claro que debía de realizarse con monitores, para automatizar las ejecuciones. Al tratarse de varios hilos (filósofos) accediendo a varios recursos creo que es la manera más sencilla.
Al principio realice que los filósofos tenían que coger dos tenedores uno a su derecha y el que está a su izquierda pero esto bloqueaba el programa al poco tiempo de comenzar. Todos terminaba cogiendo el tenedor de la derecha y ninguno lo soltaba.
Entonces cree otro recurso previo de acceso (Portero del comedor) y era que existen cuatro plazas para comer y que los filósofos tiene que acceder previamente a una de esas plazas. Después deben conseguir los tenedores para comer. Esto funcionaba pero no era lo que yo esperaba. Al principio se ejecutaba bien, pero al cabo de unos minutos solo comía un filósofo cada vez y era muy complicado que volvieran a ser dos los que comieran.
Entonces completé el algoritmo implementando una nueva función synchronized en la clase Tenedor para coger el tenedor izquierdo en la cual si el tiempo aleatorio de espera para cogerlo se agota, el filósofo debe soltar el primer tenedor, abandonar el puesto de comensal y salir a pensar.
Y con esto se resuelve el problema y se completa el algoritmo: cada filósofo debe acceder al comedor consiguiendo un turno de los cuatro que tiene el portero del comedor, después debe coger un tenedor y si en un tiempo aleatorio consigue el otro tenedor come, pero si no lo consigue debe soltar el tenedor que tiene, abandonar el comedor y salir a pensar.
Así casi siempre hay dos filósofos comiendo y uno pensando, se puede ejecutar indefinidamente, y no entran en bloqueo.
Y como podemos ver las comidas son muy estables en cuanto a veces por cada filósofo:
Se han creado unos tiempos aleatorios para que las comidas o las esperas sean aleatorias y tengan unos tiempos de espera y la ejecución sea ralentizada y sea más fácil de ver.
También tiene una clase para la gestión de errores en los Thread.
El trabajo lo he planteado con un main.Main que es el encargado de arrancar y diferentes paquetes para estructurar la aplicación con cierta lógica:
Paquete: vistas contiene todas las interfaces gráficas y las clases relacionadas con la interface.
utilidades contiene todas las clases que aportan utilidad a la ejecución del programa.
logica contiene todas las clases que tiene la estructura principal del programa.
filósofos contiene todas las clases realcionadas con los hilos Filosofo y con los recursos Portero_del_Comedor y con los Tenedor.
images contiene todas las imágenes del programa.
La aplicación cuenta con el Javadoc.
Pruebas realizadas para ver su correcto funcionamiento:
Las pruebas realizadas han sido básicamente dejado correr la aplicación y observado que los patrones de ejecución se cumplen. Estos patrones son que siempre estén dos filósofos comiendo y que este patrón se cumple indefinidamente. También viendo el log generado y comprobando su coherencia.
También he realizado pruebas en Sistemas Operativos Linux y Windows con resultados positivos.
Enlaces al código:
El código está disponible en un repositorio de GitHub, así como la aplicación a través del siguiente enlace:
Video explicativo:
En este vídeo podrás ver este artículo de una forma más visual:
Fuentes y recursos:
Me he inspirado para este trabajo y para elaborar esta documentación en: