Understanding Deadlock Concepts

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

#include <pthread.h>
#include <stdbool.h>
 
pthread_mutex_t mutex_A, mutex_B;
 
/* DEADLOCK: Both threads block waiting */
void* deadlock_thread_1(void* arg) {
    pthread_mutex_lock(&mutex_A);       // Acquires A
    sleep(1);                           // Allow other thread to acquire B
    pthread_mutex_lock(&mutex_B);       // BLOCKS forever (B held by thread 2)
    // Never reaches here
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
    return NULL;
}
 
void* deadlock_thread_2(void* arg) {
    pthread_mutex_lock(&mutex_B);       // Acquires B
    sleep(1);                           // Allow other thread to acquire A
    pthread_mutex_lock(&mutex_A);       // BLOCKS forever (A held by thread 1)
    // Never reaches here
    pthread_mutex_unlock(&mutex_A);
    pthread_mutex_unlock(&mutex_B);
    return NULL;
}
 
/* 
 * Deadlock state:
 * - Thread 1: Blocked on lock(&mutex_B), holding A
 * - Thread 2: Blocked on lock(&mutex_A), holding B
 * - CPU usage: ~0% (both threads sleeping in kernel)
 */
 
/* LIVELOCK: Both threads actively spin, yielding to each other */
void* livelock_thread_1(void* arg) {
    bool acquired_both = false;
    while (!acquired_both) {
        pthread_mutex_lock(&mutex_A);           // Get A
        
        if (pthread_mutex_trylock(&mutex_B) != 0) {
            // Can't get B immediately, be "polite"
            pthread_mutex_unlock(&mutex_A);     // Release A
            // Retry (but so does the other thread!)
            continue;
        }
        
        acquired_both = true;
    }
    // Critical section...
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
    return NULL;
}
 
void* livelock_thread_2(void* arg) {
    bool acquired_both = false;
    while (!acquired_both) {
        pthread_mutex_lock(&mutex_B);           // Get B
        
        if (pthread_mutex_trylock(&mutex_A) != 0) {
            // Can't get A immediately, be "polite"
            pthread_mutex_unlock(&mutex_B);     // Release B
            // Retry (but so does the other thread!)
            continue;
        }
        
        acquired_both = true;
    }
    // Critical section...
    pthread_mutex_unlock(&mutex_A);
    pthread_mutex_unlock(&mutex_B);
    return NULL;
}
 
/*
 * Livelock state (worst case):
 * - Thread 1: Gets A, tries B, fails, releases A, repeats
 * - Thread 2: Gets B, tries A, fails, releases B, repeats
 * - CPU usage: 100% (both threads actively spinning)
 * - Progress: 0% (neither ever gets both locks)
 * 
 * The "polite" retry behavior that prevents deadlock
 * has created livelock!
 */

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

/* 
 * CAUSE 1: Symmetric Retry Logic
 * Both processes do exactly the same thing on conflict
 */
void symmetric_retry_process(int id, Resource* r1, Resource* r2) {
    while (true) {
        acquire(r1);
        if (!try_acquire(r2)) {
            release(r1);
            // Both processes hit this SIMULTANEOUSLY
            // and will retry SIMULTANEOUSLY
            continue;
        }
        // Got both
        break;
    }
}
 
/*
 * CAUSE 2: Hot Potato Message
 * Message bounces between handlers that all reject it
 */
void message_handler(Message* msg) {
    if (!can_handle(msg)) {
        // "Not my problem!" - forward to next handler
        Route next = find_next_handler(msg);
        forward(msg, next);
        // But what if all handlers reject it?
        // The message circulates forever!
    }
}
 
/*
 * CAUSE 3: Optimistic Concurrency Conflict
 * STM or database optimistic locking under high contention
 */
void stm_transaction() {
retry:
    begin_transaction();
    
    // Read some values
    int x = read(var_x);
    int y = read(var_y);
    
    // Compute new values
    write(var_x, x + 1);
    write(var_y, y - 1);
    
    if (!commit()) {
        // Conflict detected - another transaction modified x or y
        // Under high contention, conflicts happen constantly
        // All transactions keep aborting and retrying
        goto retry;  // LIVELOCK if conflicts never stop!
    }
}
 
/*
 * CAUSE 4: Collision in CSMA/CD (network level)
 * Two senders detect collision, wait, and retransmit together
 */
