Breaking Hold and Wait

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

// Total Allocation Protocol Implementation
typedef struct {
    int resource_counts[MAX_RESOURCES];  // Available resources
    mutex_t allocation_lock;              // Protects allocation decisions
    cond_t resources_available;           // Signal when resources released
} resource_manager_t;
 
typedef struct {
    int required[MAX_RESOURCES];   // Resources process needs
    int allocated[MAX_RESOURCES];  // Resources currently held
    bool executing;                // Has process started execution?
} process_resources_t;
 
resource_manager_t rm;
 
// Attempt to allocate ALL resources atomically
bool request_all_resources(process_resources_t* proc) {
    mutex_lock(&rm.allocation_lock);
    
    while (true) {
        // Check if ALL required resources are available
        bool all_available = true;
        for (int i = 0; i < MAX_RESOURCES; i++) {
            if (proc->required[i] > rm.resource_counts[i]) {
                all_available = false;
                break;
            }
        }
        
        if (all_available) {
            // Allocate all resources atomically
            for (int i = 0; i < MAX_RESOURCES; i++) {
                rm.resource_counts[i] -= proc->required[i];
                proc->allocated[i] = proc->required[i];
            }
            proc->executing = true;
            mutex_unlock(&rm.allocation_lock);
            return true;  // Process can now execute
        }
        
        // Not all available - wait (process holds NOTHING while waiting)
        // This is the key: we never hold resources while waiting
        cond_wait(&rm.resources_available, &rm.allocation_lock);
    }
}
 
// Release ALL resources when done
void release_all_resources(process_resources_t* proc) {
    mutex_lock(&rm.allocation_lock);
    
    for (int i = 0; i < MAX_RESOURCES; i++) {
        rm.resource_counts[i] += proc->allocated[i];
        proc->allocated[i] = 0;
    }
    proc->executing = false;
    
    // Wake up all waiting processes to check availability
    cond_broadcast(&rm.resources_available);
    mutex_unlock(&rm.allocation_lock);
}
 
/*
 * DEADLOCK PREVENTION PROOF:
 * 
 * Hold-and-wait requires: process holds R1 while waiting for R2
 * 
 * Under total allocation:
 * - Before request_all: process holds NOTHING
 * - During wait: process holds NOTHING (never allocated partial set)
 * - After allocation: process holds EVERYTHING (no more requests)
 * 
 * At no point does a process hold some resources while waiting for others.
 * Therefore, hold-and-wait condition is never satisfied.
 * Deadlock is impossible under this protocol.
 */

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

// Release-Before-Request Protocol Implementation
typedef struct {
    int resource_counts[MAX_RESOURCES];
    mutex_t lock;
    cond_t available;
} resource_manager_t;
 
typedef struct {
    int held[MAX_RESOURCES];         // Currently held resources
    int pending[MAX_RESOURCES];      // Resources we want to acquire
    void* saved_state;               // Saved computation state
} process_t;
 
resource_manager_t rm;
 
// Request additional resources (must release current first)
bool request_resources(process_t* proc, int requested[MAX_RESOURCES]) {
    mutex_lock(&rm.lock);
    
    // Step 1: Release ALL currently held resources
    for (int i = 0; i < MAX_RESOURCES; i++) {
        rm.resource_counts[i] += proc->held[i];
        proc->held[i] = 0;
    }
    
    // Step 2: Save any state that depends on released resources
    save_process_state(proc);
    
    // Step 3: Calculate new total requirement
    // (original work still needs some resources + new requests)
    int total_needed[MAX_RESOURCES];
    for (int i = 0; i < MAX_RESOURCES; i++) {
        total_needed[i] = requested[i];  // May include previously held
    }
    
    // Step 4: Wait for ALL needed resources (holding nothing)
    while (true) {
        bool can_allocate = true;
        for (int i = 0; i < MAX_RESOURCES; i++) {
            if (total_needed[i] > rm.resource_counts[i]) {
                can_allocate = false;
                break;
            }
        }
        
        if (can_allocate) {
            // Allocate all at once
            for (int i = 0; i < MAX_RESOURCES; i++) {
                rm.resource_counts[i] -= total_needed[i];
                proc->held[i] = total_needed[i];
            }
            
            // Restore state and continue
            restore_process_state(proc);
            cond_broadcast(&rm.available);  // Others might proceed now
            mutex_unlock(&rm.lock);
            return true;
        }
        
        // Wait while holding NOTHING
        cond_wait(&rm.available, &rm.lock);
    }
}
 
/*
 * EXAMPLE: Process needs files A, B, then later needs files A, B, C
 * 
 * Phase 1: Request {A, B}
 *   - Currently holds: nothing
 *   - Request {A, B} → granted
 *   - Now holds {A, B}
 * 
 * Phase 2: Need to add C
 *   - Release ALL: {A, B} returned to pool
 *   - Save state (data read from A, B)
 *   - Now holds: nothing
 *   - Request {A, B, C} → wait if necessary
 *   - When granted, holds {A, B, C}
 *   - Restore state and continue
 * 
 * At no point: holds {A,B} while waiting for C
 * → Hold-and-wait prevented!
 */

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

// Conservative Two-Phase Locking for Database Transactions
 
