Проблема со спящим парикмахером

В информатике — проблема спящего парикмахера это классическая проблема межпроцессного взаимодействия и синхронизации , которая иллюстрирует сложности, возникающие при наличии нескольких операционной системы процессов .

Первоначально задача была предложена в 1965 году пионером информатики Эдсгером Дейкстрой . который использовал его, чтобы подчеркнуть, что общие семафоры часто бывают излишними.

Постановка задачи

Представьте себе гипотетическую парикмахерскую с одним парикмахером, одним парикмахерским креслом и залом ожидания с n стульями ( n может быть 0) для ожидающих клиентов. Применяются следующие правила:

• Если клиентов нет, парикмахер засыпает в кресле.
• Клиент должен разбудить парикмахера, если он спит.
• Если клиент приходит, пока парикмахер работает, клиент уходит, если все стулья заняты, и садится на пустой стул, если он доступен.
• Когда парикмахер заканчивает стрижку, он осматривает зал ожидания, чтобы увидеть, есть ли ожидающие клиенты, и засыпает, если их нет.

Есть две основные сложности. Во-первых, существует риск возникновения состояния гонки , когда парикмахер спит, пока клиент ждет, пока парикмахер его пострижет, возникнет из-за того, что все действия — проверка зала ожидания, вход в магазин, взятие стула в зале ожидания — занять определенное время. В частности, клиент может прийти и обнаружить, что парикмахер стрижет волосы, и он возвращается в зал ожидания, чтобы занять место, но, возвращаясь в зал ожидания, парикмахер заканчивает стрижку и идет в зал ожидания, который оказывается пустым (потому что клиент медленно ходит или пошел в туалет) и поэтому засыпает в парикмахерском кресле. Во-вторых, другая проблема может возникнуть, когда два клиента приходят одновременно, когда в зале ожидания есть только одно свободное место и оба пытаются сесть на один стул; сесть сможет только тот, кто первым доберется до стула.

Проблема нескольких спящих парикмахеров имеет дополнительную сложность, связанную с координацией нескольких парикмахеров среди ожидающих клиентов.

Решения

Существует несколько возможных решений, но для всех решений требуется мьютекс , который гарантирует, что только один из участников может изменить состояние одновременно. Парикмахер должен получить мьютекс состояния комнаты перед проверкой наличия клиентов и освободить его, когда они начинают спать или стричься; покупатель должен приобрести его перед входом в магазин и отдать, когда он сидит в зале ожидания или в кресле парикмахера, а также когда он покидает магазин из-за отсутствия свободных мест. Это решит обе проблемы, упомянутые выше. ряд семафоров Для индикации состояния системы также требуется . Например, можно сохранить количество людей в зале ожидания.

Реализация

Следующий псевдокод гарантирует синхронизацию между парикмахером и клиентом и не допускает взаимоблокировок , но может привести к истощению клиента. Проблему голодания можно решить с помощью «первым пришел – первым обслужен» (FIFO) очереди . Семафор : будет выполнять две функции wait() и signal(), что с точки зрения кода C будет соответствовать P() и 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.)

См. также

• Проблема обедающих философов
• Проблема курильщиков сигарет
• Проблема производителей-потребителей
• Проблема читателей и писателей