Sleeping Barber Problem in Operating System

The Sleeping Barber Problem is one of the most well-known examples in operating systems and concurrent programming, used to demonstrate how processes can coordinate access to shared resources without causing errors like race conditions, deadlocks, or starvation. The problem is set in a barbershop scenario, making it easier to visualize the real-world implications of process synchronization.

Imagine a small barbershop with one barber, a single barber chair in the work area, and N chairs in the waiting room for customers. The barber’s schedule depends entirely on the flow of customers. If there are no customers, the barber does not stay idle in a busy-waiting loop; instead, he goes to sleep until someone wakes him. When a customer arrives and finds the barber sleeping, they wake him up so that the haircut can begin immediately.

If the barber is busy cutting another customer’s hair, the new arrival must check for a free chair in the waiting area. If a chair is available, the customer sits and waits their turn. However, if all the chairs are already occupied, the customer leaves, indicating that the system must be able to reject new requests when the capacity is full.

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

1. 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.
2. 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 of Barbershop

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).

Synchronization Challenge

The Sleeping Barber Problem is not about haircuts at all, it is about coordinating multiple processes that share limited resources. In the analogy:

• The barber chair is a shared resource that can only be used by one customer at a time.
• The waiting room chairs represent a finite buffer where requests can be queued.
• The barber and customers are separate processes that must communicate without conflicting with each other.

Without proper synchronization, you might have multiple customers trying to take the same seat, the barber serving more than one customer at the same time, or even cases where the barber sleeps despite customers waiting, all of which are logical errors in the system.

Sleeping Barber Semaphore-Based Solution

The most common solution to this problem uses semaphores — synchronization primitives that allow processes to signal each other and control access to shared resources. Typically, three semaphores are used:

1. customers – Counts the number of customers waiting (including the one possibly being served). If there are no customers, the barber waits on this semaphore.
2. barbers – Signals when the barber is ready to cut hair. Customers wait on this semaphore until it’s their turn.
3. mutex – Ensures mutual exclusion when accessing shared variables such as the number of free chairs. This prevents race conditions where multiple customers could incorrectly update the count simultaneously.

Additionally, a variable (often called waiting) is used to track how many customers are currently in the waiting room. Since you can’t directly check the value of a semaphore without affecting it, this variable helps keep a record without interfering with semaphore behavior.

Workflow for Customers:
When a customer arrives, they first acquire the mutex lock to check if there is a free chair. If there is, they increment waiting, signal the customers semaphore (indicating that a customer is ready), release mutex, and then wait on barbers for their turn. If no chair is available, they release mutex and leave.

Workflow for Barber:
The barber waits on the customers semaphore until at least one customer is available. Once signaled, the barber acquires mutex, decrements waiting (freeing up a chair), signals barbers to invite a customer, releases mutex, and then performs the haircut. After finishing, the barber repeats the cycle.

Key Concepts

• 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.

Conclusion

The Sleeping Barber Problem is a simplified model of many real-world computing problems where resources are limited, and processes must be carefully coordinated. It is closely related to scenarios like thread pool management, request queue handling in servers, and job scheduling in operating systems.