Dining Philosopher Problem

Problem Statement

Five philosophers sit around a circular table. Each philosopher alternates between two states:

State	Action
Thinking	Does not interact with forks.
Eating	Needs two forks (left and right) to eat.

Each philosopher must pick up their left and right forks to eat. Each fork is shared between adjacent philosophers.

Solution 1

Synchronization Primitives

Semaphore	Initial Value	Purpose
`fork[i]`	1	Represents availability of fork `i`. Only one philosopher can hold it at a time.

Shared Data

1#define N 5                        // number of philosophers
2
3semaphore fork[N] = {1,1,1,1,1};  // one semaphore per fork

Philosopher Process

 1while (true) {
 2    think();                            // not accessing forks
 3
 4    wait(fork[i]);                      // pick up left fork
 5    wait(fork[(i+1) % N]);              // pick up right fork
 6
 7    eat();                              // critical section
 8
 9    signal(fork[i]);                    // put down left fork
10    signal(fork[(i+1) % N]);            // put down right fork
11}

How the Semaphores Coordinate the Processes

Step	Semaphore Action	Effect
Acquire forks	`wait(fork[i])` and `wait(fork[(i+1)%N])`	Philosopher picks up both forks or blocks if unavailable.
Eat section	No conflict	Exclusive access to both forks ensures mutual exclusion.
Release forks	`signal(fork[i])` and `signal(fork[(i+1)%N])`	Makes forks available to neighbors.

Deadlock

If all philosophers pick up their left forks simultaneously, no one can pick up their right fork — resulting in a deadlock.

Condition	Present
Mutual Exclusion	Yes
Hold and Wait	Yes
No Preemption	Yes
Circular Wait	Yes

All four Coffman conditions for deadlock are present.

Correctness Issues

Requirement	Problem in Naive Solution
Mutual Exclusion	Satisfied via binary semaphores on forks.
Deadlock-Free	❌ May deadlock if all pick left fork first.
No Starvation	❌ If a philosopher is always blocked by others.
Concurrency	✅ When forks are free, philosophers eat freely.

Solution 2

To avoid deadlock and ensure progress and bounded waiting, the solution must prevent all four philosophers from holding one fork and waiting for the other.

Use a single mutex semaphore for mutual exclusion and N state flags to track each philosopher’s status. Use condition semaphores for each philosopher to avoid busy waiting.

Synchronization Primitives

State	Meaning
THINKING	Not interested in forks
HUNGRY	Wants to eat (tries to pick forks)
EATING	Holding both forks

Shared Data

1#define N 5
2
3enum { THINKING, HUNGRY, EATING } state[N]; // philosopher states
4
5semaphore mutex = 1;                        // global mutex
6semaphore S[N];                             // one semaphore per philosopher

`test(i)`

Check if philosopher i can eat (both neighbors are not eating).

1void test(int i) {
2    if (state[i] == HUNGRY &&
3        state[(i+N-1)%N] != EATING &&
4        state[(i+1)%N] != EATING) {
5
6        state[i] = EATING;
7        signal(S[i]);  // wake up philosopher i
8    }
9}

`take_forks(i)`

Philosopher i wants to eat.

1void take_forks(int i) {
2    wait(mutex);              // enter critical section
3        state[i] = HUNGRY;
4        test(i);              // check if i can eat
5    signal(mutex);            // leave critical section
6
7    wait(S[i]);               // block if not yet able to eat
8}

`put_forks(i)`

Philosopher i finishes eating and releases forks.

1void put_forks(int i) {
2    wait(mutex);              // enter critical section
3        state[i] = THINKING;
4        test((i+N-1)%N);      // check if left neighbor can now eat
5        test((i+1)%N);        // check if right neighbor can now eat
6    signal(mutex);            // leave critical section
7}

Philosopher Code

1while (true) {
2    think();                  // not interested in forks
3
4    take_forks(i);            // try to acquire forks
5
6    eat();                    // critical section
7
8    put_forks(i);             // release forks
9}

How the Semaphores Coordinate the Processes

Issue	Resolution
Deadlock	Avoided: a philosopher only proceeds when both forks are available.
Starvation	Prevented by checking neighbors after every `put_forks` (fair wakeups).
Mutual Exclusion	Guaranteed: Only one philosopher accesses shared state at a time.
Concurrency	Enabled: Non-adjacent philosophers may eat simultaneously.

Correctness Achieved

Requirement	Mechanism
Mutual Exclusion	Global `mutex` ensures exclusive access to shared state.
Deadlock-Free	`test()` only allows eating if neighbors are not eating.
No Starvation	Each philosopher eventually gets a chance to eat via FIFO semaphore `S[i]`.
Concurrency	Multiple non-neighbor philosophers can eat simultaneously.

Solution 3

Synchronization Primitives

Semaphore	Initial Value	Purpose
T	4	Limit philosophers at the table
FORK	1	One semaphore per fork

Shared Data

1#define N 5
2
3semaphore T = 4;                        // Limit philosophers at the table
4semaphore FORK[5] = {1, 1, 1, 1, 1};    // One semaphore per fork

Philosopher Code

 1Pi(){
 2  while(TRUE){
 3    wait(T);
 4      wait(FORK[i]);
 5        wait(FORK[(i + 1) % 5]);
 6          eat;
 7        signal(FORK[(i + 1) % 5]);
 8      signal(FORK[i]);
 9    signal(T);
10  }
11}

Last updated on May 24, 2025

Readers Writers Problem Sleeping Barber Problem