Введение
Проблема конкурентного доступа в программном обеспечении. В информатике проблема спящего парикмахера — это классическая задача межпроцессного взаимодействия и синхронизации, иллюстрирующая сложности, возникающие при наличии нескольких процессов операционной системы. Проблема была впервые предложена в 1965 году Эдсгером Дейкстрой, который использовал её, чтобы показать, что общие семафоры часто избыточны. Если нет клиентов, парикмахер засыпает в кресле. Клиент должен разбудить парикмахера, если он спит. Если клиент приходит, пока парикмахер занят, он уходит, если все стулья заняты, и садится на свободный стул, если он есть. Когда парикмахер заканчивает стрижку, он осматривает комнату ожидания, чтобы проверить, есть ли там ожидающие клиенты, и засыпает, если их нет.
In computer science, the sleeping barber problem is a classic inter process communication and synchronization problem that illustrates the complexities that arise when there are multiple operating system processes. The problem was originally proposed in 1965 by computer science pioneer Edsger Dijkstra, who used it to make the point that general semaphores are often superfluous. If there are no customers, the barber falls asleep in the chair
A customer must wake the barber if he is asleep
If a customer arrives while the barber is working, the customer leaves if all chairs are occupied and sits in an empty chair if it's available
When the barber finishes a haircut, he inspects the waiting room to see if there are any waiting customers and falls asleep if there are none
Существует два основных осложнения. Во-первых, существует риск возникновения гонки данных, когда парикмахер засыпает, а клиент ждёт, чтобы его постригли. Это происходит из-за того, что все действия — проверка комнаты ожидания, вход в парикмахерскую, занятие стула в комнате ожидания — занимают определённое время. В частности, клиент может прийти и увидеть, что парикмахер стрижёт другого клиента, поэтому он возвращается в комнату ожидания, чтобы занять место, но пока он идёт обратно, парикмахер заканчивает стрижку и идёт в комнату ожидания, где обнаруживает, что она пуста (потому что клиент шёл медленно или отлучился), и поэтому засыпает в кресле. Во-вторых, другая проблема может возникнуть, когда два клиента приходят одновременно, а в комнате ожидания есть только одно свободное место, и оба пытаются сесть на него; только первый успевший занять стул сможет это сделать. Задача о нескольких спящих парикмахерах усложняется необходимостью координировать работу нескольких парикмахеров с ожидающими клиентами.
Решение
Существует несколько возможных решений, но все они требуют использования мьютекса, который гарантирует, что в любой момент времени только один участник может изменять состояние. Парикмахер должен захватить мьютекс статуса помещения перед проверкой наличия клиентов и освободить его, когда он начинает либо спать, либо стричь волосы; клиент должен захватить его перед входом в парикмахерскую и освободить, когда он садится в комнату ожидания или в кресло парикмахера, а также когда он покидает парикмахерскую из-за отсутствия свободных мест. Это решит обе вышеупомянутые проблемы. Кроме того, для индикации состояния системы потребуется несколько семафоров. Например, один из них может хранить количество людей в комнате ожидания.