Operating SystemsBanker's Algorithm

Banker's Algorithm: Deadlock Avoidance

LevelIntermediate

Duration75 mins

TopicBanker's Algorithm

2 / 5

Safety Algorithm

From Concept to Computation

We now understand what a safe state means conceptually—a state from which all processes can complete execution. But how do we determine programmatically whether a given state is safe?

The Safety Algorithm answers this question. It's a systematic procedure that attempts to construct a safe sequence by simulating resource allocation and release. If the algorithm succeeds in finding any valid ordering, the state is safe. If it fails to complete all processes through simulation, no safe sequence exists, and the state is unsafe.

This algorithm is the computational backbone of the Banker's Algorithm. Every time a process requests resources, the system hypothetically grants the request, runs the Safety Algorithm on the resulting state, and only commits the allocation if the state remains safe.

What You Will Learn

By the end of this page, you will understand the Safety Algorithm's data structures, its step-by-step execution procedure, complexity analysis, implementation considerations, and be able to trace through the algorithm manually on any system state.

Data Structures

The Safety Algorithm operates on well-defined data structures that capture the complete resource allocation state of the system.

Input Data Structures:

Safety Algorithm Input Structures
Structure	Dimensions	Description
`Available`	Vector[m]	Number of available instances of each resource type
`Max`	Matrix[n][m]	Maximum claim of each process for each resource type
`Allocation`	Matrix[n][m]	Current allocation to each process for each resource type
`Need`	Matrix[n][m]	Remaining need: `Need[i][j] = Max[i][j] - Allocation[i][j]`

Where:

n = number of processes in the system
m = number of resource types

Working Data Structures (used during algorithm execution):

Safety Algorithm Working Structures
Structure	Dimensions	Purpose
`Work`	Vector[m]	Simulates available resources as processes complete; initialized to `Available`
`Finish`	Vector[n]	Tracks which processes have been marked as completable; initialized to all `false`

Why Copy Available?

We copy Available into Work rather than modifying Available directly. This is because the Safety Algorithm is a simulation—we're asking 'what if processes completed in this order?' without actually changing system state. The actual allocation might not follow the sequence we discover.

The Safety Algorithm

The Safety Algorithm attempts to find a safe sequence by iteratively finding processes that could complete with current resources, simulating their completion (adding their allocated resources to the work pool), and repeating until all processes are accounted for—or no progress can be made.

Algorithm Steps:

safety_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
SAFETY_ALGORITHM(Available, Max, Allocation, Need, n, m):
    // Step 1: Initialize working structures
    Work[m] ← Available[m]          // Copy available resources
    Finish[n] ← [false, false, ...]  // No process finished yet
    
    // Step 2: Find a process that can complete
    REPEAT:
        found ← false
        FOR i ← 0 TO n-1:
            IF Finish[i] = false AND Need[i] ≤ Work THEN:
                // Step 3: Simulate process completion
                Work ← Work + Allocation[i]  // Resources released
                Finish[i] ← true
                found ← true
                // Note: Don't break - continue checking all processes
        
        // Continue until no unfinished process can complete
    UNTIL found = false
    
    // Step 4: Check final result
    IF all Finish[i] = true THEN:
        RETURN SAFE
    ELSE:
        RETURN UNSAFE

Detailed Explanation:

Step 1 - Initialization:

Work starts as a copy of Available—the resources we can currently distribute
Finish marks all processes as incomplete

Step 2 - Search for Completable Process:

Scan through all processes looking for one where:
- It hasn't been marked finished yet
- Its remaining need can be satisfied with current work resources
Need[i] ≤ Work means every resource type in the need vector is less than or equal to the corresponding type in the work vector

Step 3 - Simulate Completion:

When a suitable process is found, pretend it runs to completion
Add its allocated resources back to the work pool (simulating release)
Mark it as finished

Step 4 - Termination:

Repeat until no unfinished process can complete in a full pass
If all processes are marked finished, a safe sequence exists (the order we found them)
If some remain unfinished, no safe sequence exists—the state is unsafe

Implementation in C

Here's a complete, production-quality implementation of the Safety Algorithm in C. This implementation includes detailed comments, proper memory handling, and clear structure for educational purposes.

