It is a synchronization and inter-process communication problem. This problem is based on a barbershop.
A barbershop has a single barber, single barber chair and n number of chairs for customers. When there is no customer in the barbershop then the barber sleeps. When a customer comes, he has to get up the barber. When there are multiple customers, and the barber is cutting one customer’s hair, then the entire customers either wait for their number or they leave the barbershop when all chairs are full.
When the chair is present, the customer waits in the waiting room. It increments the waiting value of the variable. The point at that, both the customer and barber are waking up, and the barber is set to give a haircut. If the haircut is completed, when no any customer in the waiting room, the barber sleeps. The trouble is to program barbers and customers without entering into the race condition.
What is Sleeping Barber Problem?
The Sleeping Barber Problem is a classic problem in computer science that illustrates issues with process synchronization and resource allocation in operating systems. It presents a scenario involving a barbershop with one barber, one barber chair, and a waiting room with several chairs for the customers.
Here’s how the problem unfolds:
- Barber’s Behavior: If there are no customers, the barber goes to sleep. When a customer arrives and finds the barber sleeping, they wake him up for their haircut. If the barber is already cutting someone’s hair, new arrivals wait in the waiting room if there are free chairs available.
- Customer’s Behavior: If a customer arrives and all chairs in the waiting room are occupied, they leave the barbershop (indicating the system must handle a high load by either turning away new requests or queuing them appropriately).
The core of the Sleeping Barber Problem is to ensure the system efficiently manages these interactions without deadlock (where the system gets stuck because the barber and customers are waiting on each other indefinitely) and without busy waiting (where customers continuously check for the barber’s availability, wasting CPU resources).
Scenario Description
Imagine a barbershop with a waiting room with N chairs and a barber room with one barber chair. If there are no customers, the barber goes to sleep. When a customer arrives, they have to check if the barber is asleep or busy:
- If the barber is asleep, the customer wakes him up, and the barber starts servicing the customer.
- If the barber is busy but there are free chairs in the waiting room, the customer sits in one of the free chairs.
- If the barber is busy and there are no free chairs, the customer leaves (indicating that the system must handle this scenario without blocking resources or causing a deadlock).
Sleeping Barber Problem Solution
The problem can be solved using semaphores for synchronization between the barber and the customers:
- Barber Semaphore: Indicates whether the barber is sleeping (0) or working (1). The barber waits on this semaphore, going to sleep if there’s no customer. When a customer arrives and finds the barber asleep, they signal this semaphore to wake the barber up.
- Customer Semaphore: Used for the barber to wait for a customer. If there’s no customer, the barber waits on this semaphore. When a customer arrives, they signal this semaphore to indicate their presence.
- Mutex (Mutual Exclusion Semaphore): Protects access to the waiting room chairs count. Before a customer enters the waiting room or leaves, they acquire this semaphore to ensure that checking for free chairs and sitting down or leaving is done atomically.
It can also be explained as Here, we use 3 semaphores. Waiting customers are calculated by semaphore customers. The number of free barbers (0,1) is the semaphore barbers. The mutex is used for mutual exclusion.
The semaphore would facilitate two functions: wait() and signal(). One semaphore is also needed to represent the state of the system. Waiting customers are also calculated by a shared data variable customers1, which is a copy of customers. It is needed since there is no path to read the present value of the semaphore.
We can’t access the value of semaphores immediately, so we require it here. We also require a semaphore cutting which assures that the barber won’t cut other customer’s hair before the first customer quits.
Key Concepts Demonstrated
- Mutual Exclusion: Ensures that critical sections of code that manipulate shared resources (e.g., the count of available chairs) are not executed by more than one thread or process at a time.
- Synchronization: Coordinates the timing of processes for accessing shared resources, ensuring the barber does not sleep when there are customers waiting and that customers wait or leave based on the availability of the barber or chairs.
- Deadlock Avoidance: The problem setup and solution ensure that the system does not enter a state where processes are waiting on each other indefinitely.
- Starvation Freedom: Ensures that every customer will eventually get served if they wait long enough or leave if the shop is consistently full, thus not being indefinitely denied service.