El barbero dormilón (1 y N barberos)

💡 En simple

Una barbería con un barbero, una silla de barbero y 5 sillas de espera:

• Si no hay clientes, el barbero duerme.
• Si llega un cliente y el barbero está libre, lo atienden enseguida.
• Si está ocupado y hay una silla de espera libre, el cliente se sienta a esperar.
• Si no hay sillas libres, el cliente se va sin corte.

Lo difícil no es el corte: es «mirar si hay sillas y sentarse» sin que dos clientes se sienten en la misma, y que cada cliente sepa cuándo terminó su corte. Es el mismo problema que una cola de banco con varias ventanillas.

🎯 Al terminar podrás

1. Explicar por qué wait(seats) y sem_getvalue fallan, y por qué sem_trywait sí sirve (comprobar y tomar en una sola operación atómica).
2. Escribir la solución de 1 barbero con 4 semáforos, sabiendo el valor inicial de cada uno y quién hace signal.
3. Encontrar los errores del código de N barberos de las diapositivas y justificar si se puede quitar barber_chair.
4. Discutir la justicia: barging y starvation con semáforos que no son FIFO.

Antes necesitas: Semáforos POSIX y sem_trywait · Productor–consumidor

• Detective escribe tu hipótesis del bug antes de abrir el diagnóstico
• Laboratorio sube la escalera: resuelto → completa → solo → variante
• Socrático responde la pregunta guía antes de seguir leyendo

Las sillas de espera: tres intentos (diap. 34–37)

Intento 1: `semaphore seats = 5; wait(seats);` — «Does it work?»

No. wait bloquea si no hay sillas: el cliente se queda esperando en la puerta en lugar de irse, y la regla «si no hay silla, se va» no se cumple. Las colas de espera crecen sin límite.

🔍 Detective · intento 2: if (sem_getvalue(seats) > 0) wait(seats);

Síntoma: Con una silla libre llegan dos clientes a la vez. Uno se sienta, pero el otro se queda bloqueado en la puerta en lugar de irse.

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

Pista

¿Qué puede pasar entre el sem_getvalue de un cliente y su wait?

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

Tampoco. Es un check-then-act no atómico, como el lock ingenuo del parcial. Con una sola silla libre:

#	Cliente A	Cliente B	seats
1	sem_getvalue → 1 > 0		1
2		sem_getvalue → 1 > 0	1
3	wait(seats) ✔		0
4		wait(seats) ⛔ se bloquea en vez de irse	0

Además, sem_getvalue solo da una foto: el valor puede cambiar apenas retorna. En Linux, con esperadores devuelve 0, nunca un negativo.

Intento 3, correcto: un mutex + contador (diap. 35). La comprobación y el decremento quedan dentro de la misma sección crítica:

sem_t mutex;  int seats = 5;
wait(mutex);
if (seats > 0) { seats--; signal(mutex); enters_barbershop(); }
else           {          signal(mutex); leaves_barbershop(); }

Más simple: sem_trywait (diap. 36–37). Decrementa solo si el valor es positivo; si no, retorna −1 con EAGAIN sin bloquear. Comprobar y tomar es una sola operación atómica:

semaphore seats = 5;
if (trywait(seats) == 0) enters_barbershop();
else                     leaves_barbershop();      // sin corte

«Los clientes solo esperan en las sillas.»

La silla del barbero (diap. 37–39)

«All clients need to wait on the seats?»

Con el diseño de las diapositivas, sí: todo cliente toma primero una silla de espera (trywait(seats)) y desde ahí espera la silla del barbero (wait(barber_chair)). Si el barbero está libre, el cliente ocupa la silla de espera solo un instante: la toma y la suelta de inmediato.

La alternativa sería intentar primero la silla del barbero. Es la pregunta siguiente, y tiene un problema de justicia.

Diap. 38: «Barber chair dispute… Is it a fair approach?»

if (trywait(barber_chair) == 0)        // ¿la silla del barbero está libre? me siento directo
    ...
else if (trywait(seats) == 0)          // si no, busco silla de espera
    wait(barber_chair);

No es justo. Un cliente que acaba de llegar puede encontrar la silla del barbero libre justo cuando se desocupa y adelantarse a los que llevan rato esperando (barging). Peor aún, los que esperan en wait(barber_chair) no tienen orden garantizado: los semáforos POSIX no son FIFO. Un cliente puede quedarse esperando indefinidamente mientras otros pasan: starvation.

Para ser justo, hace falta una cola FIFO explícita: números de turno como en Bakery, o un semáforo fuerte.

