Operating SystemsBanker's Algorithm

Banker's Algorithm: Deadlock Avoidance

LevelIntermediate

Duration75 mins

TopicBanker's Algorithm

3 / 5

Resource Request Algorithm

The Gatekeeper of Resource Allocation

We can now determine whether any given state is safe. But that's only half the story. When a process actually requests resources at runtime, the operating system faces a decision: grant the request, or make the process wait?

The Resource Request Algorithm is the gatekeeper that makes this decision. It doesn't just check if resources are available—it looks ahead to determine whether granting the request would move the system from a safe state to an unsafe one. If so, the request is denied or deferred, even if resources are technically available.

This algorithm transforms the theoretical concept of safe states into practical, real-time resource management. It's the mechanism that actually prevents deadlock, not just detects it.

What You Will Learn

By the end of this page, you will understand how the Resource Request Algorithm works, how it integrates with the Safety Algorithm, the complete request handling flow, implementation details, and the relationship between process requests and system safety.

Representing Resource Requests

Before diving into the algorithm, let's establish how resource requests are represented.

Request Vector:

When process Pᵢ requests resources, it specifies a request vector Request[i] where:

Request[i][j] = number of instances of resource type Rⱼ that Pᵢ is requesting

Example:

If Request[2] = (1, 0, 2) for a system with resource types A, B, C
Process P₂ is requesting: 1 instance of A, 0 instances of B, 2 instances of C

Constraints on Valid Requests:

Non-negative: Request[i][j] ≥ 0 for all j
Within Need: Request[i] ≤ Need[i] — a process cannot request more than it declared it might still need
Within Total: Request[i] ≤ Max[i] (implied by constraint 2)

Exceeding Declared Need

If a process requests more than its remaining Need, the request is erroneous. This is a violation of the system contract—the process declared a maximum claim and has already received some allocation. The remaining Need represents the upper bound on what it can still request. Exceeding this is a bug or malicious behavior, and the system may terminate the offending process.

Request Types:

In practice, processes may make different types of requests:

Type	Description	Example
Single Resource	Request one instance of one type	`(0, 0, 1)`
Multiple Same Type	Request several of one type	`(3, 0, 0)`
Multiple Types	Request instances of different types	`(1, 2, 1)`
Blocking	Wait until request can be granted	Standard behavior
Non-blocking	Return immediately if not available	Optional variation

The Resource Request Algorithm handles all these uniformly—it processes the request vector as a whole.

The Resource Request Algorithm

The Resource Request Algorithm is executed whenever a process Pᵢ makes a resource request. It decides whether to grant the request immediately, deny it, or make the process wait.

Algorithm Steps:

resource_request_algorithm.pseudo
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
RESOURCE_REQUEST(i, Request):
    // Step 1: Validate the request
    IF Request[i] > Need[i] THEN:
        ERROR: "Process exceeded its maximum claim"
        // Terminate process or raise exception
        RETURN DENIED
    
    // Step 2: Check if resources are currently available
    IF Request[i] > Available THEN:
        // Resources not available - process must wait
        BLOCK process Pᵢ
        RETURN BLOCKED
    
    // Step 3: Pretend to allocate (create hypothetical state)
    // Save current state for potential rollback
    Available_saved ← Available
    Allocation_saved[i] ← Allocation[i]
    Need_saved[i] ← Need[i]
    
    // Tentatively allocate resources
    Available ← Available - Request[i]
    Allocation[i] ← Allocation[i] + Request[i]
    Need[i] ← Need[i] - Request[i]
    
    // Step 4: Check if resulting state is safe
    IF SAFETY_ALGORITHM() = SAFE THEN:
        // Allocation is safe - commit it
        RETURN GRANTED
    ELSE:
        // Allocation would create unsafe state - rollback
        Available ← Available_saved
        Allocation[i] ← Allocation_saved[i]
        Need[i] ← Need_saved[i]
        
        BLOCK process Pᵢ (wait for resources)
        RETURN BLOCKED

Detailed Explanation:

Step 1 - Validation: First, verify that the request doesn't exceed what the process claimed it might need. This is a sanity check—violating this indicates a bug or protocol violation.

Step 2 - Availability Check: Even if safe, we can't grant what we don't have. If requested resources exceed what's available, the process must wait regardless of safety considerations.

Step 3 - Hypothetical Allocation: This is the clever part. We pretend to grant the request by temporarily modifying the system state. We then test whether this new state is safe.