safety_algorithm.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
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
#define MAX_PROCESSES 10
#define MAX_RESOURCES 10
 
/**
 * Checks if vector a is less than or equal to vector b
 * (component-wise comparison for all resource types)
 * 
 * @param a First vector (typically Need)
 * @param b Second vector (typically Work)
 * @param m Number of resource types
 * @return true if a[i] <= b[i] for all i
 */
bool vector_le(int a[], int b[], int m) {
    for (int j = 0; j < m; j++) {
        if (a[j] > b[j]) {
            return false;  // Found a resource type where need exceeds work
        }
    }
    return true;
}
 
/**
 * Adds vector b to vector a (a = a + b)
 * Used to simulate releasing resources when process completes
 * 
 * @param a Destination vector (modified in place)
 * @param b Source vector
 * @param m Number of resource types
 */
void vector_add(int a[], int b[], int m) {
    for (int j = 0; j < m; j++) {
        a[j] += b[j];
    }
}
 
/**
 * The Safety Algorithm
 * 
 * Determines whether the current system state is safe by attempting
 * to construct a safe sequence. If successful, all processes can
 * complete; if not, deadlock is possible.
 * 
 * @param n Number of processes
 * @param m Number of resource types
 * @param available Current available resources
 * @param allocation Current allocation matrix
 * @param need Current need matrix
 * @param safe_sequence Output: the safe sequence if one exists
 * @return true if state is safe, false otherwise
 */
bool safety_algorithm(
    int n, int m,
    int available[],
    int allocation[MAX_PROCESSES][MAX_RESOURCES],
    int need[MAX_PROCESSES][MAX_RESOURCES],
    int safe_sequence[]  // Output parameter
) {
    // Step 1: Initialize working structures
    int work[MAX_RESOURCES];
    bool finish[MAX_PROCESSES];
    int sequence_index = 0;
    
    memcpy(work, available, sizeof(int) * m);
    memset(finish, false, sizeof(finish));
    
    // Step 2 & 3: Find and simulate completing processes
    bool found;
    do {
        found = false;
        
        for (int i = 0; i < n; i++) {
            // Check if process i can complete
            if (!finish[i] && vector_le(need[i], work, m)) {
                // Process i can complete with current resources
                
                // Simulate completion: release its resources
                vector_add(work, allocation[i], m);
                
                // Mark as finished
                finish[i] = true;
                
                // Record in safe sequence
                safe_sequence[sequence_index++] = i;
                
                found = true;
                
                // Debug output (optional)
                printf("Process P%d can complete. Work: [", i);
                for (int j = 0; j < m; j++) {
                    printf("%d%s", work[j], j < m-1 ? ", " : "");
                }
                printf("]\n");
            }
        }
    } while (found);
    
    // Step 4: Check if all processes finished
    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            printf("Process P%d cannot complete - STATE UNSAFE\n", i);
            return false;
        }
    }
    
    return true;
}
 
// Example usage and test
int main() {
    int n = 5;  // Number of processes
    int m = 3;  // Number of resource types (A, B, C)
    
    int available[] = {3, 3, 2};
    
    int allocation[MAX_PROCESSES][MAX_RESOURCES] = {
        {0, 1, 0},  // P0
        {2, 0, 0},  // P1
        {3, 0, 2},  // P2
        {2, 1, 1},  // P3
        {0, 0, 2}   // P4
    };
    
    int need[MAX_PROCESSES][MAX_RESOURCES] = {
        {7, 4, 3},  // P0
        {1, 2, 2},  // P1
        {6, 0, 0},  // P2
        {0, 1, 1},  // P3
        {4, 3, 1}   // P4
    };
    
    int safe_sequence[MAX_PROCESSES];
    
    printf("Checking system safety...\n\n");
    
    if (safety_algorithm(n, m, available, allocation, need, safe_sequence)) {
        printf("\nSYSTEM IS SAFE\n");
        printf("Safe sequence: <");
        for (int i = 0; i < n; i++) {
            printf("P%d%s", safe_sequence[i], i < n-1 ? ", " : "");
        }
        printf(">\n");
    } else {
        printf("\nSYSTEM IS UNSAFE - Deadlock possible\n");
    }
    
    return 0;
}

Output for Example

Running this code produces:

