The Sleeping Barber Problem is a classic computer science problem that illustrates challenges in synchronization and concurrency.
Problem Description:
A barbershop has one barber, one barber chair, and several waiting chairs.
When there are no customers, the barber sleeps in the barber chair.
When a customer arrives, they must wake the barber if they are sleeping.
If the barber is busy but waiting chairs are available, the customer sits and waits.
If all chairs are full, the customer leaves.
After finishing a haircut, the barber checks for waiting customers. If none, goes back to sleep.
This problem represents real-world scenarios where resources (barber) must be synchronized with requests (customers) using semaphores or similar concurrency mechanisms.
Solution Approach
In a proper concurrent implementation, the solution typically uses semaphores to coordinate between barber and customer threads:
Semaphores used:
customers: Counts waiting customers (initialized to 0)
barber: Signals if barber is available (initialized to 0)
mutex: Protects access to the waiting counter (initialized to 1)
Barber's workflow:
Wait for customers (P(customers)) - sleeps if none available
Signal barber is ready (V(barber))
Cut hair
Check for more customers
Customer's workflow:
Enter mutex to check/update waiting count (P(mutex))
If chairs are full, leave; otherwise take a seat
Signal arrival (V(customers))
Release mutex (V(mutex))
Wait for barber (P(barber))
Get haircut
In this web simulation, we use JavaScript timeouts and callbacks to simulate the concurrent behavior without actual threads.
Pseudocode Implementation
// Semaphores
semaphore customers = 0 // Counts waiting customers
semaphore barber = 0 // Signals barber availability
semaphore mutex = 1 // Protects access to waiting counter
int waiting = 0 // Customers currently waiting
// Barber Thread
function barber() {
while (true) {
customers.P() // Wait for a customer (sleep if none)
mutex.P() // Enter critical section
waiting = waiting - 1// Reduce waiting count
barber.V() // Signal barber is ready
mutex.V() // Exit critical section
cutHair() // Cut hair (working)
}
}
// Customer Thread
function customer() {
mutex.P() // Enter critical section
if (waiting < CHAIRS) {// If chairs available
waiting = waiting + 1// Increment waiting count
customers.V() // Signal arrival to barber
mutex.V() // Exit critical section
barber.P() // Wait for barber
getHaircut() // Get haircut
} else {
mutex.V() // Exit critical section
leaveShop() // Leave if no seats
}
}
// Note: In semaphore operations:
// P() is "wait" operation (decrements semaphore)
// V() is "signal" operation (increments semaphore)