Filósofos comensales: las 8 versiones del curso

🎯 Al terminar podrás

Leer la salida de los programas del curso y reconocer un deadlock (los 5 con un tenedor) o una starvation.
Para cada una de las 8 versiones, decir si tiene deadlock o starvation, cuál es su paralelismo máximo y qué condición de Coffman rompe.
Escribir en C, con sem_t, una solución sin deadlock (sillas limitadas o asimétrica). Es candidata a pregunta de código.
Explicar cómo Tanenbaum puede tener starvation y cómo arreglarlo sin perder paralelismo.

Antes necesitas: Coffman · Semáforos POSIX

Simulador predice el estado antes de pulsar el paso siguiente
Detective escribe tu hipótesis del bug antes de abrir el diagnóstico
Laboratorio sube la escalera: resuelto → completa → solo → variante
Debate elige una alternativa para el escenario y defiéndela

El problema (Dijkstra, 1971)

Cinco filósofos piensan y comen espagueti; cada uno necesita dos tenedores para comer.

Requisitos:

Exclusión mutua: dos filósofos no usan el mismo tenedor a la vez.
Sin deadlock y sin starvation: ningún filósofo «muere de hambre».
Alto paralelismo: con N filósofos pueden comer como máximo $\lfloor N/2 \rfloor$ a la vez (2 de 5, 5 de 10). Las diapositivas dicen que esto es «ahora no tan importante», pero es lo que distingue a las soluciones.

Notación de las diapositivas: T piensa (think), H hambriento (hungry), E come (eat). F0…F4 son los filósofos y G0…G4 los tenedores. El filósofo i usa fork[i] y fork[(i+1) % N].

1 · La versión con deadlock (`deadlock-bug.c`)

void* f_phil(void *v) {
  int phil_id = *(int *) v;
  for (i = 0; i < N_CYCLES; i++) {
    stay_starve(phil_id);         // H
    take_fork_right(phil_id);     // sem_wait(&sem_fork[(phil_id+1) % N]); … sleep(1)
    take_fork_left(phil_id);      // sem_wait(&sem_fork[phil_id])
    eat(phil_id);
    release_fork_think(phil_id);  // sem_post de ambos
  }
}

Ejecución de prueba (N = 5; extracto de la salida. A los 40 s se cortó y el programa no había terminado):

- H - T - T - T - T -
- H - H - H - H - T -
- H - H - H - H - H -
- H|  H|- H|- H|- H|-
- H|  H|  H|- H|- H|-
- H|  H|  H|  H|  H|-
  H|  H|  H|  H|  H|        ← los 5 con un tenedor, esperando el otro: DEADLOCK

Por qué (diap. 21): aparece la espera circular.

Hilo 0	Hilo 1	Hilo 2	Hilo 3	Hilo 4
`sem_wait(1)` ✔	`sem_wait(2)` ✔	`sem_wait(3)` ✔	`sem_wait(4)` ✔	`sem_wait(0)` ✔
`sem_wait(0)` ⛔	`sem_wait(1)` ⛔	`sem_wait(2)` ⛔	`sem_wait(3)` ⛔	`sem_wait(4)` ⛔

Se cumplen las cuatro condiciones de Coffman:

Exclusión mutua: cada tenedor es un semáforo en 1.
Hold and wait: cada filósofo retiene un tenedor mientras espera el otro.
Sin expropiación: nadie le quita el tenedor a otro.
Espera circular: 0 espera a 4, 4 espera a 3, …, 1 espera a 0.

Detalle del código: take_fork_right hace sleep(1) justo después de tomar el primer tenedor. Así da tiempo a que los cinco tomen el suyo antes de que alguno pida el segundo, y el deadlock es casi seguro. Sin ese sleep, el programa a veces termina: el deadlock es posible, no obligatorio. Pruébalo en el simulador con «Filósofos ingenuos»:

Simulador de semáforos