Process P1 can complete. Work: [5, 3, 2]
Process P3 can complete. Work: [7, 4, 3]
Process P0 can complete. Work: [7, 5, 3]
Process P2 can complete. Work: [10, 5, 5]
Process P4 can complete. Work: [10, 5, 7]

SYSTEM IS SAFE
Safe sequence: <P1, P3, P0, P2, P4>

Complexity Analysis

Understanding the computational cost of the Safety Algorithm is essential for evaluating its practicality in real systems.

Time Complexity:

Safety Algorithm Time Complexity Breakdown
Operation	Frequency	Cost	Total
Outer loop (do-while)	At most n iterations	—	O(n)
Inner loop (for each process)	n processes per outer iteration	—	O(n) × O(n)
Vector comparison (Need ≤ Work)	Each inner iteration	O(m)	O(n²) × O(m)
Vector addition	At most n times total	O(m)	O(n) × O(m)

Overall Time Complexity: O(n² × m)

Where:

n = number of processes
m = number of resource types

Reasoning:

The outer loop runs at most n times (each iteration marks at least one process as finished, or we terminate)
The inner loop scans all n processes
Each vector comparison takes O(m) time
Total: O(n × n × m) = O(n²m)

Space Complexity: O(n + m)

Work vector: O(m)
Finish array: O(n)
Safe_sequence array: O(n)
Input structures are not counted (already exist)

Total additional space: O(n + m)

Practical Implications

With n=100 processes and m=20 resource types, the algorithm performs roughly 200,000 operations per safety check. Since the algorithm runs for every resource request, a system handling 1000 requests/second would need 200 million operations/second just for safety checking. This overhead is significant and explains why pure deadlock avoidance is uncommon in general-purpose OS.

Optimization Opportunities:

Early Exit: The algorithm can terminate as soon as it finds that all processes can complete, but we're already doing this implicitly.
Smart Ordering: Start by checking processes that are closest to completion (smallest Need), as they're most likely to succeed.
Incremental Updates: Rather than running the full algorithm after each request, maintain auxiliary data structures that allow O(n × m) updates.
Process Subset: Only run safety checks on processes that could potentially be affected by the new allocation.
Caching: Cache recent safety results if system state is relatively stable.

Correctness Proof

For the Safety Algorithm to be trusted, we must prove it correctly identifies safe and unsafe states.

Theorem: The Safety Algorithm returns SAFE if and only if the state is safe.

Proof (Soundness - If algorithm returns SAFE, state is safe):

Assume the algorithm returns SAFE. Then:

All Finish[i] are true
Each process was marked finished because Need[i] ≤ Work at some point
The order in which processes were marked finished forms a valid sequence

For any process Pₖ marked finished at step k:

Work at step k = Available + Σ(Allocation[j] for all j finished before k)
We verified Need[k] ≤ Work before marking Pₖ
Therefore, the sequence satisfies the safe sequence definition

Proof (Completeness - If state is safe, algorithm returns SAFE):

Assume the state is safe, so a safe sequence <Pₐ, Pᵦ, ...> exists.

We show by induction that the algorithm will find some safe sequence (not necessarily the same one):

Base: Initially, Work = Available. For the first process Pₐ in the safe sequence, Need[a] ≤ Available = Work. So the algorithm will find at least one process to mark finished.

Inductive Step: Assume the algorithm has marked k processes finished. The Work vector equals Available plus all released allocations from these k processes. Since a safe sequence exists and the algorithm's marked processes could appear at the beginning of some safe sequence, the next process in that sequence can be satisfied by current Work. Therefore, at least one more process can be marked finished.

Conclusion: The algorithm will mark all n processes finished, returning SAFE. ∎

Order Independence

A crucial property: the algorithm finds some safe sequence if one exists, but doesn't need to find a specific one. The order in which the inner loop examines processes may affect which sequence is discovered, but not whether one is found.

Detailed Trace: Step by Step

Let's trace through the Safety Algorithm execution in complete detail using our standard example.

Initial State:

Processes: P₀, P₁, P₂, P₃, P₄
Resources: A(10 total), B(5 total), C(7 total)
Available: (3, 3, 2)

