Dining Philosophers: A Deadlock Simulation

The Dining Philosophers Problem

The Dining Philosophers problem is a metaphor for the challenges of resource allocation in multi-threaded or multi-process systems. Let's start with a video that clearly explains the scenario.

To summarize the setup:

• There are five philosophers sitting at a round table.
• Between each pair of adjacent philosophers is a single fork (or chopstick). So, five philosophers, five forks.
• A philosopher's life consists of two alternating states: thinking and eating.
• To eat, a philosopher must pick up both the fork to their left and the fork to their right.
• A fork is a resource that can only be used by one philosopher at a time (mutual exclusion).

This seemingly simple scenario contains all the ingredients for deadlock.

From Philosophy to Pthreads: Mapping to Code

Let's translate this abstract problem into the concrete terms of C and pthreads:

• Philosophers are threads.
• Forks are shared resources, which we will protect with mutexes.
• Thinking can be simulated with a sleep() or another non-critical computation.
• Eating is the critical section where a thread must hold two mutex locks simultaneously.

The naive and most intuitive approach is for each philosopher to do the same thing:

1. Think for a while.
2. Pick up the fork on their left.
3. Pick up the fork on their right.
4. Eat for a while.
5. Put down the right fork.
6. Put down the left fork.
7. Repeat.

Why does this lead to deadlock? Let's revisit the four conditions in this context.

The Dining Philosophers problem with the naive algorithm satisfies all four conditions:

1. Mutual Exclusion: A fork can only be used by one philosopher at a time. A pthread_mutex_t inherently enforces this.
2. Hold and Wait: A philosopher successfully locks their left fork's mutex and holds it while waiting to acquire the lock for their right fork.
3. No Preemption: We cannot forcibly take a fork (release a mutex) from another philosopher (thread).
4. Circular Wait: This is the fatal flaw. If every philosopher picks up their left fork at roughly the same time, then Philosopher 0 is waiting for Philosopher 1's fork, Philosopher 1 is waiting for Philosopher 2's, and so on, until Philosopher 4 is waiting for Philosopher 0's fork.

This circular dependency is the deadlock.

Let's see this circular wait explained visually.

Implementing the Deadlock

Now, let's move from theory to practice. Your task is to write a C program that simulates this problem and reliably triggers the deadlock. The logic is surprisingly simple.

The following resource provides a complete, minimal C implementation that demonstrates the deadlock.

Let's analyze the core of the eat function from that resource:

void *eat(void *arg) {
    int n = (int) (long)arg; // Philosopher number (0 to 4)

    // A philosopher tries to take the chopstick with the same index first (e.g., their 'left'),
    // then the next one in the circle.
    pthread_mutex_lock(&chopstick[n]);
    printf("Philosopher %d got chopstick %d\n", n, n);
    
    // The moment of truth: try to get the second chopstick.
    pthread_mutex_lock(&chopstick[(n+1)%5]);
    printf("Philosopher %d got chopstick %d\n", n, (n+1)%5);

    printf ("Philosopher %d is eating\n",n);
    sleep(1);
    
    // Release the chopsticks (in reverse order).
    printf("Philosopher %d set down chopstick %d\n", n, (n+1)%5);
    pthread_mutex_unlock(&chopstick[(n+1)%5]);
    printf("Philosopher %d set down chopstick %d\n", n, n);
    pthread_mutex_unlock(&chopstick[n]);

    return NULL;
}

The logic is identical for all five threads, creating the perfect symmetry that leads to deadlock.

    pthread_mutex_lock(&chopstick[n]);
    printf("Philosopher %d got chopstick %d\n", n, n);
    
    sleep(1); // Give other threads a chance to grab their first chopstick.

    pthread_mutex_lock(&chopstick[(n+1)%5]);
    // ...

Philosopher 1 got chopstick 1
Philosopher 0 got chopstick 0
Philosopher 3 got chopstick 3
Philosopher 2 got chopstick 2
Philosopher 4 got chopstick 4

This simple exercise perfectly demonstrates how a symmetric resource acquisition strategy among multiple threads can lead to a complete system standstill.

Conclusion

In this lesson, we demystified the Dining Philosophers problem and brought it to life with a practical C implementation.

Key Takeaways:

• The Dining Philosophers problem is a classic metaphor for resource contention and deadlock in concurrent systems.
• We can model the problem using threads (philosophers) and mutexes (forks).
• A naive, symmetric algorithm where every thread attempts to acquire resources in the same relative order (e.g., "left then right") creates a circular wait condition, leading to deadlock.
• Due to the non-deterministic nature of thread scheduling, a deadlock-prone program might not fail on every execution. Techniques like adding a sleep() can help expose the underlying flaw by creating a window for the race condition to occur reliably.

Preview of the Next Lesson:
We've successfully created a deadlock. Now, how do we fix it? In our next lesson, we will solve the dining philosophers problem without deadlock by applying a lock-ordering hierarchy. This will involve breaking the symmetry that caused the circular wait, directly applying the deadlock prevention strategy we studied earlier.