---
title: "Dining philosophers problem and solution"
subject: "Operating System"
chapter: 3
key: "semester_6/operating_system:dining-philosophers"
source: https://www.bctengineer.com/q/semester_6/operating_system/dining-philosophers
site: BCT Engineering
---

# Dining philosophers problem and solution

Operating System · Chapter 3: Process Communication and Synchronization

- Asked in: 2068 Magh, 3+5 marks; 2073 Magh, 3.5 marks; year not given (asked 2 times)
- Video: [OS 17 : Dining Philosopher Problem with Semaphore Solution](https://www.youtube.com/watch?v=kusbrK7zuNk) — CS & IT Tutorials by Vrushali 👩‍🎓
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/operating_system/dining-philosophers
- Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-3

## Question

Explain the dining philosopher problem. How can it be solved (using semaphore)?

## Short answer

Five philosophers share five forks, needing both to eat, risking deadlock if all grab left forks simultaneously. The semaphore solution uses a mutex, state array, and per-philosopher semaphores; a philosopher eats only if neither neighbor is eating, tested when forks are taken or put down.

## Answer

#### The problem

Five philosophers sit around a circular table. Between each pair of philosophers there is one fork (five forks in all), and in front of each is a plate of spaghetti. A philosopher alternately **thinks** and **eats**; to eat, he needs **both** the fork on his left and the fork on his right. After eating he puts both forks down and thinks again.

```text
        P0
    f4      f0
  P4          P1
    f3      f1
       P3 f2 P2
```

The problem models processes competing for exclusive access to a limited set of resources. Care is needed to avoid:
- **Deadlock**: if every philosopher picks up the left fork at the same time, each waits forever for the right fork.
- **Starvation**: a philosopher may never get both forks, while neighbours eat repeatedly.

A simple solution, where each philosopher does `down(fork[i])` then `down(fork[(i+1)%5])`, is wrong because of the deadlock above. Waiting a random time before retrying avoids deadlock but is not guaranteed.

#### Solution using semaphores (Tanenbaum)

A philosopher may start eating only if neither neighbour is eating. An array `state[]` records THINKING, HUNGRY or EATING; a mutex protects `state`, and each philosopher has a semaphore `s[i]` on which he blocks if the forks are not available.

```c
#define N        5                 /* number of philosophers */
#define LEFT     (i+N-1)%N         /* left neighbour of i */
#define RIGHT    (i+1)%N           /* right neighbour of i */
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                      /* state of each philosopher */
semaphore mutex = 1;               /* protects critical regions */
semaphore s[N];                    /* one semaphore per philosopher, all 0 */

void philosopher(int i) {
    while (TRUE) {
        think();
        take_forks(i);             /* get both forks or block */
        eat();
        put_forks(i);              /* release forks */
    }
}
void take_forks(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    test(i);                       /* try to acquire both forks */
    up(&mutex);
    down(&s[i]);                   /* block if forks were not acquired */
}
void put_forks(int i) {
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);                    /* can left neighbour eat now? */
    test(RIGHT);                   /* can right neighbour eat now? */
    up(&mutex);
}
void test(int i) {
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}
```

**How it works**: `take_forks` marks the philosopher HUNGRY and calls `test`; if both neighbours are not eating, he becomes EATING and `up(s[i])` allows `down(s[i])` to pass at once; otherwise he blocks. When he finishes, `put_forks` tests his left and right neighbours and wakes them if they are hungry and can now eat. This gives **no deadlock** and the maximum parallelism (two philosophers may eat together).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does each philosopher need in order to eat?
   A. Only the left fork
   B. Both the left and right forks
   C. Any one of the five forks
   D. The fork opposite him
   Answer: B. Each philosopher needs both adjacent forks, and there are only five forks for five philosophers. (Key point: Problem statement)

2. Why is the simple solution down(fork[i]) then down(fork[(i+1)%5]) wrong?
   A. Forks are not semaphores
   B. It lets two philosophers eat together
   C. Only one philosopher could ever eat
   D. If all pick up left forks at once, each waits forever for the right one
   Answer: D. Circular waiting leads to deadlock when every philosopher holds his left fork. (Key point: Deadlock in naive solution)

3. In the semaphore solution, when may philosopher i start eating?
   A. When state[i] is HUNGRY and neither neighbour is EATING
   B. When he has waited longest
   C. When state[i] is THINKING
   D. When all other philosophers are thinking
   Answer: A. test(i) sets EATING only if i is HUNGRY and neither the left nor the right neighbour is EATING. (Key point: Tanenbaum solution rule)

4. What does put_forks(i) do after setting THINKING?
   A. Releases a global lock for all
   B. Tests left and right neighbours and wakes those who can now eat
   C. Waits for neighbours to finish
   D. Resets all semaphores to 1
   Answer: B. It calls test(LEFT) and test(RIGHT), which do up(s[neighbour]) for hungry neighbours that can eat. (Key point: put_forks role)

## Related in Operating System

- [Monitor; dining philosophers with semaphore](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Amonitor-dining-philosopher) — Operating System, chapter 3
- [Readers-writers problem with semaphore](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Areaders-writers) — Operating System, chapter 3

## Related in other subjects

- [Multipath inheritance problem and solution](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Amultipath-inheritance-problem) — Object Oriented Programming, chapter 6, asked 2×
- [TOH problem with solution for n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-n-disks-solution) — Data Structure and Algorithm, chapter 5, asked 2×