void csma_cd_transmit(Frame* frame) {
    while (true) {
        if (channel_is_busy()) {
            wait();
            continue;
        }
        
        start_transmission(frame);
        
        if (collision_detected()) {
            abort_transmission();
            // Without randomized backoff, both senders
            // might wait the same amount and collide again!
            wait_fixed_time();  // BUG: should be random!
            continue;
        }
        
        // Success
        break;
    }
}

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

#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
 
#define SLOT_TIME_US 51200  // 51.2 microseconds for 10 Mbps Ethernet
#define MAX_ATTEMPTS 16
#define BACKOFF_LIMIT 10
 
typedef struct {
    uint8_t* data;
    size_t length;
} Frame;
 
typedef enum { SUCCESS, COLLISION, CHANNEL_BUSY, FAILURE } TransmitResult;
 
/*
 * Binary Exponential Backoff Algorithm
 * This is how Ethernet prevents livelock during collisions
 */
TransmitResult transmit_with_backoff(Frame* frame) {
    int attempts = 0;
    
    while (attempts < MAX_ATTEMPTS) {
        // Wait for channel to be free
        while (carrier_sense()) {
            // Channel busy, wait
        }
        
        // Start transmission
        start_transmission(frame);
        
        // Monitor for collision during transmission
        if (!collision_detected()) {
            // Success!
            complete_transmission();
            return SUCCESS;
        }
        
        // Collision occurred
        send_jam_signal();
        abort_transmission();
        attempts++;
        
        if (attempts >= MAX_ATTEMPTS) {
            // Too many collisions - give up
            return FAILURE;
        }
        
        // Calculate backoff
        int k = (attempts < BACKOFF_LIMIT) ? attempts : BACKOFF_LIMIT;
        int max_slots = (1 << k);  // 2^k
        int random_slots = rand() % max_slots;  // Random from 0 to 2^k - 1
        
        // Wait for random number of slot times
        usleep(random_slots * SLOT_TIME_US);
    }
    
    return FAILURE;
}
 
/*
 * WHY THIS PREVENTS LIVELOCK:
 * 
 * 1. RANDOMIZATION: After first collision, station picks 0 or 1 slots.
 *    With 50% probability, the two stations pick different values.
 * 
 * 2. EXPONENTIAL GROWTH: If they collide again, range doubles to {0,1,2,3}.
 *    Probability of picking same value: 25%. After 3rd collision: 12.5%.
 *    The probability of continuous collisions drops exponentially.
 * 
 * 3. BOUNDED RETRIES: If extremely unlucky (16 collisions), give up.
 *    This bounds the maximum time any frame can be stuck.
 * 
 * Expected behavior: Most frames transmit successfully within 1-3 attempts.
 * Livelock probability is vanishingly small.
 */
 
// Example: Probability of k consecutive unsuccessful backoffs
void analyze_collision_probability() {
    /*
     * P(collision after attempt k) ≈ 1 / 2^k
     * 
     * P(16 consecutive collisions) ≈ (1/2) * (1/4) * (1/8) * ... * (1/1024)
     *                              ≈ 1 / 2^55  (effectively impossible)
     * 
     * This is why Ethernet works reliably under high load:
     * The exponential backoff makes persistent livelock
     * astronomically unlikely.
     */
}

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

#include <stdint.h>
#include <stdbool.h>
#include <time.h>
 
/* Progress-based livelock detection */
 
typedef struct {
    uint64_t work_started;      // Count of tasks started
    uint64_t work_completed;    // Count of tasks completed
    uint64_t retries;           // Count of retry operations
    time_t last_completion;     // Timestamp of last completion
    uint64_t cpu_cycles;        // CPU cycles consumed
} ProcessMetrics;
 
typedef struct {
    ProcessMetrics metrics[MAX_PROCESSES];
    time_t check_interval;
    uint64_t max_retries_per_interval;
    double min_progress_ratio;
} LivelockDetector;
 