Haz clic en un proceso para ejecutar su siguiente instrucción. Semántica de Stallings: el valor puede ser negativo (|valor| = procesos en cola) y la cola es FIFO.

fork[0]1

fork[1]1

fork[2]1

fork[3]1

fork[4]1

Registro vacío.

Haz que cada filósofo tome su tenedor izquierdo (un clic en F0…F4): los 5 quedan bloqueados esperando el derecho. Es DEADLOCK por espera circular.

2 · Semáforo central (`sem_central.c`)

semaphore lock = 1;
while (true) {
    think();
    wait(lock);                 // solo uno intenta tomar tenedores
      wait(fork[i]);  wait(fork[(i+1) % N]);
      eat();
      signal(fork[(i+1) % N]);  signal(fork[i]);
    signal(lock);
}

Sin deadlock, porque nunca hay dos filósofos compitiendo por tenedores. Pero el costo es paralelismo bajo: come uno a la vez. En la ejecución de prueba (N = 10, sem_central = 1), el máximo de filósofos comiendo a la vez fue 1, en promedio 0.17 por línea.

Diapositiva 24: «What about if lock == 2? Modify and test»

Lo verifiqué recorriendo todos los estados posibles (5 filósofos, el semáforo central con valor k):

k	¿Deadlock?	Máximo comiendo a la vez
1	no	1
2	no	2
3	no	2
4	no	2
5	sí	2

Respuesta: con lock = 2 no hay deadlock: dos filósofos no alcanzan a cerrar un ciclo de 5. Y el paralelismo sube a 2, que ya es el máximo posible para N = 5. El deadlock solo aparece cuando todos pueden entrar, es decir con k = N. En general, cualquier k ≤ N − 1 evita el deadlock. Ojo: con k = N − 1 el semáforo central es exactamente la solución de las sillas limitadas.

3 · Menos sillas que filósofos (`limit_seats.c`, `table.c`)

semaphore seat_table = N - 1;      // «echar» a un filósofo de la mesa
while (true) {
    think();
    wait(seat_table);
      wait(fork[i]);  wait(fork[(i+1) % N]);
      eat();
      signal(fork[(i+1) % N]);  signal(fork[i]);
    signal(seat_table);
}

¿Por qué no hay deadlock? Por palomar. Con N − 1 filósofos en la mesa y N tenedores, aunque cada uno tome un tenedor sobra uno. Ese tenedor es vecino de algún filósofo sentado, que entonces puede tomar el segundo, comer y liberar.

Rompe la espera circular: el ciclo necesitaría a los N filósofos.

4 · Solución asimétrica (`assymetric.c`)

while (true) {
    think();
    if (i % 2 == 0) { wait(fork[i]);            wait(fork[(i+1) % N]); }   // pares: izquierda primero
    else            { wait(fork[(i+1) % N]);    wait(fork[i]); }           // impares: derecha primero
    eat();
    signal(fork[(i+1) % N]);  signal(fork[i]);
}

El código del curso lo escribe como if (phil_id % 2): los impares toman primero el derecho y los pares el izquierdo. Es lo mismo.

¿Por qué no hay deadlock? Para que haya ciclo, cada filósofo tendría que tener su primer tenedor y esperar el segundo, y todos «en la misma dirección». Dos vecinos con distinta paridad compiten por el mismo primer tenedor: uno de los dos ni siquiera toma su primer tenedor, así que el ciclo no se cierra.

Lo verifiqué recorriendo todos los estados con N = 5 (donde 0 y 4 son ambos pares y quedan vecinos) y con N = 10: sin deadlock en ambos casos.

Diapositiva 26: «Does it exhibit lower parallelism? Why?»

No. En la ejecución de prueba (N = 10), el máximo de filósofos comiendo a la vez fue 5, que es justo $\lfloor 10/2 \rfloor$ , el máximo posible, con 1.35 en promedio por línea. En el recorrido de estados, el máximo alcanzable también es 5 de 10 y 2 de 5.