Initial Allocation and Need Matrices
Process	Allocation	Need
P₀	(0, 1, 0)	(7, 4, 3)
P₁	(2, 0, 0)	(1, 2, 2)
P₂	(3, 0, 2)	(6, 0, 0)
P₃	(2, 1, 1)	(0, 1, 1)
P₄	(0, 0, 2)	(4, 3, 1)

Initialization:

Work = [3, 3, 2]  (copy of Available)
Finish = [false, false, false, false, false]
Sequence = []

Iteration 1:

Iteration 1: Finding First Completable Process
Process	Finish?	Need	Work	Need ≤ Work?	Action
P₀	false	(7,4,3)	(3,3,2)	7>3 ✗	Skip
P₁	false	(1,2,2)	(3,3,2)	1≤3, 2≤3, 2≤2 ✓	Can complete!

After P₁ completes:

Work = [3, 3, 2] + [2, 0, 0] = [5, 3, 2]
Finish = [false, true, false, false, false]
Sequence = [1]
found = true → continue outer loop

Iteration 2 (continues scanning from P₂):

Iteration 2: After P₁ Completes
Process	Finish?	Need	Work	Need ≤ Work?	Action
P₀	false	(7,4,3)	(5,3,2)	7>5 ✗	Skip
P₁	true	—	—	—	Already finished
P₂	false	(6,0,0)	(5,3,2)	6>5 ✗	Skip
P₃	false	(0,1,1)	(5,3,2)	0≤5, 1≤3, 1≤2 ✓	Can complete!

After P₃ completes:

Work = [5, 3, 2] + [2, 1, 1] = [7, 4, 3]
Finish = [false, true, false, true, false]
Sequence = [1, 3]

Iteration 3:

Iteration 3: After P₃ Completes
Process	Finish?	Need	Work	Need ≤ Work?	Action
P₀	false	(7,4,3)	(7,4,3)	7≤7, 4≤4, 3≤3 ✓	Can complete!

After P₀ completes:

Work = [7, 4, 3] + [0, 1, 0] = [7, 5, 3]
Finish = [true, true, false, true, false]
Sequence = [1, 3, 0]

Iteration 4:

P₂: (6,0,0) ≤ (7,5,3)? 6≤7 ✓ → Can complete!
Work = [7,5,3] + [3,0,2] = [10,5,5]
Sequence = [1, 3, 0, 2]

Iteration 5:

P₄: (4,3,1) ≤ (10,5,5)? All ✓ → Can complete!
Work = [10,5,5] + [0,0,2] = [10,5,7]
Sequence = [1, 3, 0, 2, 4]

Termination:

All Finish[i] = true
Return SAFE
Safe sequence: <P₁, P₃, P₀, P₂, P₄>

Tracing an Unsafe State

It's equally important to see how the algorithm detects unsafe states. Let's modify our example to create an unsafe condition.

Modified State:

Same allocation and need as before
But Available = (1, 1, 0) instead of (3, 3, 2)

Unsafe State Analysis
Process	Need	Work=(1,1,0)	Can Complete?
P₀	(7, 4, 3)	7>1, 4>1, 3>0	NO
P₁	(1, 2, 2)	1≤1, 2>1	NO
P₂	(6, 0, 0)	6>1	NO
P₃	(0, 1, 1)	0≤1, 1≤1, 1>0	NO
P₄	(4, 3, 1)	4>1, 3>1, 1>0	NO

Algorithm Execution:

Iteration 1:

Work = [1, 1, 0]
Check all processes: none can complete
found = false

Termination:

Outer loop exits (found = false, no progress made)
Check Finish array: all false
Return UNSAFE

No safe sequence exists with these available resources. The system could deadlock if processes request their maximum needs.

The Critical Insight

In an unsafe state, the algorithm completes exactly one pass through the inner loop without finding any process to mark finished. This is the termination condition for detecting unsafety—when a complete scan yields no progress, no safe sequence is possible.

Why This State Is Unsafe:

With only (1, 1, 0) available:

No single process can get all the resources it might still need
If all processes simultaneously request their maximum remaining needs, none can proceed
Deadlock is possible (though not certain—processes might request less than their maximum)

The Banker's Algorithm would have prevented this state from ever being reached by refusing the allocation request that reduced Available from (3, 3, 2) to (1, 1, 0).

