Operating SystemsDeadlock Concepts

Understanding Deadlock Concepts

LevelIntermediate

Duration60 mins

TopicDeadlock Concepts

3 / 5

System Model

Modeling Reality for Rigorous Analysis

To reason precisely about deadlock—to prove properties, design algorithms, and verify correctness—we need a formal model that captures the essential elements of resource allocation while abstracting away implementation details. This model serves as the mathematical foundation upon which all deadlock theory is built.

The system model defines what processes are, what resources are, how they interact, and what states the system can be in. It provides a common language for discussing deadlock across different operating systems, programming languages, and hardware platforms. Without this model, we would be limited to ad-hoc reasoning about specific implementations.

What You Will Learn

By the end of this page, you will understand the formal system model for deadlock analysis, including process and resource representations, allocation and request matrices, the safe state concept, and how to use this model to analyze real systems. You will be equipped to formally specify and verify deadlock properties.

Components of the System Model

The system model for deadlock analysis consists of four fundamental components that interact according to well-defined rules.

Model Components

•Processes (P): A finite set P = {P₁, P₂, ..., Pₙ} of n processes. Each process executes a sequence of operations that may include resource requests and releases. Processes are the active entities that compete for resources.
•Resource Types (R): A finite set R = {R₁, R₂, ..., Rₘ} of m resource types. Each resource type Rⱼ has a fixed number of identical instances, denoted as Total[j]. The total vector T = [T₁, T₂, ..., Tₘ] represents the total instances of each type in the system.
•Allocation State (A): An n×m matrix where A[i,j] represents the number of instances of resource type Rⱼ currently allocated to process Pᵢ. This matrix captures who holds what at any given moment.
•Request State (Q or Need): An n×m matrix where Q[i,j] (or Need[i,j]) represents the number of additional instances of Rⱼ that Pᵢ may still request. In the Banker's Algorithm, this is Max[i,j] - Allocation[i,j].

Available Resources Vector:

At any point in time, the system has a vector of available resources:

Available[j] = Total[j] - Σᵢ Allocation[i,j]

This vector represents the pool of unallocated instances of each resource type. It's computed by subtracting all allocated resources from the total.

The Conservation Invariant:

For reusable resources, the following invariant always holds:

Available + (sum of all allocations per resource type) = Total

Or equivalently: ∀j: Available[j] + Σᵢ A[i,j] = Total[j]

This conservation law is fundamental—resources can be allocated or available, but the total never changes. This property makes the mathematics tractable.

system_model.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
#include <stdio.h>
#include <stdbool.h>
 
#define MAX_PROCESSES 10
#define MAX_RESOURCES 5
 
typedef struct {
    int n;  // Number of processes
    int m;  // Number of resource types
    
    // Total instances of each resource type
    int total[MAX_RESOURCES];
    
    // Available instances (computed from total - allocated)
    int available[MAX_RESOURCES];
    
    // Allocation matrix: allocation[i][j] = instances of Rj held by Pi
    int allocation[MAX_PROCESSES][MAX_RESOURCES];
    
    // Need matrix: need[i][j] = additional instances of Rj that Pi may request
    // In Banker's: need[i][j] = max[i][j] - allocation[i][j]
    int need[MAX_PROCESSES][MAX_RESOURCES];
    
    // Maximum demand (for Banker's Algorithm)
    int max[MAX_PROCESSES][MAX_RESOURCES];
    
} SystemState;
 
/* Recompute available vector from allocation */
void compute_available(SystemState* state) {
    for (int j = 0; j < state->m; j++) {
        int allocated = 0;
        for (int i = 0; i < state->n; i++) {
            allocated += state->allocation[i][j];
        }
        state->available[j] = state->total[j] - allocated;
    }
}
 
/* Verify the conservation invariant holds */
bool verify_conservation(SystemState* state) {
    for (int j = 0; j < state->m; j++) {
        int sum = state->available[j];
        for (int i = 0; i < state->n; i++) {
            sum += state->allocation[i][j];
        }
        if (sum != state->total[j]) {
            printf("INVARIANT VIOLATION: Resource %d, expected %d got %d
", 
                   j, state->total[j], sum);
            return false;
        }
    }
    return true;
}
 
/* Example: Initialize a system state */
void example_system() {
    SystemState state;
    state.n = 3;  // 3 processes
    state.m = 3;  // 3 resource types
    
    // Total resources: [10, 5, 7]
    state.total[0] = 10; state.total[1] = 5; state.total[2] = 7;
    
    // Current allocations
    // P0 holds [0, 1, 0], P1 holds [2, 0, 0], P2 holds [3, 0, 2]
    state.allocation[0][0] = 0; state.allocation[0][1] = 1; state.allocation[0][2] = 0;
    state.allocation[1][0] = 2; state.allocation[1][1] = 0; state.allocation[1][2] = 0;
    state.allocation[2][0] = 3; state.allocation[2][1] = 0; state.allocation[2][2] = 2;
    
    compute_available(&state);
    // Available = [10-0-2-3, 5-1-0-0, 7-0-0-2] = [5, 4, 5]
    
    printf("Available: [%d, %d, %d]
", 
           state.available[0], state.available[1], state.available[2]);
    
    verify_conservation(&state);
}

Process Behavior Model

The system model makes specific assumptions about how processes behave. These assumptions simplify analysis while capturing the essential patterns that lead to deadlock.

The Request-Use-Release Protocol:

Every process follows a structured lifecycle when interacting with resources:

Request: The process asks the system to allocate one or more resource instances. The request must not exceed the process's declared maximum need. The process blocks if the request cannot be immediately satisfied.
Use: Once granted, the process uses the resource to perform its work. The system model assumes this phase is finite—the process will eventually move to release.
Release: When finished with the resource, the process explicitly releases it back to the system, making it available for other processes.

This cycle may repeat many times during a process's lifetime, acquiring and releasing different resources.

Converting Mermaid diagram...

Key Assumptions About Process Behavior:

