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

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

Проблема

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

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

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

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

Решение

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

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

См. также

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

Ссылки

• 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.