Summary: The Safety Algorithm

The Safety Algorithm is the computational core of deadlock avoidance. Let's consolidate the key insights:

Key Takeaways

•Purpose: Determine if a system state is safe by attempting to construct a safe sequence through simulation.
•Method: Iteratively find processes whose needs can be met, simulate their completion (releasing resources), and repeat until all processes are accounted for or no progress can be made.
•Complexity: O(n²m) time, O(n + m) space—significant overhead that limits practical applicability.
•Correctness: The algorithm is both sound (if it says safe, state is safe) and complete (if state is safe, it will find a sequence).
•Termination: Algorithm always terminates—either all processes marked finished (safe) or a full pass with no progress (unsafe).
•Integration: This algorithm is called by the Resource Request Algorithm to evaluate whether granting a request would leave the system in a safe state.

What's Next:

The Safety Algorithm tells us whether a state is safe, but we haven't yet discussed how to handle incoming resource requests. The next page introduces the Resource Request Algorithm—the procedure that receives process requests, hypothetically grants them, checks safety, and decides whether to commit or defer the allocation.

Page Complete

You now understand the Safety Algorithm—the computational heart of deadlock avoidance. You can trace through the algorithm manually, analyze its complexity, understand its correctness, and recognize both safe and unsafe states.

2 / 5

Loading learning content...

Operating SystemsBanker's Algorithm

Banker's Algorithm: Deadlock Avoidance

LevelIntermediate

Duration75 mins

TopicBanker's Algorithm

2 / 5

Safety Algorithm

From Concept to Computation

We now understand what a safe state means conceptually—a state from which all processes can complete execution. But how do we determine programmatically whether a given state is safe?

What You Will Learn

Data Structures

The Safety Algorithm operates on well-defined data structures that capture the complete resource allocation state of the system.

Input Data Structures:

Safety Algorithm Input Structures
Structure	Dimensions	Description
`Available`	Vector[m]	Number of available instances of each resource type
`Max`	Matrix[n][m]	Maximum claim of each process for each resource type
`Allocation`	Matrix[n][m]	Current allocation to each process for each resource type
`Need`	Matrix[n][m]	Remaining need: `Need[i][j] = Max[i][j] - Allocation[i][j]`

Where:

n = number of processes in the system
m = number of resource types

Working Data Structures (used during algorithm execution):

Safety Algorithm Working Structures
Structure	Dimensions	Purpose
`Work`	Vector[m]	Simulates available resources as processes complete; initialized to `Available`
`Finish`	Vector[n]	Tracks which processes have been marked as completable; initialized to all `false`

Why Copy Available?

The Safety Algorithm

Algorithm Steps:

safety_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
SAFETY_ALGORITHM(Available, Max, Allocation, Need, n, m):
    // Step 1: Initialize working structures
    Work[m] ← Available[m]          // Copy available resources
    Finish[n] ← [false, false, ...]  // No process finished yet
    
    // Step 2: Find a process that can complete
    REPEAT:
        found ← false
        FOR i ← 0 TO n-1:
            IF Finish[i] = false AND Need[i] ≤ Work THEN:
                // Step 3: Simulate process completion
                Work ← Work + Allocation[i]  // Resources released
                Finish[i] ← true
                found ← true
                // Note: Don't break - continue checking all processes
        
        // Continue until no unfinished process can complete
    UNTIL found = false
    
    // Step 4: Check final result
    IF all Finish[i] = true THEN:
        RETURN SAFE
    ELSE:
        RETURN UNSAFE

Detailed Explanation:

Step 1 - Initialization:

Work starts as a copy of Available—the resources we can currently distribute
Finish marks all processes as incomplete

Step 2 - Search for Completable Process:

Scan through all processes looking for one where:
- It hasn't been marked finished yet
- Its remaining need can be satisfied with current work resources
Need[i] ≤ Work means every resource type in the need vector is less than or equal to the corresponding type in the work vector

Step 3 - Simulate Completion:

When a suitable process is found, pretend it runs to completion
Add its allocated resources back to the work pool (simulating release)
Mark it as finished

Step 4 - Termination:

Repeat until no unfinished process can complete in a full pass
If all processes are marked finished, a safe sequence exists (the order we found them)
If some remain unfinished, no safe sequence exists—the state is unsafe