/* Check if a process is in livelock */
bool check_for_livelock(LivelockDetector* detector, int pid) {
    ProcessMetrics* m = &detector->metrics[pid];
    time_t now = time(NULL);
    
    // Check 1: No completions for extended period
    if (now - m->last_completion > detector->check_interval) {
        if (m->work_started > m->work_completed + 10) {
            // Started work but haven't completed any recently
            // Possible livelock
            return true;
        }
    }
    
    // Check 2: Excessive retries relative to completions
    double progress_ratio = 0;
    if (m->retries > 0) {
        progress_ratio = (double)m->work_completed / m->retries;
    }
    
    if (m->retries > detector->max_retries_per_interval && 
        progress_ratio < detector->min_progress_ratio) {
        // Many retries but little progress
        // Strong indicator of livelock
        return true;
    }
    
    // Check 3: High CPU usage with no progress
    // (would need additional CPU monitoring)
    
    return false;
}
 
/* Retry counter with livelock protection */
typedef struct {
    int count;
    int threshold;
    void (*on_livelock_detected)(void* context);
    void* context;
} LivelockProtectedRetry;
 
bool should_retry(LivelockProtectedRetry* retry) {
    retry->count++;
    
    if (retry->count >= retry->threshold) {
        // Too many retries - likely livelock
        if (retry->on_livelock_detected) {
            retry->on_livelock_detected(retry->context);
        }
        return false;  // Stop retrying
    }
    
    return true;  // Okay to retry
}
 
void reset_retry_counter(LivelockProtectedRetry* retry) {
    retry->count = 0;  // Reset after successful operation
}
 
/* State cycle detection */
typedef struct {
    uint64_t state_hashes[HISTORY_SIZE];
    int history_index;
    int cycle_threshold;
} StateCycleDetector;
 
bool detect_state_cycle(StateCycleDetector* detector, void* state, size_t state_size) {
    // Hash current state
    uint64_t current_hash = hash_state(state, state_size);
    
    // Check if we've seen this state recently
    int matches = 0;
    for (int i = 0; i < HISTORY_SIZE; i++) {
        if (detector->state_hashes[i] == current_hash) {
            matches++;
        }
    }
    
    // Store current state
    detector->state_hashes[detector->history_index] = current_hash;
    detector->history_index = (detector->history_index + 1) % HISTORY_SIZE;
    
    // If same state appears multiple times, we're cycling
    return matches >= detector->cycle_threshold;
}

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
131

#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <stdbool.h>
 
pthread_mutex_t mutex_A, mutex_B;
 
/*
 * STRATEGY 1: Randomized Backoff
 * Add random delay before retry
 */
void acquire_both_random_backoff(int thread_id) {
    int attempts = 0;
    
    while (true) {
        pthread_mutex_lock(&mutex_A);
        
        if (pthread_mutex_trylock(&mutex_B) == 0) {
            // Success - got both
            break;
        }
        
        pthread_mutex_unlock(&mutex_A);
        
        // RANDOM backoff - different threads wait different times
        int backoff_us = (rand() % 1000) + 100;  // 100-1099 microseconds
        usleep(backoff_us);
        
        attempts++;
    }
    
    // Use resources...
    
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
}
 
/*
 * STRATEGY 2: Exponential Backoff
 * Increase wait range with each failure
 */
void acquire_both_exponential(int thread_id) {
    int attempts = 0;
    int max_backoff = 100;  // Start with 100 microseconds
    
    while (attempts < MAX_ATTEMPTS) {
        pthread_mutex_lock(&mutex_A);
        
        if (pthread_mutex_trylock(&mutex_B) == 0) {
            break;  // Success
        }
        
        pthread_mutex_unlock(&mutex_A);
        
        // EXPONENTIAL backoff
        int backoff_us = rand() % max_backoff;
        usleep(backoff_us);
        
        attempts++;
        max_backoff = (max_backoff < MAX_BACKOFF) ? max_backoff * 2 : MAX_BACKOFF;
    }
    
    if (attempts >= MAX_ATTEMPTS) {
        // Handle failure - escalate or use alternative
        handle_resource_unavailable();
        return;
    }
    
    // Use resources...
    
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
}
 
/*
 * STRATEGY 3: Priority-Based Yielding
 * Higher-priority thread never yields
 */
