Deadlock Prevention Strategies

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

# Visualization of the ordering invariant
 
class ResourceOrderingSimulator:
    """
    Demonstrates why resource ordering prevents deadlock.
    
    Invariant: At any moment, for any process P:
        max(held_by_P) < min(waiting_for_P)
    
    This invariant guarantees no cycles in the wait-for graph.
    """
    
    def __init__(self, resource_order: dict):
        # resource_order maps resource names to integers
        # e.g., {"mutex_a": 1, "mutex_b": 2, "mutex_c": 3}
        self.order = resource_order
        self.held = {}      # process -> set of held resources
        self.waiting = {}   # process -> resource waiting for (or None)
    
    def acquire(self, process: str, resource: str) -> bool:
        """
        Attempt to acquire resource following ordering protocol.
        Returns True if acquisition is valid, False if it violates order.
        """
        resource_num = self.order[resource]
        
        # Check ordering constraint
        current_held = self.held.get(process, set())
        if current_held:
            max_held = max(self.order[r] for r in current_held)
            if resource_num <= max_held:
                print(f"VIOLATION: {process} holds resource with order "
                      f"{max_held}, cannot acquire order {resource_num}")
                return False
        
        # Valid acquisition
        if process not in self.held:
            self.held[process] = set()
        self.held[process].add(resource)
        print(f"{process} acquired {resource} (order {resource_num})")
        return True
    
    def check_deadlock_impossible(self) -> bool:
        """
        Verify that no cycle can exist given current state.
        Uses the invariant: held < waiting for all processes.
        """
        for process, held_resources in self.held.items():
            waiting_for = self.waiting.get(process)
            if waiting_for:
                max_held = max(self.order[r] for r in held_resources)
                waiting_order = self.order[waiting_for]
                if max_held >= waiting_order:
                    return False  # Invariant violated
        return True  # Invariant holds → no cycles possible
 
# Example: Classic deadlock scenario made impossible
order = {"resource_A": 1, "resource_B": 2}
sim = ResourceOrderingSimulator(order)
 
# Process 1 wants A then B
sim.acquire("P1", "resource_A")  # OK: order 1, holds nothing
sim.acquire("P1", "resource_B")  # OK: order 2 > 1 (max held)
 
# Process 2 also wants A then B (MUST follow same order)
sim.acquire("P2", "resource_A")  # Would block until P1 releases
sim.acquire("P2", "resource_B")  # Would block until P1 releases
 
# IF Process 2 tried B then A:
# sim.acquire("P2", "resource_B")  # OK: order 2, holds nothing  
# sim.acquire("P2", "resource_A")  # VIOLATION: order 1 < 2 (max held)
 
# The protocol PREVENTS the ordering that would cause deadlock!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

// Production-Ready Resource Ordering Framework
// Enforces ordering at runtime with debugging support
 
#include <pthread.h>
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
 
#define MAX_RESOURCES 100
#define MAX_HELD_PER_THREAD 20
 
// Global resource order registry
typedef struct {
    const char* name;
    uint32_t order;         // Lower = must acquire first
    pthread_mutex_t* mutex; // The actual mutex
} resource_entry_t;
 
resource_entry_t resource_registry[MAX_RESOURCES];
int registry_count = 0;
pthread_mutex_t registry_lock = PTHREAD_MUTEX_INITIALIZER;
 
// Per-thread tracking of held resources
typedef struct {
    int held_indices[MAX_HELD_PER_THREAD]; // Indices into registry
    int held_count;
    uint32_t max_held_order;               // Highest order currently held
} thread_state_t;
 
// Thread-local state (or use pthread_key)
__thread thread_state_t thread_state = {.held_count = 0, .max_held_order = 0};
 
// Register a resource with its order
int register_ordered_resource(const char* name, uint32_t order, 
                              pthread_mutex_t* mutex) {
    pthread_mutex_lock(&registry_lock);
    
    int idx = registry_count++;
    resource_registry[idx].name = name;
    resource_registry[idx].order = order;
    resource_registry[idx].mutex = mutex;
    
    pthread_mutex_unlock(&registry_lock);
    return idx;
}
 
