Problema de la cena de los filósofos

Ilustración del problema de la cena de los filósofos.

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. Cabe aclarar que la interpretación está basada 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. El problema de los 5 filósofos presenta una situación hipotética donde cinco filósofos se sientan alrededor de una mesa redonda, cada uno con un plato de pasta y un tenedor entre cada par de filósofos adyacentes. La dificultad radica en permitir que cada filósofo alterne entre dos estados, pensamiento y comer, sin que se produzcan bloqueos mutuos mientras intentan adquirir los tenedores adyacentes necesarios para comer.

En el contexto de las ciencias de la computación, los filósofos representan a los hilos de ejecución (threads) o procesos concurrentes, mientras que los tenedores simbolizan los recursos compartidos del sistema, tales como sectores de memoria, archivos, puertos de comunicación o registros de una base de datos.

Además del bloqueo mutuo (deadlock), donde todos los procesos se detienen indefinidamente esperando un recurso que posee otro, este problema ilustra el concepto de inanición (starvation). La inanición ocurre cuando un proceso no logra obtener los recursos necesarios para progresar debido a que otros procesos los acaparan constantemente. Por lo tanto, un algoritmo de solución óptimo no solo debe prevenir el estancamiento del sistema, sino también garantizar la equidad (fairness) en la asignación de recursos para que todos los hilos puedan ejecutar su tarea eventualmente.

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.

Diversas soluciones posibles

La resolución exitosa de este problema implica abordar cuestiones adicionales relacionadas con la comunicación entre nodos, la consistencia de los datos distribuidos y la tolerancia a fallos. Además, requiere el diseño e implementación de algoritmos de sincronización y coordinación que garanticen la coherencia y eficiencia en la ejecución de procesos distribuidos. En este contexto, la comprensión profunda de los principios de concurrencia y coordinación es esencial para la construcción y el mantenimiento de sistemas distribuidos robustos y eficientes.

• Por turno cíclico

Se empieza por un filósofo, que si quiere puede comer y después pasa su turno al de la derecha. Cada filósofo sólo puede comer en su turno. Problema: si el número de filósofos es muy alto, uno puede morir de hambre antes de su turno.

• Varios turnos

Se establecen varios turnos. Para hacerlo más claro supongamos que cada filósofo que puede comer (es su turno) tiene una ficha que después pasa a la derecha. Si por ejemplo hay 7 comensales podemos poner 3 fichas en posiciones alternas (entre dos de las fichas quedarían dos filósofos).

Se establecen turnos de tiempo fijo. Por ejemplo cada 5 minutos se pasan las fichas (y los turnos) a la derecha.

Con base al tiempo que suelen tardar los filósofos en comer y en volver a tener hambre, el tiempo de turno establecido puede hacer que sea peor solución que la anterior. Si el tiempo de turno se aproxima al tiempo medio que tarda un filósofo en comer esta variante da muy buenos resultados. Si además el tiempo medio de comer es similar al tiempo medio en volver a tener hambre la solución se aproxima al óptimo.

• Colas de tenedores

Cuando un filósofo quiere comer se pone en la cola de los dos tenedores que necesita. Cuando un tenedor está libre lo toma. Cuando toma los dos tenedores, come y deja libre los tenedores.

Visto desde el otro lado, cada tenedor sólo puede tener dos filósofos en cola, siempre los mismos.

Esto crea el problema comentado de que si todos quieren comer a la vez y todos empiezan tomando el tenedor de su derecha se bloquea el sistema (deadlock).

• Resolución de conflictos en colas de tenedores

Cada vez que un filósofo tiene un tenedor espera un tiempo aleatorio para conseguir el segundo tenedor. Si en ese tiempo no queda libre el segundo tenedor, suelta el que tiene y vuelve a ponerse en cola para sus dos tenedores.

Si un filósofo A suelta un tenedor (porque ha comido o porque ha esperado demasiado tiempo con el tenedor en la mano) pero todavía desea comer, vuelve a ponerse en cola para ese tenedor. Si el filósofo adyacente B está ya en esa cola de tenedor (tiene hambre) lo toma y si no vuelve a cogerlo A.

Es importante que el tiempo de espera sea aleatorio o se mantendrá el bloqueo del sistema.

• El portero del comedor

Se indica a los filósofos que abandonen la mesa cuando no tengan hambre y que no regresen a ella hasta que vuelvan a estar hambrientos (cada filósofo siempre se sienta en la misma silla). La misión del portero es controlar el número de filósofos en la sala, limitando su número a n-1, pues si hay n-1 comensales seguro que al menos uno puede comer con los dos tenedores.

Pseudocódigo

int tenedores[5];

int estado_filosofos[5];

void cambiar_estado(int filosofo, int nuevo_estado) {
    estado_filosofos[filosofo] = nuevo_estado;
}

int estado_izquierdo(int filosofo) {
    return estado_filosofos[(filosofo + 4) % 5];
}

int estado_derecho(int filosofo) {
    return estado_filosofos[(filosofo + 1) % 5];
}