Por qué: no hay ningún semáforo global que serialice. Cada filósofo solo compite con sus dos vecinos, igual que en la versión ingenua; solo cambia el orden en que algunos toman los tenedores, lo justo para que no se forme el ciclo.

Comparado con las soluciones 2 y 3, la asimétrica no limita cuántos pueden intentar comer.

5 · La solución de Tanenbaum (`tanen-sem.c`)

Ya no se piensa en tenedores. Cada filósofo tiene un estado (T, H o E) y un semáforo propio (inicializado en 0) donde espera. Un filósofo hambriento solo pasa a E si ninguno de sus vecinos está comiendo, y lo decide dentro de una sección crítica (sem):

#define LEFT  (phil_id + 1) % N
#define RIGHT (phil_id + N - 1) % N
sem_t sem;                 // = 1: protege state[]
sem_t philosopher[N];      // = 0: aquí espera cada uno

void test_forks(int k) {   // se llama con sem tomado
  if (state[k] == H && state[left(k)] != E && state[right(k)] != E) {
    state[k] = E;
    sem_post(&philosopher[k]);          // lo «despierta» (o lo deja pasar)
  }
}
void take_forks(int i) {
  sem_wait(&sem);
  state[i] = H;
  test_forks(i);                        // ¿puedo comer ya?
  sem_post(&sem);
  sem_wait(&philosopher[i]);            // si no, espero a que un vecino me deje
}
void release_forks(int i) {
  sem_wait(&sem);
  state[i] = T;
  test_forks(LEFT);                     // ¿mi vecino izquierdo puede comer ahora?
  test_forks(RIGHT);
  sem_post(&sem);
}

Sin deadlock: un filósofo nunca retiene un tenedor mientras espera, porque toma los dos «de golpe» al pasar a E. Se rompe hold and wait.
Alto paralelismo: pueden comer todos los que no tengan un vecino comiendo.
El truco del sem_post adelantado: si test_forks(i) lo deja comer, hace sem_post(&philosopher[i]) y el sem_wait posterior no bloquea. Si no puede, se bloquea hasta que un vecino, al terminar, haga test_forks(i) por él.

Ejecución de prueba con N = 11, hasta 100 porciones: cada filósofo comió 9 o 10 porciones. Con tiempos iguales, el reparto es justo.

Las diapositivas 28–29 muestran una versión «simple» donde take_forks hace wait(philosopher[i]) solo en la rama else. La versión «original» (diap. 30), que es la del código, hace siempre test_forks(i) seguido de wait(phil[i]), y es más limpia.

6 · Starvation con alto paralelismo

Diap. 31: «How to starve the philosophers? Need to control the time.»

Tanenbaum no tiene deadlock, pero no garantiza que todos coman. Si los dos vecinos de un filósofo se turnan para comer de forma que siempre hay al menos uno de los dos comiendo, test_forks nunca lo deja pasar. Los programas del curso fuerzan esos tiempos:

Programa	Tiempos	Porciones (ejecución de prueba)
`tanen-5-1.c` (N = 5)	0, 1 y 4 piensan 1 s y comen 3 s; 2 y 3 piensan 3 s y comen 1 s	F0: 0 · F1: 10 · F2: 10 · F3: 10 · F4: 10
`tanen-4-2.c` (N = 4)	todos comen 3 s; los impares arrancan desfasados	F0: 20 · F1: 0 · F2: 20 · F3: 0

En tanen-4-2 la salida se ve así: 0 y 2 comen alternándose con un desfase, de modo que en todo instante 1 y 3 tienen un vecino comiendo:

E H T H
E H E H      ← F1 y F3 hambrientos para siempre
T H E H
E H E H
…

Diapositiva 31: «Is it possible to have high parallelism and do not starve at the same time?» — sí (solución propia, medida)

