Process Synchronization
Sleeping Barber Problem

Sleeping Barber Problem

Problem Statement

The Sleeping Barber Problem is a classic inter-process communication and synchronization problem. It models a barbershop with the following characteristics:

ElementDescription
BarberSleeps when there are no customers. Wakes up and serves a customer if there is one.
CustomersEither get a haircut or leave if the waiting room is full.
Waiting RoomHas a limited number of chairs.

Key Conditions

Solution

  1. If there are no customers, the barber sleeps.

  2. When a customer arrives:

    • If all chairs are occupied, the customer leaves.
    • If there is a free chair, the customer sits and waits.

  3. When the barber finishes a haircut:

    • He checks for waiting customers.
    • If no one is waiting, he sleeps again.

Synchronization Primitives

SemaphoreInitial ValuePurpose
customers0Counts waiting customers (to wake up barber).
barbers0Number of barbers ready to cut hair.
mutex1Ensures mutual exclusion for access to waiting.

Shared Variables 

1int waiting = 0;           // number of customers waiting
2int CHAIRS = N;            // total number of chairs
3
4semaphore customers = 0;   // customers waiting
5semaphore barbers = 0;     // barbers ready
6semaphore mutex = 1;       // for mutual exclusion

Customer Process 

 1Customer() {
 2    wait(mutex);                  // enter critical section
 3    if (waiting < CHAIRS) {
 4        waiting++;                // sit in a waiting chair
 5        signal(customers);        // notify barber
 6        signal(mutex);            // leave critical section
 7
 8        wait(barbers);            // wait to be called by barber
 9        get_haircut();
10    } else {
11        signal(mutex);            // leave (no chair available)
12        leave_shop();
13    }
14}

Barber Process 

 1Barber() {
 2    while (true) {
 3        wait(customers);          // sleep if no customers
 4        wait(mutex);              // enter critical section
 5
 6        waiting--;                // take a customer out of waiting
 7        signal(barbers);          // call customer
 8        signal(mutex);            // leave critical section
 9
10        cut_hair();               // perform haircut
11    }
12}

How the Semaphores Coordinate the Processes

StepSemaphore UsedEffect
Customer arriveswait(mutex)Enters critical section to check space in waiting room
Free chair availablewaiting++Sits and waits
Notify barbersignal(customers)Increments count of waiting customers
Barber sleepswait(customers)Waits for a customer to arrive
Barber wakes upsignal(barbers)Wakes up and allows customer to get haircut
Protect waiting countermutexEnsures waiting is updated atomically

Correctness Achieved

RequirementMechanism
Mutual Exclusionmutex protects access to waiting variable.
Deadlock-FreeSemaphores coordinate process entry without circular waits.
No StarvationFIFO nature of semaphore queues ensures fair access.
EfficiencyBarber only sleeps when no customers; customers only wait if space is available.

This model ensures that both customers and barbers behave correctly and efficiently with respect to the limited resources in the barbershop.

Last updated on
Dining Philosopher ProblemDeadlock