睡眠理发师问题

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 chairs for the customers. We can depict the problem by sticking with the original proposal, like in the figure below.

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:

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:

function ConstantsAndSyncPrimitives():
    // OUTPUT
    //    Initializes some constants and synchronization primitives for the sleeping barber problem
    
    CHAIRS <- 5
    customers <- 0
    barbers <- 0
    mutex <- 1
    num_waiting <- 0

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 semaphore we wait for the barber and provide one of the important synchronization conditions:

function BarberRoutine():
    // OUTPUT
    //    synchronize the barber's actions with the arrival of customers

    while true:
        sem_wait(customers)
        sem_wait(mutex)
        waiting <- waiting - 1
        sem_post(barbers)
        sem_post(mutex)
        cut_hair()

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 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:

function CustomerRoutine():
    // INPUT
    //    None
    // OUTPUT
    //    Synchronize the customer's behavior in the barbershop
    
    sem_wait(mutex)
    
    if waiting < CHAIRS:
        waiting <- waiting + 1
        sem_post(customers)
        
        sem_post(mutex)
        
        sem_wait(barbers)
        
        get_haircut()
    
    sem_post(mutex)

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.