Problema del barbero durmiendo

En informática, 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.

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

Declaración del problema

Imagine a hypothetical barbershop with one barber, on barber chair, and a waiting room with n chairs (n may be 0) for waiting customers. The following rules apply:

• 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 deja si todas las sillas están ocupadas y se sienta en una silla vacía si está disponible
• Cuando el barbero termina un corte de pelo, inspecciona la sala de espera para ver si hay clientes de espera y se queda dormido si no hay ninguno

Hay dos complicaciones principales. En primer lugar, existe el riesgo de que surja una condición de carrera, en la que el barbero duerme mientras un cliente espera a que el barbero le corte el pelo, debido a que todas las acciones (revisar la sala de espera, entrar a la tienda, tomar una silla de la sala de espera) —tomar una cierta cantidad de tiempo. En concreto, un cliente puede llegar y encontrar al barbero cortándole el pelo y regresar a la sala de espera para tomar asiento, pero mientras camina de regreso a la sala de espera el barbero termina el corte de pelo y se dirige a la sala de espera, que encuentra vacía (porque el el cliente camina lentamente o va al baño) y por lo tanto se queda dormido en el sillón del peluquero. En segundo lugar, puede ocurrir otro problema cuando dos clientes llegan al mismo tiempo cuando sólo hay un asiento vacío en la sala de espera y ambos intentan sentarse en esa única silla; Sólo la primera persona que llegue a la silla podrá sentarse.

Un problema de varios barberos durmiendo tiene la complejidad adicional de coordinar a varios barberos entre los clientes que esperan.

Soluciones

Hay varias soluciones posibles, pero todas requieren un mutex, lo que garantiza que solo uno de los participantes pueda cambiar de estado a la vez. El barbero debe adquirir el mutex del estado de la habitación antes de buscar clientes y liberarlo cuando empiezan a dormir o a cortarse el pelo; el cliente debe adquirirlo antes de entrar a la tienda y liberarlo una vez que esté sentado en una sala de espera o sillón de barbero, y también cuando salga de la tienda porque no hay asientos disponibles. Esto solucionaría los dos problemas mencionados anteriormente. También se requieren varios semáforos para indicar el estado del sistema. Por ejemplo, se podría almacenar el número de personas en la sala de espera.

Implementación

El siguiente pseudocódigo garantiza la sincronización entre el peluquero y el cliente y está libre de interbloqueos, pero puede provocar que un cliente muera de hambre. El problema del hambre se puede resolver con una cola de primero en entrar, primero en salir (FIFO). El semáforo proporcionaría dos funciones: wait() y signal(), que en términos de código C corresponderían a P() y V(), respectivamente.

# Los dos primeros son mutexes (sólo 0 o 1 posible)Semaphore barbero Listo = 0Semaphore accessWRSeats = 1 # if 1, the number of seats in the waiting room can be increaseed or decrementedSemaphore custReady = 0 # the number of customers currently in the waiting room, ready to be servedint numberOfFreeWRSeats = N # Número total de asientos en la sala de esperadef Barber(): mientras verdadero: Corre en un bucle infinito. Espera.()custReady) # Trate de adquirir un cliente - si ninguno está disponible, vaya a dormir. Espera.()accessWRSeats) # Despertarse - tratar de obtener acceso para modificar # de asientos disponibles, de otro modo dormir. numberOfFreeWRSeats += 1 # Una silla de sala de espera se hace libre. señal de señal()barbero Listo) Estoy listo para cortar. señal de señal()accessWRSeats) # Ya no necesito la cerradura en las sillas. # (Pelo cortado aquí.)def Cliente(): mientras verdadero: # Corre en un bucle infinito para simular múltiples clientes. Espera.()accessWRSeats) # Intenta acceder a las sillas de la sala de espera. si numberOfFreeWRSeats ■ 0: # Si hay asientos gratis: numberOfFreeWRSeats -= 1 # Siéntate en una silla señal de señal()custReady) # Notificar al barbero, que está esperando hasta que haya un cliente señal de señal()accessWRSeats) # No necesito cerrar las sillas más Espera.()barbero Listo) # Espera hasta que el barbero esté listo # (Heve hair cut here.) más: # De lo contrario, no hay asientos libres; mala suerte... señal de señal()accessWRSeats) # pero no olvides soltar la cerradura en los asientos! # (Deja sin un corte de pelo.)