Implementation in C

safety_algorithm.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
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
#define MAX_PROCESSES 10
#define MAX_RESOURCES 10
 
/**
 * Checks if vector a is less than or equal to vector b
 * (component-wise comparison for all resource types)
 * 
 * @param a First vector (typically Need)
 * @param b Second vector (typically Work)
 * @param m Number of resource types
 * @return true if a[i] <= b[i] for all i
 */
bool vector_le(int a[], int b[], int m) {
    for (int j = 0; j < m; j++) {
        if (a[j] > b[j]) {
            return false;  // Found a resource type where need exceeds work
        }
    }
    return true;
}
 
/**
 * Adds vector b to vector a (a = a + b)
 * Used to simulate releasing resources when process completes
 * 
 * @param a Destination vector (modified in place)
 * @param b Source vector
 * @param m Number of resource types
 */
void vector_add(int a[], int b[], int m) {
    for (int j = 0; j < m; j++) {
        a[j] += b[j];
    }
}
 
/**
 * The Safety Algorithm
 * 
 * Determines whether the current system state is safe by attempting
 * to construct a safe sequence. If successful, all processes can
 * complete; if not, deadlock is possible.
 * 
 * @param n Number of processes
 * @param m Number of resource types
 * @param available Current available resources
 * @param allocation Current allocation matrix
 * @param need Current need matrix
 * @param safe_sequence Output: the safe sequence if one exists
 * @return true if state is safe, false otherwise
 */
bool safety_algorithm(
    int n, int m,
    int available[],
    int allocation[MAX_PROCESSES][MAX_RESOURCES],
    int need[MAX_PROCESSES][MAX_RESOURCES],
    int safe_sequence[]  // Output parameter
) {
    // Step 1: Initialize working structures
    int work[MAX_RESOURCES];
    bool finish[MAX_PROCESSES];
    int sequence_index = 0;
    
    memcpy(work, available, sizeof(int) * m);
    memset(finish, false, sizeof(finish));
    
    // Step 2 & 3: Find and simulate completing processes
    bool found;
    do {
        found = false;
        
        for (int i = 0; i < n; i++) {
            // Check if process i can complete
            if (!finish[i] && vector_le(need[i], work, m)) {
                // Process i can complete with current resources
                
                // Simulate completion: release its resources
                vector_add(work, allocation[i], m);
                
                // Mark as finished
                finish[i] = true;
                
                // Record in safe sequence
                safe_sequence[sequence_index++] = i;
                
                found = true;
                
                // Debug output (optional)
                printf("Process P%d can complete. Work: [", i);
                for (int j = 0; j < m; j++) {
                    printf("%d%s", work[j], j < m-1 ? ", " : "");
                }
                printf("]\n");
            }
        }
    } while (found);
    
    // Step 4: Check if all processes finished
    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            printf("Process P%d cannot complete - STATE UNSAFE\n", i);
            return false;
        }
    }
    
    return true;
}
 
// Example usage and test
int main() {
    int n = 5;  // Number of processes
    int m = 3;  // Number of resource types (A, B, C)
    
    int available[] = {3, 3, 2};
    
    int allocation[MAX_PROCESSES][MAX_RESOURCES] = {
        {0, 1, 0},  // P0
        {2, 0, 0},  // P1
        {3, 0, 2},  // P2
        {2, 1, 1},  // P3
        {0, 0, 2}   // P4
    };
    
    int need[MAX_PROCESSES][MAX_RESOURCES] = {
        {7, 4, 3},  // P0
        {1, 2, 2},  // P1
        {6, 0, 0},  // P2
        {0, 1, 1},  // P3
        {4, 3, 1}   // P4
    };
    
    int safe_sequence[MAX_PROCESSES];
    
    printf("Checking system safety...\n\n");
    
    if (safety_algorithm(n, m, available, allocation, need, safe_sequence)) {
        printf("\nSYSTEM IS SAFE\n");
        printf("Safe sequence: <");
        for (int i = 0; i < n; i++) {
            printf("P%d%s", safe_sequence[i], i < n-1 ? ", " : "");
        }
        printf(">\n");
    } else {
        printf("\nSYSTEM IS UNSAFE - Deadlock possible\n");
    }
    
    return 0;
}

