La cena de los filósofos

1. El problema

La cena de los filósofos es un problema de sincronización propuesto por Dijkstra en 1965. Cinco filósofos se sientan alrededor de una mesa circular con cinco tenedores (uno entre cada par de filósofos). Cada filósofo alterna entre pensar y comer. Para comer, necesita tomar los dos tenedores adyacentes (el de su izquierda y el de su derecha). Después de comer, suelta los tenedores y vuelve a pensar.

El problema es: diseñar un protocolo que permita a los filósofos comer sin que se produzca un interbloqueo (deadlock) ni inanición (starvation).

El filósofo F0 necesita T4 y T0. F1 necesita T0 y T1. F2 necesita T1 y T2. F3 necesita T2 y T3. F4 necesita T3 y T4.

2. La solución ingenua (que se bloquea)

La solución más natural es: tomar el tenedor izquierdo, luego el derecho, comer, soltar ambos:

/* Cada filósofo i tiene tenedores i y (i+1) % 5. */
void filosofo(int id) {
    while (1) {
        pensar();
        tomar_tenedor(id);           /* tenedor izquierdo */
        tomar_tenedor((id + 1) % 5); /* tenedor derecho */
        comer();
        soltar_tenedor(id);
        soltar_tenedor((id + 1) % 5);
    }
}

Esta solución se bloquea (deadlock) si todos los filósofos toman su tenedor izquierdo simultáneamente: cada uno tiene un tenedor y espera el otro, que tiene otro filósofo. Es un ciclo de espera circular.

3. Por qué se bloquea

El deadlock ocurre porque se cumplen las cuatro condiciones de Coffman (que se estudian en el bloque 8):

1. Exclusión mutua: cada tenedor solo puede ser usado por un filósofo a la vez. mutex
2. Retención y espera: un filósofo retiene un tenedor mientras espera el otro. hold & wait
3. No apropiación: un tenedor no se puede quitar a un filósofo que lo tiene. no preemption
4. Espera circular: F0 espera T0 (que tiene F1), F1 espera T1 (que tiene F2), ..., F4 espera T4 (que tiene F0). ciclo

Para evitar el deadlock, basta con romper una de estas cuatro condiciones.

4. Solución 1: limitar a 4 filósofos

La primera solución rompe la espera circular limitando el número de filósofos que pueden intentar comer simultáneamente a 4 (con un semáforo):

sem_t sem_filosofos;  /* valor inicial 4 */

void filosofo(int id) {
    while (1) {
        pensar();
        sem_wait(&sem_filosofos);  /* solo 4 pueden intentar */
        tomar_tenedor(id);
        tomar_tenedor((id + 1) % 5);
        comer();
        soltar_tenedor(id);
        soltar_tenedor((id + 1) % 5);
        sem_post(&sem_filosofos);
    }
}

Con solo 4 filósofos intentando comer, al menos uno puede tomar ambos tenedores (por el principio del palomar). Esto rompe la espera circular.

Ventaja: simple. Desventaja: limita el paralelismo (solo 4 de 5 pueden comer a la vez).

5. Solución 2: tomar ambos tenedores a la vez

La segunda solución rompe la retención y espera: un filósofo solo toma los tenedores si ambos están disponibles. Si no, no toma ninguno:

void filosofo(int id) {
    while (1) {
        pensar();
        /* Tomar ambos tenedores atómicamente. */
        pthread_mutex_lock(&mutex_tenedores);
        while (tenedor[id] == 1 || tenedor[(id + 1) % 5] == 1) {
            /* Esperar a que ambos estén disponibles. */
            pthread_cond_wait(&cond, &mutex_tenedores);
        }
        tenedor[id] = 1;
        tenedor[(id + 1) % 5] = 1;
        pthread_mutex_unlock(&mutex_tenedores);

        comer();

        pthread_mutex_lock(&mutex_tenedores);
        tenedor[id] = 0;
        tenedor[(id + 1) % 5] = 0;
        pthread_cond_broadcast(&cond);
        pthread_mutex_unlock(&mutex_tenedores);
    }
}

Esta solución usa un mutex y una variable de condición para proteger el estado de los tenedores. Un filósofo solo toma ambos tenedores si están disponibles.

Ventaja: no hay deadlock. Desventaja: más compleja, y puede haber inanición si un filósofo siempre toma los tenedores antes que otro.

