En informática , el problema del barbero dormido es un problema clásico de comunicación entre procesos y sincronización entre múltiples procesos del sistema operativo . El problema es análogo al de mantener a un barbero trabajando cuando hay clientes, descansando cuando no los hay, y hacerlo de forma ordenada.
El problema del barbero durmiente se atribuye a menudo a Edsger Dijkstra (1965), uno de los pioneros en informática.
Definición
La analogía se basa en una peluquería hipotética con un peluquero. El peluquero tiene una silla de barbero en una sala de despiece y una sala de espera que contiene varias sillas. Cuando el peluquero termina de cortar el cabello de un cliente, lo despide y se dirige a la sala de espera para ver si hay otros esperando. Si los hay, lleva a uno de ellos a la silla y le corta el pelo. Si no hay ninguno, vuelve a la silla y duerme en ella.
Cada cliente, cuando llega, mira para ver qué está haciendo el peluquero. Si el peluquero está durmiendo, el cliente lo despierta y se sienta en la silla de la sala de despiece. Si el peluquero está cortando el pelo, el cliente se queda en la sala de espera. Si hay una silla libre en la sala de espera, el cliente se sienta en ella y espera su turno. Si no hay silla libre, el cliente se marcha.
Problemas que surgen
Con base en un análisis ingenuo, las decisiones anteriores deben asegurar que la tienda funcione correctamente, con el peluquero cortando el cabello de cualquiera que llegue hasta que no haya más clientes, y luego durmiendo hasta que llegue el próximo cliente. En la práctica, pueden ocurrir varios problemas que son ilustrativos de problemas generales de programación.
Todos los problemas están relacionados con el hecho de que las acciones tanto del peluquero como del cliente (revisar la sala de espera, entrar en la tienda, tomar una silla de la sala de espera, etc.) toman una cantidad de tiempo desconocida. Por ejemplo, un cliente puede llegar y observar que el peluquero se está cortando el pelo, por lo que se dirige a la sala de espera. Mientras están en camino, el peluquero termina su corte de pelo actual y va a revisar la sala de espera. Como no hay nadie (tal vez la sala de espera está lejos y el peluquero camina más rápido pasando al cliente, o tal vez el cliente fue al baño o se dirigía hacia la silla y el peluquero pensó que se iba), entonces el peluquero va vuelve a su silla y duerme. El peluquero ahora está esperando a un cliente, pero el cliente está esperando al peluquero.
En otra situación, pueden llegar dos clientes al mismo tiempo cuando hay un solo asiento en la sala de espera. Observan que el peluquero se está cortando el pelo, van a la sala de espera y ambos intentan ocupar la única silla.
Soluciones
Hay muchas posibles soluciones disponibles. El elemento clave de cada uno es un mutex , que asegura que solo uno de los participantes pueda cambiar de estado a la vez. El peluquero debe adquirir / hacer cumplir esta exclusión mutua (del estado de la habitación) antes de verificar si hay clientes y liberarla cuando comiencen a dormir o cortarse el cabello. Un cliente debe adquirirlo antes de ingresar a la tienda y liberarlo una vez que esté sentado en una silla de la sala de espera o en la silla de barbero, y también cuando salga de la tienda porque no había asientos disponibles. Esto elimina los dos problemas mencionados en la sección anterior. 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.
Un problema de varios peluqueros durmientes tiene la complejidad adicional de coordinar a varios peluqueros entre los clientes que esperan.
Implementación
El siguiente pseudocódigo garantiza la sincronización entre el peluquero y el cliente y está libre de interbloqueo , pero puede provocar la inanición de un cliente. El problema de la inanición se puede resolver utilizando una cola donde los clientes se agregan a medida que llegan, de modo que el barbero pueda atenderlos por orden de llegada (FIFO => Primero en entrar, primero en salir) Las funciones esperar () y señalizar ( ) son funciones proporcionadas por los semáforos . En notación de código C, una espera () es una P () y una señal () es una V ().
# Los dos primeros son mutex (solo 0 o 1 posible) Semaphore barberReady = 0 Semaphore accessWRSeats = 1 # si 1, el número de asientos en la sala de espera se puede incrementar o disminuir Semaphore custReady = 0 # el número de clientes actualmente en el sala de espera, lista para ser atendida int numberOfFreeWRSeats = N # número total de asientos en la sala de esperadef Barber (): while true : # Ejecutar en un bucle infinito. wait ( custReady ) # Intente adquirir un cliente; si no hay ninguno disponible, vaya a dormir. wait ( accessWRSeats ) # Awake: intente obtener acceso para modificar el número de asientos disponibles; de lo contrario, duerma. numberOfFreeWRSeats + = 1 # Una silla de la sala de espera queda libre. señal ( barberReady ) # Estoy listo para cortar. signal ( accessWRSeats ) # Ya no es necesario el candado en las sillas. # (Corta el cabello aquí.)def Customer (): while true : # Ejecutar en un ciclo infinito para simular múltiples clientes. wait ( accessWRSeats ) # Intente acceder a las sillas de la sala de espera. if numberOfFreeWRSeats > 0 : # Si hay asientos libres: numberOfFreeWRSeats - = 1 # sentarse en una silla señal ( custReady ) # notificar al peluquero, que está esperando hasta que haya una señal de cliente ( accessWRSeats ) # no es necesario bloquear las sillas ya esperan ( barberReady ) # espera hasta que el peluquero esté listo # (Córtate el pelo aquí.) else : # de lo contrario, no hay asientos libres; mala suerte - señal ( accessWRSeats ) # ¡pero no te olvides de soltar el seguro de los asientos! # (Salir sin cortar el pelo).
Ver también
Referencias
- Sistemas operativos modernos (segunda edición) por Andrew S. Tanenbaum ( ISBN 0-13-031358-0 )
- El pequeño libro de los semáforos de Allen B. Downey, http://greenteapress.com/semaphores
- Cooperación de procesos secuenciales por EW Dijkstra. Informe técnico EWD-123, 1965, Universidad Tecnológica de Eindhoven, Países Bajos.