Diap. 39: `wait(barber_chair); signal(barber_chair);` — «And the other clients?»

Si el cliente libera la silla apenas la toma, la silla no queda reservada durante el corte: otro cliente puede tomarla y «sentarse» mientras el primero se está cortando el pelo. La silla debe retenerse hasta que el corte termina. ¿Y quién sabe cuándo termina? El barbero (siguiente punto).

🔮 Predice antes de seguir

El cliente ya está en la silla del barbero. ¿Cómo sabe que su corte terminó y que puede levantarse? Propón un mecanismo con semáforos antes de seguir.

Ya tengo mi respuesta: comparar

No lo puede saber solo: quien sabe cuándo termina es el barbero. Hace falta un semáforo en 0 (hair_cut) donde el cliente espera y que el barbero señala al terminar. Es el patrón de señalización (un semáforo en 0 usado como aviso entre dos hilos), igual que client_seat en sentido contrario: el barbero duerme en él hasta que alguien se sienta.

¿Quién decide terminar? (diap. 40–41)

El barbero. El cliente no puede saber cuándo terminó su corte, así que hace falta un semáforo más, hair_cut, que el barbero señala al terminar.

Solución completa con 1 barbero:

semaphore seats = 5, barber_chair = 1;
semaphore client_seat = 0, hair_cut = 0;

