Operating System - Dining Philosophers Problem

What is the Dining Philosophers Problem?

Imagine five philosophers sitting around a circular dining table. Each philosopher alternates between thinking and eating.

There is:

  • A bowl of spaghetti in front of each philosopher.

  • One fork between each pair of philosophers.

  • So, 5 philosophers but only 5 forks in total (one between each philosopher).

To eat, a philosopher needs both the left and the right fork.

The Problem

The challenge is to design a protocol (solution) where:

  • No two philosophers use the same fork at the same time (mutual exclusion).

  • Philosophers don’t starve (they eventually get to eat).

  • No deadlock happens (e.g., all philosophers pick up their left fork and wait forever for the right one).

Example Situation:

Let’s label the philosophers P1, P2, P3, P4, P5 and the forks F1 to F5 as follows:

  • P1 has F1 (left) and F2 (right)

  • P2 has F2 and F3

  • ...

  • P5 has F5 and F1

Problem Scenario (Deadlock Example):

  1. All philosophers pick up their left fork at the same time:

    • P1 picks F1

    • P2 picks F2

    • P3 picks F3

    • P4 picks F4

    • P5 picks F5

  2. Now, each philosopher is waiting for the right fork, but that fork is already taken by their neighbor.

  3. No one can eat. No one will put down a fork. This is deadlock.

Common Solutions

1. Allow Only Four Philosophers to Sit at the Table at Once

  • This avoids the circular wait condition that leads to deadlock.

2. Use a Semaphore or Mutex

  • A philosopher checks (locks) both forks before picking them up.

  • If both are not available, they release the one they have and try again later.

3. Numbered Forks – Pick in Order

  • A philosopher always picks up the lower-numbered fork first, then the higher.

  • For example, P5 will pick up F1 before F5.

  • This prevents circular wait.

4. Asymmetric Behavior

  • Odd-numbered philosophers pick up the left fork first.

  • Even-numbered philosophers pick up the right fork first.

 What It Teaches

  • Deadlock: When every process is waiting for a resource held by another, and none can proceed.

  • Starvation: When a process waits indefinitely because others keep taking the resources.

  • Concurrency Control: How to manage access to shared resources.