6. Solución 3: asimetría (orden de adquisición)

La tercera solución rompe la espera circular cambiando el orden de adquisición: los filósofos pares toman primero el tenedor izquierdo y luego el derecho; los impares toman primero el derecho y luego el izquierdo:

void filosofo(int id) {
    while (1) {
        pensar();
        if (id % 2 == 0) {
            tomar_tenedor(id);           /* izquierdo primero */
            tomar_tenedor((id + 1) % 5); /* derecho después */
        } else {
            tomar_tenedor((id + 1) % 5); /* derecho primero */
            tomar_tenedor(id);           /* izquierdo después */
        }
        comer();
        soltar_tenedor(id);
        soltar_tenedor((id + 1) % 5);
    }
}

Esta solución rompe la espera circular: no todos los filósofos toman el mismo tenedor primero. Al menos uno tomará el tenedor derecho primero, rompiendo el ciclo.

Ventaja: simple, no necesita semáforos adicionales. Desventaja: no garantiza la espera acotada (puede haber inanición).

7. Código completo

La solución 3 (asimetría) es la más simple y la más usada:

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define NUM_FILOSOFOS 5

pthread_mutex_t tenedores[NUM_FILOSOFOS];

void *filosofo(void *arg) {
    int id = *(int *)arg;
    int izq = id;
    int der = (id + 1) % NUM_FILOSOFOS;

    for (int i = 0; i < 3; i++) {  /* comer 3 veces */
        printf("Filósofo %d: pensando...\n", id);
        usleep(100000 + (id * 50000));

        /* Tomar tenedores (asimetría). */
        if (id % 2 == 0) {
            pthread_mutex_lock(&tenedores[izq]);
            pthread_mutex_lock(&tenedores[der]);
        } else {
            pthread_mutex_lock(&tenedores[der]);
            pthread_mutex_lock(&tenedores[izq]);
        }

        printf("Filósofo %d: comiendo...\n", id);
        usleep(200000);

        /* Soltar tenedores. */
        pthread_mutex_unlock(&tenedores[izq]);
        pthread_mutex_unlock(&tenedores[der]);
    }
    return NULL;
}

int main(void) {
    pthread_t hilos[NUM_FILOSOFOS];
    int ids[NUM_FILOSOFOS];

    for (int i = 0; i < NUM_FILOSOFOS; i++) {
        pthread_mutex_init(&tenedores[i], NULL);
        ids[i] = i;
        pthread_create(&hilos[i], NULL, filosofo, &ids[i]);
    }
    for (int i = 0; i < NUM_FILOSOFOS; i++) {
        pthread_join(hilos[i], NULL);
        pthread_mutex_destroy(&tenedores[i]);
    }
    return 0;
}

8. Propiedades

9. Inanición

La inanición es un problema en las soluciones 2 y 3: un filósofo puede esperar indefinidamente si los demás siempre toman los tenedores antes que él.

En la solución 3 (asimetría), un filósofo impar puede esperar indefinidamente si los filósofos pares siempre toman los tenedores primero. La solución es usar un mecanismo de justicia (como la espera acotada) o un ticket lock.

En la práctica, la inanición es rara porque los filósofos pasan tiempo pensando (no comiendo continuamente). Pero es un problema teórico que se debe considerar.

10. Simulador interactivo

Este simulador muestra la cena de los filósofos con la solución de asimetría:

11. Resumen

• La cena de los filósofos es un problema clásico de sincronización.
• Cinco filósofos, cinco tenedores; cada filósofo necesita dos tenedores para comer.
• La solución ingenua se bloquea (deadlock) por espera circular.
• Solución 1: limitar a 4 filósofos (rompe la espera circular).
• Solución 2: tomar ambos tenedores a la vez (rompe la retención y espera).
• Solución 3: asimetría (rompe la espera circular con orden de adquisición).
• La inanición es un problema en las soluciones 2 y 3.
• La solución 3 es la más simple y la más usada.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa la solución ingenua y observa el deadlock.
2. Implementa la solución 1 y verifica que no hay deadlock.
3. Implementa la solución 3 y verifica que no hay deadlock.
4. Modifica la solución 3 para 3 o 7 filósofos.
5. Diseña un mecanismo de justicia para evitar la inanición.
6. Investiga cómo se implementa la cena de los filósofos en otros lenguajes.