Process Model Assumptions
Assumption	Formal Statement	Why It Matters
Finite Resource Need	∀i,j: Need[i,j] ≤ Max[i,j] ≤ Total[j]	Prevents unbounded requests that can't ever be satisfied
Bounded Hold Time	If granted, process releases in finite time	Enables eventually-terminates arguments
Atomic Request/Release	Single resource operation is indivisible	Prevents race conditions in allocation logic
Request Before Use	Process doesn't use until request granted	Ensures valid allocation state
Correct Declaration	Declared max is honest upper bound	Banker's Algorithm depends on this honesty
No Early Release	Resources held until explicitly released	Simplifies state tracking

When Assumptions Fail

Real systems sometimes violate these assumptions. A process might crash while holding resources (violating 'releases in finite time'). A process might lie about its maximum need (violating 'correct declaration'). Robust systems must handle these cases—typically through timeouts, watchdog mechanisms, or resource cleanup on process termination.

The Allocation Matrix

The Allocation Matrix is the central data structure for tracking the current state of resource ownership. Understanding its structure and manipulation is essential for implementing deadlock detection and avoidance algorithms.

Matrix Structure:

Allocation Matrix A (n processes × m resource types)

              R₁  R₂  R₃  ...  Rₘ
         P₁ [ a₁₁ a₁₂ a₁₃ ... a₁ₘ ]
         P₂ [ a₂₁ a₂₂ a₂₃ ... a₂ₘ ]
         P₃ [ a₃₁ a₃₂ a₃₃ ... a₃ₘ ]
         ...[ ... ... ... ... ... ]
         Pₙ [ aₙ₁ aₙ₂ aₙ₃ ... aₙₘ ]

Where:

Row i (Allocation_i) = resources currently held by process Pᵢ
Column j = how resource type Rⱼ is distributed among processes
Entry a_ij = number of instances of Rⱼ allocated to Pᵢ

Operations on the Allocation Matrix:

allocation_matrix_ops.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
/* Allocation Matrix Operations */
 
typedef struct {
    int n, m;                         // Dimensions
    int allocation[MAX_P][MAX_R];     // The matrix
    int available[MAX_R];             // Available vector
    int total[MAX_R];                 // Total instances
} AllocationState;
 
/* Operation: Allocate resources to a process */
bool allocate(AllocationState* s, int process, int request[]) {
    // Check if request can be satisfied
    for (int j = 0; j < s->m; j++) {
        if (request[j] > s->available[j]) {
            return false;  // Insufficient resources
        }
    }
    
    // Perform allocation
    for (int j = 0; j < s->m; j++) {
        s->allocation[process][j] += request[j];
        s->available[j] -= request[j];
    }
    return true;
}
 
/* Operation: Release resources from a process */
void release(AllocationState* s, int process, int release_vec[]) {
    for (int j = 0; j < s->m; j++) {
        // Sanity check: can't release more than held
        if (release_vec[j] > s->allocation[process][j]) {
            // Error handling...
        }
        s->allocation[process][j] -= release_vec[j];
        s->available[j] += release_vec[j];
    }
}
 
/* Query: Total resources held by a process */
void get_process_resources(AllocationState* s, int process, int result[]) {
    for (int j = 0; j < s->m; j++) {
        result[j] = s->allocation[process][j];
    }
}
 
/* Query: How is a resource type distributed? */
void get_resource_distribution(AllocationState* s, int resource, int holders[], int* count) {
    *count = 0;
    for (int i = 0; i < s->n; i++) {
        if (s->allocation[i][resource] > 0) {
            holders[(*count)++] = i;
        }
    }
}
 
/* Query: Is process waiting (has need but holds less)? */
bool is_waiting(AllocationState* s, int process, int need[]) {
    for (int j = 0; j < s->m; j++) {
        if (need[j] > s->available[j]) {
            return true;  // Needs something that's not available
        }
    }
    return false;
}
 
/* 
 * CRITICAL INVARIANT: After any operation:
 * ∀j: s->available[j] + Σᵢ s->allocation[i][j] == s->total[j]
 * 
 * Violations indicate bugs in allocation logic!
 */

Worked Example:

Consider a system with 3 processes and 4 resource types:

	R₁	R₂	R₃	R₄
Total	6	4	7	2
P₀ holds	1	0	2	0
P₁ holds	2	1	1	1
P₂ holds	0	1	0	0
Available	3	2	4	1

Verification:

R₁: 1 + 2 + 0 + 3 = 6 ✓
R₂: 0 + 1 + 1 + 2 = 4 ✓
R₃: 2 + 1 + 0 + 4 = 7 ✓
R₄: 0 + 1 + 0 + 1 = 2 ✓

The conservation invariant holds. This state can be analyzed for deadlock potential.

The Need and Request Matrices

While the Allocation Matrix tells us what resources are currently held, we also need to track what resources processes need and are requesting. These related matrices serve different purposes in deadlock analysis.

Maximum Demand Matrix (Max)

•Definition: Max[i,j] = maximum instances of Rⱼ that Pᵢ will EVER need simultaneously
•Declared: by process at creation time
•Used by: Banker's Algorithm for avoidance
•Constraint: Max[i,j] ≤ Total[j] always
•Interpretation: Upper bound on demand

Need Matrix

•Definition: Need[i,j] = Max[i,j] - Allocation[i,j]
•Computed: from Max and Allocation
•Used by: Safety algorithm to check completion
•Constraint: Need[i,j] ≥ 0 always
•Interpretation: What more might be requested

The Request Matrix:

While Max and Need represent potential future demands, the Request matrix captures current pending requests—resources that have been asked for but not yet granted:

Request[i,j] = instances of Rⱼ that Pᵢ has requested and is waiting for

The Request matrix is more dynamic than Need—it changes whenever a process makes a request or gets a grant. The Need matrix is an upper bound; Request is the current specific demand.

Matrix	Represents	Changes When
Max	Lifetime maximum need	Set at process creation, fixed
Allocation	Currently held	Request granted or release executed
Need	Max - Allocation	Allocation changes
Request	Currently pending	Request made or granted

need_matrix.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
/* Need Matrix Computation and Validation */
 
typedef struct {
    int max[MAX_P][MAX_R];        // Maximum demand (declared)
    int allocation[MAX_P][MAX_R]; // Currently held
    int need[MAX_P][MAX_R];       // Max - Allocation (derived)
    int request[MAX_P][MAX_R];    // Currently pending requests
} DeadlockState;
 