// Acquire with ordering enforcement
int ordered_lock(int resource_idx) {
    resource_entry_t* res = &resource_registry[resource_idx];
    
    // ORDERING CHECK: New resource must have higher order than all held
    if (thread_state.held_count > 0 && 
        res->order <= thread_state.max_held_order) {
        
        // VIOLATION DETECTED!
        fprintf(stderr, 
            "ORDERING VIOLATION: Thread attempting to acquire '%s' (order %u) "
            "while holding resource with order %u\n",
            res->name, res->order, thread_state.max_held_order);
        
        // In debug mode, print stack trace and abort
        #ifdef DEBUG
            print_held_resources();
            print_stack_trace();
            abort();
        #endif
        
        // In production, return error (caller must fix their code)
        return -1;
    }
    
    // Acquire the actual mutex
    int result = pthread_mutex_lock(res->mutex);
    if (result != 0) return result;
    
    // Update thread state
    thread_state.held_indices[thread_state.held_count++] = resource_idx;
    if (res->order > thread_state.max_held_order) {
        thread_state.max_held_order = res->order;
    }
    
    return 0;
}
 
// Release with state tracking
int ordered_unlock(int resource_idx) {
    resource_entry_t* res = &resource_registry[resource_idx];
    
    // Verify we actually hold this resource
    int found = -1;
    for (int i = 0; i < thread_state.held_count; i++) {
        if (thread_state.held_indices[i] == resource_idx) {
            found = i;
            break;
        }
    }
    
    if (found == -1) {
        fprintf(stderr, "ERROR: Unlocking '%s' not held by this thread\n",
                res->name);
        return -1;
    }
    
    // Release the mutex
    int result = pthread_mutex_unlock(res->mutex);
    
    // Update thread state (remove from held list)
    thread_state.held_indices[found] = 
        thread_state.held_indices[--thread_state.held_count];
    
    // Recalculate max held order
    thread_state.max_held_order = 0;
    for (int i = 0; i < thread_state.held_count; i++) {
        uint32_t order = resource_registry[thread_state.held_indices[i]].order;
        if (order > thread_state.max_held_order) {
            thread_state.max_held_order = order;
        }
    }
    
    return result;
}
 
