Preventing Deadlocks with Lock Ordering

The Core Principle: Break the Cycle

Recall the simple deadlock scenario from last time:

• Thread 1: lock(M1) -> lock(M2)
• Thread 2: lock(M2) -> lock(M1)

If Thread 1 grabs M1 and Thread 2 grabs M2 at roughly the same time, they will wait for each other indefinitely. The problem isn't that they need two locks; the problem is that they are acquiring them in a conflicting order, creating a potential for a circular dependency.

The solution is remarkably simple in principle: if all threads that need to acquire the same set of locks do so in the exact same order, a circular wait is impossible.

This strategy is known as a lock-ordering policy or lock hierarchy.

As the article states, you establish a global, prescribed order for your mutexes. For example, if you have mutex_A and mutex_B, you might decide that mutex_A must always be locked before mutex_B. Any code in your program that needs both locks must respect this rule.

• Allowed: lock(A); lock(B);
• Forbidden: lock(B); lock(A);

By enforcing this, you eliminate the possibility of a circular wait between these two locks.

Applying Lock Ordering: Solving the Dining Philosophers Problem

Let's make this concrete by solving the Dining Philosophers problem we discussed in the last lesson. The deadlock occurred because each philosopher tried to grab their "right" fork, then their "left" fork. This created a circular wait.

We can break this cycle by imposing a global order on the forks (our mutexes). A simple and effective ordering is to use their numerical index (or, more generally, their memory address). The rule becomes: always lock the fork with the lower index first.

Let's see how this works for Philosopher 4, who was the final link in the circular wait chain:

• Forks needed: Fork 4 and Fork 0.
• Old, deadlock-prone rule: Grab Fork 4, then grab Fork 0.
• New, lock-ordering rule: Grab the fork with the minimum index first. min(4, 0) is 0. So, Philosopher 4 must grab Fork 0, then Fork 4.

But wait, Philosopher 0 also needs Fork 0. Under the new rule, both Philosopher 4 and Philosopher 0 will try to lock Fork 0 first. Only one will succeed. The other will wait. The key is that neither of them will be holding another fork while they wait. The "hold and wait" condition is transformed in a way that prevents a cycle. If Philosopher 0 gets Fork 0, they will then proceed to lock Fork 1. Philosopher 4 is still just waiting for Fork 0. No deadlock.

Implementing a Lock-Ordering Policy in C

Let's translate this into a C implementation. Imagine you have a function that needs to transfer a value from one bank account to another. This operation needs to be atomic, so you must lock both accounts to prevent race conditions.

#include <stdio.h>
#include <pthread.h>

typedef struct {
    int balance;
    pthread_mutex_t lock;
} Account;

// Function to transfer money from one account to another
// This is the function you will implement.
void transfer(Account *from, Account *to, int amount) {
    // ???
}

// Assume we have two accounts
Account acc1 = { .balance = 1000, .lock = PTHREAD_MUTEX_INITIALIZER };
Account acc2 = { .balance = 1000, .lock = PTHREAD_MUTEX_INITIALIZER };

A naive implementation might be:

// DANGEROUS - PRONE TO DEADLOCK
void transfer_deadlock(Account *from, Account *to, int amount) {
    pthread_mutex_lock(&from->lock);
    pthread_mutex_lock(&to->lock);
    
    from->balance -= amount;
    to->balance += amount;
    
    pthread_mutex_unlock(&to->lock);
    pthread_mutex_unlock(&from->lock);
}

If thread1 calls transfer(&acc1, &acc2, 100) and thread2 calls transfer(&acc2, &acc1, 50) concurrently, they will attempt to lock the mutexes in opposite orders, leading to a deadlock.

void transfer(Account *from, Account *to, int amount) {
    // Your implementation here
}

void transfer(Account *from, Account *to, int amount) {
    // Establish pointers to the two mutexes based on their address order.
    // This defines our lock hierarchy.
    pthread_mutex_t *lock1 = (from < to) ? &from->lock : &to->lock;
    pthread_mutex_t *lock2 = (from < to) ? &to->lock : &from->lock;

    // Acquire locks in the prescribed order.
    pthread_mutex_lock(lock1);
    pthread_mutex_lock(lock2);

    // Critical Section
    // Note: This check should be more robust in a real application.
    if (from->balance >= amount) {
        from->balance -= amount;
        to->balance += amount;
    }

    // Release locks in the reverse order.
    pthread_mutex_unlock(lock2);
    pthread_mutex_unlock(lock1);
}

Lock Ordering in Data Structures

This principle isn't just for pairs of mutexes; it's a fundamental pattern for designing thread-safe data structures. Consider deleting a node from a singly linked list where each node has its own mutex. To safely remove a node, you typically need to lock both the node to be removed (current) and its predecessor, because you need to modify predecessor->link.

typedef struct node {
    int value;
    struct node *link;
    pthread_mutex_t lock;
} node_t;

If you always traverse the list from the head, you naturally create a lock hierarchy. To delete current, you first have the lock on prev. You then acquire the lock on current. Your lock acquisition order (prev then current) follows the list's structure. Since all threads must traverse from the head, no thread will ever try to lock current and then prev.

This technique, sometimes called lock coupling or hand-over-hand locking, is a direct application of lock hierarchies. We will implement this in detail in a future module on thread-safe data structures.

Conclusion

You've now learned the most important technique for preventing deadlocks. While other strategies exist, enforcing a strict lock-ordering policy is often the simplest and most robust.

Key Takeaways:

• Deadlocks involving multiple mutexes are typically caused by acquiring locks in inconsistent orders, which creates a circular wait.
• You can prevent this by implementing a lock-ordering policy (or lock hierarchy), where all threads must acquire locks from a given set in the same, globally-defined sequence.
• This order can be defined arbitrarily (e.g., by the memory address of the mutexes or the objects they protect) or structurally (e.g., by the traversal order of a data structure).
• By enforcing this policy, the circular wait condition is broken, and deadlocks are prevented.

Preview of the Next Lesson:
A strict lock hierarchy is powerful, but what if you're in a situation where it's difficult or impossible to enforce? For example, in a complex graph data structure without a clear "head" node. In the next lesson, we will explore an alternative strategy: using pthread_mutex_trylock in a loop to acquire locks opportunistically without deadlocking.