void acquire_both_priority(int thread_id, int priority) {
    while (true) {
        pthread_mutex_lock(&mutex_A);
        
        if (pthread_mutex_trylock(&mutex_B) == 0) {
            break;  // Success
        }
        
        // Only yield if we're lower priority than current holder
        int holder_priority = get_holder_priority(&mutex_B);
        
        if (priority < holder_priority) {
            // We're lower priority - yield and retry
            pthread_mutex_unlock(&mutex_A);
            usleep(100);
        } else {
            // We're higher priority - wait for other to yield
            pthread_mutex_unlock(&mutex_A);
            usleep(10);  // Short wait; holder should yield soon
        }
    }
    
    // Use resources...
    
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
}
 
/*
 * STRATEGY 4: Lock Ordering (Best!)
 * Eliminate the livelock source entirely
 */
void acquire_both_ordered(int thread_id) {
    // ALWAYS acquire in same order: A before B
    pthread_mutex_lock(&mutex_A);
    pthread_mutex_lock(&mutex_B);  // No trylock needed!
    
    // Use resources...
    
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
}
 
/*
 * Lock ordering is the best solution because:
 * 1. No livelock possible - no release-and-retry loops
 * 2. No deadlock possible - consistent ordering breaks cycles
 * 3. Simpler code - no backoff logic
 * 4. Predictable behavior - no randomness
 * 
 * The only downside: requires global agreement on lock order,
 * which may not be feasible in all systems.
 */

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

"""
Distributed Transaction Livelock Example
 
Scenario: Two distributed transactions repeatedly conflict
"""
 
class DistributedTransaction:
    def __init__(self, tx_id, resources_needed):
        self.tx_id = tx_id
        self.resources = resources_needed
        self.retries = 0
        self.max_retries = 100
    
    def execute(self, coordinator):
        while self.retries < self.max_retries:
            try:
                # Phase 1: Prepare
                if not coordinator.prepare(self):
                    raise ConflictException()
                
                # Phase 2: Commit
                coordinator.commit(self)
                return True  # Success!
                
            except ConflictException:
                coordinator.rollback(self)
                self.retries += 1
                
                # LIVELOCK PREVENTION: Exponential backoff with jitter
                base_delay = 0.01 * (2 ** min(self.retries, 10))
                jitter = random.uniform(0, base_delay)
                time.sleep(base_delay + jitter)
        
        # Exceeded max retries
        raise LivelockException(f"Transaction {self.tx_id} aborted after {self.max_retries} attempts")
 
 
class Coordinator:
    def __init__(self):
        self.locks = {}  # resource -> (holder_tx_id, mode)
    
    def prepare(self, tx):
        """Try to acquire locks for transaction."""
        for resource in tx.resources:
            current_holder = self.locks.get(resource)
            if current_holder and current_holder[0] != tx.tx_id:
                # Conflict detected
                # LIVELOCK RISK: If we just return False, both
                # transactions might abort and retry together
                
                # PREVENTION: Use wait-die or wound-wait scheme
                if self._should_yield(tx, current_holder[0]):
                    return False  # We yield
                else:
                    # We don't yield; other transaction should abort
                    self._request_abort(current_holder[0])
                    # Wait briefly for other to actually abort
                    time.sleep(0.001)
                    return False  # Retry
        
        # No conflicts - acquire locks
        for resource in tx.resources:
            self.locks[resource] = (tx.tx_id, 'X')
        return True
    
    def _should_yield(self, tx, holder_tx_id):
        """Wait-Die scheme: Older transactions wait, younger die (abort)."""
        # Older = lower tx_id (assuming monotonic IDs)
        if tx.tx_id > holder_tx_id:
            return True   # We're younger, we abort
        return False      # We're older, holder should abort
 
 
"""
DISTRIBUTED LIVELOCK PREVENTION SCHEMES:
 
1. Wait-Die (Wound-Wait):
   - Assign timestamps/priorities to transactions
   - Older transactions ALWAYS win conflicts
   - Breaks symmetry deterministically
   - No livelock possible because conflicts resolve consistently
 
2. Random Priority on Conflict:
   - When conflict detected, flip a coin for who yields
   - 50% chance each time, so livelock statistically unlikely
   - Less efficient than wait-die but simpler
 
3. Backoff with Unique Delays:
   - Each node picks backoff based on node ID
   - E.g., backoff = base_delay * (1 + node_id * 0.1)
   - Deterministic yet asymmetric
 
4. Centralized Conflict Resolution:
   - Send all conflicts to a coordinator
   - Coordinator makes consistent decisions
   - Single point of failure but no livelock
"""