Войти
В информатике проблема спящего парикмахера - это классическая проблема межпроцессного взаимодействия и синхронизации между несколькими процессами операционной системы . Проблема аналогична тому, как заставить парикмахера работать, когда есть клиенты, отдыхать, когда их нет, и делать это упорядоченным образом.
Проблема спящего цирюльника часто приписывается Эдсгеру Дейкстре (1965), одному из пионеров информатики.
Основана аналогия на гипотетической парикмахерской с одним парикмахером. У парикмахера есть одно кресло в парикмахерской и зал ожидания, в котором есть несколько стульев. Когда парикмахер заканчивает стрижку покупателя, он отпускает покупателя и идет в зал ожидания, чтобы посмотреть, не ждут ли другие. Если есть, он возвращает одного из них к стулу и стригет им волосы. Если их нет, он возвращается на стул и засыпает.
Каждый покупатель, приходя, смотрит, что делает парикмахер. Если парикмахер спит, покупатель будит его и садится в кресло для парикмахерской. Если парикмахер стрижет волосы, клиент остается в зале ожидания. Если в зале ожидания есть свободный стул, покупатель садится на него и ждет своей очереди. Если свободного стула нет, заказчик уходит.
Основываясь на наивном анализе, приведенные выше решения должны гарантировать, что магазин работает правильно: парикмахер стригет волосы всем, кто приходит, пока не исчезнут клиенты, а затем спит до прихода следующего клиента. На практике может возникнуть ряд проблем, которые иллюстрируют общие проблемы планирования.
Все проблемы связаны с тем, что действия парикмахера и покупателя (проверка зала ожидания, вход в магазин, занятие стула в зале ожидания и т. Д.) Занимают неизвестное время.. Например, клиент может прийти и заметить, что парикмахер стрижет волосы, поэтому он идет в зал ожидания. Пока они в пути, парикмахер заканчивает их текущую стрижку и идет проверять комнату ожидания. Поскольку там никого нет (может быть, зал ожидания далеко и парикмахер идет быстрее, минуя клиента, или, может быть, клиент пошел в туалет или шел к стулу, а парикмахер подумал, что он уходит), то парикмахер идет обратно в кресло и засыпает. Парикмахер теперь ждет клиента, а клиент ждет парикмахера.
В другой ситуации два клиента могут прибыть одновременно, если в зале ожидания есть одно место. Они замечают, что парикмахер стрижет волосы, идут в зал ожидания, и оба пытаются занять единственный стул.
Доступно множество возможных решений. Ключевым элементом каждого из них является мьютекс , который гарантирует, что только один из участников может изменить состояние одновременно. Парикмахер должен получить / применить это взаимное исключение (статуса комнаты) перед проверкой клиентов и освободить его, когда они начнут спать или стричь волосы. Покупатель должен приобрести его перед тем, как войти в магазин, и освободить его, когда он сидит в кресле в зале ожидания или в парикмахерском кресле, а также когда они покидают магазин, потому что не было свободных мест. Это устраняет обе проблемы, упомянутые в предыдущем разделе. Также требуется ряд семафоров для индикации состояния системы. Например, можно сохранить количество людей в зале ожидания.
Проблема нескольких спящих парикмахеров связана с дополнительной сложностью координации нескольких парикмахеров среди ожидающих клиентов.
Следующий псевдокод гарантирует синхронизацию между парикмахером и клиентом и не тупиков, но может привести к голоданию заказчика. Проблема голодания может быть решена путем использования очереди, в которую клиенты добавляются по мере их поступления, чтобы парикмахер мог обслуживать их в порядке очереди (FIFO =>First In, First Out) Функции wait () и signal () - это функции, предоставляемые семафорами . В обозначении c-кода wait () - это P (), а signal () - это V ().
# Первые два - мьютексы (возможно только 0 или 1) Semaphore barberReady = 0 Semaphore accessWRSeats = 1 # если 1, количество мест в зале ожидания может увеличиваться или уменьшаться Semaphore custReady = 0 # количество клиентов в данный момент находится в зале ожидания, готов к обслуживанию int numberOfFreeWRSeats = N # общее количество мест в зале ожидания def Barber (): while true: # Запускать в бесконечном цикле. wait (custReady) # Попытаться привлечь клиента - если его нет, ложитесь спать. wait (accessWRSeats) # Пробудить - попытаться получить доступ, чтобы изменить # доступных мест, иначе спите. numberOfFreeWRSeats + = 1 # Один стул в зале ожидания освобождается. signal (barberReady) # Я готов резать. signal (accessWRSeats) # Замок на стульях больше не нужен. # (Подстригите здесь волосы.) Def Customer (): while true: # Выполните бесконечный цикл для имитации нескольких клиентов. wait (accessWRSeats) # Попытайтесь получить доступ к стульям в зале ожидания. if numberOfFreeWRSeats>0: # Если есть свободные места: numberOfFreeWRSeats - = 1 # сесть в кресло, сигнал (custReady) # уведомить парикмахера, который ждет сигнала клиента (accessWRSeats) # блокировать не нужно стулья больше ждут (barberReady) # подождите, пока парикмахер будет готов # (постригитесь здесь.) else: # в противном случае свободных мест нет; не повезло - сигнал (accessWRSeats) # но не забудьте отпустить замок на сиденьях! # (Оставьте без стрижки.)
