Deadlock Prevention - Learning Module

Loading content...

0/227

Breaking Hold and Wait

Preventing the Hold-and-Wait Condition

The hold-and-wait condition states that a process holding at least one resource is waiting to acquire additional resources currently held by other processes. This is a necessary condition for deadlock—if we can eliminate it, deadlock becomes impossible regardless of the other conditions.

Unlike mutual exclusion, which is often dictated by the intrinsic nature of resources, hold-and-wait is a behavioral property of how processes request and use resources. This makes it a more tractable target for prevention: we can design protocols that constrain process behavior to eliminate this condition.

The Core Insight

Hold-and-wait prevention ensures that whenever a process requests a resource, it must not be holding any other resources. This is achieved through either: (1) requesting all resources before execution begins, or (2) releasing all held resources before requesting additional ones.

Why hold-and-wait prevention is powerful:

Consider the classic deadlock scenario:

Process A holds Resource 1, waits for Resource 2
Process B holds Resource 2, waits for Resource 1

If we enforce that a process cannot hold a resource while waiting for another, this scenario becomes impossible:

When A wants Resource 2, it must first release Resource 1
Since A no longer holds Resource 1, B can obtain it and complete
When B completes and releases both resources, A can proceed

The deadlock is impossible because the circular wait cannot form.

Protocol 1: Total Allocation (Request All at Once)

The first and most stringent protocol for preventing hold-and-wait is total allocation: require each process to request and be allocated all resources it will need before beginning execution. The process either receives all resources simultaneously and proceeds, or receives none and waits.

Formal Definition:

A process P must:

Declare its complete resource requirements (R₁, R₂, ..., Rₙ) before starting
Request all resources as a single atomic operation
Either receive all resources and begin execution
Or receive none and wait until all can be allocated simultaneously

Under this protocol, hold-and-wait is impossible: a process is never in a state where it holds some resources while waiting for others.

total_allocation_protocol.c
C
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.
 */

Atomicity is Crucial

