Deadlock-Free Dining Philosophers with Lock Ordering

Breaking the Cycle: The Theory of Lock-Ordering

The deadlock in our previous program occurred because the chain of dependencies formed a closed loop: P0 → P1 → P2 → P3 → P4 → P0. To prevent deadlock, we only need to break this circular wait. We don't need to eliminate the other three conditions.

The most effective way to do this is to enforce a global ordering on the resources (the forks/mutexes). If every thread in a program agrees to acquire multiple locks in the same, predefined order, a circular wait is impossible.

For the dining philosophers, this means they can't all just grab their "left" fork first. They need a common rule. A simple and robust rule is: always lock the mutex with the lower index first.

Let's see this strategy explained.

Why This Works: A Visual Explanation

So, how does this simple rule change prevent the deadlock?

Consider Philosopher 4, who needs forks 4 and 0. In our deadlocking program, they picked up fork 4 and then waited for fork 0. This is what completed the circle, as Philosopher 0 was holding fork 0 and waiting for fork 1.

With our new rule, Philosopher 4 must acquire the forks in ascending order of their indices. Since 0 < 4, they must attempt to lock fork 0 before fork 4. Now, both Philosopher 0 (needing forks 0 and 1) and Philosopher 4 (needing forks 4 and 0) will try to lock fork 0 first. They will contend for it, and one will win while the other waits. The crucial part is that Philosopher 4 is not holding fork 4 while waiting for fork 0. The "hold and wait" chain that formed our circle is broken.

Let's watch the final part of the video, which illustrates this.

Implementing the Lock-Ordering Hierarchy in C

Now for the practical part. Let's modify the deadlocking code from the previous lesson. The core of the change will be in the eat function. Instead of blindly locking chopstick[n] and then chopstick[(n+1)%5], we must first check which of these two indices is smaller and lock that one first.

The resource CS3130: Dining Philosophers that we used previously describes this exact approach.

Here's how you could implement that logic in C. Inside your eat function:

void *eat(void *arg) {
    int n = (int)(long)arg;

    // The two forks this philosopher needs
    int left_fork = n;
    int right_fork = (n + 1) % 5;

    printf("Philosopher %d is thinking.\n", n);
    // sleep(rand() % 3); // Optional: simulate thinking

    // Implement the resource hierarchy
    if (left_fork > right_fork) {
        // Swap to ensure we always lock the smaller index first
        int temp = left_fork;
        left_fork = right_fork;
        right_fork = temp;
    }

    // Now, lock the forks in the determined order
    pthread_mutex_lock(&chopstick[left_fork]);
    printf("Philosopher %d got chopstick %d\n", n, left_fork);
    
    // The original `sleep(1)` from our deadlock experiment can go here
    // to prove the solution is robust.
    
    pthread_mutex_lock(&chopstick[right_fork]);
    printf("Philosopher %d got chopstick %d\n", n, right_fork);

    printf("Philosopher %d is eating\n", n);
    sleep(1);

    // Unlock in reverse order
    printf("Philosopher %d set down chopstick %d\n", n, right_fork);
    pthread_mutex_unlock(&chopstick[right_fork]);
    printf("Philosopher %d set down chopstick %d\n", n, left_fork);
    pthread_mutex_unlock(&chopstick[left_fork]);

    return NULL;
}

Notice that only Philosopher 4 will trigger the if condition, since for them left_fork is 4 and right_fork is 0. This single change breaks the circular dependency.

An Alternative Implementation: The Odd/Even Strategy

The principle of breaking symmetry is the key, not the specific implementation. Another common way to enforce a lock order is to have odd-numbered philosophers pick up forks in one order (e.g., left, then right) and even-numbered philosophers pick them up in the opposite order (right, then left).

This also breaks the symmetry and prevents a circular wait. The following resource provides a C code snippet and a clear explanation of this alternative.

This shows that as long as you establish some consistent, global ordering that all threads adhere to, you can prevent deadlock.

Conclusion

Today we successfully resolved the deadlock in the Dining Philosophers problem. By moving from a symmetric to an asymmetric resource acquisition strategy, we broke the circular wait condition.

Key Takeaways:

• A lock-ordering hierarchy is a powerful and common technique for preventing deadlock.
• The core principle is to establish a global, consistent order in which all threads agree to acquire locks. This breaks the symmetry required for a circular wait.
• We implemented this using a "lower-index-first" rule, which is a general and effective strategy.
• Alternative strategies, like an odd/even acquisition order, also work because they adhere to the same principle of breaking symmetry.

Preview of the Next Lesson:
We have now concluded our deep dive into deadlock. In the next module, we will begin applying our knowledge of mutexes and synchronization to a new, practical domain: implementing thread-safe data structures. We will start by designing and building a thread-safe stack using a single mutex to protect its critical sections. This will be our first step towards building more complex concurrent components.