// Debugging: print all resources held by current thread
void print_held_resources() {
    fprintf(stderr, "Thread holds %d resources:\n", thread_state.held_count);
    for (int i = 0; i < thread_state.held_count; i++) {
        resource_entry_t* res = &resource_registry[thread_state.held_indices[i]];
        fprintf(stderr, "  - %s (order %u)\n", res->name, res->order);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

// Example: Bank account transfer with ordered locks
 
// Define resources with explicit ordering
pthread_mutex_t account_mutex[1000];  // One mutex per account
int account_resources[1000];          // Resource indices
 
void init_account_system() {
    for (int i = 0; i < 1000; i++) {
        pthread_mutex_init(&account_mutex[i], NULL);
        // Order by account number - simple and consistent!
        account_resources[i] = register_ordered_resource(
            "account_mutex", 
            i,              // Account 0 < Account 1 < Account 2 < ...
            &account_mutex[i]
        );
    }
}
 
// Transfer money between accounts - DEADLOCK FREE!
int transfer(int from_account, int to_account, double amount) {
    // Always acquire in account number order
    int first = (from_account < to_account) ? from_account : to_account;
    int second = (from_account < to_account) ? to_account : from_account;
    
    // Acquire locks in order
    if (ordered_lock(account_resources[first]) != 0) {
        return -1;  // Ordering violation would be caught here
    }
    if (ordered_lock(account_resources[second]) != 0) {
        ordered_unlock(account_resources[first]);
        return -1;
    }
    
    // Critical section - safe from deadlock
    if (get_balance(from_account) >= amount) {
        debit(from_account, amount);
        credit(to_account, amount);
    }
    
    // Release in reverse order (good practice, not required)
    ordered_unlock(account_resources[second]);
    ordered_unlock(account_resources[first]);
    
    return 0;
}
 
/*
 * WHY THIS WORKS:
 * 
 * Thread 1: transfer(5, 10, $100)
 *   - Acquires account 5 (order 5)
 *   - Acquires account 10 (order 10 > 5 ✓)
 * 
 * Thread 2: transfer(10, 5, $200)  
 *   - Acquires account 5 (order 5) - must wait for Thread 1
 *   - When Thread 1 releases, Thread 2 continues
 *   - Acquires account 10 (order 10 > 5 ✓)
 * 
 * Both threads acquire in order 5→10, never 10→5.
 * No cycle is possible!
 * 
 * Thread 3: transfer(7, 3, $50)
 *   - Acquires account 3 (order 3) - might need to wait
 *   - Acquires account 7 (order 7 > 3 ✓)
 * 
 * Even with many concurrent transfers, the ordering prevents all deadlocks.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

// Strategy 1: Memory Address Ordering
// Simple, requires no registration, works for any pointer
 
int compare_by_address(const void* a, const void* b) {
    return (uintptr_t)a - (uintptr_t)b;
}
 
void lock_multiple_by_address(pthread_mutex_t** mutexes, int count) {
    // Sort mutexes by address
    pthread_mutex_t* sorted[count];
    memcpy(sorted, mutexes, count * sizeof(void*));
    qsort(sorted, count, sizeof(void*), compare_by_address);
    
    // Lock in address order
    for (int i = 0; i < count; i++) {
        pthread_mutex_lock(sorted[i]);
    }
}
 
// Strategy 2: Lock Leveling (Semantic Layers)
// Common in operating systems and complex software
 
typedef enum {
    // Lower numbers = acquired first = released last
    LOCK_LEVEL_HARDWARE = 0,     // IRQ disable, spinlocks
    LOCK_LEVEL_ALLOCATOR = 10,   // Memory allocator locks
    LOCK_LEVEL_SCHEDULER = 20,   // Scheduler locks
    LOCK_LEVEL_FILESYSTEM = 30,  // VFS, inode locks
    LOCK_LEVEL_NETWORK = 40,     // Socket, protocol locks
    LOCK_LEVEL_PROCESS = 50,     // Process table, cred locks
    LOCK_LEVEL_APPLICATION = 60, // Application-defined locks
} lock_level_t;
 
typedef struct {
    pthread_mutex_t mutex;
    lock_level_t level;
    const char* name;
} leveled_lock_t;
 
__thread lock_level_t current_level = -1; // No locks held
 
void leveled_lock(leveled_lock_t* lock) {
    // Enforce level ordering
    if (lock->level <= current_level) {
        panic("Lock level violation: %s (level %d) while at level %d",
              lock->name, lock->level, current_level);
    }
    
    pthread_mutex_lock(&lock->mutex);
    current_level = lock->level;
}
 
// Strategy 3: Hierarchical Ordering (Tree-Based)
// For resources with parent-child relationships
 
typedef struct node {
    int id;
    pthread_mutex_t lock;
    struct node* parent;
    struct node* children[MAX_CHILDREN];
    int child_count;
} tree_node_t;
 
// Lock from root to leaf - always parent before children
void lock_path_to_node(tree_node_t* target) {
    // Build path from root to target
    tree_node_t* path[MAX_DEPTH];
    int depth = 0;
    
    for (tree_node_t* n = target; n != NULL; n = n->parent) {
        path[depth++] = n;
    }
    
    // Lock from root (end of path array) to target
    for (int i = depth - 1; i >= 0; i--) {
        pthread_mutex_lock(&path[i]->lock);
    }
}
 
// Unlock from leaf to root (reverse of acquisition)
void unlock_path_to_node(tree_node_t* target) {
    tree_node_t* path[MAX_DEPTH];
    int depth = 0;
    
    for (tree_node_t* n = target; n != NULL; n = n->parent) {
        path[depth++] = n;
    }
    
    // Unlock from target to root
    for (int i = 0; i < depth; i++) {
        pthread_mutex_unlock(&path[i]->lock);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

// Linux Kernel Lock Ordering Examples
 
/* 
 * Example 1: Inode Lock Ordering (fs/namei.c)
 * When renaming files, must lock both source and destination directories
 * Ordering: by inode pointer address to prevent A→B vs B→A deadlock
 */
static struct inode *lock_two_directories(struct inode *p1, struct inode *p2)
{
    struct inode *p;
    
    if (p1 == p2) {
        // Same directory - lock once
        inode_lock(p1);
        return NULL;
    }
    
    // Lock by address order
    if (p1 < p2) {
        inode_lock(p1);
        inode_lock(p2);
        p = p1;
    } else {
        inode_lock(p2);
        inode_lock(p1);
        p = p2;
    }
    
    return p;
}
 
/*
 * Example 2: mm_struct lock ordering (mm/mmap.c)
 * When operating on multiple address spaces (e.g., fork, exec)
 * Uses consistent ordering to prevent mm_struct deadlocks
 */
static void lock_two_mms(struct mm_struct *mm1, struct mm_struct *mm2)
{
    if (mm1 == mm2)
        return;
        
    if (mm1 < mm2) {
        mutex_lock(&mm1->mmap_lock);
        mutex_lock(&mm2->mmap_lock);
    } else {
        mutex_lock(&mm2->mmap_lock);
        mutex_lock(&mm1->mmap_lock);
    }
}
 
/*
 * Example 3: Lock Classes and Nesting (include/linux/lockdep.h)
 * Lockdep uses lock "classes" to group locks of the same type
 * Subclasses define allowed nesting patterns
 */
 
// Define lock class with nesting levels
enum page_lock_subclass {
    ZONE_LRU = 0,      // Zone LRU lock
    ZONE_BATCH = 1,    // Zone batch allocation lock  
    PAGE_TABLE = 2,    // Page table lock
};
 
// Use spin_lock_nested() to tell lockdep about intended nesting
static void lock_zone_and_page(struct zone *zone, struct page *page)
{
    spin_lock(&zone->lock);
    // Tell lockdep this is intentional nesting, not a deadlock
    spin_lock_nested(&page->lock, PAGE_TABLE);
}
 
/*
 * Example 4: Lock Order Documentation (kernel common patterns)
 * Documentation/locking/ describes many agreed-upon orderings
 */
 
/*
 * VFS Lock Ordering:
 * 1. sb_writers (superblock writers)
 * 2. s_type->i_mutex_dir_key (directory inodes)
 * 3. s_type->i_mutex_key (regular inodes)
 * 4. mapping->i_mmap_rwsem
 * 5. mapping->invalidate_lock
 * 6. mmap_lock
 * 7. page lock
 *
 * All kernel code must follow this order.
 * Lockdep validates compliance automatically.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

// Trylock with Backoff Pattern
// When ordering violation is unavoidable, use non-blocking acquisition
 
int acquire_unordered(resource_t* resources[], int count) {
    int acquired = 0;
    int retries = 0;
    
    while (acquired < count && retries < MAX_RETRIES) {
        // Try to acquire all resources
        for (int i = acquired; i < count; i++) {
            int result = pthread_mutex_trylock(&resources[i]->mutex);
            
            if (result == 0) {
                acquired++;
            } else if (result == EBUSY) {
                // Couldn't get this lock - back off
                // Release everything we've acquired
                for (int j = 0; j < acquired; j++) {
                    pthread_mutex_unlock(&resources[j]->mutex);
                }
                acquired = 0;
                
                // Exponential backoff to prevent livelock
                usleep((1 << retries) * 100);
                retries++;
                
                // Optional: sort resources for next attempt
                sort_by_address(resources, count);
                break;
            } else {
                // Actual error
                return -1;
            }
        }
    }
    
    return (acquired == count) ? 0 : -1;
}
 
// Lock Coupling Pattern
// For linked list traversal without holding all locks
 
typedef struct node {
    pthread_mutex_t lock;
    int data;
    struct node* next;
} node_t;
 
node_t* find_in_list(node_t* head, int target) {
    if (head == NULL) return NULL;
    
    // Lock first node
    pthread_mutex_lock(&head->lock);
    node_t* current = head;
    
    while (current->next != NULL) {
        // Lock next before unlocking current (coupling)
        pthread_mutex_lock(&current->next->lock);
        
        if (current->data == target) {
            // Found it! Keep current locked, return it
            pthread_mutex_unlock(&current->next->lock);
            return current;
        }
        
        // Move forward: unlock current, advance
        node_t* next = current->next;
        pthread_mutex_unlock(&current->lock);
        current = next;
    }
    
    // Check last node
    if (current->data == target) {
        return current;  // Still locked
    }
    
    pthread_mutex_unlock(&current->lock);
    return NULL;
}
 
/*
 * LOCK COUPLING ANALYSIS:
 * - We always hold at most 2 locks
 * - We always acquire "right" (next) before releasing "left" (current)
 * - Order is always: earlier nodes before later nodes
 * - Deadlock is impossible because we always make forward progress
 * 
 * Compare to: locking entire list (poor performance)
 * Or: no locking (data races)
 */