void intentar_comer(int filosofo) {
    if (estado_filosofos[filosofo] == 1 && estado_izquierdo(filosofo) != 2 && estado_derecho(filosofo) != 2) {
        cambiar_estado(filosofo, 2);
        tomar_tenedores(filosofo);
    }
}

void dejar_comer(int filosofo) {
    cambiar_estado(filosofo, 0);
    dejar_tenedores(filosofo);
    intentar_comer((filosofo + 4) % 5);
    intentar_comer((filosofo + 1) % 5);
}

void filosofo(int id) {
    while (true) {
        pensar();
        cambiar_estado(id, 1);
        intentar_comer(id);
        esperar();
        dejar_comer(id);
    }
}

Aplicaciones en sistemas distribuidos y embebidos

El problema de la cena de los filósofos tiene aplicaciones prácticas en una amplia gama de sistemas distribuidos y embebidos, donde la correcta gestión de los recursos garantiza tanto la coherencia de los datos como el funcionamiento adecuado del sistema. En un sistema embebido, por ejemplo, como los utilizados en automóviles o electrodomésticos, los sensores actúan como productores, generando datos que son consumidos por un controlador central. Estos sistemas requieren que múltiples procesos se coordinen adecuadamente para acceder a los recursos de manera ordenada y evitar condiciones de carrera. En un entorno distribuido, una interrupción en la coordinación entre nodos o procesos puede afectar la integridad de los datos y el rendimiento general del sistema. Por esta razón, los problemas de sincronización en el problema de los filósofos ayudan a ilustrar y resolver desafíos críticos en la asignación de recursos en sistemas complejos y distribuidos.

En sistemas distribuidos al llevarlo a la práctica, este problema es de mucha ayuda, por ejemplo, en sistemas en donde estos deben responder al instante, por lo regular se hace que los procesos se turnen de forma controlada. Es decir que, obligamos a que las tareas en cada nos se intercalen mediante tiempos fijos y predecibles, así nos aseguramos de que todos los grupos tengan su oportunidad de trabajar y evitamos que alguna tarea se quede esperando su turno para siempre.

Mientras que, cuando tenemos redes donde los procesos manejan diferentes prioridades, funciona usar temporizadores al azar, o sea que, si un proceso llega a no conseguir todos los recursos que ocupa para terminar su tarea, tiene que soltar esos recursos y esperar un tiempo aleatorio antes de poder volver a intentar. Esto es muy importante al diseñar protocolos de red porque rompe los ciclos de espera circular, bajando el riesgo a gran medida de que se presente un deadlock que congele todos los nodos. Todo esto impacta directamente en la programación, dado que a nivel interno, los kernels de los sistemas operativos ya usan estas lógicas para manejar miles de bloqueos al mismo tiempo, evitando deadlocks y que los datos compartidos se corrompan. Por ello cuando programamos de manera concurrente, los lenguajes ya tienen herramientas listas para usarse, como lo es el manejo de hilos o colas de mensajes optimizando el "apartado" de recursos de forma segura, sin causar condiciones de carrera y sin trabar al resto del sistema.

En el contexto de la planificación de tareas en sistemas operativos y distribuidos, el problema de los filósofos sirve como base para entender conceptos relacionados con la exclusión mutua y la evitación de interbloqueos. Está estrechamente relacionado con algoritmos de planificación como EDF (Earliest Deadline First) , donde se busca cumplir con restricciones temporales en entornos aperiódicos y periódicos, tanto preemptivos como no preemptivos. Este problema clásico ayuda a ilustrar los desafíos de sincronización que surgen cuando múltiples procesos compiten por recursos limitados.

Ventajas y desventajas en sistemas distribuidos

Impacto del problema de la cena de los filósofos en sistemas distribuidos

Aspecto	Ventajas	Desventajas
Sincronización	Permite estudiar mecanismos de coordinación entre procesos concurrentes.	La sincronización excesiva puede reducir el rendimiento del sistema.
Gestión de recursos	Ayuda a diseñar estrategias seguras para compartir recursos.	Puede provocar bloqueos mutuos si no existe un control adecuado.
Descentralización	Facilita el análisis de sistemas sin un controlador central.	La toma de decisiones distribuida aumenta la complejidad.
Prevención de interbloqueos	Permite desarrollar algoritmos para evitar deadlocks.	Algunas soluciones pueden generar inanición de procesos.
Escalabilidad	El modelo puede adaptarse a múltiples nodos y procesos distribuidos.	El aumento de nodos incrementa la dificultad de coordinación.
Sistemas concurrentes	Ayuda a comprender la ejecución simultánea de tareas.	Los errores de concurrencia pueden afectar la estabilidad del sistema.

El problema de la cena de los filósofos continúa siendo utilizado como modelo conceptual para analizar desafíos relacionados con concurrencia, sincronización y asignación de recursos en sistemas distribuidos modernos. Su estudio permite comprender las dificultades que surgen cuando múltiples procesos compiten simultáneamente por recursos compartidos.

Extensión a sistemas complejos y simulación distribuida

Aunque el problema de la cena de los filósofos se plantea originalmente con cinco individuos en una mesa circular para ilustrar el control de concurrencia, su abstracción es un modelo fundamental para el estudio de la complejidad y la gestión de recursos en entornos computacionales masivos.