typedef enum { UNLOCKED, READ_LOCKED, WRITE_LOCKED } lock_state_t;
 
typedef struct {
    lock_state_t state;
    int read_count;
    pid_t write_owner;
    mutex_t lock;
    cond_t released;
} data_item_t;
 
typedef struct {
    int num_items;
    int* item_ids;          // Items this transaction will access
    lock_state_t* modes;    // READ or WRITE for each item
    bool in_shrinking_phase;
} transaction_t;
 
data_item_t items[MAX_ITEMS];
 
// Conservative 2PL: Acquire ALL locks before starting
bool begin_transaction(transaction_t* txn) {
    // Sort items to prevent deadlock (same as resource ordering)
    sort_by_item_id(txn);
    
    // Acquire all locks atomically (all-or-nothing)
    for (int i = 0; i < txn->num_items; i++) {
        int item_id = txn->item_ids[i];
        lock_state_t mode = txn->modes[i];
        
        mutex_lock(&items[item_id].lock);
        
        while (true) {
            if (mode == READ_LOCKED) {
                // Read lock: compatible with other reads
                if (items[item_id].state != WRITE_LOCKED) {
                    items[item_id].state = READ_LOCKED;
                    items[item_id].read_count++;
                    break;
                }
            } else {  // WRITE_LOCKED
                // Write lock: exclusive access
                if (items[item_id].state == UNLOCKED) {
                    items[item_id].state = WRITE_LOCKED;
                    items[item_id].write_owner = txn_id();
                    break;
                }
            }
            
            // Cannot acquire - wait (holding previous locks)
            // NOTE: This could still deadlock without ordering!
            cond_wait(&items[item_id].released, &items[item_id].lock);
        }
        
        mutex_unlock(&items[item_id].lock);
    }
    
    txn->in_shrinking_phase = false;
    return true;  // All locks acquired - transaction can proceed
}
 
// Perform transaction operations (growing/working phase)
void execute_transaction(transaction_t* txn) {
    // Transaction executes with all locks held
    // No new locks can be acquired
    // This is the critical section for all accessed data
    perform_transaction_logic(txn);
}
 
// Release all locks (shrinking phase)
void commit_transaction(transaction_t* txn) {
    txn->in_shrinking_phase = true;
    
    for (int i = 0; i < txn->num_items; i++) {
        int item_id = txn->item_ids[i];
        
        mutex_lock(&items[item_id].lock);
        
        if (txn->modes[i] == READ_LOCKED) {
            items[item_id].read_count--;
            if (items[item_id].read_count == 0) {
                items[item_id].state = UNLOCKED;
            }
        } else {
            items[item_id].state = UNLOCKED;
            items[item_id].write_owner = -1;
        }
        
        cond_broadcast(&items[item_id].released);
        mutex_unlock(&items[item_id].lock);
    }
}
 
/*
 * DEADLOCK ANALYSIS:
 * 
 * With naive C2PL (acquire all at start without ordering):
 * - Txn A wants {X, Y} - gets X, waits for Y
 * - Txn B wants {Y, X} - gets Y, waits for X
 * - DEADLOCK!
 * 
 * C2PL with resource ordering (acquire in sorted order):
 * - Txn A wants {X, Y} - tries X first
 * - Txn B wants {Y, X} - tries X first (after sorting)
 * - One gets X, other waits
 * - No circular wait possible
 * - DEADLOCK PREVENTED!
 */

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

// Timeout-Based Release Strategy
// Prevents indefinite blocking, converts potential deadlock to retry
 
#define RESOURCE_TIMEOUT_MS 1000
#define MAX_RETRIES 5
 
typedef struct {
    int held[MAX_RESOURCES];
    time_t hold_start;
    int retry_count;
} process_t;
 
result_t acquire_with_timeout(process_t* proc, int resource_id) {
    time_t start = time(NULL);
    
    mutex_lock(&rm.lock);
    
    while (rm.resource_counts[resource_id] == 0) {
        // Check if we've been waiting too long
        if (time(NULL) - start > RESOURCE_TIMEOUT_MS / 1000) {
            // Timeout! Release everything and retry
            release_all_resources_internal(proc);
            mutex_unlock(&rm.lock);
            
            proc->retry_count++;
            if (proc->retry_count > MAX_RETRIES) {
                return RESULT_ABORTED;  // Give up
            }
            
            // Back-off with exponential delay
            sleep_ms(50 * (1 << proc->retry_count));
            
            // Restart acquisition from scratch
            return RESULT_RETRY;
        }
        
        // Wait with timeout
        cond_timedwait(&rm.available, &rm.lock, RESOURCE_TIMEOUT_MS);
    }
    
    // Resource available - acquire it
    rm.resource_counts[resource_id]--;
    proc->held[resource_id]++;
    
    mutex_unlock(&rm.lock);
    return RESULT_SUCCESS;
}
 
/*
 * BEHAVIOR:
 * - Process A holds R1, waits for R2
 * - Process B holds R2, waits for R1
 * - After timeout, A releases R1 and retries
 * - B gets R1, completes, releases both
 * - A retries and succeeds
 * 
 * TRADEOFF:
 * - Converts deadlock to temporary livelock
 * - Exponential backoff prevents thundering herd
 * - May increase latency but guarantees progress
 */