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

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

Проблема

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

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

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

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

Решение

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

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

См. также

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

Ссылки

• Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
• The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
• Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.