/* Cliente */                               /* Barbero */
if (trywait(seats) == 0) {                  while (true) {
    wait(barber_chair);  // espero silla        wait(client_seat);   // duerme si no hay nadie
    signal(seats);       // libero espera        cut_shave();
    signal(client_seat); // «ya me senté»        signal(hair_cut);    // «terminé»
    wait(hair_cut);      // espero el corte  }
    signal(barber_chair);
} else leaves_barbershop();

Semáforo	Valor inicial	Para qué
seats	5	sillas de espera
barber_chair	1	exclusión mutua sobre la silla del barbero
client_seat	0	señal «hay un cliente sentado»: el barbero duerme aquí
hair_cut	0	señal «corte terminado»: el cliente espera aquí

Ejecución de prueba (lo pide la diap. 41, «implement a solution barber.c»). 300 clientes llegando cada 0–120 µs, cortes de 0–300 µs, con un assert de que el barbero nunca corta a dos a la vez:

barberos=1: atendidos=237, se fueron=63 (total 300), máx esperando en sillas=5 (<= 5)

Nunca hubo más de 5 esperando, el assert no falló, y los 63 que no encontraron silla se fueron en lugar de bloquearse.

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

Complétalo: los 4 semáforos de la solución de 1 barbero

Sin mirar arriba, completa la tabla.

Semáforo	Valor inicial	¿Quién hace wait?	¿Quién hace signal?
seats	?	?	?
barber_chair	?	?	?
client_seat	?	?	?
hair_cut	?	?	?

Comparar

Semáforo	Valor inicial	wait	signal
seats	5	cliente (trywait)	cliente, al pasar a la silla del barbero
barber_chair	1	cliente	cliente, al terminar el corte
client_seat	0	barbero (duerme aquí)	cliente («ya me senté»)
hair_cut	0	cliente	barbero («terminé»)

Regla mental: los semáforos de exclusión empiezan en la cantidad de recursos (5 y 1). Los de aviso empiezan en 0, y los señala el otro actor.

Peldaño 3 · Solosin ayuda; luego compara

Solo: el barbero completo en C (25 minutos)

1 barbero, 5 sillas y 40 clientes que llegan a intervalos aleatorios. Cuenta los atendidos y los que se fueron, y agrega un assert de que el barbero nunca corta a dos a la vez. Compila con gcc -Wall -pthread.

Una solución (probada: 30 de 30 ejecuciones terminaron sin fallar el assert)

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

#define SILLAS 5
#define CLIENTES 40

sem_t seats, barber_chair, client_seat, hair_cut, cuenta;
int atendidos = 0, se_fueron = 0, en_corte = 0;

void *barbero(void *arg) {
    (void)arg;
    while (1) {
        sem_wait(&client_seat);
        sem_wait(&cuenta);
        en_corte++;
        assert(en_corte == 1);
        sem_post(&cuenta);
        usleep(rand() % 300);
        sem_wait(&cuenta);
        en_corte--;
        atendidos++;
        sem_post(&cuenta);
        sem_post(&hair_cut);
    }
    return NULL;
}

void *cliente(void *arg) {
    (void)arg;
    if (sem_trywait(&seats) == 0) {
        sem_wait(&barber_chair);
        sem_post(&seats);
        sem_post(&client_seat);
        sem_wait(&hair_cut);
        sem_post(&barber_chair);
    } else {
        sem_wait(&cuenta);
        se_fueron++;
        sem_post(&cuenta);
    }
    return NULL;
}

int main(void) {
    pthread_t b, c[CLIENTES];
    sem_init(&seats, 0, SILLAS);
    sem_init(&barber_chair, 0, 1);
    sem_init(&client_seat, 0, 0);
    sem_init(&hair_cut, 0, 0);
    sem_init(&cuenta, 0, 1);
    pthread_create(&b, NULL, barbero, NULL);
    for (int i = 0; i < CLIENTES; i++) {
        pthread_create(&c[i], NULL, cliente, NULL);
        usleep(rand() % 100);
    }
    for (int i = 0; i < CLIENTES; i++) pthread_join(c[i], NULL);
    printf("atendidos=%d se_fueron=%d total=%d\n", atendidos, se_fueron, atendidos + se_fueron);
    return 0;
}

En una ejecución: atendidos=27 se_fueron=13 total=40. Los números cambian en cada corrida; lo que no puede cambiar es que total = 40 y que el assert nunca falle. El barbero queda en un while (1): el programa termina cuando main retorna tras el join de los clientes.

N barberos (diap. 42–47)

Ahora hay n barberos (n sillas de barbero) y m sillas de espera. El cliente necesita saber qué barbero lo atiende: es el problema de la cola del banco («pase a la ventanilla 3»). Idea de las diapositivas: un panel donde un barbero libre publica su id.

• Los barberos escriben el panel, uno a la vez, y solo cuando el id anterior ya fue leído.
• Los clientes leen el panel, uno por cada id publicado.

semaphore write_panel = 1, read_panel = 0;
int panel;

🔍 Detective · el código de N barberos de las diapositivas 45–46

Síntoma: Transcrito tal cual y ejecutado con 2 barberos y 6 clientes: 0 clientes atendidos en 3 s. Ningún hilo termina.

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

Pista

Mira el primer wait que hace cada barbero y el valor inicial de ese semáforo. Después busca una línea con ==.

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

Tiene cuatro errores:

1. El barbero hace wait(read_panel), que empieza en 0, así que ningún barbero publica nunca y todos quedan bloqueados. Debería ser wait(write_panel).
2. my_seat == panel; es una comparación, no una asignación. Debería ser my_seat = panel;.
3. barber_chair[N_BARBERS] = {0, …, 0} y nadie hace signal sobre él: el cliente que llega a wait(barber_chair[my_seat]) queda bloqueado para siempre. Con el panel, además, es innecesario (ver la tarea).
4. signal(seats) justo después del trywait libera la silla de espera antes de tener barbero. Así las sillas no limitan nada. Debe liberarse cuando el cliente ya obtuvo su barbero.

Son pseudocódigo de clase, pero si el LC3 los muestra, las preguntas serán justamente «¿funciona?» y «¿qué cambiarías?». Cómo verificar la corrección: la versión de abajo, con un assert de un cliente por barbero, atendió a 299 o 300 de 300 clientes.

Versión corregida (propia):

semaphore seats = M, write_panel = 1, read_panel = 0;
semaphore client_seat[N] = {0…}, hair_cut[N] = {0…};
int panel;

/* Barbero id */                              /* Cliente */
while (true) {                                if (trywait(seats) == 0) {
    wait(write_panel);   // ¿panel libre?          wait(read_panel);      // espero un id
    panel = id;          // «estoy libre»          int my = panel;        // lo leo
    signal(read_panel);  // que un cliente lo lea  signal(write_panel);   // panel libre otra vez
    wait(client_seat[id]);                         signal(seats);         // dejo la silla de espera
    cut_shave();                                   signal(client_seat[my]);
    signal(hair_cut[id]);                          wait(hair_cut[my]);
}                                             } else leaves_barbershop();

Ejecución de prueba (300 clientes, 5 sillas de espera, assert de que ningún barbero corta a dos a la vez):

barberos=2: atendidos=299, se fueron=1   (total 300), máx esperando en sillas=5 (<= 5)
barberos=3: atendidos=300, se fueron=0   (total 300), máx esperando en sillas=2 (<= 5)
barberos=4: atendidos=300, se fueron=0   (total 300), máx esperando en sillas=1 (<= 5)

Con más barberos se van menos clientes y la sala de espera se usa menos, como era de esperar.

Tarea (diap. 47): «Discuss and evaluate if we can remove the barber_chair»

Sí, se puede quitar. La versión corregida de arriba no tiene barber_chair y la prueba con 2, 3 y 4 barberos no violó nunca «un cliente por barbero».

Por qué: la exclusión sobre la silla ya la garantiza el panel. Un barbero solo publica su id cuando está libre: lo hace al inicio de cada vuelta del while, después de terminar el corte anterior. Cada publicación la consume exactamente un cliente, porque read_panel vale 1 por cada id publicado y write_panel impide publicar otro antes de que se lea. Por lo tanto, nunca hay dos clientes con el mismo my al mismo tiempo, y barber_chair[my] sería un semáforo que siempre se toma sin esperar.

Con 1 barbero, en cambio, barber_chair sí hace falta. Sin él, dos clientes podrían hacer signal(client_seat) y quedar los dos en wait(hair_cut). Cuando el barbero termina el primer corte, signal(hair_cut) puede despertar al cliente equivocado, porque el semáforo no es FIFO: alguien se iría sin terminar su corte. En la versión de N barberos ese papel lo cumple el panel.

El mismo problema, con monitores: el ejercicio 8 · Barbería (2 barberos, 5 sillas) se resolvió con mutex + condition variables, y su assert detectó un bug en la primera versión.

⚠️ Errores que cuestan puntos

• Usar wait(seats) para «ver si hay silla».wait bloquea. Para «si no hay, me voy» se usa sem_trywait (o mutex + contador).
• Comprobar con sem_getvalue y después tomar.Check-then-act no es atómico, y además el valor es solo una foto.
• Inicializar client_seat o hair_cut en 1.Son avisos: empiezan en 0. Con 1, el barbero cortaría sin cliente o el cliente se iría sin corte.
• Soltar seats antes de tener barbero (en N barberos).Las sillas dejarían de limitar la espera. Se suelta al obtener barbero.
• Suponer que los clientes en wait(barber_chair) pasan en orden de llegada.Los semáforos POSIX no son FIFO. Para garantizar justicia hacen falta turnos.

Autoevaluación

0/5 correctas · 0 respondidas Reiniciar

1. ¿Por qué wait(seats) no cumple «si no hay silla, el cliente se va»?

a) Porque no es atómicob) Porque bloquea en vez de irsec) Porque seats empieza en 0d) Sí lo cumple

