-
Notifications
You must be signed in to change notification settings - Fork 32
/
6、死锁问题及多种处理策略.md
218 lines (135 loc) · 12 KB
/
6、死锁问题及多种处理策略.md
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
# 死锁
## 条件及预防
死锁发生的四个基本条件
* 互斥（Mutual Exclusion）：资源不能被共享，一个资源每次只能被一个进程使用。
* 不可剥夺（No Preemption）：进程已获得的资源，在未使用完之前，不能强行剥夺。
* 请求与保持（Hold and Wait）：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
* 循环等待（Circular Wait）：若干进程之间形成一种头尾相接的循环性资源等待关系。
一旦能够破坏这四个必要条件中的某个条件，死锁也就不会形成了，这就是死锁预防的基本想法。
* “互斥”和“不可剥夺”这两个条件通常是很难破坏的
* “互斥”是许多资源自身的基本特性，很多时候无法改变的，比如临界区、共享缓存区、打印机等资源都是临界资源，一次只能让一个进程访问，不能改变。
* “不可剥夺”是由程序本身造成的，很多资源如果不是程序执行到一定的时候主动释放，是不能被强行剥夺的，否则就会造成错误
* 所以死锁预防主要是破坏“请求与保持”和“循环等待”这两个必要条件。
* 不“请求与保持”就是或者不请求或者不保持，当然不请求是不可以的，因为只有申请获得了资源以后程序才能顺序执行。那么能否不保持，即在不占有任何资源的前提下申请资源？此时申请资源的方式就只能有一个：一次性申请进程所需的所有资源。
* 破坏“循环等待”的方法是不让资源等待形成环路。资源等待是由资源申请引起的，所以也要对程序的资源申请进行控制，资源按序申请就可以不让资源等待关系中出现环路。
资源分配图
* 资源等待关系可以用一个资源分配图（Resource-AllocationGraph）来表示，而循环等待就是在这个资源分配图中出现了一个环路。
* 资源分配图中有环路并不意味着一定出现了死锁，但如果出现了死锁，则资源分配图中一定出现了环路，所以环路等待是死锁的必要条件。
* 资源分配图中的顶点是进程和资源，从资源出发到进程的边表示进程占有了该资源，如果这个资源有多个实例，这条边就表示占有了一个资源实例
* 如下图：其中的确存在一条资源等待回路：R1 ,C1 ,R2 ,C2 ,R3 ,C3 ,R4 ,C4 ,R1 。
* 原因是 C4 持有 R4 再申请 R1 。
* 资源按序申请就是对资源进行编号，进程对资源的申请必须按照编号顺序从小到大（或从大到小）依次申请。如果出现了环路，就一定存在一个进程其持有资源的编号大于其请求资源的编号
* 如果是按从小到大的顺序申请，C4 就会申请 R1 再申请 R4 。由于R1 已经被 C1 占有，所以 C4 对 R1 的申请不会成功，停下来等待。
* 由于此时 C4还没申请 R4 ，所以 C4 要停在进入 R 4 路口之前，这样 C3 就能顺利通过，整个交叉路口不会死锁。
* 虽然解决了死锁问题，但也引入了很大的不灵活性和不合理性：
* （1）需要预先计算程序要请求的资源，对于存在诸如 if 等分支语句的程序而言，准确的计算程序会请求哪些资源几乎是不可行的；
* （2）虽然在很远的未来才能使用到的资源，都要早早的预留下来，这势必造成计算机资源的极大浪费，等等。
* 因此，针对死锁问题需要给出一些不属于死锁预防的其他办法。
## 死锁避免
* 死锁避免的处理思想：每次资源申请都要判断是否有出现死锁的危险，如果有危险就拒绝此次申请
银行家算法
* （1）银行是操作系统，资金就是资源，客户相当于要申请资源的进程；
* （2）客户能最终偿还贷款需要银行满足客户的全部贷款请求，相当于操作系统满足进程的所有资源请求，即让进程执行完成，不造
成死锁；
* （3）银行判断贷款请求是否应该被批准相当于操作系统判断进程资源请求是否可以被允许，银行没有损失相当于操作系统没有死锁；
* （4）操作系统判断这个资源请求是否安全的算法就是银行判断此次贷款是否安全的算法，因此被称为银行家算法。
银行家算法的核心就是要找到安全序列
* 能让所有进程都顺利完成的进程序列 P1 ,P2 ,··· ,Pn 被称为是 安全序列。
* 在遇到一个资源请求时，首先假设允许此次资源请求，如果发现在允许该请求以后的操作系统上仍能找到安全序列，说明此次资源请求安全，操作系统就真的分配资源
* 如果发现找不到安全序列，虽然不能说明系统就一定会发生死锁，但至少存在死锁的风险，此次资源请求就被拒绝。
银行家算法示例
* 当前现状说明：
* 其中 A、B、C 是三种类型的资源
* P1 ,P2 ,P3 ,P4 ,P5 是系统中的五个进程
* Allocation 是已经分配给各个进程的资源
* Max 是这些进程需要的最大资源量
* Available 是系统当前还剩下的可用资源
* 现在 P3 提出了一个资源申请：1 0 1
* 首先假设允许了这个请求，此时Available 会变为 3 3 2，而 P3 的 Allocation 会变为 3 0 2。在这个状态下，“银行家”会努力寻找一个让所有进程都能获得其全部所需资源的调度序列。
* 在这个状态下，“银行家”会努力寻找一个让所有进程都能获得其全部所需资源的调度序列。现在的可用资源是 3 3 2，那要把这些资源分配给哪个进程合适呢？
* 显然不应该分配给P 1 ，因为即使分配给了 P 1 ，P 1 拥有的资源为 (0 1 0) + (3 3 2) = (3 4 2)，也不能满足 P 1 总共需要的资源请求数量，因为 (3 4 2) < (7 5 3)。
* 但可以将当前的可用资源分配给 P2 ，因为再加上 P2 现在已经拥有的资源 2 0 0 以后，P2 就有 5 3 2资源数量，大于其要求的资源总量，即 (5 3 2) > (3 2 2)，这样 P2 就能顺利执行完成。一旦 P2 执行完成，分配给 P2 的资源就可以被回收，此时系统可用的资源就会变成为 5 3 2
* 继续按照上面的思路，至此所有进程都能执行完成，根据定义，P2 ,P4 ,P3 ,P5 ,P1 就是一个安全序列。
```c
int Available[1..m]; //每种资源剩余数量
int Allocation[1..n, 1..m]; //已分配资源数量
int Max[1..n, 1..m];//进程总共需要的资源数量
int Work[1..m]; //工作向量
bool Finish [1..n]; //进程是否结束
Work = Available;
Finish[1..n] = false;
while(true)
{
find = false;
for(i=1; i<=n; i++)
{
if(Finish[i] == false && Work +Allocation[i] ≥ Max[i])
{
Finish[i] = true; //进程 i 可以执行完
Work = Work + Allocation[i];
find = true;
}
}
// 思想类似于编译原理的求 First/Follow 集，一次循环都不变时就完了
if(find == false) {goto END;}
}
END: for(i=1;i<=n;i++)
if(Finish[i] == false) return ”deadlock”;
```
银行家算法的确是一个可行的系统安全状态判定算法，但基于银行家算法的死锁避免是否是一个完美的死锁处理方法？
* 答案通常都是否定的。银行家算法仍然存在一些重要缺陷，基于银行家算法的死锁避免机制是保守的，也就是说本来不会导致死锁的资源请求很可能不被系统允许，势必造成计算资源的浪费、用户进程执行的拖延。
* 为什么安全序列不存在但系统却不死锁呢？因为前提是“进程资源在最终一起释放”这一假设，而进程中的资源不是等待获得全部资源以后才一起释放的，是使用完成就马上释放的。
除了保守以外，其他问题
* 银行家算法存在的另一个不足是这个算法的效率不高，对于具有上千个进程，上千个资源的大系统而言，O($mn^2$ ) 并不是一个可以忽略的数字，因为 O($mn^2$ ) 是每个进程在每请求一次资源时都必需花费的此外，
* 银行家算法还需要已知进程执行完成所需的资源总数，这并不是一个容易获得的信息。
* 这两个不足使已经不很优美的银行家算法（因为是一个偏于保守的充分性算法）在实际系统中还是难于发挥其作用：参数难获得、效率低、系统代价大，所以还应该再从一个新的角度来思考死锁问题。
## 检测/恢复/忽略
死锁预防和死锁避免都是通过对资源使用的限制来保证不出现死锁，这样的限制势必造成资源使用效率的降低。
* 死锁预防对进程使用资源的方式进行了严格限制，比如一次性申请或按序申请等，这些限制条件将严重影响资源的使用效率。
* 死锁避免对资源请求带来的风险进行了保守的估计，从而拒绝了很多资源请求，同样也会造成资源使用效率的下降
能不能破除这些限制，让资源随意使用
* 死锁检测/恢复就是要能通过算法检测出哪些进程死锁了，并能通过一些机制将这些进程从死锁状态中恢复过来。
死锁检测算法
* 可以改造银行家算法来进行死锁检测，一个简单的改造就是将银行家算法中的 Max 修改为Request， Request 是进程当前提出的资源请求（即每个进程只保存当前持有的，还有正在等待请求的）
* 虽然和银行家算法一样，这个死锁检测算法的时间复杂性也是 O($mn^2$)，但死锁检测算法不像银行家算法那样会被频繁调用。是定时调用或者是检测到系统可能出现死锁（如果资源长时间没有使用，进程长时间不被调度等等）时才调用
```c
int Available[1..m];
int Allocation[1..n, 1..m];
int Request[1..n, 1..m];//进程当前申请的资源数量
int Work[1..m];
bool Finish [1..n];
Work = Available;
if Allocation[i] ̸= 0, then Finish[i] = false; else Finish[i] = true;
//不保持资源的进程不会死锁
while(true)
{
for(i=1; i<=n; i++)
{
find = false;
if(Finish[i] == false && Request[i] ≤ Work)
{
Work = Work + Allocation[i];
Finish[i] = true;
find = true;
}
}
if(find == false) {goto END;}
}
END: for(i=1;i<=n;i++)
if(Finish[i] == false){
Deadlock = Deadlock ∪ {i};
return ”deadlock”;
}
```
虽然死锁检测算法造成的系统开销完全可以接受，但死锁检测/恢复机制中的死锁恢复却并不容易实现。
* 对于进程，就是要选择一些进程进行回滚（Rollback），即让这些进程从曾经的某个状态、某条语句开始重新开始执行。
* 这里就会出现很多问题：
* （1）如何实现回滚，执行指针 PC 的往前调整比较容易，但一个进程对系统做出的修改，如已经修改的文件、发出的网络数据包应该怎么办？
* （2）回滚到哪里更加合适，应该是回滚到能刚好解除死锁的地方最好，但如何找到这个地方呢？
* （3）选择哪些进程回滚，选择优先级低的进程可能对死锁解除的效果不好
死锁忽略
* 实际上就是针对死锁不做任何处理
* 死锁预防和死锁避免对资源的使用造成了诸多限制，死锁检测/恢复虽然没有这些限制，但在死锁真的出现时处理起来也很麻烦。这就出现了死锁忽略处理方法
* 很多我们非常熟悉的操作系统，如 Windows，Linux 等，采用的就是这种“什么也不做”的死锁忽略处理方法。