Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Overview

In this tutorial, we’ll explain the sleeping barber problem. It’s another famous inter-process communication and synchronization problem that takes place in a barbershop. Dijkstra proposed this problem in 1965 to show the complexities when there is more than one operating system process.

2. Problem Definition

In this problem, the barbershop has one barber, one barber chair, and a waiting room with N chairs for the customers. We can depict the problem by sticking with the original proposal, like in the figure below.

barbershop

Let’s look at the characteristics of the problem:

  • The barber sleeps when there is no customer in the waiting room. Therefore, when a customer arrives, he should wake up the barber
  • As we’ve seen from the figure, customers can enter the waiting room and should wait for whether the barber is available or not
  • If other customers keep coming while the barber is cutting a customer’s hair, they sit down in the waiting room
  • Customers leave the barbershop if there is no empty chair in the waiting room

We need to synchronize the barber and the customers so there wouldn’t be any race conditions. Since we have limited resources and waiting tasks, this problem has so many similarities with various queueing situations.

The figure below shows the main characteristics of the problem:

sleepingbarber

3. Solution

In the solution, we use three semaphores:

  • One for customers, which counts the number of waiting customers, excludes the customer in the barber chair since he isn’t waiting.
  • Another one for the situation of the barber, whether he’s waiting or busy.
  • And the last one for the mutual exclusion since there’re some critical sections that should be thread-safe.

Let’s continue with the pseudocode of the solution. We can start with the semaphores and some constants like the number of chairs in the waiting room:

Rendered by QuickLaTeX.com

When the barber comes to the barbershop, he executes the barber routine below. Since there are no customers, he needs to wait until a customer arrives. That’s why he goes to sleep and stays asleep until the first customer arrives. By using the customers semaphore we wait for the barber and provide one of the important synchronization conditions:

Rendered by QuickLaTeX.com

So, we’ve synchronized the barber routine, but we still need to arrange the customer routine to provide a flawless concurrent system for the barbershop. When a customer arrives, he executes the customer() routine. The routine starts by acquiring the mutex to enter the critical region. First, when he arrives at the barbershop, he needs to check if there is an available chair for him. If there isn’t, he leaves the shop. Otherwise, he could wait for the barber, and when the barber is available, he can get a haircut:

Rendered by QuickLaTeX.com

When the haircut is over, the customer leaves the shop by executing the procedure. As we’ve seen, there is no while loop in the customer routine since every customer gets only one haircut at a time. However, the barber keeps doing to get the new customer. If one customer comes to the shop, he gives a haircut. Otherwise, he goes to sleep.

4. Conclusion

In this tutorial, we’ve given a brief definition of the problem and then shared the solution. It’s another important problem in concurrent programming because it applies to other types of queuing problems in computing, networks, industrial engineering, telecommunication, and traffic engineering.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!