死锁概述
死锁（Deadlock）：是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法再向前推进。
资源问题
可重用性资源和消耗性资源：
- 可重用性资源：
- 是一种可供用户重复使用多次的资源。每一个可重用性资源只能分配给一个进程使用，不允许多个进程共享。
- 资源的单元数目是相对固定的，在运行期间既不能创建也不能删除它
- 消耗性资源：
- 在进程运行期间，由进程动态地创建和消耗。
- 资源的单元数目在进程运行期间可以不断变化的。进程可以请求若干个可消耗性资源单元。
- 可消耗性资源通常由生产者创建，消费者消耗。
可抢占性资源和不可抢占性资源。
- 可抢占性资源：
- 某进程获得该资源后，该资源可以再被其他进程或系统抢占。
- 不会引起死锁。
- 不可抢占性资源是指资源一旦被分配给进程，只能在进程用完后自行释放。
### 计算机中的死锁
竞争不可抢占性资源引起死锁。
- 两进程分别保持一个临界资源，而又分别因请求对方所保持的资源被阻塞。
竞争可消耗性资源引起死锁。
- 一进程需接受到对方发送的消息a后才能发送消息b，而另一进程需接受到对方发送的消息b后才能发送消息a。
进程推进顺序不当引起死锁。
死锁的定义：
如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的时间，那么该组进程是死锁的。
产生死锁的必要条件
互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。
请求和保持条件：指进程已经保持了至少一个资源，但又提出了
新的资源请求（该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放）。
不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放
环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链。即进程集合{P0,P1,P2,…,Pn}中的P0正在等待一个P1占用的资源；P1正在等待一个P2占用的资源，……，Pn正在等待一个已被P0占用的资源。
死锁处理方法
预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件的一个或几个，来预防发生死锁。
避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁
检测死锁：通过系统所设置的检测机构，及时的检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉
解除死锁：当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源
预防死锁
由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏其它三个条件。
破坏“请求和保持”条件
第一种协议：
规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。在整个运行期间便不会再提出资源要求，从而破坏了请求条件。
在分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，即在该进程的等待期间，它并未占有任何资源，因而也破坏了保持条件。
第二种协议：
允许进程只获得运行初期所需的资源后，便开始运行。
进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再去请求新的所需资源
破坏不可抢占条件
当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。
这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被抢占了，从而破坏了“不可抢占”条件。
破坏 循环等待条件
系统将所有类型资源进行线性排队，并赋予不同的序号。规定每个进程必须按序号递增的顺序请求资源。
假如某进程已请求到一些序号较高的资源，后来它又想请求一个序号低的资源时，它必须先释放所有具有相同和更高序号的资源后，才能申请序号低的资源
在采用这种策略后不可能再出现环路，因而破坏了“循环等待”条件。
避免死锁
系统安全状态：
系统在进行资源分配之前，应先计算此次资源分配的安全性。
安全状态，是指系统能按某种进程顺序（ P0, P1, P2, …, Pn
）来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态
安全状态下不会产生死锁，但是不安全状态不一定产生死锁
利用银行家算法避免死锁
描述资源的数据结构
在系统中必须设置四种数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
（设系统中有m类资源，n个进程）
上述三个矩阵间存在下述关系：Need[i, j] = Max[i, j] - Allocation[i,
j]
银行家算法：
设 Request[i] 是进程 P i 的请求向量，如果 Request[i][j]=K，表示进程 P
i需要 K 个 R j 类型的资源。当 P
i发出资源请求后，系统按下述步骤进行检查：
- 如果
Request[i][j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值
- 如果
Request[i][j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi
须等待。
- 系统试探着把资源分配给进程 P i，并修改下面数据结构中的数值：
- Available[j] = Available[j]-Request[i][j]； 更新可用资源数目
- Allocation[i,j] = Allocation[i,j]+Request[i][j]；
更新分配给该进程的资源数
- Need[i,j] = Need[i,j]-Request[i][j]； 更新该进程需要的资源数
安全性算法：
- 设置两个向量：
- 工作向量
Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有
m个元素，在执行安全算法开始时，Work=Available。
- Finish:
含n个元素的一维数组，表示系统是否有足够的资源分配给n个进程，使之运行完成。开始时先令Finish[i]:=false
(i=1..n); 当有足够资源分配给进程i时，再令Finish[i]:=true。
- 从进程集合中找到一个能满足下述条件的进程：
- Finish[i]=false;
- Need[i,j]≤Work[j]；
- 若找到，执行步骤(3)，否则，执行步骤(4)。
- 当进程
Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
- Work[j] = Work[j]+Allocation[i,j]；
- Finish[i] = true；
- go to step 2；
- 如果所有进程的 Finish[i]=true
都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
死锁的检测和解除
- 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此系统必须：
- 保存有关资源的请求和分配信息；
- 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。
- 资源分配图：
系统死锁可利用资源分配图来描述：
该图由表示进程的圆圈和表示一类资源的方框组成
其中方框中的一个点代表一个该类资源，请求边是由进程指向方框中的rj，而分配边则应始于方框中的一个点。如图所示。
image-20250429200304004
- 死锁定理：
在资源分配图中找出一个既不阻塞又非独立的进程结点Pi，在顺利的情况下运行完毕，释放其占有的全部资源。
由于释放了资源，这样能使其它被阻塞的进程获得资源继续运行。
在经过一系列简化后若能消去图中的所有的边，使所有进程结点都孤立，则称该图是可完全简化的，反之是不可完全简化的。
S 状态为死锁状态的充分条件是当且仅当 S
状态的资源分配图是不可完全简化的
- 死锁的解除：
剥夺资源：从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。
撤销进程：最简单的是让全部进程都死掉；温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用，使死锁状态消除为止。
死锁避免的处理代码
使用银行家算法，C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
| #include <bits/stdc++.h>
using namespace std;
const int PROCESS_COUNT = 5;
const int RESOURCE_TYPE = 3;
vector<vector<int>> Max = {
{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3}
};
vector<vector<int>> allocation = {
{0, 1, 0},
{2, 0, 0},
{3, 0, 2},
{2, 1, 1},
{0, 0, 2}
};
vector<int> available = {3, 3, 2};
vector<vector<int>> need(5, vector<int>(3));
void calculate_need() {
for (int i = 0; i < PROCESS_COUNT; i++) {
for (int j = 0; j < RESOURCE_TYPE; j++) {
need[i][j] = Max[i][j] - allocation[i][j];
}
}
}
vector<vector<int>> safe_sequences;
void Safe_Check(vector<int> work, vector<bool> finish, vector<int> path) {
if (path.size() == PROCESS_COUNT) {
safe_sequences.push_back(path);
}
for (int i = 0; i < PROCESS_COUNT; i++) {
bool can_execute = true;
for (int j = 0; j < RESOURCE_TYPE; j++) {
if (need[i][j] > work[j]) {
can_execute = false;
break;
}
}
if (!finish[i] && can_execute) {
vector<int> new_work = work;
for (int j = 0; j < RESOURCE_TYPE; j++) {
new_work[j] += allocation[i][j];
}
vector<bool> new_finish = finish;
new_finish[i] = true;
vector<int> new_path = path;
new_path.push_back(i);
Safe_Check(new_work, new_finish, new_path);
}
}
}
pair<bool, vector<vector<int>>> check_safety() {
safe_sequences.clear();
vector<int> work = available;
vector<bool> finish(PROCESS_COUNT, false);
Safe_Check(work, finish, {});
return {!safe_sequences.empty(), safe_sequences};
}
bool handle_request(int pid, vector<int> request) {
calculate_need();
for(int j = 0; j < RESOURCE_TYPE; j++){
if(request[j] > need[pid][j]){
cout << "错误：P" << pid << "请求超过最大需求，出现死锁("
<< need[pid][0] << "," << need[pid][1] << "," << need[pid][2] << ")" << endl;
return false;
}
}
for (int j = 0; j < RESOURCE_TYPE; j++) {
if(request[j] > available[j]){
cout << "请求被拒绝：可用资源不足（当前"
<< available[0] << "," << available[1] << "," << available[2] << "）" << endl;
return false;
}
}
vector<int> original_available = available;
vector<vector<int>> original_allocation = allocation;
vector<vector<int>> original_need = need;
vector<int> new_available = available;
vector<vector<int>> new_allocation = allocation;
vector<vector<int>> new_need = need;
for (int j = 0; j < RESOURCE_TYPE; j++) {
new_available[j] -= request[j];
new_allocation[pid][j] += request[j];
new_need[pid][j] -= request[j];
}
available = new_available;
allocation = new_allocation;
need = new_need;
auto [is_safe, seqs] = check_safety();
available = original_available;
allocation = original_allocation;
need = original_need;
if (is_safe) {
available = new_available;
allocation = new_allocation;
need = new_need;
cout << "请求批准，系统进入安全状态" << endl;
cout << "安全序列：";
for (auto seq : seqs) {
for (int p : seq) cout << "P" << p+1 << " ";
cout << "| ";
}
cout << endl;
return true;
} else {
cout << "请求拒绝：分配后系统不安全" << endl;
return false;
}
}
void algorithm_explanation() {
cout << "\n=== 银行家算法核心过程可视化 ===" << endl;
cout << "\n1. T0时刻初始状态：" << endl;
cout << "可用资源 Available: " << available[0] << "," << available[1] << "," << available[2] << endl;
cout << "分配矩阵 Allocation:" << endl;
for (int i=0; i<5; i++)
cout << "P" << i+1 << ": " << allocation[i][0] << "," << allocation[i][1] << "," << allocation[i][2] << endl;
calculate_need();
cout << "需求矩阵 Need:" << endl;
for (int i=0; i<5; i++)
cout << "P" << i+1 << ": " << need[i][0] << "," << need[i][1] << "," << need[i][2] << endl;
cout << "\n2. 安全检查逻辑：" << endl;
cout << "寻找满足Need[i] <= Work的进程（初始Work=Available）" << endl;
auto [is_safe, seqs] = check_safety();
cout << "找到" << seqs.size() << "个安全序列，例如：";
for (int p : seqs[0]) cout << "P" << p+1 << "->";
cout << "\b （释放资源后Work更新）" << endl;
cout << "\n3. P1请求(1,0,2)处理流程：" << endl;
cout << "请求前Available: " << available[0] << "," << available[1] << "," << available[2] << endl;
cout << "Need[P1] before: " << need[0][0] << "," << need[0][1] << "," << need[0][2] << endl;
handle_request(0, {1,0,2});
cout << "请求后Available: " << available[0] << "," << available[1] << "," << available[2] << endl;
cout << "Allocation[P1] after: " << allocation[0][0] << "," << allocation[0][1] << "," << allocation[0][2] << endl;
cout << "Need[P1] after: " << need[0][0] << "," << need[0][1] << "," << need[0][2] << endl;
}
int main() {
calculate_need();
cout << "=== T0时刻系统安全检查 ===" << endl;
auto [initial_safe, initial_seqs] = check_safety();
if (initial_safe) {
cout << "系统处于安全状态，安全序列：";
for (auto seq : initial_seqs) {
for (int p : seq) cout << "P" << p+1 << "->";
}
cout << "\b （共" << initial_seqs.size() << "种）" << endl;
} else {
cout << "系统不安全" << endl;
}
cout << "\n=== 处理P1的资源请求(1,0,2) ===" << endl;
handle_request(0, {1,0,2});
algorithm_explanation();
return 0;
}
|
