Hugo's Cyber Heritage

Shine or Die

OS-07 Deadlocks

Posted on Edited on In
Symbols count in article: 11k Reading time ≈ 10 mins.

Notes on deadlocks in operating systems.

System Model

Notations:

  • Threads T1, T2, …, Tn
  • Resource types R1, R2, …, Rm
    • e.g., CPU, memory space, I/O devices, mutex and semaphores
  • Each resource type Ri has Wi instances.

Definition: a set of threads is in a deadlocked state when every thread in the set is waiting for an event that can only be caused by another thread in the set. These events are mainly the acquisition and release of resources.

e.g. two vehicles travelling in opposite directions meeting on a single-lane road

Deadlock Characterization

A deadlock arises when the following four conditions hold simultaneously:

  • Mutual Exclusion: at that moment the resource is held exclusively by one thread
  • Hold and Wait: a thread is waiting for another thread to release a resource
  • No Preemption: a thread cannot preempt the resources of another thread
  • Circular Wait: a set of threads forms a cycle, each waiting for another thread to release a resource

Resource-Allocation Graph

The Resource-Allocation Graph (RAG) is a directed graph used to represent the relationships of resource allocation and requests.

  • Nodes represent processes and resources
  • Edges represent processes’ requests for and releases of resources

Methods for Handling Deadlocks

  • Never enters a deadlock
    • Deadlock prevention
    • Deadlock avoidance
  • Detect and recover from deadlock
    • Deadlock detection
    • Recovery from deadlock

Deadlock Prevention

Break one of the four conditions:

  • Mutual exclusion: remove the mutual exclusion of shared resources
  • Hold and wait: request all resources at once / only request resources when holding none
  • No preemption: allow resources to be preempted
  • Circular wait: impose an ordering on resources

Deadlock Avoidance

Requires additional information:

  • The maximum demand of each process for each type of resource
  • The number of available instances of each type of resource

safe state: a sequence is safe if, for every process, it can complete in finite time and the resources it needs can be satisfied by the currently available resources plus the resources previously allocated

Resource allocation policy: allocate resources when a safe sequence exists

resource-allocation-graph algorithm

  1. Related concepts: a new concept is introduced, the claim edge, drawn as a dashed directed edge Ti → Rj, meaning thread Ti may request resource Rj. When the thread requests the resource, the claim edge is converted into a request edge; when the resource is allocated to the thread, the request edge is converted into an assignment edge; when the thread releases the resource, the assignment edge is converted back into a claim edge (if the thread terminates, the edge is removed).
  2. Core decision of the algorithm: when thread Ti requests resource Rj, the request can be granted only if converting the request edge into an assignment edge does not create a cycle in the resource-allocation graph. If a cycle would be formed, a deadlock may occur, so the request cannot be granted and the thread must wait. For example, if thread T1 requests resource R1 and, starting from the current resource-allocation graph, converting the request edge from T1 to R1 into an assignment edge would produce a cycle such as T1 → R1 → T2 → R2 → T1, then T1‘s request for R1 cannot be granted and T1 has to wait

Banker’s Algorithm

The Banker’s Algorithm is a well-known deadlock avoidance algorithm. It gets its name because the algorithm was originally the strategy a bank uses to allocate its resources.

Basic Concepts

  1. Data structures

    • Available: a vector of length m, the number of available instances of each resource type
    • Max: an n×m matrix, the maximum demand of each process for each resource type
    • Allocation: an n×m matrix, the number of instances of each resource type currently allocated to each process
    • Need: an n×m matrix, the number of instances of each resource type each process still needs
      where n is the number of processes and m is the number of resource types

  2. Safe state
    The system is in a safe state if there exists a safe sequence such that all processes can complete in that order.

Algorithm Flow
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
#include <stdio.h>
#include <stdbool.h>

// Define the number of threads and the number of resource types
#define N 5
#define M 3

// Safety check function
bool isSafe(int available[], int max[][M], int allocation[][M], int need[][M], int *safeSequence) {
    int work[M];
    bool finish[N] = {false};
    int count = 0;

    // Initialize the work vector
    for (int i = 0; i < M; i++) {
        work[i] = available[i];
    }

    // Look for a safe sequence
    while (count < N) {
        bool found = false;
        for (int i = 0; i < N; i++) {
            if (!finish[i]) {
                int j;
                for (j = 0; j < M; j++) {
                    if (need[i][j] > work[j]) {
                        break;
                    }
                }
                if (j == M) {
                    // thread i's need can be satisfied
                    for (int k = 0; k < M; k++) {
                        work[k] += allocation[i][k];
                    }
                    safeSequence[count++] = i;
                    finish[i] = true;
                    found = true;
                }
            }
        }
        if (!found) {
            break;
        }
    }

    return count == N;
}

// Resource request handling function
bool requestResources(int available[], int max[][M], int allocation[][M], int need[][M], int request[], int threadId) {
    // Check whether the request exceeds the maximum need
    for (int i = 0; i < M; i++) {
        if (request[i] > need[threadId][i]) {
            printf("Thread %d requested more resources than its maximum need, error!\n", threadId);
            return false;
        }
    }

    // Check whether the request exceeds the available resources
    for (int i = 0; i < M; i++) {
        if (request[i] > available[i]) {
            printf("Thread %d requested more resources than are available, waiting!\n", threadId);
            return false;
        }
    }

    // Try to allocate the resources
    for (int i = 0; i < M; i++) {
        available[i] -= request[i];
        allocation[threadId][i] += request[i];
        need[threadId][i] -= request[i];
    }

    int safeSequence[N];
    if (isSafe(available, max, allocation, need, safeSequence)) {
        printf("Thread %d's resource request has been granted!\n", threadId);
        return true;
    } else {
        // Restore the resource allocation state
        for (int i = 0; i < M; i++) {
            available[i] += request[i];
            allocation[threadId][i] -= request[i];
            need[threadId][i] += request[i];
        }
        printf("Thread %d's resource request would lead to deadlock, waiting!\n", threadId);
        return false;
    }
}

