GATE CS 1996 Q2.19 — Concurrency and Synchronization

To prevent deadlock in the Dining Philosophers Problem, we must break at least one of the four necessary conditions for deadlock. The most common approach is to break the circular wait condition.

Let us analyze the options:

• Options A and B: If all philosophers follow the exact same protocol (either all picking up the left fork first, or all picking up the right fork first), a symmetric state can arise where every philosopher holds one fork and waits indefinitely for the other. This creates a circular wait, resulting in a deadlock.
• Option C: By introducing asymmetry—where at least one philosopher (say, Philosopher $0$) picks up the forks in the opposite order compared to the other $N-1$ philosophers—we break the circular symmetry. For example, if Philosopher $0$ picks up the left fork first, and all other philosophers pick up their right fork first, it is impossible for all philosophers to simultaneously acquire their first fork and block. This guarantees that at least one philosopher will always be able to acquire both forks and eat, thereby preventing deadlock.

Therefore, the correct option is C.