Problema del barbero dormido

En ciencias de la computación , el problema del barbero durmiente es un problema clásico de comunicación y sincronización entre procesos que ilustra las complejidades que surgen cuando hay múltiples procesos del sistema operativo . ^{[ 1 ]}

El problema fue propuesto originalmente en 1965 por el pionero de la informática Edsger Dijkstra , ^{[ 2 ]} quien lo utilizó para señalar que los semáforos generales suelen ser superfluos. ^{[ 3 ]}

Imaginemos una barbería hipotética con un barbero, una silla de barbero y una sala de espera con n sillas ( n puede ser 0) para los clientes que esperan. Se aplican las siguientes reglas: ^{[ 4 ]}

• Si no hay clientes, el barbero se queda dormido en la silla.
• Un cliente debe despertar al barbero si está dormido.
• Si un cliente llega mientras el barbero está trabajando, el cliente se va si todas las sillas están ocupadas y se sienta en una silla vacía si hay alguna disponible.
• Cuando el barbero termina un corte de pelo, inspecciona la sala de espera para ver si hay clientes esperando y se duerme si no hay ninguno ^{[ 3 ] [ 5 ]}

Existen dos complicaciones principales. Primero, existe el riesgo de que se produzca una situación de espera , en la que el barbero se duerme mientras un cliente espera para que le corten el pelo, ya que todas las acciones —revisar la sala de espera, entrar en la barbería, sentarse en una silla de la sala de espera— consumen cierto tiempo. Específicamente, un cliente puede llegar y encontrar al barbero cortando el pelo, por lo que regresa a la sala de espera para sentarse, pero mientras camina de regreso a la sala de espera, el barbero termina el corte de pelo y va a la sala de espera, que encuentra vacía (porque el cliente camina despacio o fue al baño) y así se queda dormido en la silla del barbero. Segundo, otro problema puede ocurrir cuando dos clientes llegan al mismo tiempo cuando solo hay una silla libre en la sala de espera y ambos intentan sentarse en la única silla; solo la primera persona en llegar a la silla podrá sentarse.

El problema de varios barberos durmiendo tiene la complejidad adicional de coordinar a varios barberos entre los clientes que esperan. ^{[ 6 ]}

Existen varias soluciones posibles, pero todas requieren un mutex , que garantiza que solo uno de los participantes pueda cambiar de estado a la vez. El barbero debe adquirir el mutex de estado de la sala antes de atender a los clientes y liberarlo cuando estos comiencen a dormir o a cortar el pelo; un cliente debe adquirirlo antes de entrar a la barbería y liberarlo una vez que esté sentado en la sala de espera o en la silla del barbero, y también cuando salga de la barbería porque no había asientos disponibles. Esto resolvería ambos problemas mencionados anteriormente. También se requiere un conjunto de semáforos para indicar el estado del sistema. Por ejemplo, se podría almacenar el número de personas en la sala de espera.

# Los dos primeros son mutexes (solo 0 o 1 posible) Semáforo barberReady = 0 Semáforo accessWRSeats = 1 # si es 1, el número de asientos en la sala de espera se puede incrementar o decrementar Semáforo custReady = 0 # el número de clientes actualmente en la sala de espera, listos para ser atendidos int numberOfFreeWRSeats = N # número total de asientos en la sala de esperadef Barber (): while true : # Ejecutar en un bucle infinito. wait ( custReady ) # Intentar conseguir un cliente; si no hay ninguno disponible, ir a dormir. wait ( accessWRSeats ) # Despierto: intentar obtener acceso para modificar # los asientos disponibles; de lo contrario, dormir. numberOfFreeWRSeats += 1 # Una silla de la sala de espera queda libre. signal ( barberReady ) # Estoy listo para cortar. signal ( accessWRSeats ) # Ya no necesito el candado en las sillas. # (Cortar el pelo aquí.)def Cliente (): while true : # Ejecutar en un bucle infinito para simular varios clientes. wait ( accessWRSeats ) # Intentar obtener acceso a las sillas de la sala de espera. if numberOfFreeWRSeats > 0 : # Si hay asientos libres: numberOfFreeWRSeats -= 1 # sentarse en una silla signal ( custReady ) # notificar al barbero, que está esperando hasta que haya un cliente signal ( accessWRSeats ) # ya no es necesario bloquear las sillas wait ( barberReady ) # esperar hasta que el barbero esté listo # (Cortarse el pelo aquí.) else : # de lo contrario, no hay asientos libres; mala suerte -- signal ( accessWRSeats ) # ¡pero no olvides desbloquear los asientos! # (Irse sin cortarse el pelo.)

• El problema de los filósofos comensales
• Problema de fumadores de cigarrillos
• Problema entre productores y consumidores
• El problema de los lectores y escritores