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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Проблема[править | править вики-текст]

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

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

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

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

Решение[править | править вики-текст]

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

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]