Problem Statement (1 mark)

Five philosophers sit around a circular table. Between each pair of adjacent philosophers is one chopstick (fork). Each philosopher alternates between thinking and eating. To eat, a philosopher must hold both the left and right chopsticks.

Correctness Requirements (1 mark)

Any solution must ensure:

1. Mutual Exclusion: No two neighbors hold the same chopstick.
2. Deadlock Freedom: The system must never reach a state where every philosopher holds one chopstick and waits forever for the other.
3. Starvation Freedom (Fairness): Every philosopher who wants to eat eventually gets to eat.

Naïve Semaphore Model (1 mark)

// One binary semaphore per chopstick
semaphore fork[5] = {1,1,1,1,1};

philosopher(i):
  while (true) {
    think();
    wait(fork[i]);               // pick up left
    wait(fork[(i+1)%5]);         // pick up right
    eat();
    signal(fork[i]);             // put down left
    signal(fork[(i+1)%5]);       // put down right
  }

• Issue: If all 5 philosophers simultaneously pick up their left fork, each holds one and waits for the right → deadlock.

Deadlock Condition (1 mark)

All five wait(fork[i]) succeed, then each blocks on wait(fork[(i+1)%5]). No one can proceed or release their held fork—circular wait.

Deadlock-Free Solution: The “Waiter” (Resource-Count) Semaphore (2 marks)

Introduce a semaphore room initialized to 4 (N–1):

semaphore room = 4;
semaphore fork[5] = {1,1,1,1,1};

• Before trying to pick up forks, a philosopher must wait(room).