Sleeping Barber Problem

Table of Contents

• What is the sleeping barber problem
• What is a synchronization problem in computer science
• What are Semaphores
• What are Mutex
• What is a Thread?
• Solution

What is the sleeping barber problem?

The sleeping barber problem is a synchronization problem in computer science that deals with the management of a shared resource by multiple processes. The problem is presented in the example of a barber shop where there is one barber who cuts hair and a number of chairs for waiting customers.

The problem statement is that there is a barber who owns a shop with one barber chair and a waiting room with a certain number of chairs for customers to wait. When the barber has no customers to serve, he goes to sleep in his chair and when a new customer arrives and finds the barber sleeping, they have to wake him up to get a haircut. If there are no empty chairs in the waiting room, then the customer will leave but if there are empty chairs, the customer will sit in one of them and wait their turn. The problem is to come up with a solution that makes sure that the barber is not awakened unnecessarily and that the customers do not enter the shop when it is full and that the customers are served in the order in which they arrive.

The image below shows the main characteristics of the problem:

What is a synchronization problem in computer science?

In computer science synchronization problems arise when multiple processeses need to access shared resources or data simultaneously. These types of problems occur because it's possible for one process to read or modify a shared resource at the same time that another process is attempting to do the same thing. This can result in unpredictable or incorrect behavior, such as race conditions, deadlocks, or data corruption.

What are Semaphores?

Semaphores are a synchronization mechanism used to coordinate the activities of multiple processes in a computer system. They are used to enforce mutual exclusion, avoid race conditions and implement synchronization between multiple processes.

What are Mutex?

In computer science a mutex (mutual exclusion object) is a program object that is created so that a multiple program thread can take turns sharing the same resource such as access to a file.

What is a Thread?

A thread is placeholder information associated with a single use of a program that can handle multiple users. In a browser many tabs can be viewed as threads. Microsoft Word uses many threads such as formatting text from one thread, processing input from another thread etc.

Also the sleeping barber problem can be used to demostrate multi threading in computer programming. In a multi threaded environment, multiple threads of execution can access shared resources simultaneously, which can lead to synchronization issues. For example in a multi-threaded program which is simulating the sleeping barber problem, each thread would represent a customer or the barber. These threads would have to synchronize their access to the waiting room and the barber's chair to ensure that the barber is not called to cut hair when there are no customers and that the customers are not allowed to enter the waiting room if it is full.

Solution

The solution to this problem includes using three semaphores. The first is for the customer which counts the number of customers present in the waiting room. Also the customer in the barber chair is not included because he is not waiting. The second semaphore is the barber. For the barber 0 or 1 is used to tell whether the barber is idle or is working. The third is used to provide the mutual exclusion (mutex) which is required for the process to execute.

In the solution the customer has the record of the number of customers waiting in the waiting room, if the number of customers is equal to the number of chairs in the waiting room then the upcoming customer leaves the barbershop. When the barber shows up in the morning he executes the procedure barber, causing him to block on the semaphore customers because it is initially 0. Then the barber goes to sleep until the first customer comes up. When a customer arrives he executes the customer procedure and the customer acquires the mutex for entering the critical region.

If a second customer enters then they wont be able to do anything until the first one has released the mutex. The customer then checks the chairs in the waiting room and if the waiting customers are less then the number of chairs he sits otherwise he leaves and releases the mutex. If the chair is available then customer sits in the waiting room and increments the variable waiting value and also increases the customer’s semaphore and this wakes up the barber if he is sleeping. At this point the customer and barber are both awake and the barber is ready to give that person a haircut. When the haircut is over, the customer exits the procedure and if there are no customers in waiting room barber sleeps.

Here is the Python3 implementation:

import threading
import time
import random

# Define the maximum number of customers and the number of chairs in the waiting room
MAX_CUSTOMERS = 5
NUM_CHAIRS = 3

# Define the semaphores for the barber, the customers, and the mutex
barber_semaphore = threading.Semaphore(0)
customer_semaphore = threading.Semaphore(0)
mutex = threading.Semaphore(1)

# Define a list to keep track of the waiting customers
waiting_customers = []

# Define the barber thread function
def barber():
	while True:
		print("The barber is sleeping...")
		barber_semaphore.acquire()
		mutex.acquire()
		if len(waiting_customers) > 0:
			customer = waiting_customers.pop(0)
			print(f"The barber is cutting hair for customer {customer}")
			mutex.release()
			time.sleep(random.randint(1, 5))
			print(f"The barber has finished cutting hair for customer {customer}")
			customer_semaphore.release()
		else:
			mutex.release()
	
# Define the customer thread function
def customer(index):
	global waiting_customers
	time.sleep(random.randint(1, 5))
	mutex.acquire()
	if len(waiting_customers) < NUM_CHAIRS:
		waiting_customers.append(index)
		print(f"Customer {index} is waiting in the waiting room")
		mutex.release()
		barber_semaphore.release()
		customer_semaphore.acquire()
		print(f"Customer {index} has finished getting a haircut")
	else:
		print(f"Customer {index} is leaving because the waiting room is full")
		mutex.release()

# Create a thread for the barber
barber_thread = threading.Thread(target=barber)

# Create a thread for each customer
customer_threads = []
for i in range(MAX_CUSTOMERS):
	customer_threads.append(threading.Thread(target=customer, args=(i,)))
	
# Start the barber and customer threads
barber_thread.start()
for thread in customer_threads:
	thread.start()
	
# Wait for the customer

Here in our implementation we can see that the code creates two thread functions, one for the barber and one for the customer. The MAX_CUSTOMERS variable defines the maximum number of customers that can visit the barber shop and the NUM_CHAIRS variable defines the number of chairs in the waiting room.

The barber_semaphore and customer_semaphore variables are semaphores that control access to the barber and customers. The mutex semaphore is a binary semaphore used to protect the waiting_customers list from race conditions. The waiting_customers list keeps track of the customers waiting in the waiting room.

The barber() function is the thread function for the barber. The function runs in an infinite loop and first acquires the barber_semaphore to sleep if there are no customers. When a customer arrives and acquires the mutex, the barber checks if there are any waiting customers, if there are the barber selects the first customer from the list and serves them. The barber then releases the mutex, sleeps for a random amount of time and releases the customer_semaphore to signal to the customer that their haircut is complete. If there are no waiting customers, the barber releases the mutex and goes back to sleep.

The customer(index) function is the thread function for the customers. The index argument is the unique identifier for each customer. The function first sleeps for a random amount of time before entering the barber shop. When the customer acquires the mutex, they check if there is an available chair in the waiting room. If there is then the customer takes a seat and adds themselves to the waiting_customers list. The function then releases the mutex and signals to the barber using the barber_semaphore and waits for their turn using the customer_semaphore. Once the customer's turn arrives, they release the mutex again and print that they have finished getting a haircut. If there are no available chairs in the waiting room, the customer releases the mutex and leaves without getting a haircut.

The code creates a thread for the barber using threading.Thread(), passing the barber() function as the target. Then it creates a thread for each customer using a for loop, passing the customer() function as the target and an index as the argument. Finally, the code starts both the barber and customer threads using the start() method.