/* Recompute need matrix from max and allocation */
void compute_need(DeadlockState* s, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            s->need[i][j] = s->max[i][j] - s->allocation[i][j];
            
            // Invariant check: need should never be negative
            if (s->need[i][j] < 0) {
                printf("ERROR: Process %d allocated more than max for resource %d
", i, j);
                // This indicates a bug—allocated more than maximum!
            }
        }
    }
}
 
/* Validate a request against declared maximum */
bool validate_request(DeadlockState* s, int process, int request[], int m) {
    for (int j = 0; j < m; j++) {
        // Request must not exceed remaining need
        if (request[j] > s->need[process][j]) {
            printf("ERROR: Process %d requesting %d of R%d but need is only %d
",
                   process, request[j], j, s->need[process][j]);
            return false;
        }
    }
    return true;
}
 
/* Example: A process makes a request */
bool make_request(DeadlockState* s, int available[], int process, int request[], int m) {
    // Step 1: Validate request doesn't exceed need
    if (!validate_request(s, process, request, m)) {
        return false;  // Invalid request
    }
    
    // Step 2: Check if resources are available
    for (int j = 0; j < m; j++) {
        if (request[j] > available[j]) {
            // Resources not available—process must wait
            for (int k = 0; k < m; k++) {
                s->request[process][k] = request[k];  // Record pending request
            }
            return false;  // Return false to indicate blocking
        }
    }
    
    // Step 3: Resources available—tentatively allocate
    // (In Banker's, we'd also check if resulting state is safe)
    for (int j = 0; j < m; j++) {
        available[j] -= request[j];
        s->allocation[process][j] += request[j];
        s->need[process][j] -= request[j];
        s->request[process][j] = 0;  // Request satisfied
    }
    
    return true;  // Success
}

The Honesty Assumption

The Banker's Algorithm critically depends on processes honestly declaring their maximum needs upfront. If a process lies (declares a lower max than it will actually need), the algorithm's safety guarantees fail. In practice, many systems don't use Banker's precisely because getting accurate max declarations is impractical for dynamic workloads.

Safe and Unsafe States

A crucial concept in deadlock avoidance is the distinction between safe and unsafe states. This classification provides a framework for making allocation decisions that prevent deadlock by never entering states from which deadlock might be unavoidable.

Safe State Definition:

A system state is safe if there exists a sequence of process completions (called a safe sequence) such that:

Each process in the sequence can acquire its remaining needed resources from currently available resources plus resources held by all previously completed processes in the sequence
Once a process completes, it releases all its resources back to the available pool
All processes eventually complete

Formally, a safe sequence is a permutation ⟨P₁, P₂, ..., Pₙ⟩ of all n processes such that for each Pᵢ:

Need[i] ≤ Available + Σⱼ₍ⱼ<ᵢ₎ Allocation[j]

In other words, when it's Pᵢ's turn in the sequence, enough resources are available (either initially or from earlier completions) to satisfy its needs.

Safe State

•At least one safe sequence exists
•Guaranteed: NO deadlock if we stay in safe states
•Processes CAN complete if we schedule carefully
•May have multiple safe sequences
•System has escape path from current state

Unsafe State

•No safe sequence exists
•NOT guaranteed: deadlock is possible, not certain
•Some resource requests might lead to deadlock
•May still avoid deadlock with luck
•System has entered risky territory

Unsafe ≠ Deadlocked

A critical point: an unsafe state is NOT the same as a deadlock state. Unsafe means deadlock MIGHT occur depending on future requests. Deadlock means processes ARE irrevocably blocked. An unsafe state can lucky its way to completion if processes happen to make the right sequence of requests. The Banker's Algorithm is conservative—it avoids unsafe states entirely, which means it might deny requests that would have been fine.

Converting Mermaid diagram...

Relationship Between State Categories:

Safe States ⊂ All Non-Deadlock States
Deadlock States ⊂ Unsafe States
Unsafe States = Potential Deadlock States ∪ Lucky Completion States

The key insight is that Safe States and Deadlock States are non-overlapping, but Unsafe States include both inevitable deadlocks and states that happen to work out.

The Safety Algorithm

The Safety Algorithm determines whether a given system state is safe by attempting to find a safe sequence. This algorithm is central to the Banker's Algorithm for deadlock avoidance.

safety_algorithm.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
#include <stdbool.h>
#include <string.h>
 
#define MAX_P 10
#define MAX_R 5
 
/*
 * THE SAFETY ALGORITHM
 * 
 * Input:
 *   - n: number of processes
 *   - m: number of resource types
 *   - available[m]: currently available resources
 *   - allocation[n][m]: current allocation matrix
 *   - need[n][m]: remaining need matrix (max - allocation)
 * 
 * Output:
 *   - true if state is safe, false otherwise
 *   - safe_sequence[n]: a valid safe sequence if one exists
 */
bool safety_algorithm(
    int n, int m,
    int available[],
    int allocation[][MAX_R],
    int need[][MAX_R],
    int safe_sequence[],      // Output: the safe sequence
    int* sequence_length      // Output: length of sequence (should be n if safe)
) {
    // Step 1: Initialize working variables
    int work[MAX_R];
    bool finish[MAX_P];
    
    for (int j = 0; j < m; j++) {
        work[j] = available[j];  // Work = Available initially
    }
    for (int i = 0; i < n; i++) {
        finish[i] = false;       // No process finished yet
    }
    
    *sequence_length = 0;
    
    // Step 2: Find a process that can finish with current work
    while (true) {
        // Find unfinished process whose need ≤ work
        int found = -1;
        for (int i = 0; i < n; i++) {
            if (!finish[i]) {
                // Check if need[i] ≤ work
                bool can_finish = true;
                for (int j = 0; j < m; j++) {
                    if (need[i][j] > work[j]) {
                        can_finish = false;
                        break;
                    }
                }
                
                if (can_finish) {
                    found = i;
                    break;
                }
            }
        }
        
        // Step 3: Process found or no more candidates
        if (found == -1) {
            break;  // No process can proceed
        }
        
        // Found a process that can complete
        // Simulate: process finishes and releases resources
        for (int j = 0; j < m; j++) {
            work[j] += allocation[found][j];
        }
        finish[found] = true;
        safe_sequence[(*sequence_length)++] = found;
    }
    
    // Step 4: Check if all processes finished
    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            return false;  // UNSAFE: some process couldn't finish
        }
    }
    
    return true;  // SAFE: found a safe sequence
}
 