Output for Example

Running this code produces:

Process P1 can complete. Work: [5, 3, 2]
Process P3 can complete. Work: [7, 4, 3]
Process P0 can complete. Work: [7, 5, 3]
Process P2 can complete. Work: [10, 5, 5]
Process P4 can complete. Work: [10, 5, 7]

SYSTEM IS SAFE
Safe sequence: <P1, P3, P0, P2, P4>

Complexity Analysis

Understanding the computational cost of the Safety Algorithm is essential for evaluating its practicality in real systems.

Time Complexity:

Safety Algorithm Time Complexity Breakdown
Operation	Frequency	Cost	Total
Outer loop (do-while)	At most n iterations	—	O(n)
Inner loop (for each process)	n processes per outer iteration	—	O(n) × O(n)
Vector comparison (Need ≤ Work)	Each inner iteration	O(m)	O(n²) × O(m)
Vector addition	At most n times total	O(m)	O(n) × O(m)

Overall Time Complexity: O(n² × m)

Where:

n = number of processes
m = number of resource types

Reasoning:

The outer loop runs at most n times (each iteration marks at least one process as finished, or we terminate)
The inner loop scans all n processes
Each vector comparison takes O(m) time
Total: O(n × n × m) = O(n²m)

Space Complexity: O(n + m)

Work vector: O(m)
Finish array: O(n)
Safe_sequence array: O(n)
Input structures are not counted (already exist)

Total additional space: O(n + m)

Practical Implications

Optimization Opportunities:

Early Exit: The algorithm can terminate as soon as it finds that all processes can complete, but we're already doing this implicitly.
Smart Ordering: Start by checking processes that are closest to completion (smallest Need), as they're most likely to succeed.
Incremental Updates: Rather than running the full algorithm after each request, maintain auxiliary data structures that allow O(n × m) updates.
Process Subset: Only run safety checks on processes that could potentially be affected by the new allocation.
Caching: Cache recent safety results if system state is relatively stable.

Correctness Proof

For the Safety Algorithm to be trusted, we must prove it correctly identifies safe and unsafe states.

Theorem: The Safety Algorithm returns SAFE if and only if the state is safe.

Proof (Soundness - If algorithm returns SAFE, state is safe):

Assume the algorithm returns SAFE. Then:

All Finish[i] are true
Each process was marked finished because Need[i] ≤ Work at some point
The order in which processes were marked finished forms a valid sequence

For any process Pₖ marked finished at step k:

Work at step k = Available + Σ(Allocation[j] for all j finished before k)
We verified Need[k] ≤ Work before marking Pₖ
Therefore, the sequence satisfies the safe sequence definition

Proof (Completeness - If state is safe, algorithm returns SAFE):

Assume the state is safe, so a safe sequence <Pₐ, Pᵦ, ...> exists.

We show by induction that the algorithm will find some safe sequence (not necessarily the same one):

Base: Initially, Work = Available. For the first process Pₐ in the safe sequence, Need[a] ≤ Available = Work. So the algorithm will find at least one process to mark finished.

Conclusion: The algorithm will mark all n processes finished, returning SAFE. ∎

Order Independence

Detailed Trace: Step by Step

Let's trace through the Safety Algorithm execution in complete detail using our standard example.

Initial State:

Processes: P₀, P₁, P₂, P₃, P₄
Resources: A(10 total), B(5 total), C(7 total)
Available: (3, 3, 2)

Initial Allocation and Need Matrices
Process	Allocation	Need
P₀	(0, 1, 0)	(7, 4, 3)
P₁	(2, 0, 0)	(1, 2, 2)
P₂	(3, 0, 2)	(6, 0, 0)
P₃	(2, 1, 1)	(0, 1, 1)
P₄	(0, 0, 2)	(4, 3, 1)

Initialization:

Work = [3, 3, 2]  (copy of Available)
Finish = [false, false, false, false, false]
Sequence = []

Iteration 1:

Iteration 1: Finding First Completable Process
Process	Finish?	Need	Work	Need ≤ Work?	Action
P₀	false	(7,4,3)	(3,3,2)	7>3 ✗	Skip
P₁	false	(1,2,2)	(3,3,2)	1≤3, 2≤3, 2≤2 ✓	Can complete!