Enfoque de sistemas multiagentes

El problema se analiza naturalmente bajo el paradigma de los sistemas multiagentes (SMA). En este contexto, cada filósofo es un "agente" autónomo que toma decisiones basándose en percepciones estrictamente locales (la disponibilidad de los tenedores a su lado) sin poseer un conocimiento global del estado de la mesa.

Cuando este modelo se generaliza y escala a miles de agentes interactuando a través de grafos o topologías de red irregulares (sustituyendo la mesa circular), se transforma en el modelo de un sistema complejo. En estas dimensiones, las reglas locales de adquisición de recursos generan comportamientos macroscópicos de emergencia. Pequeños retrasos en la liberación de un recurso pueden desencadenar efectos no lineales, propagando cascadas de inanición (starvation) o bloqueos a lo largo de toda la red de manera impredecible.

Desafíos en la simulación distribuida

En el ámbito de la computación y la Simulación distribuida, el problema de los filósofos trasciende la categoría de ejemplo académico para representar un desafío de arquitectura técnica. Cuando una simulación a gran escala (como la predicción climática o el modelado de redes de telecomunicaciones) se fragmenta en múltiples servidores, cada nodo actúa como un filósofo que necesita solicitar datos o sincronizarse con nodos adyacentes para avanzar en su cálculo de tiempo.

Si los nodos esperan indefinidamente los datos de sus vecinos, toda la simulación puede sufrir un bloqueo mutuo a nivel de red. Para solucionar esto, los arquitectos de sistemas diseñan algoritmos de sincronización de tiempo inspirados en las soluciones a este problema. Por ejemplo, en los algoritmos de simulación distribuida conservadora (como el algoritmo de Chandy-Misra-Bryant), los procesos lógicos intercambian constantemente "mensajes nulos" que actúan como promesas temporales, rompiendo la espera circular de los recursos y garantizando que la simulación global pueda avanzar sin detenerse.

Implementación práctica en lenguajes de programación

El problema de los cinco filósofos es un excelente modelo educativo para comprender la programación concurrente y la sincronización de procesos en lenguajes como Java o Python. A través de este problema, los desarrolladores pueden aprender a implementar estructuras de sincronización, como semáforos y mutex, y a gestionar el acceso a los recursos de manera segura y eficiente. En Java, por ejemplo, la clase BlockingQueue facilita la sincronización entre hilos, permitiendo que un proceso espere hasta que haya recursos disponibles sin bloquear el acceso de otros procesos. En Python, el módulo threading proporciona herramientas para implementar concurrencia y exclusión mutua, asegurando que los recursos compartidos sean accesibles sin riesgo de condiciones de carrera. Estos lenguajes permiten simular el problema de los cinco filósofos para observar cómo diferentes soluciones de sincronización afectan la eficiencia y evitan el interbloqueo, aplicando estos conocimientos en el diseño de sistemas embebidos y distribuidos.

Variantes y extensiones del problema de los filósofos

El problema de los cinco filósofos tiene diversas variantes que permiten explorar soluciones más complejas a los desafíos de sincronización y concurrencia en sistemas distribuidos. Por ejemplo:

1. Añadir un Portero o "Footman": En esta variante, se introduce un portero que permite que solo cuatro filósofos se sienten a la mesa al mismo tiempo. Esta restricción reduce las probabilidades de interbloqueo, ya que siempre hay un filósofo que puede acceder a ambos tenedores, evitando que todos esperen simultáneamente por el tenedor de su vecino. Este enfoque muestra cómo una pequeña restricción en el acceso a los recursos puede mejorar significativamente la eficiencia y seguridad en la concurrencia.
2. Uso de Temporizadores Aleatorios para Evitar el Interbloqueo: Otra solución consiste en permitir que cada filósofo suelte los tenedores después de esperar un tiempo aleatorio si no puede obtener ambos. Esto simula una espera probabilística que reduce la posibilidad de interbloqueo y se utiliza en sistemas donde los procesos deben ceder los recursos temporalmente si no logran completar su tarea en un período específico. Esta técnica es útil en sistemas distribuidos donde los procesos tienen diferentes prioridades y tiempos de espera.
3. Modelo de "Pensar-Comer" Cíclico: Esta variante sugiere que cada filósofo alterna entre pensar y comer en un ciclo fijo o programado, de manera que los recursos se distribuyen en intervalos predecibles. Este enfoque se usa en sistemas de tiempo real donde los procesos necesitan sincronizarse en intervalos regulares para evitar el bloqueo y garantizar que todos accedan a los recursos equitativamente. Por ejemplo, en sistemas embebidos de monitoreo de sensores, esta estrategia permite que todos los dispositivos tengan acceso equitativo a la red o a los recursos de procesamiento sin esperar indefinidamente.

Véase también

• Problema del barbero durmiente

Enlaces externos

• Wikilibros alberga un libro o manual sobre Programación en Ada.

• Ejemplos de problemas clásicos de sincronización

• Datos: Q865867
• Multimedia: Dining philosophers / Q865867