/* Example usage */
void safety_example() {
    int n = 5, m = 3;
    
    int available[] = {3, 3, 2};
    
    int allocation[5][MAX_R] = {
        {0, 1, 0},  // P0
        {2, 0, 0},  // P1
        {3, 0, 2},  // P2
        {2, 1, 1},  // P3
        {0, 0, 2}   // P4
    };
    
    int need[5][MAX_R] = {
        {7, 4, 3},  // P0 needs
        {1, 2, 2},  // P1 needs
        {6, 0, 0},  // P2 needs
        {0, 1, 1},  // P3 needs
        {4, 3, 1}   // P4 needs
    };
    
    int safe_sequence[5];
    int length;
    
    if (safety_algorithm(n, m, available, allocation, need, safe_sequence, &length)) {
        printf("SAFE STATE
");
        printf("Safe sequence: ");
        for (int i = 0; i < length; i++) {
            printf("P%d ", safe_sequence[i]);
        }
        printf("
");
        // Output: Safe sequence: P1 P3 P4 P0 P2
    } else {
        printf("UNSAFE STATE
");
    }
}

Algorithm Complexity Analysis:

Operation	Complexity	Notes
Finding one candidate	O(n × m)	Check each process's need vs. work
Finding all n candidates	O(n² × m)	Each of n iterations scans up to n processes
Overall Safety Algorithm	O(n² × m)	Dominates any constant-time operations

For systems with many processes and resource types, this quadratic complexity can be significant. This is one reason why deadlock avoidance (checking safety on every request) is used sparingly in practice.

Multiple Safe Sequences

The Safety Algorithm finds ONE safe sequence, but there may be many. The algorithm's greedy approach (pick any eligible process) doesn't guarantee finding the 'best' sequence—just a valid one. In practice, existence of any safe sequence is sufficient; the specific sequence doesn't matter for safety determination.

State Transitions and System Evolution

The system state changes over time as processes make requests, receive allocations, and release resources. Understanding how states transition is crucial for maintaining deadlock-free operation.

State Transition Events:

The system state S = (Allocation, Available, Need, Request) changes due to three types of events:

Request Event: Process Pᵢ requests resources R
- If R ≤ Available AND resulting state is safe: Grant the request, update Allocation and Available
- Otherwise: Block the process, record pending request
Release Event: Process Pᵢ releases resources R
- Always succeeds (process owns the resources)
- Update: Allocation[i] -= R, Available += R
- May enable blocked processes to proceed
Process Completion: Process Pᵢ terminates
- Implicitly releases all held resources
- Remove process from active set
- Update all tracking structures

state_transitions.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
/*
 * State Transition Manager
 * Maintains system state and processes events atomically
 */
 
typedef enum {
    EVENT_REQUEST,
    EVENT_RELEASE,
    EVENT_TERMINATE
} EventType;
 
typedef struct {
    EventType type;
    int process_id;
    int resources[MAX_R];
} Event;
 
typedef struct {
    int n, m;
    int available[MAX_R];
    int allocation[MAX_P][MAX_R];
    int need[MAX_P][MAX_R];
    bool process_active[MAX_P];
} SystemState;
 
/* Process a request event */
typedef enum { GRANTED, BLOCKED, INVALID } RequestResult;
 
RequestResult process_request(SystemState* s, int pid, int request[]) {
    // Validate: request ≤ need
    for (int j = 0; j < s->m; j++) {
        if (request[j] > s->need[pid][j]) {
            return INVALID;  // Exceeds declared maximum
        }
    }
    
    // Check: request ≤ available
    for (int j = 0; j < s->m; j++) {
        if (request[j] > s->available[j]) {
            return BLOCKED;  // Must wait
        }
    }
    
    // Tentatively allocate
    for (int j = 0; j < s->m; j++) {
        s->available[j] -= request[j];
        s->allocation[pid][j] += request[j];
        s->need[pid][j] -= request[j];
    }
    
    // Check safety of new state (if using avoidance)
    int seq[MAX_P], len;
    if (!safety_algorithm(s->n, s->m, s->available, s->allocation, s->need, seq, &len)) {
        // UNSAFE! Roll back the allocation
        for (int j = 0; j < s->m; j++) {
            s->available[j] += request[j];
            s->allocation[pid][j] -= request[j];
            s->need[pid][j] += request[j];
        }
        return BLOCKED;  // Deny request to stay safe
    }
    
    return GRANTED;
}
 
/* Process a release event */
void process_release(SystemState* s, int pid, int release[]) {
    for (int j = 0; j < s->m; j++) {
        s->available[j] += release[j];
        s->allocation[pid][j] -= release[j];
        // Note: need doesn't decrease on release (process already has less)
    }
    
    // After release, check if any blocked process can proceed
    // (This would involve scanning a wait queue—omitted for brevity)
}
 
/* Process a termination event */
void process_terminate(SystemState* s, int pid) {
    // Release all held resources
    for (int j = 0; j < s->m; j++) {
        s->available[j] += s->allocation[pid][j];
        s->allocation[pid][j] = 0;
        s->need[pid][j] = 0;
    }
    s->process_active[pid] = false;
}
 
/*
 * INVARIANTS TO MAINTAIN ACROSS ALL TRANSITIONS:
 * 
 * 1. Conservation: ∀j: available[j] + Σᵢ allocation[i][j] = total[j]
 * 2. Validity: ∀i,j: allocation[i][j] ≤ max[i][j]
 * 3. Non-negative: ∀i,j: allocation[i][j] ≥ 0, available[j] ≥ 0, need[i][j] ≥ 0
 * 4. Safety (if using avoidance): State remains in safe region
 */

Atomicity Is Critical

State transition operations must be atomic—completed entirely or not at all. If a request is granted but the process is interrupted before updating Available, the state becomes inconsistent. Real implementations use locks around state transitions and often log operations for crash recovery.

Summary: The System Model Foundation

The system model provides the formal framework for all deadlock analysis. With this foundation, we can precisely specify, detect, prevent, and avoid deadlock.

Key Takeaways

•The system model consists of processes, resource types, and matrices (Allocation, Max, Need, Request, Available) that capture the complete state of resource allocation at any moment.
•Conservation invariants ensure resources are neither created nor destroyed during operation: Available + Total Allocated = Total Resources.
•Processes follow the Request-Use-Release protocol, making explicit requests, using acquired resources, then releasing them. This structured behavior enables formal analysis.
•Safe states guarantee freedom from deadlock—there exists at least one sequence in which all processes can complete. Unsafe states carry deadlock risk.
•The Safety Algorithm determines state safety by simulating process completion, running in O(n² × m) time—practical for small systems, expensive for large ones.
•State transitions occur atomically through request, release, and termination events, each updating the system matrices while maintaining invariants.
•The model abstracts implementation details to enable analysis across different OS implementations, programming languages, and hardware platforms.

What's Next:

With the formal system model established, we're ready to explore real-world examples of deadlock. These examples will ground the abstract theory in concrete scenarios—from database transactions to device driver conflicts to distributed system communication patterns. Seeing deadlock in action makes the theory tangible.

Page Complete

You now possess the formal vocabulary and mathematical framework for deadlock analysis. The system model—with its processes, resources, matrices, and state transition rules—is the lens through which all deadlock phenomena become analyzable. This foundation supports everything from simple lock ordering to sophisticated avoidance algorithms.

3 / 5

Loading learning content...

Operating SystemsDeadlock Concepts

Understanding Deadlock Concepts

LevelIntermediate

Duration60 mins

TopicDeadlock Concepts

3 / 5

System Model

Modeling Reality for Rigorous Analysis

What You Will Learn

Components of the System Model

The system model for deadlock analysis consists of four fundamental components that interact according to well-defined rules.

Model Components

•Processes (P): A finite set P = {P₁, P₂, ..., Pₙ} of n processes. Each process executes a sequence of operations that may include resource requests and releases. Processes are the active entities that compete for resources.
•Resource Types (R): A finite set R = {R₁, R₂, ..., Rₘ} of m resource types. Each resource type Rⱼ has a fixed number of identical instances, denoted as Total[j]. The total vector T = [T₁, T₂, ..., Tₘ] represents the total instances of each type in the system.
•Allocation State (A): An n×m matrix where A[i,j] represents the number of instances of resource type Rⱼ currently allocated to process Pᵢ. This matrix captures who holds what at any given moment.
•Request State (Q or Need): An n×m matrix where Q[i,j] (or Need[i,j]) represents the number of additional instances of Rⱼ that Pᵢ may still request. In the Banker's Algorithm, this is Max[i,j] - Allocation[i,j].

Available Resources Vector:

At any point in time, the system has a vector of available resources:

Available[j] = Total[j] - Σᵢ Allocation[i,j]

This vector represents the pool of unallocated instances of each resource type. It's computed by subtracting all allocated resources from the total.

The Conservation Invariant:

For reusable resources, the following invariant always holds:

Available + (sum of all allocations per resource type) = Total

Or equivalently: ∀j: Available[j] + Σᵢ A[i,j] = Total[j]

This conservation law is fundamental—resources can be allocated or available, but the total never changes. This property makes the mathematics tractable.

system_model.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
#include <stdio.h>
#include <stdbool.h>
 
#define MAX_PROCESSES 10
#define MAX_RESOURCES 5
 
typedef struct {
    int n;  // Number of processes
    int m;  // Number of resource types
    
    // Total instances of each resource type
    int total[MAX_RESOURCES];
    
    // Available instances (computed from total - allocated)
    int available[MAX_RESOURCES];
    
    // Allocation matrix: allocation[i][j] = instances of Rj held by Pi
    int allocation[MAX_PROCESSES][MAX_RESOURCES];
    
    // Need matrix: need[i][j] = additional instances of Rj that Pi may request
    // In Banker's: need[i][j] = max[i][j] - allocation[i][j]
    int need[MAX_PROCESSES][MAX_RESOURCES];
    
    // Maximum demand (for Banker's Algorithm)
    int max[MAX_PROCESSES][MAX_RESOURCES];
    
} SystemState;
 
/* Recompute available vector from allocation */
void compute_available(SystemState* state) {
    for (int j = 0; j < state->m; j++) {
        int allocated = 0;
        for (int i = 0; i < state->n; i++) {
            allocated += state->allocation[i][j];
        }
        state->available[j] = state->total[j] - allocated;
    }
}
 
/* Verify the conservation invariant holds */
bool verify_conservation(SystemState* state) {
    for (int j = 0; j < state->m; j++) {
        int sum = state->available[j];
        for (int i = 0; i < state->n; i++) {
            sum += state->allocation[i][j];
        }
        if (sum != state->total[j]) {
            printf("INVARIANT VIOLATION: Resource %d, expected %d got %d
", 
                   j, state->total[j], sum);
            return false;
        }
    }
    return true;
}
 
/* Example: Initialize a system state */
void example_system() {
    SystemState state;
    state.n = 3;  // 3 processes
    state.m = 3;  // 3 resource types
    
    // Total resources: [10, 5, 7]
    state.total[0] = 10; state.total[1] = 5; state.total[2] = 7;
    
    // Current allocations
    // P0 holds [0, 1, 0], P1 holds [2, 0, 0], P2 holds [3, 0, 2]
    state.allocation[0][0] = 0; state.allocation[0][1] = 1; state.allocation[0][2] = 0;
    state.allocation[1][0] = 2; state.allocation[1][1] = 0; state.allocation[1][2] = 0;
    state.allocation[2][0] = 3; state.allocation[2][1] = 0; state.allocation[2][2] = 2;
    
    compute_available(&state);
    // Available = [10-0-2-3, 5-1-0-0, 7-0-0-2] = [5, 4, 5]
    
    printf("Available: [%d, %d, %d]
", 
           state.available[0], state.available[1], state.available[2]);
    
    verify_conservation(&state);
}

Process Behavior Model

The system model makes specific assumptions about how processes behave. These assumptions simplify analysis while capturing the essential patterns that lead to deadlock.

The Request-Use-Release Protocol:

Every process follows a structured lifecycle when interacting with resources:

Request: The process asks the system to allocate one or more resource instances. The request must not exceed the process's declared maximum need. The process blocks if the request cannot be immediately satisfied.
Use: Once granted, the process uses the resource to perform its work. The system model assumes this phase is finite—the process will eventually move to release.
Release: When finished with the resource, the process explicitly releases it back to the system, making it available for other processes.

This cycle may repeat many times during a process's lifetime, acquiring and releasing different resources.

Converting Mermaid diagram...

Key Assumptions About Process Behavior:

Process Model Assumptions
Assumption	Formal Statement	Why It Matters
Finite Resource Need	∀i,j: Need[i,j] ≤ Max[i,j] ≤ Total[j]	Prevents unbounded requests that can't ever be satisfied
Bounded Hold Time	If granted, process releases in finite time	Enables eventually-terminates arguments
Atomic Request/Release	Single resource operation is indivisible	Prevents race conditions in allocation logic
Request Before Use	Process doesn't use until request granted	Ensures valid allocation state
Correct Declaration	Declared max is honest upper bound	Banker's Algorithm depends on this honesty
No Early Release	Resources held until explicitly released	Simplifies state tracking

When Assumptions Fail

The Allocation Matrix

Matrix Structure:

Allocation Matrix A (n processes × m resource types)

              R₁  R₂  R₃  ...  Rₘ
         P₁ [ a₁₁ a₁₂ a₁₃ ... a₁ₘ ]
         P₂ [ a₂₁ a₂₂ a₂₃ ... a₂ₘ ]
         P₃ [ a₃₁ a₃₂ a₃₃ ... a₃ₘ ]
         ...[ ... ... ... ... ... ]
         Pₙ [ aₙ₁ aₙ₂ aₙ₃ ... aₙₘ ]

Where:

Row i (Allocation_i) = resources currently held by process Pᵢ
Column j = how resource type Rⱼ is distributed among processes
Entry a_ij = number of instances of Rⱼ allocated to Pᵢ

Operations on the Allocation Matrix:

allocation_matrix_ops.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
/* Allocation Matrix Operations */
 
typedef struct {
    int n, m;                         // Dimensions
    int allocation[MAX_P][MAX_R];     // The matrix
    int available[MAX_R];             // Available vector
    int total[MAX_R];                 // Total instances
} AllocationState;
 
/* Operation: Allocate resources to a process */
bool allocate(AllocationState* s, int process, int request[]) {
    // Check if request can be satisfied
    for (int j = 0; j < s->m; j++) {
        if (request[j] > s->available[j]) {
            return false;  // Insufficient resources
        }
    }
    
    // Perform allocation
    for (int j = 0; j < s->m; j++) {
        s->allocation[process][j] += request[j];
        s->available[j] -= request[j];
    }
    return true;
}
 
/* Operation: Release resources from a process */
void release(AllocationState* s, int process, int release_vec[]) {
    for (int j = 0; j < s->m; j++) {
        // Sanity check: can't release more than held
        if (release_vec[j] > s->allocation[process][j]) {
            // Error handling...
        }
        s->allocation[process][j] -= release_vec[j];
        s->available[j] += release_vec[j];
    }
}
 
/* Query: Total resources held by a process */
void get_process_resources(AllocationState* s, int process, int result[]) {
    for (int j = 0; j < s->m; j++) {
        result[j] = s->allocation[process][j];
    }
}
 
/* Query: How is a resource type distributed? */
void get_resource_distribution(AllocationState* s, int resource, int holders[], int* count) {
    *count = 0;
    for (int i = 0; i < s->n; i++) {
        if (s->allocation[i][resource] > 0) {
            holders[(*count)++] = i;
        }
    }
}
 
/* Query: Is process waiting (has need but holds less)? */
bool is_waiting(AllocationState* s, int process, int need[]) {
    for (int j = 0; j < s->m; j++) {
        if (need[j] > s->available[j]) {
            return true;  // Needs something that's not available
        }
    }
    return false;
}
 
/* 
 * CRITICAL INVARIANT: After any operation:
 * ∀j: s->available[j] + Σᵢ s->allocation[i][j] == s->total[j]
 * 
 * Violations indicate bugs in allocation logic!
 */

Worked Example:

Consider a system with 3 processes and 4 resource types:

	R₁	R₂	R₃	R₄
Total	6	4	7	2
P₀ holds	1	0	2	0
P₁ holds	2	1	1	1
P₂ holds	0	1	0	0
Available	3	2	4	1

Verification:

R₁: 1 + 2 + 0 + 3 = 6 ✓
R₂: 0 + 1 + 1 + 2 = 4 ✓
R₃: 2 + 1 + 0 + 4 = 7 ✓
R₄: 0 + 1 + 0 + 1 = 2 ✓

The conservation invariant holds. This state can be analyzed for deadlock potential.

The Need and Request Matrices

Maximum Demand Matrix (Max)

•Definition: Max[i,j] = maximum instances of Rⱼ that Pᵢ will EVER need simultaneously
•Declared: by process at creation time
•Used by: Banker's Algorithm for avoidance
•Constraint: Max[i,j] ≤ Total[j] always
•Interpretation: Upper bound on demand

Need Matrix

•Definition: Need[i,j] = Max[i,j] - Allocation[i,j]
•Computed: from Max and Allocation
•Used by: Safety algorithm to check completion
•Constraint: Need[i,j] ≥ 0 always
•Interpretation: What more might be requested

The Request Matrix:

While Max and Need represent potential future demands, the Request matrix captures current pending requests—resources that have been asked for but not yet granted:

Request[i,j] = instances of Rⱼ that Pᵢ has requested and is waiting for

The Request matrix is more dynamic than Need—it changes whenever a process makes a request or gets a grant. The Need matrix is an upper bound; Request is the current specific demand.

Matrix	Represents	Changes When
Max	Lifetime maximum need	Set at process creation, fixed
Allocation	Currently held	Request granted or release executed
Need	Max - Allocation	Allocation changes
Request	Currently pending	Request made or granted

need_matrix.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
/* Need Matrix Computation and Validation */
 
typedef struct {
    int max[MAX_P][MAX_R];        // Maximum demand (declared)
    int allocation[MAX_P][MAX_R]; // Currently held
    int need[MAX_P][MAX_R];       // Max - Allocation (derived)
    int request[MAX_P][MAX_R];    // Currently pending requests
} DeadlockState;
 
/* Recompute need matrix from max and allocation */
void compute_need(DeadlockState* s, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            s->need[i][j] = s->max[i][j] - s->allocation[i][j];
            
            // Invariant check: need should never be negative
            if (s->need[i][j] < 0) {
                printf("ERROR: Process %d allocated more than max for resource %d
", i, j);
                // This indicates a bug—allocated more than maximum!
            }
        }
    }
}
 
/* Validate a request against declared maximum */
bool validate_request(DeadlockState* s, int process, int request[], int m) {
    for (int j = 0; j < m; j++) {
        // Request must not exceed remaining need
        if (request[j] > s->need[process][j]) {
            printf("ERROR: Process %d requesting %d of R%d but need is only %d
",
                   process, request[j], j, s->need[process][j]);
            return false;
        }
    }
    return true;
}
 
/* Example: A process makes a request */
bool make_request(DeadlockState* s, int available[], int process, int request[], int m) {
    // Step 1: Validate request doesn't exceed need
    if (!validate_request(s, process, request, m)) {
        return false;  // Invalid request
    }
    
    // Step 2: Check if resources are available
    for (int j = 0; j < m; j++) {
        if (request[j] > available[j]) {
            // Resources not available—process must wait
            for (int k = 0; k < m; k++) {
                s->request[process][k] = request[k];  // Record pending request
            }
            return false;  // Return false to indicate blocking
        }
    }
    
    // Step 3: Resources available—tentatively allocate
    // (In Banker's, we'd also check if resulting state is safe)
    for (int j = 0; j < m; j++) {
        available[j] -= request[j];
        s->allocation[process][j] += request[j];
        s->need[process][j] -= request[j];
        s->request[process][j] = 0;  // Request satisfied
    }
    
    return true;  // Success
}

The Honesty Assumption

Safe and Unsafe States

Safe State Definition:

A system state is safe if there exists a sequence of process completions (called a safe sequence) such that:

Each process in the sequence can acquire its remaining needed resources from currently available resources plus resources held by all previously completed processes in the sequence
Once a process completes, it releases all its resources back to the available pool
All processes eventually complete

Formally, a safe sequence is a permutation ⟨P₁, P₂, ..., Pₙ⟩ of all n processes such that for each Pᵢ:

Need[i] ≤ Available + Σⱼ₍ⱼ<ᵢ₎ Allocation[j]

In other words, when it's Pᵢ's turn in the sequence, enough resources are available (either initially or from earlier completions) to satisfy its needs.

Safe State

•At least one safe sequence exists
•Guaranteed: NO deadlock if we stay in safe states
•Processes CAN complete if we schedule carefully
•May have multiple safe sequences
•System has escape path from current state

Unsafe State

•No safe sequence exists
•NOT guaranteed: deadlock is possible, not certain
•Some resource requests might lead to deadlock
•May still avoid deadlock with luck
•System has entered risky territory

Unsafe ≠ Deadlocked

Converting Mermaid diagram...

Relationship Between State Categories:

Safe States ⊂ All Non-Deadlock States
Deadlock States ⊂ Unsafe States
Unsafe States = Potential Deadlock States ∪ Lucky Completion States

The key insight is that Safe States and Deadlock States are non-overlapping, but Unsafe States include both inevitable deadlocks and states that happen to work out.

The Safety Algorithm

The Safety Algorithm determines whether a given system state is safe by attempting to find a safe sequence. This algorithm is central to the Banker's Algorithm for deadlock avoidance.

safety_algorithm.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
#include <stdbool.h>
#include <string.h>
 
#define MAX_P 10
#define MAX_R 5
 
/*
 * THE SAFETY ALGORITHM
 * 
 * Input:
 *   - n: number of processes
 *   - m: number of resource types
 *   - available[m]: currently available resources
 *   - allocation[n][m]: current allocation matrix
 *   - need[n][m]: remaining need matrix (max - allocation)
 * 
 * Output:
 *   - true if state is safe, false otherwise
 *   - safe_sequence[n]: a valid safe sequence if one exists
 */
bool safety_algorithm(
    int n, int m,
    int available[],
    int allocation[][MAX_R],
    int need[][MAX_R],
    int safe_sequence[],      // Output: the safe sequence
    int* sequence_length      // Output: length of sequence (should be n if safe)
) {
    // Step 1: Initialize working variables
    int work[MAX_R];
    bool finish[MAX_P];
    
    for (int j = 0; j < m; j++) {
        work[j] = available[j];  // Work = Available initially
    }
    for (int i = 0; i < n; i++) {
        finish[i] = false;       // No process finished yet
    }
    
    *sequence_length = 0;
    
    // Step 2: Find a process that can finish with current work
    while (true) {
        // Find unfinished process whose need ≤ work
        int found = -1;
        for (int i = 0; i < n; i++) {
            if (!finish[i]) {
                // Check if need[i] ≤ work
                bool can_finish = true;
                for (int j = 0; j < m; j++) {
                    if (need[i][j] > work[j]) {
                        can_finish = false;
                        break;
                    }
                }
                
                if (can_finish) {
                    found = i;
                    break;
                }
            }
        }
        
        // Step 3: Process found or no more candidates
        if (found == -1) {
            break;  // No process can proceed
        }
        
        // Found a process that can complete
        // Simulate: process finishes and releases resources
        for (int j = 0; j < m; j++) {
            work[j] += allocation[found][j];
        }
        finish[found] = true;
        safe_sequence[(*sequence_length)++] = found;
    }
    
    // Step 4: Check if all processes finished
    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            return false;  // UNSAFE: some process couldn't finish
        }
    }
    
    return true;  // SAFE: found a safe sequence
}
 
