Dining Philosophers and Sleeping Barber are classical Operating System synchronization problems used to explain resource sharing, blocking, deadlock, starvation and semaphore coordination. In the Dining Philosophers problem, five philosophers compete for five forks and each philosopher needs two forks to eat. A careless solution can deadlock if everyone holds one fork and waits for the other. In the Sleeping Barber problem, one barber, one barber chair and a limited waiting room must coordinate arriving customers. If no customer exists, the barber sleeps; if the waiting room is full, a new customer leaves. This chapter explains both problems from the story first, then builds the semaphore logic, solved traces and deadlock-free approaches step by step.
Why Are These Problems So Important in Operating Systems?
Both problems are small stories that represent real synchronization situations. They help students see why processes cannot simply grab shared resources whenever they want.
Dining Philosophers
Focuses on multiple processes competing for multiple resources and shows how circular waiting can cause deadlock.
Sleeping Barber
Focuses on coordination between a service process and arriving client processes when waiting space is limited.
These problems make much more sense if you already understand Semaphores in OS and Critical Section & Mutual Exclusion.
What Is the Dining Philosophers Problem?
The Dining Philosophers Problem has five philosophers sitting around a circular table with one fork between each pair. A philosopher must hold both the left and right fork to eat.
Each philosopher repeatedly does two things: thinks and eats. Thinking needs no fork. Eating needs two forks.
5 PHILOSOPHERS
5 FORKS
How Does Deadlock Happen?
Imagine every philosopher follows this rule:
Now suppose all five philosophers pick up their left fork at almost the same time.
waits F0
waits F1
waits F2
waits F3
waits F4
Every philosopher holds one fork and waits for another fork held by the next philosopher. Nobody can move forward. This is deadlock.
Which Deadlock Conditions Appear Here?
The Dining Philosophers problem is therefore a perfect visual example of the four classic deadlock conditions.
How Can Forks Be Represented With Semaphores?
Each fork can be represented as a binary semaphore initialized to 1.
A philosopher waits on the two required forks before eating and signals them after eating.
Naive Philosopher Pi
while (true) {
think();
wait(left_fork);
wait(right_fork);
eat();
signal(right_fork);
signal(left_fork);
}
Main Problem
If every philosopher takes one fork first, all five can hold one resource and wait forever for the second.
How Can We Prevent Dining Philosopher Deadlock?
1. Allow at most four philosophers to try
Use another semaphore initialized to 4. With only four philosophers competing for forks, the complete circular wait can be broken.
2. Pick forks in a global order
Always request the lower-numbered fork first and then the higher-numbered fork. This removes circular resource ordering.
3. Make one philosopher reverse order
For example, four philosophers pick left then right while one philosopher picks right then left. This breaks the perfect cycle.
4. Use a monitor/state-based solution
A philosopher eats only when both neighbors are not eating, while condition variables manage waiting safely.
Solution Using a “Room” Semaphore of 4
Add:
Each philosopher must enter the room before trying to pick forks.
Deadlock-Free Idea
while (true) {
think();
wait(room);
wait(left_fork);
wait(right_fork);
eat();
signal(right_fork);
signal(left_fork);
signal(room);
}
Why it helps
Only 4 philosophers can compete for 5 forks. At least one philosopher can eventually obtain two forks and eat. The full 5-process circular wait is broken.
Simple Dining Philosophers Execution Trace
Can Dining Philosophers Still Have Starvation?
Yes. A deadlock-free solution is not automatically starvation-free.
A philosopher may repeatedly lose access to forks while neighbors keep getting them first. Fair queueing or a monitor design may be needed to provide stronger fairness.
Deadlock
No philosopher in the deadlocked set can move forward.
Starvation
The system keeps making progress, but one unlucky philosopher waits for an extremely long time.
What Is the Sleeping Barber Problem?
The Sleeping Barber Problem models a barber shop with one barber, one barber chair and a limited number of waiting chairs. If no customer is present, the barber sleeps. If a customer arrives and the barber is sleeping, the customer wakes the barber. If the barber is busy, the customer waits if a chair is free. If all waiting chairs are occupied, the customer leaves.
Customer
Customer
Empty
Empty
new customers arrive
Main Sleeping Barber Synchronization Rules
Which Semaphores Are Used in the Sleeping Barber Solution?
Typical initialization is:
Sleeping Barber Semaphore Solution: Barber Code
Barber
while (true) {
wait(customers);
wait(mutex);
waiting = waiting - 1;
signal(barbers);
signal(mutex);
cut_hair();
}
Meaning
sleep if no customer lock waiting count take one waiting customer tell customer barber is ready unlock shared count cut hair
Sleeping Barber Semaphore Solution: Customer Code
Customer
wait(mutex);
if (waiting < chairs) {
waiting = waiting + 1;
signal(customers);
signal(mutex);
wait(barbers);
get_haircut();
}
else {
signal(mutex);
leave_shop();
}
Meaning
lock waiting count
check free chair
if chair exists:
join queue
wake/notify barber
unlock
wait for barber
else:
unlock
leave shop
Sleeping Barber Example With 3 Waiting Chairs
Assume the barber is sleeping and all three waiting chairs are empty.
Why Is mutex Needed in the Barber Problem?
The variable waiting is shared. Many customers can arrive while the barber is also changing the number of waiting customers.
mutex protects the check-and-update of the waiting count so two customers do not both claim the same last chair.
Without mutual exclusion, two customers could read the same old waiting value and both believe that one free chair exists.
customers, barbers and mutex: Different Jobs
| Semaphore / Variable | Main Purpose | What Goes Wrong Without It? |
|---|---|---|
| customers | Counts/announces waiting customers | Barber would not know when work exists |
| barbers | Signals barber readiness to a customer | Customer may not coordinate correctly with service |
| mutex | Protects waiting count and chair decisions | Race conditions on waiting-room state |
| waiting | Tracks occupied waiting chairs | Cannot know whether new customer can stay |
| chairs | Maximum waiting-room capacity | No bounded waiting-room rule |
What Happens in These Classical Scenarios?
Dining Philosophers: Naive Deadlock
Diagnosis
Dining Philosophers vs Sleeping Barber
| Point | Dining Philosophers | Sleeping Barber |
|---|---|---|
| Main idea | Processes compete for multiple resources | Service process coordinates with arriving clients |
| Main resource | Forks | Barber chair and waiting chairs |
| Main risk | Deadlock and starvation | Race conditions, lost coordination, full waiting room |
| Common semaphore use | Fork semaphores plus optional room/monitor logic | customers, barbers and mutex |
| Capacity issue | Limited forks | Limited waiting chairs |
| Teaching focus | Resource allocation and circular wait | Blocking/wakeup and bounded waiting-room coordination |
Common Student Confusions
How to Write These Problems in Semester Exams
Problem definition
Write the story, shared resources and the main synchronization problem.
One classical problem
Add a diagram, semaphore variables and explain how deadlock or waiting is handled.
Complete answer
Write full semaphore pseudocode, explain every semaphore, add a solved trace and discuss deadlock/starvation or full waiting-room cases.
Fast memory trick
Dining Philosophers = forks + circular wait · Sleeping Barber = customers + chairs + wake/sleepPractice Questions With Answers
1. What is the Dining Philosophers Problem?
It is a synchronization problem where philosophers compete for shared forks and each philosopher needs two forks to eat.
2. How can deadlock occur in Dining Philosophers?
If every philosopher picks one fork and waits for the second, a circular wait can form and nobody can proceed.
3. How can a room semaphore prevent Dining Philosopher deadlock?
If room is initialized to 4, at most four of five philosophers compete for forks at one time, which breaks the complete five-process circular wait.
4. Can Dining Philosophers have starvation?
Yes. A solution may avoid deadlock but still allow one philosopher to wait for a very long time if access is unfair.
5. What is the Sleeping Barber Problem?
It is a synchronization problem where one barber serves customers, sleeps when no customer exists, and uses a limited waiting room for customers who arrive while the barber is busy.
6. What does the customers semaphore do?
It counts or announces waiting customers and allows the barber to sleep when no customer exists.
7. Why is mutex needed in Sleeping Barber?
mutex protects the shared waiting count and prevents multiple customers from claiming the same free chair through a race condition.
8. What happens when all waiting chairs are full?
A newly arriving customer leaves the shop because no waiting space is available.
9. What are the four deadlock conditions visible in Dining Philosophers?
Mutual exclusion, hold and wait, no preemption and circular wait.
10. Which OS topic connects both problems?
Process synchronization using semaphores, mutual exclusion and correct coordination of shared resources connects both problems.
One-Minute Revision Board
Frequently Asked Questions
What is the main idea of the Dining Philosophers Problem?
It shows how multiple processes competing for multiple shared resources can create deadlock or starvation if resource acquisition is not coordinated correctly.
Why does the naive Dining Philosophers solution deadlock?
If every philosopher holds one fork and waits for the next fork, a circular wait forms and no philosopher can obtain both forks.
What is one simple deadlock-free Dining Philosophers solution?
Use a semaphore initialized to 4 so at most four of the five philosophers may try to acquire forks at the same time.
What is the Sleeping Barber Problem in simple words?
It models one barber serving arriving customers with a limited waiting room, where the barber sleeps when no customer exists and customers leave when all waiting chairs are full.
Which semaphores are commonly used in Sleeping Barber?
A common solution uses customers to count waiting customers, barbers to signal barber readiness and mutex to protect the shared waiting count.
What is the difference between deadlock and starvation in these problems?
Deadlock means a set of processes cannot make progress, while starvation means the system progresses but one process may wait for an extremely long time.
What Should You Learn Next?
Next: Inter-Process Communication (IPC)
After mastering classical synchronization problems, move to Inter-Process Communication in OS: Shared Memory, Message Passing, Pipes & IPC Models.
That topic explains how processes exchange data after you already understand how they coordinate safely. You can also revise Producer-Consumer Problem in OS because shared buffers are a direct bridge between synchronization and IPC.