The key to total allocation is the atomic all-or-nothing semantics. If we allowed partial allocation (give what's available now, wait for the rest), we would reintroduce hold-and-wait. The single lock protecting the allocation decision ensures atomicity.

Protocol 2: Release Before Request

The second protocol is more flexible: allow processes to request resources incrementally, but require them to release all currently held resources before making a new request. This is sometimes called the request-release protocol.

Formal Definition:

A process P holding resources {R₁, R₂, ..., Rₖ} that wishes to acquire resource Rₙ must:

Release all currently held resources (R₁ through Rₖ)
Request the new set of resources it needs (which may include some or all of the previously held resources plus Rₙ)
Wait if necessary (while holding nothing)
Receive the complete new set and resume execution

release_before_request.c
C
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!
 */

Comparison with Total Allocation:

The release-before-request protocol offers more flexibility than total allocation because processes don't need to know all requirements upfront. However, it introduces additional complexity:

State management: When releasing resources mid-execution, the process may need to save and restore state
Potential repeated work: If resources become unavailable, previously completed work may need to be redone
Starvation risk: A process might repeatedly release and re-request, never getting all resources together

Despite these challenges, this protocol is useful when resource requirements genuinely cannot be known in advance or when resources are expensive to hold.

Two-Phase Locking Protocol

In database systems, a refined version of hold-and-wait prevention is implemented through two-phase locking (2PL). While 2PL doesn't strictly prevent hold-and-wait, its variant called conservative 2PL or static 2PL does.

Standard Two-Phase Locking:

A transaction's execution is divided into two phases:

Growing phase: Transaction may acquire locks but cannot release any
Shrinking phase: Transaction may release locks but cannot acquire any

Conservative Two-Phase Locking (C2PL):

The conservative variant adds a requirement: acquire all locks at the start of the transaction before accessing any data. This is equivalent to the total allocation protocol applied to database locks.

two_phase_locking.c
C
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!
 */

2PL and Hold-and-Wait

Standard 2PL does NOT prevent hold-and-wait—transactions can acquire locks incrementally during the growing phase. Conservative 2PL prevents it by requiring all locks upfront. In practice, databases often combine 2PL with deadlock detection rather than strict prevention.

Practical Challenges and Tradeoffs

While breaking hold-and-wait is more practical than breaking mutual exclusion, it comes with significant challenges that limit its applicability in many real-world systems.

Major Challenges of Hold-and-Wait Prevention

•Unknown resource requirements — Many applications cannot predict all resources needed before starting. A web server doesn't know which database tables a request will access. A compiler doesn't know which files will be included.
•Low resource utilization — Requiring all resources upfront means resources are held even when not actively used. A process needing both a printer and network connection holds the printer idle during network I/O.
•Starvation potential — Processes requiring many resources may never acquire them all simultaneously, especially if resources are in high demand. Large requests starve while small requests succeed.
•State management complexity — The release-before-request protocol requires saving and restoring state, which may be complex (in-memory data structures) or impossible (irreversible operations).
•Increased waiting times — Waiting for many resources simultaneously takes longer than incremental acquisition. Processes experience longer delays before starting execution.
•Memory overhead — Holding all resources throughout execution increases peak memory usage, as resources that would be released incrementally are held the entire time.

Quantitative Impact Analysis
Scenario	Without Prevention	With Total Allocation	Impact
Process needs resources A(1s), B(1s), C(1s)	Holds each ~1s	Holds all 3s each	3x resource hold time
10 processes, 5 resources	Fine-grained contention	Coarse-grained blocking	Reduced parallelism
Unpredictable requirements	Request as needed	Must over-estimate or abort	Waste or retry cost
Memory allocation	Malloc per object	Pre-allocate maximum	Higher peak memory
Database transaction	Lock rows on access	Lock all tables upfront	More conservative locking

The Prediction Problem in Detail:

Consider a web application handling user requests:

function handleRequest(userId) {
    user = database.getUser(userId);      // Need lock on users table
    
    if (user.isPremium) {
        features = database.getPremiumFeatures();  // Need lock on features table
        if (features.includes('analytics')) {
            stats = database.getAnalytics(userId);  // Need lock on analytics table
        }
    }
    
    return response;
}

The resources needed depend on runtime data (is user premium? which features?). With total allocation, we would need to:

Always acquire locks on users, features, AND analytics tables
Even for non-premium users who only need the users table
This massively increases contention and reduces throughput

Mitigation Strategies

Despite the challenges, several techniques can make hold-and-wait prevention more practical:

Practical Mitigation Techniques

•Resource classes — Group resources into classes. Processes must acquire all resources within a class before proceeding to the next class. Provides partial ordering benefits while allowing incremental acquisition across classes.
•Optimistic locking — Don't acquire resources upfront, but validate at commit time. If conflicts occurred, abort and retry. Effective when conflicts are rare.
•Timeout-based release — If a process has held resources for too long while waiting for more, automatically release all and retry. Converts deadlock to livelock, then to success.
•Hybrid approaches — Use total allocation for critical resources with known requirements, incremental acquisition for others. Accept some deadlock risk in the incremental portion.
•Batching — Collect multiple small requests into larger transactions that know full requirements. Trade latency for predictability.
•Speculative execution — Execute speculatively with minimal locking, then validate. Works well when speculation is usually correct.

timeout_release.c
C
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
 */

Hold-and-Wait Prevention in Real Systems

Let's examine how different real-world systems handle the hold-and-wait condition:

Real-World Approaches to Hold-and-Wait
System	Approach	Details
POSIX pthread_mutex	Not prevented	Applications must handle deadlock; OS provides no protection
Java synchronized	Not prevented	JVM can detect deadlock but doesn't prevent it
PostgreSQL	Detection + Timeout	Detects cycles in wait graph; `lock_timeout` aborts waiting transactions
MySQL InnoDB	Detection	Detects deadlock and rolls back one transaction
Linux kernel	Lockdep (detection)	Debug tool detects potential deadlocks via lock ordering analysis
Windows Driver Verifier	Detection	Detects incorrect lock usage in kernel drivers
Rust borrow checker	Prevention via types	Type system prevents holding references while mutating (compile-time)
STM (Software Transactional Memory)	Release on conflict	Optimistic execution with rollback on conflicts

Prevention is Rare in Practice

Notice that most systems do NOT use hold-and-wait prevention. The overhead and restrictions are typically too severe. Instead, they use detection (find deadlocks when they occur) or avoidance (use Banker's algorithm-style analysis), or simply document careful lock ordering and rely on programmer discipline.

Case Study: The Dining Philosophers

The dining philosophers problem illustrates hold-and-wait prevention beautifully. Each philosopher needs two forks to eat:

With hold-and-wait (deadlock possible):

Each philosopher picks up left fork
Each philosopher waits for right fork
Deadlock: everyone holds one fork, waits for another

With hold-and-wait prevention (no deadlock):

Philosopher requests BOTH forks atomically
If both available: take both, eat, release both
If not: take neither, wait until both are free

This is the total allocation protocol applied to dining philosophers. It eliminates deadlock but reduces parallelism—adjacent philosophers can never eat simultaneously even when it would be safe.

Summary: Breaking Hold and Wait

We've thoroughly examined how to prevent the hold-and-wait condition for deadlock prevention. Let's consolidate our understanding:

Key Takeaways

•Two main protocols exist — Total allocation (request all upfront) and release-before-request (give up everything before asking for more). Both ensure a process never holds resources while waiting.
•Total allocation is simpler but restrictive — Requires knowing all requirements upfront, which is often impossible for dynamic workloads.
•Release-before-request is flexible but complex — Allows incremental resource discovery but requires state management and may cause repeated work.
•Conservative 2PL applies to databases — Acquiring all locks before starting transaction execution prevents hold-and-wait in database systems.
•Significant tradeoffs exist — Reduced utilization, potential starvation, longer waiting times, and memory overhead are common costs.
•Most real systems don't use strict prevention — The overhead is typically too high; detection, avoidance, or careful design are more common.
•Mitigation strategies help — Timeouts, optimistic locking, and resource classes can make prevention more practical.

What's next:

The next page examines the third necessary condition: breaking no preemption. This strategy allows the system to forcibly take resources away from processes that are waiting, eliminating the condition that once a resource is allocated, it cannot be taken away until voluntarily released.

Page Complete

You now understand how to break the hold-and-wait condition through total allocation and release-before-request protocols. While these approaches have significant practical challenges, they represent theoretically sound methods for deadlock prevention and are applied in specific contexts like database transactions.

Breaking Hold and Wait

Preventing the Hold-and-Wait Condition

The Core Insight

Why hold-and-wait prevention is powerful:

Consider the classic deadlock scenario:

Process A holds Resource 1, waits for Resource 2
Process B holds Resource 2, waits for Resource 1

If we enforce that a process cannot hold a resource while waiting for another, this scenario becomes impossible:

When A wants Resource 2, it must first release Resource 1
Since A no longer holds Resource 1, B can obtain it and complete
When B completes and releases both resources, A can proceed

The deadlock is impossible because the circular wait cannot form.

Protocol 1: Total Allocation (Request All at Once)

Formal Definition:

A process P must:

Declare its complete resource requirements (R₁, R₂, ..., Rₙ) before starting
Request all resources as a single atomic operation
Either receive all resources and begin execution
Or receive none and wait until all can be allocated simultaneously

Under this protocol, hold-and-wait is impossible: a process is never in a state where it holds some resources while waiting for others.

total_allocation_protocol.c
C
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.
 */

Atomicity is Crucial

Protocol 2: Release Before Request

Formal Definition:

A process P holding resources {R₁, R₂, ..., Rₖ} that wishes to acquire resource Rₙ must:

Release all currently held resources (R₁ through Rₖ)
Request the new set of resources it needs (which may include some or all of the previously held resources plus Rₙ)
Wait if necessary (while holding nothing)
Receive the complete new set and resume execution

release_before_request.c
C
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!
 */

Comparison with Total Allocation:

The release-before-request protocol offers more flexibility than total allocation because processes don't need to know all requirements upfront. However, it introduces additional complexity:

State management: When releasing resources mid-execution, the process may need to save and restore state
Potential repeated work: If resources become unavailable, previously completed work may need to be redone
Starvation risk: A process might repeatedly release and re-request, never getting all resources together

Despite these challenges, this protocol is useful when resource requirements genuinely cannot be known in advance or when resources are expensive to hold.

Two-Phase Locking Protocol

Standard Two-Phase Locking:

A transaction's execution is divided into two phases:

Growing phase: Transaction may acquire locks but cannot release any
Shrinking phase: Transaction may release locks but cannot acquire any

Conservative Two-Phase Locking (C2PL):

two_phase_locking.c
C
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!
 */

2PL and Hold-and-Wait

Practical Challenges and Tradeoffs

While breaking hold-and-wait is more practical than breaking mutual exclusion, it comes with significant challenges that limit its applicability in many real-world systems.

Major Challenges of Hold-and-Wait Prevention

•Unknown resource requirements — Many applications cannot predict all resources needed before starting. A web server doesn't know which database tables a request will access. A compiler doesn't know which files will be included.
•Low resource utilization — Requiring all resources upfront means resources are held even when not actively used. A process needing both a printer and network connection holds the printer idle during network I/O.
•Starvation potential — Processes requiring many resources may never acquire them all simultaneously, especially if resources are in high demand. Large requests starve while small requests succeed.
•State management complexity — The release-before-request protocol requires saving and restoring state, which may be complex (in-memory data structures) or impossible (irreversible operations).
•Increased waiting times — Waiting for many resources simultaneously takes longer than incremental acquisition. Processes experience longer delays before starting execution.
•Memory overhead — Holding all resources throughout execution increases peak memory usage, as resources that would be released incrementally are held the entire time.

Quantitative Impact Analysis
Scenario	Without Prevention	With Total Allocation	Impact
Process needs resources A(1s), B(1s), C(1s)	Holds each ~1s	Holds all 3s each	3x resource hold time
10 processes, 5 resources	Fine-grained contention	Coarse-grained blocking	Reduced parallelism
Unpredictable requirements	Request as needed	Must over-estimate or abort	Waste or retry cost
Memory allocation	Malloc per object	Pre-allocate maximum	Higher peak memory
Database transaction	Lock rows on access	Lock all tables upfront	More conservative locking

The Prediction Problem in Detail:

Consider a web application handling user requests:

function handleRequest(userId) {
    user = database.getUser(userId);      // Need lock on users table
    
    if (user.isPremium) {
        features = database.getPremiumFeatures();  // Need lock on features table
        if (features.includes('analytics')) {
            stats = database.getAnalytics(userId);  // Need lock on analytics table
        }
    }
    
    return response;
}

The resources needed depend on runtime data (is user premium? which features?). With total allocation, we would need to:

Always acquire locks on users, features, AND analytics tables
Even for non-premium users who only need the users table
This massively increases contention and reduces throughput

Mitigation Strategies

Despite the challenges, several techniques can make hold-and-wait prevention more practical:

Practical Mitigation Techniques

•Resource classes — Group resources into classes. Processes must acquire all resources within a class before proceeding to the next class. Provides partial ordering benefits while allowing incremental acquisition across classes.
•Optimistic locking — Don't acquire resources upfront, but validate at commit time. If conflicts occurred, abort and retry. Effective when conflicts are rare.
•Timeout-based release — If a process has held resources for too long while waiting for more, automatically release all and retry. Converts deadlock to livelock, then to success.
•Hybrid approaches — Use total allocation for critical resources with known requirements, incremental acquisition for others. Accept some deadlock risk in the incremental portion.
•Batching — Collect multiple small requests into larger transactions that know full requirements. Trade latency for predictability.
•Speculative execution — Execute speculatively with minimal locking, then validate. Works well when speculation is usually correct.

timeout_release.c
C
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
 */

Hold-and-Wait Prevention in Real Systems

Let's examine how different real-world systems handle the hold-and-wait condition:

Real-World Approaches to Hold-and-Wait
System	Approach	Details
POSIX pthread_mutex	Not prevented	Applications must handle deadlock; OS provides no protection
Java synchronized	Not prevented	JVM can detect deadlock but doesn't prevent it
PostgreSQL	Detection + Timeout	Detects cycles in wait graph; `lock_timeout` aborts waiting transactions
MySQL InnoDB	Detection	Detects deadlock and rolls back one transaction
Linux kernel	Lockdep (detection)	Debug tool detects potential deadlocks via lock ordering analysis
Windows Driver Verifier	Detection	Detects incorrect lock usage in kernel drivers
Rust borrow checker	Prevention via types	Type system prevents holding references while mutating (compile-time)
STM (Software Transactional Memory)	Release on conflict	Optimistic execution with rollback on conflicts

Prevention is Rare in Practice

Case Study: The Dining Philosophers

The dining philosophers problem illustrates hold-and-wait prevention beautifully. Each philosopher needs two forks to eat:

With hold-and-wait (deadlock possible):

Each philosopher picks up left fork
Each philosopher waits for right fork
Deadlock: everyone holds one fork, waits for another

With hold-and-wait prevention (no deadlock):

Philosopher requests BOTH forks atomically
If both available: take both, eat, release both
If not: take neither, wait until both are free

This is the total allocation protocol applied to dining philosophers. It eliminates deadlock but reduces parallelism—adjacent philosophers can never eat simultaneously even when it would be safe.

Summary: Breaking Hold and Wait

We've thoroughly examined how to prevent the hold-and-wait condition for deadlock prevention. Let's consolidate our understanding:

Key Takeaways

•Two main protocols exist — Total allocation (request all upfront) and release-before-request (give up everything before asking for more). Both ensure a process never holds resources while waiting.
•Total allocation is simpler but restrictive — Requires knowing all requirements upfront, which is often impossible for dynamic workloads.
•Release-before-request is flexible but complex — Allows incremental resource discovery but requires state management and may cause repeated work.
•Conservative 2PL applies to databases — Acquiring all locks before starting transaction execution prevents hold-and-wait in database systems.
•Significant tradeoffs exist — Reduced utilization, potential starvation, longer waiting times, and memory overhead are common costs.
•Most real systems don't use strict prevention — The overhead is typically too high; detection, avoidance, or careful design are more common.
•Mitigation strategies help — Timeouts, optimistic locking, and resource classes can make prevention more practical.

What's next:

Page Complete