Idea: respetar el orden de llegada al hambre entre vecinos. Cada vez que un filósofo pasa a H recibe un turno creciente. Un filósofo hambriento no empieza a comer si un vecino hambriento llegó antes que él, aunque los tenedores estén libres:

long ticket[N], next_ticket = 0;

void test_forks(int k) {
  if (state[k] == H && state[LEFT] != E && state[RIGHT] != E
      && !(state[LEFT]  == H && ticket[LEFT]  < ticket[k])
      && !(state[RIGHT] == H && ticket[RIGHT] < ticket[k])) {
    state[k] = E;
    sem_post(&philosopher[k]);
  }
}
/* en take_forks, después de state[i] = H: */  ticket[i] = next_ticket++;

Por qué no hay starvation: el filósofo hambriento con el turno más antiguo de todos no puede ser bloqueado por un vecino «más nuevo». Solo espera a que sus vecinos terminen de comer, cosa que ocurre en tiempo finito, y como ninguno de ellos puede volver a adelantarlo, termina comiendo. Después, el siguiente más antiguo pasa a ser el primero.

Ejecución de prueba con los mismos tiempos que provocan la starvation:

Programa	Original	Con turnos
tiempos de `tanen-5-1`	0 · 10 · 10 · 10 · 10 (39 s)	8 · 9 · 8 · 8 · 7 (48 s)
tiempos de `tanen-4-2`	20 · 0 · 20 · 0 (77 s)	11 · 10 · 9 · 10 (60 s)

El paralelismo máximo sigue siendo 2 comiendo a la vez en los cuatro casos.

El costo: un filósofo puede esperar con los tenedores libres porque un vecino más antiguo tiene hambre. Eso baja un poco el paralelismo en algunos momentos; por eso la versión con turnos tardó más con los tiempos de tanen-5-1. Con tanen-4-2 incluso terminó antes, porque los filósofos que antes no comían nunca ahora aportan porciones.

Otras soluciones conocidas: Chandy/Misra (tenedores «sucios» y «limpios»), o un monitor con cola FIFO de hambrientos.

🔮 Debate: ¿cuál entregarías?

En el LC3 te piden «filósofos sin deadlock y con el mayor paralelismo posible», y tienes 25 minutos. ¿Eliges semáforo central, sillas N − 1, asimétrica o Tanenbaum? Defiende tu elección con tres criterios: deadlock, paralelismo y riesgo de equivocarte al escribirla.

Ya tengo mi respuesta: comparar

Semáforo central = 1: fácil, pero paralelismo 1. No cumple «el mayor posible».
Sillas N − 1: fácil (un semáforo más) y sin deadlock. En teoría da ⌊N/2⌋, aunque con sleep entre tenedores en la práctica puede serializarse (lo viste en la ejecución).
Asimétrica: también fácil (un if de paridad), sin deadlock y con ⌊N/2⌋ medido. Es la mejor relación riesgo/beneficio con poco tiempo.
Tanenbaum: ⌊N/2⌋, pero tiene más piezas (estado, un semáforo por filósofo, test_forks en dos lugares), así que es más fácil equivocarse. Y tiene starvation.

Si además piden sin starvation, ninguna de las básicas lo garantiza: hay que agregar orden de llegada (los turnos de la sección 6) o una cola FIFO.

Resumen

Versión	Deadlock	Starvation	Comiendo a la vez (máx.)	Qué condición rompe
`deadlock-bug.c`	sí	sí	2 (si no se bloquea)	ninguna
semáforo central = 1	no	depende de la cola del semáforo	1	hold and wait (solo uno compite)
central = k ≤ N − 1 / sillas N − 1	no	depende de la cola	2 de 5 (en la ejecución: 1)	espera circular
asimétrica	no	posible	⌊N/2⌋	espera circular
Tanenbaum	no	sí (tanen-5-1, tanen-4-2)	⌊N/2⌋	hold and wait (toma ambos de golpe)
Tanenbaum + turnos (propia)	no	no	⌊N/2⌋	hold and wait + orden de llegada