Step 4 - Safety Check: Run the Safety Algorithm on the modified state. If safe, the allocation is committed (it's already applied). If unsafe, we rollback to the saved state and block the process.

Key Insight: The algorithm is conservative—it only grants requests that keep the system in a safe state. This means some requests that wouldn't actually cause deadlock are still denied. The price of safety is reduced concurrency.

Complete Implementation

Here's a complete C implementation of the Resource Request Algorithm, building on our Safety Algorithm from the previous page.

resource_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
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
#define MAX_PROCESSES 10
#define MAX_RESOURCES 10
 
// System state
int n, m;  // processes, resource types
int available[MAX_RESOURCES];
int max_claim[MAX_PROCESSES][MAX_RESOURCES];
int allocation[MAX_PROCESSES][MAX_RESOURCES];
int need[MAX_PROCESSES][MAX_RESOURCES];
 
// Forward declaration
bool safety_algorithm(int safe_sequence[]);
 
// Vector comparison: a <= b?
bool vector_le(int a[], int b[]) {
    for (int j = 0; j < m; j++) {
        if (a[j] > b[j]) return false;
    }
    return true;
}
 
// Vector subtraction: a = a - b
void vector_sub(int a[], int b[]) {
    for (int j = 0; j < m; j++) {
        a[j] -= b[j];
    }
}
 
// Vector addition: a = a + b
void vector_add(int a[], int b[]) {
    for (int j = 0; j < m; j++) {
        a[j] += b[j];
    }
}
 
// Copy vector: dest = src
void vector_copy(int dest[], int src[]) {
    for (int j = 0; j < m; j++) {
        dest[j] = src[j];
    }
}
 
/**
 * Resource Request Algorithm
 * 
 * Processes a resource request from process i.
 * Returns: 0 = GRANTED, 1 = BLOCKED (unsafe), -1 = ERROR
 */
int request_resources(int i, int request[]) {
    printf("\nProcess P%d requests: [", i);
    for (int j = 0; j < m; j++) {
        printf("%d%s", request[j], j < m-1 ? ", " : "");
    }
    printf("]\n");
    
    // Step 1: Validate request against need
    if (!vector_le(request, need[i])) {
        printf("ERROR: Request exceeds declared maximum need!\n");
        return -1;  // Error condition
    }
    
    // Step 2: Check if resources are available
    if (!vector_le(request, available)) {
        printf("Resources not available. Process must wait.\n");
        return 1;  // Blocked - not enough resources
    }
    
    // Step 3: Tentatively allocate (save state first)
    int available_saved[MAX_RESOURCES];
    int allocation_saved[MAX_RESOURCES];
    int need_saved[MAX_RESOURCES];
    
    vector_copy(available_saved, available);
    vector_copy(allocation_saved, allocation[i]);
    vector_copy(need_saved, need[i]);
    
    // Apply tentative allocation
    vector_sub(available, request);
    vector_add(allocation[i], request);
    vector_sub(need[i], request);
    
    printf("Tentative state - Available: [");
    for (int j = 0; j < m; j++) {
        printf("%d%s", available[j], j < m-1 ? ", " : "");
    }
    printf("]\n");
    
    // Step 4: Check safety
    int safe_sequence[MAX_PROCESSES];
    if (safety_algorithm(safe_sequence)) {
        // Safe - commit allocation
        printf("Request GRANTED. Safe sequence exists: <");
        for (int k = 0; k < n; k++) {
            printf("P%d%s", safe_sequence[k], k < n-1 ? ", " : "");
        }
        printf(">\n");
        return 0;  // Granted
    } else {
        // Unsafe - rollback
        printf("Request would lead to UNSAFE state. Rolling back.\n");
        
        vector_copy(available, available_saved);
        vector_copy(allocation[i], allocation_saved);
        vector_copy(need[i], need_saved);
        
        printf("Process must wait for resources.\n");
        return 1;  // Blocked - would be unsafe
    }
}
 
/**
 * Safety Algorithm implementation
 */
bool safety_algorithm(int safe_sequence[]) {
    int work[MAX_RESOURCES];
    bool finish[MAX_PROCESSES] = {false};
    int seq_index = 0;
    
    vector_copy(work, available);
    
    bool found;
    do {
        found = false;
        for (int i = 0; i < n; i++) {
            if (!finish[i] && vector_le(need[i], work)) {
                vector_add(work, allocation[i]);
                finish[i] = true;
                safe_sequence[seq_index++] = i;
                found = true;
            }
        }
    } while (found);
    
    for (int i = 0; i < n; i++) {
        if (!finish[i]) return false;
    }
    return true;
}
 
// Print current system state
void print_state() {
    printf("\n=== Current System State ===\n");
    printf("Available: [");
    for (int j = 0; j < m; j++) {
        printf("%d%s", available[j], j < m-1 ? ", " : "");
    }
    printf("]\n\n");
    
    printf("Process | Allocation | Max    | Need\n");
    printf("--------|------------|--------|--------\n");
    for (int i = 0; i < n; i++) {
        printf("P%d      | ", i);
        for (int j = 0; j < m; j++) printf("%d ", allocation[i][j]);
        printf("      | ");
        for (int j = 0; j < m; j++) printf("%d ", max_claim[i][j]);
        printf("  | ");
        for (int j = 0; j < m; j++) printf("%d ", need[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
int main() {
    // Initialize system
    n = 5;  m = 3;
    
    int init_available[] = {3, 3, 2};
    vector_copy(available, init_available);
    
    int init_alloc[5][3] = {
        {0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}
    };
    int init_max[5][3] = {
        {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}
    };
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            allocation[i][j] = init_alloc[i][j];
            max_claim[i][j] = init_max[i][j];
            need[i][j] = max_claim[i][j] - allocation[i][j];
        }
    }
    
    print_state();
    
    // Test requests
    printf("\n=== Processing Requests ===\n");
    
    // Request 1: P1 requests (1, 0, 2)
    int req1[] = {1, 0, 2};
    request_resources(1, req1);
    print_state();
    
    // Request 2: P4 requests (3, 3, 0) - should be denied (unsafe)
    int req2[] = {3, 3, 0};
    request_resources(4, req2);
    print_state();
    
    // Request 3: P0 requests (0, 2, 0)
    int req3[] = {0, 2, 0};
    request_resources(0, req3);
    print_state();
    
    return 0;
}

Algorithm Flow

Let's visualize the complete flow of the Resource Request Algorithm to understand all decision paths.

Converting Mermaid diagram...

Three Possible Outcomes:

GRANTED (Green path): Request is valid, resources are available, and the resulting state is safe. The allocation is committed.
WAIT (Yellow paths): Either resources aren't currently available, OR granting would make the state unsafe. Either way, the process blocks until conditions change.
ERROR (Red path): Request exceeds the process's declared maximum need. This is a protocol violation—either a bug or malicious behavior.

The 'Pretend and Check' Pattern

The algorithm's core insight is 'pretend and check': tentatively apply the allocation, check if the result is acceptable, then either commit or rollback. This pattern appears throughout OS design—it's safer to trial an operation in a reversible way than to commit and then discover problems.

Worked Example: Request Processing

Let's trace through actual requests on our example system.

Initial State:

Available = (3, 3, 2)
System is in a safe state (we verified earlier)

Initial System State
Process	Allocation	Max	Need
P₀	(0, 1, 0)	(7, 5, 3)	(7, 4, 3)
P₁	(2, 0, 0)	(3, 2, 2)	(1, 2, 2)
P₂	(3, 0, 2)	(9, 0, 2)	(6, 0, 0)
P₃	(2, 1, 1)	(2, 2, 2)	(0, 1, 1)
P₄	(0, 0, 2)	(4, 3, 3)	(4, 3, 1)

Request 1: P₁ requests (1, 0, 2)

Step 1 - Validate: Is (1, 0, 2) ≤ Need[1] = (1, 2, 2)?

1 ≤ 1 ✓, 0 ≤ 2 ✓, 2 ≤ 2 ✓ → Valid request

Step 2 - Availability: Is (1, 0, 2) ≤ Available = (3, 3, 2)?

1 ≤ 3 ✓, 0 ≤ 3 ✓, 2 ≤ 2 ✓ → Resources available

Step 3 - Tentative Allocation:

Available = (3,3,2) - (1,0,2) = (2, 3, 0)
Allocation[1] = (2,0,0) + (1,0,2) = (3, 0, 2)
Need[1] = (1,2,2) - (1,0,2) = (0, 2, 0)

Step 4 - Safety Check: Run Safety Algorithm with new state...

Can P₃ complete? Need[3]=(0,1,1) ≤ (2,3,0)? 1 > 0 ✗
Can P₁ complete? Need[1]=(0,2,0) ≤ (2,3,0)? 0≤2, 2≤3, 0≤0 ✓
Work = (2,3,0) + (3,0,2) = (5, 3, 2)
Continue... all processes can eventually complete

Result: GRANTED ✓

Updated State after Request 1:

State After P₁'s Request Granted
Process	Allocation	Need	Notes
P₀	(0, 1, 0)	(7, 4, 3)	Unchanged
P₁	(3, 0, 2)	(0, 2, 0)	Updated
P₂	(3, 0, 2)	(6, 0, 0)	Unchanged
P₃	(2, 1, 1)	(0, 1, 1)	Unchanged
P₄	(0, 0, 2)	(4, 3, 1)	Unchanged

Available = (2, 3, 0)

Request 2: P₄ requests (3, 3, 0)

Step 1 - Validate: Is (3, 3, 0) ≤ Need[4] = (4, 3, 1)?

3 ≤ 4 ✓, 3 ≤ 3 ✓, 0 ≤ 1 ✓ → Valid request

Step 2 - Availability: Is (3, 3, 0) ≤ Available = (2, 3, 0)?

3 > 2 ✗ → Resources not available

Result: WAIT (P₄ blocked waiting for resources)

Request 3: P₀ requests (0, 2, 0)

Step 1 - Validate: Is (0, 2, 0) ≤ Need[0] = (7, 4, 3)? ✓

Step 2 - Availability: Is (0, 2, 0) ≤ Available = (2, 3, 0)? ✓

Step 3 - Tentative Allocation:

Available = (2,3,0) - (0,2,0) = (2, 1, 0)
Allocation[0] = (0,1,0) + (0,2,0) = (0, 3, 0)
Need[0] = (7,4,3) - (0,2,0) = (7, 2, 3)

Step 4 - Safety Check:

With Available = (2, 1, 0), can any process complete?
P₁: Need=(0,2,0). 2>1 ✗
P₃: Need=(0,1,1). 1>0 ✗
No process can complete! State is UNSAFE

Result: BLOCKED - Request denied, state rolled back

Denied Despite Available Resources

P₀'s request for (0, 2, 0) was denied even though (0, 2, 0) ≤ Available = (2, 3, 0). This illustrates the conservative nature of deadlock avoidance: the request would leave the system in an unsafe state, so it's denied regardless of immediate availability.

Handling Process Completion

The Resource Request Algorithm handles requests, but we also need to handle what happens when a process completes and releases its resources.

Release Algorithm:

release_resources.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
RELEASE_RESOURCES(i):
    // Process i is terminating and releasing all resources
    
    // Return all allocated resources to available pool
    Available ← Available + Allocation[i]
    
    // Clear process's allocation
    Allocation[i] ← [0, 0, ..., 0]
    
    // Process no longer needs any resources
    Need[i] ← [0, 0, ..., 0]
    
    // Wake up any processes waiting for these resource types
    FOR each blocked process Pⱼ:
        IF Pⱼ was waiting for any of the released resources:
            RE-EVALUATE Pⱼ's pending request
            // Run Resource Request Algorithm again

Key Points About Resource Release:

Immediate Addition: Released resources immediately return to the available pool—no safety check needed for release.
Wake Blocked Processes: When resources are released, blocked processes should be re-evaluated. A request that was unsafe before might now be safe.
Order of Wake-up: The OS must decide which blocked process to check first. This is a scheduling decision that can affect fairness and starvation.
Batch Processing: If multiple processes are waiting, it might be more efficient to run one safety check for the best candidate rather than trying each in sequence.

Release Never Causes Unsafety

Releasing resources can only improve safety—it increases Available without changing any process's Need. A safe state remains safe after release, and an unsafe state might become safe. This is why we don't run the Safety Algorithm on release—we only check on allocation.

Request Queueing and Fairness

When multiple processes have pending requests, the system must decide which to evaluate first. This introduces fairness considerations.

Starvation Risk:

The Banker's Algorithm can cause starvation:

A process with large resource needs might be perpetually denied
Smaller requests from other processes keep getting granted
The large request is never safe to grant

Mitigation Strategies:

Fairness Mechanisms

•FIFO Ordering: Process requests in the order received. Simple but may leave resources idle when earlier requests can't be granted but later ones could.
•Aging: Increase priority of requests that have been waiting longer. Eventually, even large requests get high enough priority to be tried first.
•Bounded Waiting: Guarantee that each request is granted within some maximum number of other grants. Limits how many times a request can be 'passed over'.
•Priority-Based: Higher-priority processes get preference. May cause starvation of low-priority processes but ensures important work proceeds.
•Hybrid: Use FIFO with priority boosting for long-waiting requests, trying to balance throughput with fairness.

Fairness Strategy Comparison
Strategy	Throughput	Fairness	Starvation Risk	Complexity
FIFO	Lower	High	Low	O(1)
Smallest First	Higher	Low	High	O(n)
With Aging	Medium	High	Very Low	O(n)
Priority-Based	Variable	Low	High	O(log n)

No Perfect Solution

There's an inherent tension between throughput (granting as many requests as possible) and fairness (giving everyone a turn). High-throughput strategies may starve large requests, while strict fairness may leave resources idle. Real systems choose based on workload characteristics.

Summary: Resource Request Algorithm

The Resource Request Algorithm is the operational mechanism for deadlock avoidance. Let's consolidate:

Key Takeaways

•Four-Step Process: Validate request, check availability, tentatively allocate, verify safety—then grant or deny.
•Pretend and Check: The algorithm tentatively applies allocations and checks safety before committing, rolling back if unsafe.
•Conservative Denial: Requests may be denied even when resources are available, if granting would create an unsafe state.
•Integration with Safety Algorithm: The Resource Request Algorithm calls the Safety Algorithm as a subroutine for each request decision.
•Release Handling: Releasing resources is simpler—just return to pool and re-evaluate blocked processes.
•Fairness vs Throughput: The system must balance granting many small requests (throughput) against starvation of large requests (fairness).

What's Next:

We've been working with examples that have single instances of each resource type. Real systems often have multiple instances—10 printers, 4 CPUs, 8GB of memory regions. The next page extends the Banker's Algorithm to handle multiple instances of each resource type, which requires careful matrix arithmetic.

Page Complete

You now understand the Resource Request Algorithm—the operational component that makes deadlock avoidance work in practice. You can trace through request processing, understand grant/deny decisions, and see how this integrates with the Safety Algorithm.

3 / 5

Loading learning content...

Operating SystemsBanker's Algorithm

Banker's Algorithm: Deadlock Avoidance

LevelIntermediate

Duration75 mins

TopicBanker's Algorithm

3 / 5

Resource Request Algorithm

The Gatekeeper of Resource Allocation

This algorithm transforms the theoretical concept of safe states into practical, real-time resource management. It's the mechanism that actually prevents deadlock, not just detects it.

What You Will Learn

Representing Resource Requests

Before diving into the algorithm, let's establish how resource requests are represented.

Request Vector:

When process Pᵢ requests resources, it specifies a request vector Request[i] where:

Request[i][j] = number of instances of resource type Rⱼ that Pᵢ is requesting

Example:

If Request[2] = (1, 0, 2) for a system with resource types A, B, C
Process P₂ is requesting: 1 instance of A, 0 instances of B, 2 instances of C

Constraints on Valid Requests:

Non-negative: Request[i][j] ≥ 0 for all j
Within Need: Request[i] ≤ Need[i] — a process cannot request more than it declared it might still need
Within Total: Request[i] ≤ Max[i] (implied by constraint 2)

Exceeding Declared Need

Request Types:

In practice, processes may make different types of requests:

Type	Description	Example
Single Resource	Request one instance of one type	`(0, 0, 1)`
Multiple Same Type	Request several of one type	`(3, 0, 0)`
Multiple Types	Request instances of different types	`(1, 2, 1)`
Blocking	Wait until request can be granted	Standard behavior
Non-blocking	Return immediately if not available	Optional variation

The Resource Request Algorithm handles all these uniformly—it processes the request vector as a whole.

The Resource Request Algorithm

The Resource Request Algorithm is executed whenever a process Pᵢ makes a resource request. It decides whether to grant the request immediately, deny it, or make the process wait.

Algorithm Steps:

resource_request_algorithm.pseudo
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
RESOURCE_REQUEST(i, Request):
    // Step 1: Validate the request
    IF Request[i] > Need[i] THEN:
        ERROR: "Process exceeded its maximum claim"
        // Terminate process or raise exception
        RETURN DENIED
    
    // Step 2: Check if resources are currently available
    IF Request[i] > Available THEN:
        // Resources not available - process must wait
        BLOCK process Pᵢ
        RETURN BLOCKED
    
    // Step 3: Pretend to allocate (create hypothetical state)
    // Save current state for potential rollback
    Available_saved ← Available
    Allocation_saved[i] ← Allocation[i]
    Need_saved[i] ← Need[i]
    
    // Tentatively allocate resources
    Available ← Available - Request[i]
    Allocation[i] ← Allocation[i] + Request[i]
    Need[i] ← Need[i] - Request[i]
    
    // Step 4: Check if resulting state is safe
    IF SAFETY_ALGORITHM() = SAFE THEN:
        // Allocation is safe - commit it
        RETURN GRANTED
    ELSE:
        // Allocation would create unsafe state - rollback
        Available ← Available_saved
        Allocation[i] ← Allocation_saved[i]
        Need[i] ← Need_saved[i]
        
        BLOCK process Pᵢ (wait for resources)
        RETURN BLOCKED

Detailed Explanation:

Step 1 - Validation: First, verify that the request doesn't exceed what the process claimed it might need. This is a sanity check—violating this indicates a bug or protocol violation.

Step 2 - Availability Check: Even if safe, we can't grant what we don't have. If requested resources exceed what's available, the process must wait regardless of safety considerations.

Step 3 - Hypothetical Allocation: This is the clever part. We pretend to grant the request by temporarily modifying the system state. We then test whether this new state is safe.

Complete Implementation

Here's a complete C implementation of the Resource Request Algorithm, building on our Safety Algorithm from the previous page.

resource_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
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
#define MAX_PROCESSES 10
#define MAX_RESOURCES 10
 
// System state
int n, m;  // processes, resource types
int available[MAX_RESOURCES];
int max_claim[MAX_PROCESSES][MAX_RESOURCES];
int allocation[MAX_PROCESSES][MAX_RESOURCES];
int need[MAX_PROCESSES][MAX_RESOURCES];
 
// Forward declaration
bool safety_algorithm(int safe_sequence[]);
 
// Vector comparison: a <= b?
bool vector_le(int a[], int b[]) {
    for (int j = 0; j < m; j++) {
        if (a[j] > b[j]) return false;
    }
    return true;
}
 
// Vector subtraction: a = a - b
void vector_sub(int a[], int b[]) {
    for (int j = 0; j < m; j++) {
        a[j] -= b[j];
    }
}
 
// Vector addition: a = a + b
void vector_add(int a[], int b[]) {
    for (int j = 0; j < m; j++) {
        a[j] += b[j];
    }
}
 
// Copy vector: dest = src
void vector_copy(int dest[], int src[]) {
    for (int j = 0; j < m; j++) {
        dest[j] = src[j];
    }
}
 
/**
 * Resource Request Algorithm
 * 
 * Processes a resource request from process i.
 * Returns: 0 = GRANTED, 1 = BLOCKED (unsafe), -1 = ERROR
 */
int request_resources(int i, int request[]) {
    printf("\nProcess P%d requests: [", i);
    for (int j = 0; j < m; j++) {
        printf("%d%s", request[j], j < m-1 ? ", " : "");
    }
    printf("]\n");
    
    // Step 1: Validate request against need
    if (!vector_le(request, need[i])) {
        printf("ERROR: Request exceeds declared maximum need!\n");
        return -1;  // Error condition
    }
    
    // Step 2: Check if resources are available
    if (!vector_le(request, available)) {
        printf("Resources not available. Process must wait.\n");
        return 1;  // Blocked - not enough resources
    }
    
    // Step 3: Tentatively allocate (save state first)
    int available_saved[MAX_RESOURCES];
    int allocation_saved[MAX_RESOURCES];
    int need_saved[MAX_RESOURCES];
    
    vector_copy(available_saved, available);
    vector_copy(allocation_saved, allocation[i]);
    vector_copy(need_saved, need[i]);
    
    // Apply tentative allocation
    vector_sub(available, request);
    vector_add(allocation[i], request);
    vector_sub(need[i], request);
    
    printf("Tentative state - Available: [");
    for (int j = 0; j < m; j++) {
        printf("%d%s", available[j], j < m-1 ? ", " : "");
    }
    printf("]\n");
    
    // Step 4: Check safety
    int safe_sequence[MAX_PROCESSES];
    if (safety_algorithm(safe_sequence)) {
        // Safe - commit allocation
        printf("Request GRANTED. Safe sequence exists: <");
        for (int k = 0; k < n; k++) {
            printf("P%d%s", safe_sequence[k], k < n-1 ? ", " : "");
        }
        printf(">\n");
        return 0;  // Granted
    } else {
        // Unsafe - rollback
        printf("Request would lead to UNSAFE state. Rolling back.\n");
        
        vector_copy(available, available_saved);
        vector_copy(allocation[i], allocation_saved);
        vector_copy(need[i], need_saved);
        
        printf("Process must wait for resources.\n");
        return 1;  // Blocked - would be unsafe
    }
}
 
/**
 * Safety Algorithm implementation
 */
bool safety_algorithm(int safe_sequence[]) {
    int work[MAX_RESOURCES];
    bool finish[MAX_PROCESSES] = {false};
    int seq_index = 0;
    
    vector_copy(work, available);
    
    bool found;
    do {
        found = false;
        for (int i = 0; i < n; i++) {
            if (!finish[i] && vector_le(need[i], work)) {
                vector_add(work, allocation[i]);
                finish[i] = true;
                safe_sequence[seq_index++] = i;
                found = true;
            }
        }
    } while (found);
    
    for (int i = 0; i < n; i++) {
        if (!finish[i]) return false;
    }
    return true;
}
 
// Print current system state
void print_state() {
    printf("\n=== Current System State ===\n");
    printf("Available: [");
    for (int j = 0; j < m; j++) {
        printf("%d%s", available[j], j < m-1 ? ", " : "");
    }
    printf("]\n\n");
    
    printf("Process | Allocation | Max    | Need\n");
    printf("--------|------------|--------|--------\n");
    for (int i = 0; i < n; i++) {
        printf("P%d      | ", i);
        for (int j = 0; j < m; j++) printf("%d ", allocation[i][j]);
        printf("      | ");
        for (int j = 0; j < m; j++) printf("%d ", max_claim[i][j]);
        printf("  | ");
        for (int j = 0; j < m; j++) printf("%d ", need[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
int main() {
    // Initialize system
    n = 5;  m = 3;
    
    int init_available[] = {3, 3, 2};
    vector_copy(available, init_available);
    
    int init_alloc[5][3] = {
        {0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}
    };
    int init_max[5][3] = {
        {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}
    };
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            allocation[i][j] = init_alloc[i][j];
            max_claim[i][j] = init_max[i][j];
            need[i][j] = max_claim[i][j] - allocation[i][j];
        }
    }
    
    print_state();
    
    // Test requests
    printf("\n=== Processing Requests ===\n");
    
    // Request 1: P1 requests (1, 0, 2)
    int req1[] = {1, 0, 2};
    request_resources(1, req1);
    print_state();
    
    // Request 2: P4 requests (3, 3, 0) - should be denied (unsafe)
    int req2[] = {3, 3, 0};
    request_resources(4, req2);
    print_state();
    
    // Request 3: P0 requests (0, 2, 0)
    int req3[] = {0, 2, 0};
    request_resources(0, req3);
    print_state();
    
    return 0;
}

Algorithm Flow

Let's visualize the complete flow of the Resource Request Algorithm to understand all decision paths.

Converting Mermaid diagram...

Three Possible Outcomes:

GRANTED (Green path): Request is valid, resources are available, and the resulting state is safe. The allocation is committed.
WAIT (Yellow paths): Either resources aren't currently available, OR granting would make the state unsafe. Either way, the process blocks until conditions change.
ERROR (Red path): Request exceeds the process's declared maximum need. This is a protocol violation—either a bug or malicious behavior.

The 'Pretend and Check' Pattern

Worked Example: Request Processing

Let's trace through actual requests on our example system.

Initial State:

Available = (3, 3, 2)
System is in a safe state (we verified earlier)

Initial System State
Process	Allocation	Max	Need
P₀	(0, 1, 0)	(7, 5, 3)	(7, 4, 3)
P₁	(2, 0, 0)	(3, 2, 2)	(1, 2, 2)
P₂	(3, 0, 2)	(9, 0, 2)	(6, 0, 0)
P₃	(2, 1, 1)	(2, 2, 2)	(0, 1, 1)
P₄	(0, 0, 2)	(4, 3, 3)	(4, 3, 1)

Request 1: P₁ requests (1, 0, 2)

Step 1 - Validate: Is (1, 0, 2) ≤ Need[1] = (1, 2, 2)?

1 ≤ 1 ✓, 0 ≤ 2 ✓, 2 ≤ 2 ✓ → Valid request

Step 2 - Availability: Is (1, 0, 2) ≤ Available = (3, 3, 2)?

1 ≤ 3 ✓, 0 ≤ 3 ✓, 2 ≤ 2 ✓ → Resources available

Step 3 - Tentative Allocation:

Available = (3,3,2) - (1,0,2) = (2, 3, 0)
Allocation[1] = (2,0,0) + (1,0,2) = (3, 0, 2)
Need[1] = (1,2,2) - (1,0,2) = (0, 2, 0)

Step 4 - Safety Check: Run Safety Algorithm with new state...

Can P₃ complete? Need[3]=(0,1,1) ≤ (2,3,0)? 1 > 0 ✗
Can P₁ complete? Need[1]=(0,2,0) ≤ (2,3,0)? 0≤2, 2≤3, 0≤0 ✓
Work = (2,3,0) + (3,0,2) = (5, 3, 2)
Continue... all processes can eventually complete

Result: GRANTED ✓

Updated State after Request 1:

State After P₁'s Request Granted
Process	Allocation	Need	Notes
P₀	(0, 1, 0)	(7, 4, 3)	Unchanged
P₁	(3, 0, 2)	(0, 2, 0)	Updated
P₂	(3, 0, 2)	(6, 0, 0)	Unchanged
P₃	(2, 1, 1)	(0, 1, 1)	Unchanged
P₄	(0, 0, 2)	(4, 3, 1)	Unchanged

Available = (2, 3, 0)

Request 2: P₄ requests (3, 3, 0)

Step 1 - Validate: Is (3, 3, 0) ≤ Need[4] = (4, 3, 1)?

3 ≤ 4 ✓, 3 ≤ 3 ✓, 0 ≤ 1 ✓ → Valid request

Step 2 - Availability: Is (3, 3, 0) ≤ Available = (2, 3, 0)?

3 > 2 ✗ → Resources not available

Result: WAIT (P₄ blocked waiting for resources)

Request 3: P₀ requests (0, 2, 0)

Step 1 - Validate: Is (0, 2, 0) ≤ Need[0] = (7, 4, 3)? ✓

Step 2 - Availability: Is (0, 2, 0) ≤ Available = (2, 3, 0)? ✓

Step 3 - Tentative Allocation:

Available = (2,3,0) - (0,2,0) = (2, 1, 0)
Allocation[0] = (0,1,0) + (0,2,0) = (0, 3, 0)
Need[0] = (7,4,3) - (0,2,0) = (7, 2, 3)

Step 4 - Safety Check:

With Available = (2, 1, 0), can any process complete?
P₁: Need=(0,2,0). 2>1 ✗
P₃: Need=(0,1,1). 1>0 ✗
No process can complete! State is UNSAFE

Result: BLOCKED - Request denied, state rolled back

Denied Despite Available Resources

Handling Process Completion

The Resource Request Algorithm handles requests, but we also need to handle what happens when a process completes and releases its resources.

Release Algorithm:

release_resources.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
RELEASE_RESOURCES(i):
    // Process i is terminating and releasing all resources
    
    // Return all allocated resources to available pool
    Available ← Available + Allocation[i]
    
    // Clear process's allocation
    Allocation[i] ← [0, 0, ..., 0]
    
    // Process no longer needs any resources
    Need[i] ← [0, 0, ..., 0]
    
    // Wake up any processes waiting for these resource types
    FOR each blocked process Pⱼ:
        IF Pⱼ was waiting for any of the released resources:
            RE-EVALUATE Pⱼ's pending request
            // Run Resource Request Algorithm again

Key Points About Resource Release:

Immediate Addition: Released resources immediately return to the available pool—no safety check needed for release.
Wake Blocked Processes: When resources are released, blocked processes should be re-evaluated. A request that was unsafe before might now be safe.
Order of Wake-up: The OS must decide which blocked process to check first. This is a scheduling decision that can affect fairness and starvation.
Batch Processing: If multiple processes are waiting, it might be more efficient to run one safety check for the best candidate rather than trying each in sequence.

Release Never Causes Unsafety

Request Queueing and Fairness

When multiple processes have pending requests, the system must decide which to evaluate first. This introduces fairness considerations.

Starvation Risk:

The Banker's Algorithm can cause starvation:

A process with large resource needs might be perpetually denied
Smaller requests from other processes keep getting granted
The large request is never safe to grant

Mitigation Strategies:

Fairness Mechanisms

•FIFO Ordering: Process requests in the order received. Simple but may leave resources idle when earlier requests can't be granted but later ones could.
•Aging: Increase priority of requests that have been waiting longer. Eventually, even large requests get high enough priority to be tried first.
•Bounded Waiting: Guarantee that each request is granted within some maximum number of other grants. Limits how many times a request can be 'passed over'.
•Priority-Based: Higher-priority processes get preference. May cause starvation of low-priority processes but ensures important work proceeds.
•Hybrid: Use FIFO with priority boosting for long-waiting requests, trying to balance throughput with fairness.

Fairness Strategy Comparison
Strategy	Throughput	Fairness	Starvation Risk	Complexity
FIFO	Lower	High	Low	O(1)
Smallest First	Higher	Low	High	O(n)
With Aging	Medium	High	Very Low	O(n)
Priority-Based	Variable	Low	High	O(log n)

No Perfect Solution

Summary: Resource Request Algorithm

The Resource Request Algorithm is the operational mechanism for deadlock avoidance. Let's consolidate:

Key Takeaways

•Four-Step Process: Validate request, check availability, tentatively allocate, verify safety—then grant or deny.
•Pretend and Check: The algorithm tentatively applies allocations and checks safety before committing, rolling back if unsafe.
•Conservative Denial: Requests may be denied even when resources are available, if granting would create an unsafe state.
•Integration with Safety Algorithm: The Resource Request Algorithm calls the Safety Algorithm as a subroutine for each request decision.
•Release Handling: Releasing resources is simpler—just return to pool and re-evaluate blocked processes.
•Fairness vs Throughput: The system must balance granting many small requests (throughput) against starvation of large requests (fairness).

What's Next:

Page Complete

3 / 5