Hugo's Cyber Heritage

Shine or Die

OS-07 Deadlocks

Posted on Edited on In
Symbols count in article: 9.7k Reading time ≈ 9 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 N 5
#define M 3

// 安全状态检查函数
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;

    // 初始化work向量
    for (int i = 0; i < M; i++) {
        work[i] = available[i];
    }

    // 寻找安全序列
    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) {
                    // 可以满足线程i的需求
                    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;
}

// 资源请求处理函数
bool requestResources(int available[], int max[][M], int allocation[][M], int need[][M], int request[], int threadId) {
    // 检查请求是否超过最大需求
    for (int i = 0; i < M; i++) {
        if (request[i] > need[threadId][i]) {
            printf("线程 %d 请求的资源超过最大需求，错误！\n", threadId);
            return false;
        }
    }

    // 检查请求是否超过可用资源
    for (int i = 0; i < M; i++) {
        if (request[i] > available[i]) {
            printf("线程 %d 请求的资源超过可用资源，等待！\n", threadId);
            return false;
        }
    }

    // 尝试分配资源
    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("线程 %d 的资源请求已批准！\n", threadId);
        return true;
    } else {
        // 恢复资源分配状态
        for (int i = 0; i < M; i++) {
            available[i] += request[i];
            allocation[threadId][i] -= request[i];
            need[threadId][i] += request[i];
        }
        printf("线程 %d 的资源请求会导致死锁，等待！\n", threadId);
        return false;
    }
}

int main() {
    // 初始化资源信息
    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];

    // 计算Need矩阵
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }

    // 检查初始状态是否安全
    int safeSequence[N];
    if (isSafe(available, max, allocation, need, safeSequence)) {
        printf("系统处于安全状态，安全序列: ");
        for (int i = 0; i < N; i++) {
            printf("T%d ", safeSequence[i]);
        }
        printf("\n");
    } else {
        printf("系统处于不安全状态！\n");
    }

    // 处理线程请求
    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 死锁检测算法的数据结构
 */
typedef struct {
    int available[MAX_RESOURCES];     // 可用资源向量
    int allocation[MAX_PROCESSES][MAX_RESOURCES];    // 已分配矩阵
    int request[MAX_PROCESSES][MAX_RESOURCES];       // 请求矩阵
    int num_processes;    // 进程数量
    int num_resources;    // 资源类型数量
} SystemState;

/**
 * @brief 检查进程是否可以完成
 */
bool can_process_finish(int process_id, bool* finished, int* work, SystemState* state) {
    // 检查是否所有请求都可以被满足
    for (int j = 0; j < state->num_resources; j++) {
        if (state->request[process_id][j] > work[j]) {
            return false;
        }
    }
    return true;
}

/**
 * @brief 更新工作向量
 */
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 死锁检测算法主函数
 * @return 返回死锁进程数量，0表示无死锁
 */
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;
    
    // 初始化工作向量
    for (int i = 0; i < state->num_resources; i++) {
        work[i] = state->available[i];
    }

    // 标记没有请求的进程为已完成
    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;
        }
    }

    // 死锁检测主循环
    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);

    // 统计死锁进程
    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 打印死锁检测结果
 */
void print_deadlock_result(int* deadlocked_processes, int count) {
    if (count == 0) {
        printf("系统中没有死锁\n");
    } else {
        printf("检测到死锁！以下进程处于死锁状态：\n");
        for (int i = 0; i < count; i++) {
            printf("进程 P%d\n", deadlocked_processes[i]);
        }
    }
}

/**
 * @brief 示例使用
 */
int main() {
    SystemState state = {
        .num_processes = 3,
        .num_resources = 3,
        .available = {0, 0, 0},  // 当前可用资源
        .allocation = {          // 已分配资源
            {3, 3, 3},
            {2, 0, 3},
            {1, 2, 4}
        },
        .request = {            // 请求资源
            {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

中文