Problema del peluquero durmiendo - Sleeping barber problem

En informática , el problema del barbero dormido es un problema clásico de comunicación y sincronización entre procesos 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 peluquero 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 (). 

# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the number of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served
int numberOfFreeWRSeats = N     # total number of seats in the waiting room

def Barber():
  while true:                   # Run in an infinite loop.
    wait(custReady)             # Try to acquire a customer - if none is available, go to sleep.
    wait(accessWRSeats)         # Awake - try to get access to modify # of available seats, otherwise sleep.
    numberOfFreeWRSeats += 1    # One waiting room chair becomes free.
    signal(barberReady)         # I am ready to cut.
    signal(accessWRSeats)       # Don't need the lock on the chairs anymore.
    # (Cut hair here.)

def Customer():
  while true:                   # Run in an infinite loop to simulate multiple customers.
    wait(accessWRSeats)         # Try to get access to the waiting room chairs.
    if numberOfFreeWRSeats > 0: # If there are any free seats:
      numberOfFreeWRSeats -= 1  #   sit down in a chair
      signal(custReady)         #   notify the barber, who's waiting until there is a customer
      signal(accessWRSeats)     #   don't need to lock the chairs anymore
      wait(barberReady)         #   wait until the barber is ready
      # (Have hair cut here.)
    else:                       # otherwise, there are no free seats; tough luck --
      signal(accessWRSeats)     #   but don't forget to release the lock on the seats!
      # (Leave without a haircut.)

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.