2. if (sem_getvalue(seats) > 0) wait(seats); falla porque…

a) sem_getvalue no existeb) comprobar y tomar no es atómico: dos clientes ven 1c) bloquea siempred) no libera la silla

3. sem_trywait con el semáforo en 0…

a) bloqueab) retorna −1 (EAGAIN) sin bloquearc) lo pone en −1d) despierta a alguien

4. ¿Quién señala hair_cut?

a) El clienteb) El barbero, al terminar el cortec) El siguiente cliented) Nadie

5. Con N barberos y panel, ¿se puede quitar barber_chair?

a) No, habría dos clientes por barberob) Sí: un barbero solo publica su id estando libre y cada id lo lee un único clientec) Solo con un barberod) Solo con monitores

🗣️ Explícalo tú (Feynman)

Explica a un compañero por qué la solución de 1 barbero necesita cuatro semáforos y qué pasaría si quitas cada uno.

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…

• seats: limita la espera. Sin él, la sala no tiene límite y nadie se va.
• barber_chair: un cliente a la vez en la silla. Sin él, dos clientes esperan en hair_cut y el aviso puede despertar al equivocado.
• client_seat: el barbero duerme hasta que hay alguien. Sin él, cortaría en el aire (o habría que hacer busy waiting).
• hair_cut: el cliente sabe cuándo terminó. Sin él, se levantaría antes.

Error típico al explicarlo: confundir semáforos de exclusión (empiezan en N o en 1) con semáforos de aviso (empiezan en 0).

📈 ¿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.

0No lo reconozco o lo confundo con otro tema1Lo entiendo leyendo, pero no lo aplico solo2Resuelvo ejercicios parecidos a los vistos, con alguna pista3Resuelvo uno nuevo sin ayuda y justifico cada paso4Lo transfiero: comparo alternativas y veo casos límite

Fuente ·sem_9/11-OSL-Deadlock.pdf (diap. 32–47) · man sem_trywait(3) · Pruebas propias: barber.c (1–4 barberos) y barber_slides.c (código de las diapositivas transcrito), ejecuciones de prueba