int main() {
    // Initialize resource information
    int available[M] = {3, 3, 2};
    int max[N][M] = {
        {7, 5, 3},
        {3, 2, 2},
        {9, 0, 2},
        {2, 2, 2},
        {4, 3, 3}
    };
    int allocation[N][M] = {
        {0, 1, 0},
        {2, 0, 0},
        {3, 0, 2},
        {2, 1, 1},
        {0, 0, 2}
    };
    int need[N][M];

    // Compute the Need matrix
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }

    // Check whether the initial state is safe
    int safeSequence[N];
    if (isSafe(available, max, allocation, need, safeSequence)) {
        printf("System is in a safe state, safe sequence: ");
        for (int i = 0; i < N; i++) {
            printf("T%d ", safeSequence[i]);
        }
        printf("\n");
    } else {
        printf("System is in an unsafe state!\n");
    }

    // Handle thread requests
    int request[M] = {1, 0, 2};
    int threadId = 1;
    requestResources(available, max, allocation, need, request, threadId);

    return 0;
}

Deadlock Detection

Single instance of each resource type: maintain a wait-for graph

Multiple instances of each resource type:

  • available vector
  • allocation matrix
  • request matrix
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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_PROCESSES 100
#define MAX_RESOURCES 100

/**
 * @brief Data structure for the deadlock detection algorithm
 */
typedef struct {
    int available[MAX_RESOURCES];     // available resource vector
    int allocation[MAX_PROCESSES][MAX_RESOURCES];    // allocation matrix
    int request[MAX_PROCESSES][MAX_RESOURCES];       // request matrix
    int num_processes;    // number of processes
    int num_resources;    // number of resource types
} SystemState;

/**
 * @brief Check whether a process can finish
 */
bool can_process_finish(int process_id, bool* finished, int* work, SystemState* state) {
    // Check whether all requests can be satisfied
    for (int j = 0; j < state->num_resources; j++) {
        if (state->request[process_id][j] > work[j]) {
            return false;
        }
    }
    return true;
}

/**
 * @brief Update the work vector
 */
void update_work_vector(int process_id, int* work, SystemState* state) {
    for (int j = 0; j < state->num_resources; j++) {
        work[j] += state->allocation[process_id][j];
    }
}

/**
 * @brief Main function of the deadlock detection algorithm
 * @return number of deadlocked processes, 0 means no deadlock
 */
int detect_deadlock(SystemState* state, int* deadlocked_processes) {
    bool* finished = (bool*)calloc(state->num_processes, sizeof(bool));
    int* work = (int*)malloc(state->num_resources * sizeof(int));
    int deadlock_count = 0;
    
    // Initialize the work vector
    for (int i = 0; i < state->num_resources; i++) {
        work[i] = state->available[i];
    }

    // Mark processes with no requests as finished
    for (int i = 0; i < state->num_processes; i++) {
        bool has_request = false;
        for (int j = 0; j < state->num_resources; j++) {
            if (state->request[i][j] > 0) {
                has_request = true;
                break;
            }
        }
        if (!has_request) {
            finished[i] = true;
        }
    }

    // Main loop of deadlock detection
    bool changed;
    do {
        changed = false;
        for (int i = 0; i < state->num_processes; i++) {
            if (!finished[i] && can_process_finish(i, finished, work, state)) {
                finished[i] = true;
                update_work_vector(i, work, state);
                changed = true;
            }
        }
    } while (changed);

    // Count the deadlocked processes
    for (int i = 0; i < state->num_processes; i++) {
        if (!finished[i]) {
            deadlocked_processes[deadlock_count++] = i;
        }
    }

    free(finished);
    free(work);
    return deadlock_count;
}

/**
 * @brief Print the deadlock detection result
 */
void print_deadlock_result(int* deadlocked_processes, int count) {
    if (count == 0) {
        printf("No deadlock in the system\n");
    } else {
        printf("Deadlock detected! The following processes are deadlocked:\n");
        for (int i = 0; i < count; i++) {
            printf("Process P%d\n", deadlocked_processes[i]);
        }
    }
}

/**
 * @brief Example usage
 */
int main() {
    SystemState state = {
        .num_processes = 3,
        .num_resources = 3,
        .available = {0, 0, 0},  // currently available resources
        .allocation = {          // allocated resources
            {3, 3, 3},
            {2, 0, 3},
            {1, 2, 4}
        },
        .request = {            // requested resources
            {0, 1, 0},
            {2, 0, 0},
            {0, 0, 2}
        }
    };

    int deadlocked_processes[MAX_PROCESSES];
    int deadlock_count = detect_deadlock(&state, deadlocked_processes);
    
    print_deadlock_result(deadlocked_processes, deadlock_count);
    
    return 0;
}

Core of the algorithm: use the work vector and the finish vector to decide whether a deadlock exists, iterating in a loop to find processes that can complete

When using the detection algorithm, one has to consider overheads such as how often deadlocks occur and how many threads must be rolled back

Recovery from Deadlock

  • Process termination: terminate one or more processes until the deadlock is broken
  • Resource preemption: preempt resources from one or more processes until the deadlock is broken

Translated from the Chinese original.

Welcome to my other publishing channels

中文