Peldaño 2 · Complétalofaltan pasos clave: llénalos tú

Complétalo: sillas limitadas con sem_t

Completa los cuatro ???: dos valores iniciales y dos llamadas.

sem_t silla, tenedor[N];

void *filosofo(void *arg) {
    int i = *(int *)arg;
    for (int c = 0; c < CICLOS; c++) {
        ???;                                   /* (3) entrar a la mesa */
        sem_wait(&tenedor[i]);
        sem_wait(&tenedor[(i + 1) % N]);
        /* come */
        sem_post(&tenedor[(i + 1) % N]);
        sem_post(&tenedor[i]);
        ???;                                   /* (4) dejar la silla */
    }
    return NULL;
}
/* en main: */
sem_init(&silla, 0, ???);                      /* (1) */
for (int i = 0; i < N; i++) sem_init(&tenedor[i], 0, ???);   /* (2) */

Comparar

(1) N − 1: así nunca están los N en la mesa. (2) 1: cada tenedor es un mutex. (3) sem_wait(&silla). (4) sem_post(&silla). Si pusieras N en (1), volverías a tener la versión con deadlock: mira el detective de abajo.

🔍 Detective · «mi versión con sillas a veces se cuelga»

Síntoma: Un compañero entrega la solución de sillas limitadas. La probó 10 veces y terminó bien, pero en la corrección se quedó colgada con la salida H| H| H| H| H|.

Escribe tu hipótesis (qué variable o qué orden lo causa) antes de abrir.

Pista

Mira su sem_init(&silla, 0, N). ¿Cuántos filósofos pueden estar sentados a la vez?

Diagnóstico: causa raíz, cuándo se dispara, corrección y cómo verificarla

Causa raíz: inicializó silla en N en vez de N − 1, así que los N filósofos pueden sentarse y cada uno tomar un tenedor: vuelve la espera circular. El recorrido de estados de arriba lo muestra: con k = 5 hay deadlock.
Cuándo se dispara: solo si los 5 toman su primer tenedor antes de que alguno tome el segundo. Por eso «terminó bien 10 veces».
Corrección: sem_init(&silla, 0, N - 1).
Cómo verificar: un usleep entre los dos sem_wait hace que el caso malo sea casi seguro. Con N − 1, ni así se cuelga. Y recuerda: que funcione en las pruebas no demuestra que no haya deadlock; el argumento del palomar sí.

Peldaño 3 · Solosin ayuda; luego compara

Solo: la solución asimétrica completa en C (20 minutos, como en el LC3)

Escribe un programa completo: N = 5 hilos, 3 porciones cada uno, sin deadlock. Imprime quién come y, al final, el máximo de filósofos que comieron a la vez. Compílalo con gcc -Wall -pthread y córrelo varias veces.

Una solución (probada: 30 de 30 ejecuciones terminaron, con un máximo de 2 comiendo a la vez)

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <unistd.h>

#define N 5
#define CICLOS 3

sem_t tenedor[N];
sem_t pantalla;
int comiendo = 0, max_comiendo = 0;

void *filosofo(void *arg) {
    int i = *(int *)arg;
    int izq = i, der = (i + 1) % N;
    int primero = (i % 2 == 0) ? izq : der;
    int segundo = (i % 2 == 0) ? der : izq;
    for (int c = 0; c < CICLOS; c++) {
        usleep(1000);
        sem_wait(&tenedor[primero]);
        usleep(1000);
        sem_wait(&tenedor[segundo]);
        sem_wait(&pantalla);
        comiendo++;
        if (comiendo > max_comiendo) max_comiendo = comiendo;
        printf("F%d come (porción %d)\n", i, c + 1);
        sem_post(&pantalla);
        usleep(2000);
        sem_wait(&pantalla);
        comiendo--;
        sem_post(&pantalla);
        sem_post(&tenedor[segundo]);
        sem_post(&tenedor[primero]);
    }
    return NULL;
}

