Lock Ordering

Solving the Dining Philosophers problem by enforcing alphabetical order.

The idea

A classic cause of deadlocks is two threads trying to lock the exact same two resources, but in reverse order. If Thread 1 locks A then B, and Thread 2 locks B then A, they can easily get stuck waiting for each other. The universal solution is Global Lock Ordering: all threads must acquire locks in the exact same predefined order (e.g., alphabetically, or by Resource ID).

Step 1: Alice wants to transfer money from Acct A to Acct B. Bob wants to transfer from Acct B to Acct A.

How it works (Alphabetical Ordering)

Instead of locking the "From" account and then the "To" account, you write code that looks at the two IDs, sorts them, and always locks the smaller ID first. This guarantees cycles cannot form.

# THE BAD WAY (Causes Deadlocks)
def transfer(from_acct, to_acct, amount):
    lock(from_acct) # Alice locks A. Bob locks B.
    lock(to_acct)   # Alice waits for B. Bob waits for A. Deadlock!
    # ... transfer logic
    
# THE GOOD WAY (Global Lock Ordering)
def transfer(acct1, acct2, amount):
    # Sort the locks so we ALWAYS lock in the same order
    first_lock = min(acct1.id, acct2.id)
    second_lock = max(acct1.id, acct2.id)
    
    lock(first_lock)
    lock(second_lock)
    
    # Alice locks A (success). 
    # Bob tries to lock A (waits for Alice). 
    # Alice locks B (success). 
    # No deadlock!

Cost

Sorting locks is computationally trivial (O(1) or O(N log N)). The real cost is code complexity: developers must rigorously apply this sorting logic everywhere in the codebase. If even one function forgets to sort the locks, deadlocks will return.

Watch out for