Dining Philosophers, Sleeping Barber, and IPC Models

These notes explain two classical synchronization problems — Dining Philosophers and Sleeping Barber — and then outline the major Inter-Process Communication (IPC) models used by operating systems. These problems are important because they capture the real difficulties of mutual exclusion, deadlock, starvation, and coordination among concurrent processes.

1. Why These Problems Matter

In concurrency, several processes or threads may compete for limited resources. If synchronization is not handled properly, the system may suffer from:

• Race conditions – incorrect results due to uncontrolled interleaving
• Deadlock – processes wait forever for one another
• Starvation – some processes wait indefinitely while others keep progressing
• Busy waiting – CPU time is wasted while a process repeatedly checks a condition

2. Dining Philosophers Problem

2.1 Problem statement

Five philosophers sit around a circular table. Between every pair of adjacent philosophers there is one chopstick. Each philosopher alternates between thinking and eating. To eat, a philosopher needs both left and right chopsticks.

Since each chopstick is shared between neighbors, the problem is to design a synchronization scheme that allows philosophers to eat without causing deadlock or starvation.

2.2 What this problem models

The Dining Philosophers problem models a situation where:

• processes compete for limited resources,
• each process needs more than one resource,
• resources are shared and mutually exclusive,
• poor synchronization may cause deadlock or starvation.

2.3 Naive solution and deadlock

Suppose each philosopher first picks up the left chopstick and then tries to pick up the right one. If all philosophers do this simultaneously:

• each philosopher holds one chopstick,
• each waits for the other chopstick,
• nobody can proceed.

2.4 Semaphore-based solution idea

Let each chopstick be represented by a binary semaphore.

semaphore chopstick[5] = {1,1,1,1,1};

philosopher(i):
while(true){
    think();
    wait(chopstick[i]);              // left
    wait(chopstick[(i+1) % 5]);      // right
    eat();
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
}

This ensures mutual exclusion for each chopstick, but the naive order still allows deadlock.

2.5 Common techniques to avoid deadlock

2.6 What to remember

• Dining philosophers demonstrates mutual exclusion and deadlock risk.
• Naive semaphore use is not enough.
• A good solution must aim to avoid deadlock and reduce starvation.

3. Sleeping Barber Problem

3.1 Problem statement

A barber shop has:

• one barber,
• one barber chair,
• a number of waiting chairs for customers.

The rules are:

• If there are no customers, the barber sleeps.
• If a customer arrives and the barber is sleeping, the customer wakes the barber.
• If the barber is busy and a waiting chair is free, the customer waits.
• If all waiting chairs are occupied, the arriving customer leaves.

3.2 What this problem models

The Sleeping Barber problem models:

• a single server,
• many competing clients,
• a bounded waiting queue,
• sleep/wakeup synchronization.

3.3 Synchronization requirements

A correct solution must ensure:

• the barber does not work when no customer exists,
• customers do not occupy more waiting chairs than available,
• barber and customers coordinate correctly,
• the shared customer count is updated safely.

3.4 Semaphore-based model

A common semaphore-based solution uses:

• customers – counts waiting customers
• barber – indicates barber availability
• mutex – protects the shared count of waiting customers

semaphore customers = 0;
semaphore barber = 0;
semaphore mutex = 1;
int waiting = 0;
int chairs = N;

barber_process:
while(true){
    wait(customers);       // sleep if no customers
    wait(mutex);
    waiting--;
    signal(barber);        // barber ready
    signal(mutex);
    cut_hair();
}

customer_process:
wait(mutex);
if(waiting < chairs){
    waiting++;
    signal(customers);     // wake barber if needed
    signal(mutex);
    wait(barber);          // wait until barber is ready
    get_haircut();
}
else{
    signal(mutex);
    leave_shop();
}

3.5 Key idea of the solution

• customers semaphore wakes the barber when someone arrives.
• barber semaphore lets one customer move to the barber chair.
• mutex prevents race conditions on the waiting count.

4. Dining Philosophers vs Sleeping Barber

5. IPC Models

5.1 Meaning of IPC

Inter-Process Communication (IPC) refers to the mechanisms by which processes exchange data and coordinate their actions.

IPC is necessary because processes often need to:

• share information,
• coordinate tasks,
• signal events,
• maintain consistency of shared resources.

5.2 Two major IPC models

5.3 Common IPC mechanisms

5.4 Shared memory vs message passing

6. Applying Synchronization Techniques

The classical way to solve Dining Philosophers and Sleeping Barber is to apply synchronization tools such as:

• Binary semaphores / mutexes – for mutual exclusion
• Counting semaphores – for resource counts or waiting customers
• Monitors – for high-level structured synchronization
• Condition variables – for waiting until a condition becomes true

7. Quick Revision Snapshot

8. One-Page Summary