int main(void) {
    pthread_t t[N];
    int id[N];
    sem_init(&pantalla, 0, 1);
    for (int i = 0; i < N; i++) sem_init(&tenedor[i], 0, 1);
    for (int i = 0; i < N; i++) {
        id[i] = i;
        pthread_create(&t[i], NULL, filosofo, &id[i]);
    }
    for (int i = 0; i < N; i++) pthread_join(t[i], NULL);
    printf("terminaron todos; máximo comiendo a la vez: %d\n", max_comiendo);
    return 0;
}

Los usleep fuerzan intercalaciones malas: con la versión ingenua (todos izq primero), este mismo programa se cuelga casi siempre. El contador comiendo está protegido por pantalla, porque lo tocan todos los hilos.

Peldaño 4 · Variantecambia una condición: ¿sigue valiendo lo anterior?

Variante: ¿y si solo el filósofo 0 es «zurdo» y los demás toman primero el izquierdo?

Comparar

Tampoco hay deadlock. Para cerrar el ciclo, los N tendrían que tomar su primer tenedor «en la misma dirección». Basta con uno distinto para romper la espera circular: es prevención por orden. Ahora el zurdo (F0) y su vecino F1 compiten por el mismo primer tenedor (el 1), así que uno de los dos ni siquiera empieza. Para comparar el paralelismo con la versión por paridad, cambia primero y segundo en tu código y mide max_comiendo.

Autoevaluación

0/6 correctas · 0 respondidas

1. En deadlock-bug.c, ¿qué condición de Coffman aparece «durante la ejecución»?

2. Con un semáforo central de valor 2 y 5 filósofos…

3. Limitar a N − 1 las sillas evita el deadlock porque…

4. La solución asimétrica, ¿reduce el paralelismo?

5. En Tanenbaum, un filósofo hambriento pasa a E si…

6. tanen-4-2.c demuestra que Tanenbaum…

🗣️ Explícalo tú (Feynman)

Explica por qué con N − 1 sillas no puede haber deadlock, usando el argumento del palomar, y por qué Tanenbaum tampoco lo tiene aunque no limita las sillas.

Dilo en voz alta o escríbelo en 4–5 líneas, sin mirar la página. Después revisa qué te faltó.

Tu explicación debería mencionar…

Sillas: con N − 1 sentados y N tenedores, aunque cada uno tome uno, sobra un tenedor. Ese tenedor es vecino de alguien, que entonces come y libera. Se rompe la espera circular.
Tanenbaum: el filósofo toma los dos tenedores «de golpe», en una sección crítica, o no toma ninguno. Nunca espera reteniendo uno: se rompe hold and wait.
Cada solución rompe una condición distinta de Coffman.
Ninguna de las dos garantiza la ausencia de starvation sin un orden de llegada.

📈 ¿Qué tan bien lo dominas?

Elige pensando en lo que hiciste, no en lo que leíste. Para marcar 3 tienes que haber resuelto un ejercicio nuevo sin pistas y haberlo justificado. Si solo lo leíste y sientes que «ya entendí», todavía es un 1.

Fuente ·sem_9/11-OSL-Deadlock.pdf (diap. 15–31) · Código del curso sem9/deadlock/: deadlock-bug.c, sem_central.c, table.c, limit_seats.c, assymetric.c, tanen-sem.c, tanen-5-1.c, tanen-4-2.c (ejecuciones de prueba) · Recorrido exhaustivo de estados propio (semáforo central k = 1…5, asimétrica N = 5 y 10) · Variante propia con turnos: fair.c y fair42.c (ejecución de prueba) · Stallings §6.6, Tanenbaum «Modern Operating Systems» §2.5