/* Example usage */
void safety_example() {
    int n = 5, m = 3;
    
    int available[] = {3, 3, 2};
    
    int allocation[5][MAX_R] = {
        {0, 1, 0},  // P0
        {2, 0, 0},  // P1
        {3, 0, 2},  // P2
        {2, 1, 1},  // P3
        {0, 0, 2}   // P4
    };
    
    int need[5][MAX_R] = {
        {7, 4, 3},  // P0 needs
        {1, 2, 2},  // P1 needs
        {6, 0, 0},  // P2 needs
        {0, 1, 1},  // P3 needs
        {4, 3, 1}   // P4 needs
    };
    
    int safe_sequence[5];
    int length;
    
    if (safety_algorithm(n, m, available, allocation, need, safe_sequence, &length)) {
        printf("SAFE STATE
");
        printf("Safe sequence: ");
        for (int i = 0; i < length; i++) {
            printf("P%d ", safe_sequence[i]);
        }
        printf("
");
        // Output: Safe sequence: P1 P3 P4 P0 P2
    } else {
        printf("UNSAFE STATE
");
    }
}

Algorithm Complexity Analysis:

Operation	Complexity	Notes
Finding one candidate	O(n × m)	Check each process's need vs. work
Finding all n candidates	O(n² × m)	Each of n iterations scans up to n processes
Overall Safety Algorithm	O(n² × m)	Dominates any constant-time operations

Multiple Safe Sequences

State Transitions and System Evolution

The system state changes over time as processes make requests, receive allocations, and release resources. Understanding how states transition is crucial for maintaining deadlock-free operation.

State Transition Events:

The system state S = (Allocation, Available, Need, Request) changes due to three types of events:

Request Event: Process Pᵢ requests resources R
- If R ≤ Available AND resulting state is safe: Grant the request, update Allocation and Available
- Otherwise: Block the process, record pending request
Release Event: Process Pᵢ releases resources R
- Always succeeds (process owns the resources)
- Update: Allocation[i] -= R, Available += R
- May enable blocked processes to proceed
Process Completion: Process Pᵢ terminates
- Implicitly releases all held resources
- Remove process from active set
- Update all tracking structures

state_transitions.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
/*
 * State Transition Manager
 * Maintains system state and processes events atomically
 */
 
typedef enum {
    EVENT_REQUEST,
    EVENT_RELEASE,
    EVENT_TERMINATE
} EventType;
 
typedef struct {
    EventType type;
    int process_id;
    int resources[MAX_R];
} Event;
 
typedef struct {
    int n, m;
    int available[MAX_R];
    int allocation[MAX_P][MAX_R];
    int need[MAX_P][MAX_R];
    bool process_active[MAX_P];
} SystemState;
 
/* Process a request event */
typedef enum { GRANTED, BLOCKED, INVALID } RequestResult;
 
RequestResult process_request(SystemState* s, int pid, int request[]) {
    // Validate: request ≤ need
    for (int j = 0; j < s->m; j++) {
        if (request[j] > s->need[pid][j]) {
            return INVALID;  // Exceeds declared maximum
        }
    }
    
    // Check: request ≤ available
    for (int j = 0; j < s->m; j++) {
        if (request[j] > s->available[j]) {
            return BLOCKED;  // Must wait
        }
    }
    
    // Tentatively allocate
    for (int j = 0; j < s->m; j++) {
        s->available[j] -= request[j];
        s->allocation[pid][j] += request[j];
        s->need[pid][j] -= request[j];
    }
    
    // Check safety of new state (if using avoidance)
    int seq[MAX_P], len;
    if (!safety_algorithm(s->n, s->m, s->available, s->allocation, s->need, seq, &len)) {
        // UNSAFE! Roll back the allocation
        for (int j = 0; j < s->m; j++) {
            s->available[j] += request[j];
            s->allocation[pid][j] -= request[j];
            s->need[pid][j] += request[j];
        }
        return BLOCKED;  // Deny request to stay safe
    }
    
    return GRANTED;
}
 
/* Process a release event */
void process_release(SystemState* s, int pid, int release[]) {
    for (int j = 0; j < s->m; j++) {
        s->available[j] += release[j];
        s->allocation[pid][j] -= release[j];
        // Note: need doesn't decrease on release (process already has less)
    }
    
    // After release, check if any blocked process can proceed
    // (This would involve scanning a wait queue—omitted for brevity)
}
 
/* Process a termination event */
void process_terminate(SystemState* s, int pid) {
    // Release all held resources
    for (int j = 0; j < s->m; j++) {
        s->available[j] += s->allocation[pid][j];
        s->allocation[pid][j] = 0;
        s->need[pid][j] = 0;
    }
    s->process_active[pid] = false;
}
 
/*
 * INVARIANTS TO MAINTAIN ACROSS ALL TRANSITIONS:
 * 
 * 1. Conservation: ∀j: available[j] + Σᵢ allocation[i][j] = total[j]
 * 2. Validity: ∀i,j: allocation[i][j] ≤ max[i][j]
 * 3. Non-negative: ∀i,j: allocation[i][j] ≥ 0, available[j] ≥ 0, need[i][j] ≥ 0
 * 4. Safety (if using avoidance): State remains in safe region
 */

Atomicity Is Critical

Summary: The System Model Foundation

The system model provides the formal framework for all deadlock analysis. With this foundation, we can precisely specify, detect, prevent, and avoid deadlock.

Key Takeaways

•The system model consists of processes, resource types, and matrices (Allocation, Max, Need, Request, Available) that capture the complete state of resource allocation at any moment.
•Conservation invariants ensure resources are neither created nor destroyed during operation: Available + Total Allocated = Total Resources.
•Processes follow the Request-Use-Release protocol, making explicit requests, using acquired resources, then releasing them. This structured behavior enables formal analysis.
•Safe states guarantee freedom from deadlock—there exists at least one sequence in which all processes can complete. Unsafe states carry deadlock risk.
•The Safety Algorithm determines state safety by simulating process completion, running in O(n² × m) time—practical for small systems, expensive for large ones.
•State transitions occur atomically through request, release, and termination events, each updating the system matrices while maintaining invariants.
•The model abstracts implementation details to enable analysis across different OS implementations, programming languages, and hardware platforms.

What's Next:

Page Complete

3 / 5