WikiDer > Проблема сна парикмахера

Sleeping barber problem

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

Проблема спящего парикмахера часто приписывается Эдсгер Дейкстра (1965), один из пионеров информатики.

Определение

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

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

Возникающие проблемы

Основываясь на наивном анализе, приведенные выше решения должны гарантировать, что магазин функционирует правильно: парикмахер стригет волосы всем, кто приходит, пока не кончатся клиенты, а затем спит до прихода следующего покупателя. На практике может возникнуть ряд проблем, которые иллюстрируют общие проблемы планирования.

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

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

Решения

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

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

Реализация

Следующее псевдокод гарантирует синхронизацию между парикмахером и клиентом и тупик бесплатно, но может привести к голодание заказчика. Проблема голодания может быть решена путем использования очереди, в которую клиенты добавляются по мере их поступления, чтобы парикмахер мог обслуживать их в порядке очереди (FIFO => First In, First Out) Функции wait () и signal ( ) - это функции, предоставляемые семафоры. В обозначении c-кода wait () - это P (), а signal () - это V ().

# Первые два - мьютексы (возможны только 0 или 1)Семафор парикмахер = 0Семафор accessWRSeats = 1     # если 1, количество мест в зале ожидания можно увеличивать или уменьшатьСемафор custReady = 0         # количество клиентов в зале ожидания, готовых к обслуживаниюint numberOfFreeWRSeats = N     # общее количество мест в зале ожиданияdef Парикмахер():  в то время как правда:                   # Запускаем бесконечный цикл.    Подождите(custReady)             # Попытайтесь привлечь клиента - если его нет, ложитесь спать.    Подождите(accessWRSeats)         # Пробудиться - попытаться получить доступ к изменению # доступных мест, иначе спать.    numberOfFreeWRSeats += 1    # Одно кресло в зале ожидания освобождается.    сигнал(парикмахер)         # Я готов резать.    сигнал(accessWRSeats)       # Больше не нужен замок на стульях.    # (Стричь здесь волосы.)def Покупатель():  в то время как правда:                   # Запуск бесконечного цикла для имитации нескольких клиентов.    Подождите(accessWRSeats)         # Попытайтесь получить доступ к стульям в зале ожидания.    если numberOfFreeWRSeats > 0: # Если есть свободные места:      numberOfFreeWRSeats -= 1  # сесть в кресло      сигнал(custReady)         # уведомить парикмахера, который ждет, пока появится клиент      сигнал(accessWRSeats)     # больше не нужно запирать стулья      Подождите(парикмахер)         # ждать, пока парикмахер будет готов      # (Постричься здесь.)    еще:                       # в противном случае свободных мест нет; везет, как утопленнику --      сигнал(accessWRSeats)     # но не забудьте разблокировать сиденья!      # (Выйти без стрижки.)

Смотрите также

использованная литература

  • Современные операционные системы (2-е издание) от Эндрю С. Таненбаум (ISBN 0-13-031358-0)
  • Маленькая книга семафоров Аллен Б. Дауни, http://greenteapress.com/semaphores
  • Взаимодействующие последовательные процессы Э.В. Дейкстры. Технический отчет EWD-123, 1965, Технологический университет Эйндховена, Нидерланды.