After P₁ completes:

Work = [3, 3, 2] + [2, 0, 0] = [5, 3, 2]
Finish = [false, true, false, false, false]
Sequence = [1]
found = true → continue outer loop

Iteration 2 (continues scanning from P₂):

Iteration 2: After P₁ Completes
Process	Finish?	Need	Work	Need ≤ Work?	Action
P₀	false	(7,4,3)	(5,3,2)	7>5 ✗	Skip
P₁	true	—	—	—	Already finished
P₂	false	(6,0,0)	(5,3,2)	6>5 ✗	Skip
P₃	false	(0,1,1)	(5,3,2)	0≤5, 1≤3, 1≤2 ✓	Can complete!

After P₃ completes:

Work = [5, 3, 2] + [2, 1, 1] = [7, 4, 3]
Finish = [false, true, false, true, false]
Sequence = [1, 3]

Iteration 3:

Iteration 3: After P₃ Completes
Process	Finish?	Need	Work	Need ≤ Work?	Action
P₀	false	(7,4,3)	(7,4,3)	7≤7, 4≤4, 3≤3 ✓	Can complete!

After P₀ completes:

Work = [7, 4, 3] + [0, 1, 0] = [7, 5, 3]
Finish = [true, true, false, true, false]
Sequence = [1, 3, 0]

Iteration 4:

P₂: (6,0,0) ≤ (7,5,3)? 6≤7 ✓ → Can complete!
Work = [7,5,3] + [3,0,2] = [10,5,5]
Sequence = [1, 3, 0, 2]

Iteration 5:

P₄: (4,3,1) ≤ (10,5,5)? All ✓ → Can complete!
Work = [10,5,5] + [0,0,2] = [10,5,7]
Sequence = [1, 3, 0, 2, 4]

Termination:

All Finish[i] = true
Return SAFE
Safe sequence: <P₁, P₃, P₀, P₂, P₄>

Tracing an Unsafe State

It's equally important to see how the algorithm detects unsafe states. Let's modify our example to create an unsafe condition.

Modified State:

Same allocation and need as before
But Available = (1, 1, 0) instead of (3, 3, 2)

Unsafe State Analysis
Process	Need	Work=(1,1,0)	Can Complete?
P₀	(7, 4, 3)	7>1, 4>1, 3>0	NO
P₁	(1, 2, 2)	1≤1, 2>1	NO
P₂	(6, 0, 0)	6>1	NO
P₃	(0, 1, 1)	0≤1, 1≤1, 1>0	NO
P₄	(4, 3, 1)	4>1, 3>1, 1>0	NO

Algorithm Execution:

Iteration 1:

Work = [1, 1, 0]
Check all processes: none can complete
found = false

Termination:

Outer loop exits (found = false, no progress made)
Check Finish array: all false
Return UNSAFE

No safe sequence exists with these available resources. The system could deadlock if processes request their maximum needs.

The Critical Insight

Why This State Is Unsafe:

With only (1, 1, 0) available:

No single process can get all the resources it might still need
If all processes simultaneously request their maximum remaining needs, none can proceed
Deadlock is possible (though not certain—processes might request less than their maximum)

The Banker's Algorithm would have prevented this state from ever being reached by refusing the allocation request that reduced Available from (3, 3, 2) to (1, 1, 0).

Summary: The Safety Algorithm

The Safety Algorithm is the computational core of deadlock avoidance. Let's consolidate the key insights:

Key Takeaways

•Purpose: Determine if a system state is safe by attempting to construct a safe sequence through simulation.
•Method: Iteratively find processes whose needs can be met, simulate their completion (releasing resources), and repeat until all processes are accounted for or no progress can be made.
•Complexity: O(n²m) time, O(n + m) space—significant overhead that limits practical applicability.
•Correctness: The algorithm is both sound (if it says safe, state is safe) and complete (if state is safe, it will find a sequence).
•Termination: Algorithm always terminates—either all processes marked finished (safe) or a full pass with no progress (unsafe).
•Integration: This algorithm is called by the Resource Request Algorithm to evaluate whether granting a request would leave the system in a safe state.

What's Next:

Page Complete

2 / 5