The Sleeping Barber problem is an inter-process communication and synchronization problem. The original variation of the problem is attributed to Dijkstra, but we will work with the following variation:

A barbershop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber.

Another way to look at the Sleeping Barber Problem is to think of the Producer-Consumer problem, except that the roles of Producer and Consumer are not analogous to the usual business point of view where usually the Producer would be the barber and the Consumer would be the customer.

Customers are produced when they come to the barbershop, and barbers consume the customers when they give them haircuts.

Some concepts are vital to keep in mind before proposing a solution to this problem, such as race conditions.

Race Conditions

Processes or threads that are working together may share common storage that is used to read and write, whether it is located in memory or in a shared file. Race conditions are situations where the final result of an operation on the shared data depends on which process or thread runs precisely when.

Avoiding race conditions requires that read and write operations on shared data are never done at the same time when executed by more than one process or thread simultaneously. Which brings us to another important concept, mutual exclusion.

Mutual Exclusion

Ensuring that while one process or thread is performing read or write operations on shared data others are prohibited of doing the same.

Processes and threads aren't always executing operations that might lead to race conditions, part of the time they are running internal computations outside of their critical region.

Critical Region

Part of the program where the shared memory or file is accessed.

To have processes or threads running in parallel and cooperating efficiently while using shared data, we need four conditions to be satisfied.

  • 1. No two or more can be simultaneously inside their critical region.
  • 2. No assumptions may be made about number of CPUs or speed.
  • 3. No blocking others while outside the critical region.
  • 4. It should not take long to enter the critical region.