操作系统
第三章处理机调度与死锁

死锁

# 死锁

# 出现死锁的场景

# 进程推进顺序不当

IMG_20221117_102117

# 资源竞争

IMG_20221117_102345

# 产生死锁的四个必要条件

# 互斥

进程互斥使用资源。因为如果是可以共享使用的资源，多个进程直接同时使用就好，不会陷入等待的僵局。

# 非抢占

一个进程不能抢夺其他进程占有的资源。因为如果其它进程可以抢占资源，那么就是直接拿到资源了，也不会陷入等待的僵局。

# 请求和占有

申请新资源时不释放已占有资源，即要求进程是在占有（holding）至少一个资源的前提下，请求（waiting）新的资源的。由于新的资源被其它进程占有，此时，发出请求的进程就会带着自己占有的资源进入阻塞状态。假设 P1，P2 分别都需要 R1，R2 资源，如果是下面这种方式：

P1:          P2:
request(R1)  request(R2)
request(R2)  request(R1)

1
2
3

如果 P1 请求到了 R1 资源之后，P2 请求到了 R2 资源，那么此后不管是哪个进程再次请求资源，都是在占有资源的前提下请求的，此时就会带着这个资源陷入阻塞状态。P1 和 P2 需要互相等待，发生了死锁。

换一种情况：

P1:          P2:
request(R1)  request(R1)
request(R2)  request(R2)

1
2
3

如果 P1 请求到了 R1 资源，那么 P2 在请求 R1 的时候虽然也会阻塞，但是是在不占有资源的情况下阻塞的，不像之前那样占有 R2。所以，此时 P1 可以正常完成任务并释放 R1，P2 拿到 R1 之后再去执行任务。这种情况就不会发生死锁。

# 环路循环等待

要求存在一条进程资源的循环等待链，链中的每一个进程占有的资源同时被另一个进程所请求。

[P0，P1，P2，…Pn] 中的 P0 正在等待 P1 占用的资源，P1 正在等待 P2 占用的资源......Pn 正在等待 P0 占用的资源。

发生死锁时一定有循环等待（因为是死锁的必要条件），但是发生循环等待的时候不一定会发生死锁。这是因为，如果循环等待链中的 P1 和链外的 P6 都占有某个进程 P2 请求的资源，那么 P2 完全可以选择不等待 P1 释放该资源，而是等待 P6 释放资源。这样就不会发生死锁了。

# 预防死锁

通过设置某些限制条件，以牺牲资源利用率和系统吞吐量为代价，破坏产生死锁的四个必要条件中的一个或几个。特点是简单、限制条件严格，有可能导致资源利用率和系统吞吐量低

# 破坏互斥条件

如果可以把某个互斥资源转化成共享资源，那么就不存在互相等待资源的情况了，也就不会发生死锁。

# 破坏非抢占条件

如果资源是可以抢占的，那么在进程需要资源的时候，就可以直接抢占了，不存在互相等待资源的情况，也就不会发生死锁。要破坏非抢占条件，做到可抢占，可以从两个角度（方案）考虑：

从占有资源的进程的角度考虑，如果它请求不到新的资源，那么它必须立即释放占有的全部资源，以后需要的时候重新申请
从请求资源的进程的角度考虑，如果它需要请求资源，那么操作系统会帮助它抢占相关资源。比如现在有一个优先级更高的进程，如果是采用优先级调度算法，那么它将有机会在操作系统的帮助下抢占到资源。

这种做法的问题在于：

实现起来复杂
某个占有资源的进程释放占有的全部资源时，可能会导致工作进度丢失
反复的申请和释放资源会增加系统开销
可能导致饥饿

# 破坏 “请求和占有” 条件

所有进程在运行之前，都必须一次性地申请其在整个行过程中的所需的全部资源，此时，若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给该进程，这样，该进程在整个运行期间便不会再提出资源要求。

该方法可能导致饥饿现象。若有 ABC 三类进程，A 用到 a 资源，B 用到 b 资源，C 用到 ab 资源，那么 AB 会在运行前事先申请到 ab 资源，如果 AB 源源不断进入就绪队列，那么 C 进程没有办法在运行前拿到 ab 资源，就进入了饥饿状态。

# 破坏 “环路循环等待” 条件

将所有资源按类型进行线性排队并编号，所有进程必须严格按照序号递增的顺序请求资源，即先请求小编号资源，后请求大编号资源。这样，在形成的资源分配图中，不再出现环路。

优点：和前两种相比，资源利用率和吞吐量利用率高

缺点：系统中各类资源所分配的序号必须相对稳定，限制了新类型设备的增加；作业（进程）使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费；为方便用户，系统对用户在编程时所施加的限制条件应尽量少，但必然限制用户简单、自主地编程。

以之前的例子讲解：

P1:          P2:
request(R1)  request(R2)
request(R2)  request(R1)

1
2
3

这种情况下资源请求是无序的，尤其是 P2，它没有按照递增的顺序请求资源，因此很容易发生死锁。但是如果是这种情况：

P1:          P2:
request(R1)  request(R1)
request(R2)  request(R2)

1
2
3

实际上，这里除了破坏 “占有和请求条件” 之外，更重要的是破坏了循环等待条件 —— 因为这里是按照编号递增的顺序请求资源了，不管是 P1 还是 P2，都是先请求小编号的 R1，后请求大编号的 R2，这样的话就不会发生死锁，因为此时两个进程对资源的请求并没有形成一个闭环。

也可以拿之前的哲学家进餐问题解释，如果我们给每个筷子进行编号，规定必须按照编号递增的顺序申请资源，那么从 0 号到 3 号，它们依然会拿起左手边小编号的筷子，但是轮到 4 号的时候，情况就不一样了。因为对于 4 号来说，右手筷子编号更小，所以在拿到左手筷子之前，它会先试图拿右手筷子，又由于该筷子已经被 0 号拿走，4 号被阻塞。对于 3 号来说，没人和自己抢 4 号筷子了，所以 3 号哲学家可以拿到左右筷子，避免了死锁。

还可以从另一个角度考虑，因为我们是按照编号递增的顺序请求资源的，设想在某一时刻，若干个进程中必定有一个进程的资源编号暂时是所有进程中最大的，那么该进程在此后申请新的资源的时候，只可能申请编号更大的资源，一方面避开了小编号、可能已经被拿走的资源，也就避开了阻塞和死锁，另一方面，大编号资源并没有被其他进程拿走。因此这个时候，该进程一定可以拿到资源，不会有死锁现象。

但这种预防死锁的方法，问题在于：

如何进行编号，从什么角度考虑？

如果增加资源或设备，怎么重新编号？

虽然资源请求上是先小编号资源，后大编号资源，但是实际使用的时候可能是得先使用大编号资源，这就意味着小编号资源虽然暂时用不到，但还是被进程占用，明显有资源浪费的问题。

# 避免死锁

安全状态：指系统按某种顺序 (P1,P2,…,Pn)(称 < P1,P2,…,Pn > 为安全序列) 来为每个进程分配其所需资源，直至满足每个进程资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态

安全状态之例：假定系统中有三个进程 P1、P2 和 P3, 共有 12 台磁带机。进程 P1 总共要求 10 台磁带机，P2 和 P3 分别要求 4 台和 9 台。假设在 T0 时刻，进程 P1、P2 和 P3 分别获得 5 台、2 台和 2 台，尚有 3 台未分配，如下表所示：

IMG_20221117_111227

# 进程 - 资源分配图

当各类资源都只有一个的时候，可以使用这种方法求解。资源分配图是描述进程和资源之间请求和分配关系的有向图，从进程指向资源的虚线代表资源需求（要使用），从进程指向资源的实线代表资源请求（申请使用），从资源指向进程的实线代表资源分配（正在使用）。

如果 P1 请求 R2 资源：那么就把 P1 到 R2 的需求边改为 R2 到 P1 的分配边，此时整个图中不存在回路，那么就认为系统处于安全状态，不会发生死锁。可以分配资源。
如果 P2 请求 R2 资源：那么就把 P2 到 R2 的需求边改为 R2 到 P2 的分配边，此时整个图中存在一条回路，那么就认为系统处于不安全状态，有可能发生死锁。不可以分配资源。

# 银行家算法

银行家拥有一笔周转资金
客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能放贷
银行家应谨慎的贷款，防止出现坏帐

# 银行家算法案例

设银行家有 10 万贷款，P,Q,R 分别需要 8,3,9 万元搞项目（假设任何人满足资金总额后都会归还所有贷款)

如果 P 已申请到了 4 万：

Q 要申请 2 万，显然，如果满足 Q 的申请，有安全序列 <P,Q,R>/<Q,P,R>
R 要申请 4 万，显然，如果满足 R 的申请，则不存在安全序列。

基本思想：分配申请的资源前，判断系统是否安全。如果不安全，则不分配。

# 银行家算法过程

假设系统中有 n 个进程，m 种资源，规定：

每个进程在运行前先声明自己需要的最大资源数，用一个 n*m 的最大需求矩阵 Max 表示各个进程的需求情况，比如 Max[i][j]= K 就表示进程 i 需要 K 个 j 类型资源
用一个 n*m 的分配矩阵 Allocation 表示各个进程的已分配资源情况
用一个 n*m 的需求矩阵 Need 表示各个进程的最多还需要资源情况， Need = Max - Allocation
用一个 m 长度的一维数组 Avaliable 表示剩余资源数目
用一个 m 长度的申请矩阵 Request[i][j] 表示某个进程 i 某次申请的 j 类型资源数目

按照之前说过的流程图，银行家算法的工作过程是：

请求资源数是否超过最大资源数？ Request[i][j]<=Need[i][j] ，则到下一步；否则出错
请求资源数是否超过剩余资源数？ Request[i][j]<=Available[j] ，则到下一步；否则说明资源不够，进程等待
尝试进行资源分配。
- 剩余资源减少： Available = Available - Request
- 已分配资源增加： Allocation[i][j] = Allocation[i][j] + Request[i][j]
- 需求资源减少： Need[i][j] = Need[i][j] - Request[i][j]
对分配后的状态通过安全性算法进行预判：
- 安全状态：不会发生死锁，可以分配资源
- 不安全状态：可能发生死锁，不分配资源，进程进入等待资源状态，并恢复系统状态

# 例题 1

假如现在有 P0 ~ P4 共五个进程，ABC 三类资源，个数为（10,5,7）。在某一时刻，资源剩余量为（3,3,2），各个进程的最大需求量、已分配量和需求量如下图所示：

如何检测当前是否处于安全状态呢？尝试寻找安全序列：

当前剩余资源（3,3,2），无法满足 P0 需要的（7,4,3），所以不能首先分配给 P0；但是可以满足 P1 需要的（1,2,2），P3 需要的（0,1,1），所以可以分配给 P1 和 P3，P1 和 P3 进入安全序列。
P1 和 P3 执行完之后，归还资源，剩余资源（3,3,2）+（2,0,0）+（2,1,1）=（7,4,3），可以满足 P0 需要的（7,4,3），P2 需要的（6,0,0），P4 需要的（4,3,1），所以 P0、P2、P4 依次进入安全序列。
所以存在安全序列 P1->P3->P0->P2->P4 ，使得按照这个顺序分配资源后，每个进程都能拿到需要的资源并顺利完成，所以该状态是安全状态。

看另一种情况。假如现在有 P0 ~ P4 共五个进程，ABC 三类资源，个数为（10,5,7）。在某一时刻，资源剩余量为（3,3,2），各个进程的最大需求量、已分配量和需求量如下图所示：

当尝试寻找安全序列的时候，容易发现 P1 P3 可以满足，所以 P1 P3 进入安全序列，此后剩余资源为（7,4,3）。又由于 P0 P2 P4 都是无法满足的，所以实际上并不存在一个安全序列使得所有进程都能被分配资源。因此状态是不安全状态，可能发生死锁，取消资源分配。

# 例题 2

t0 时刻安全状态检查。如果 t0 时刻都不安全，则后面的部分都不用做了。但是考试时 t0 都是安全的。

IMG_20221117_114149

安全序列之一：<p1,p3,p4,p2,p0>

# 例题 3

在银行家算法中，若出现下述资源分配情况，试问：

Process	Allocation	Need	Available
P0	0032	0012	1622
P1	1000	1750
P2	1354	2356
P3	0332	0652
P4	0014	0656

(1) 该状态是否安全？

P0 1622+0032=1654
P3 1654+0332=1986
P1 1986+1000=2986
P4 2986+0014=299 10
P2 299 10+1354=3 12 14 14
故存在安全序列P0 P3 P1 P4 P2

1
2
3
4
5
6

(2) 若进程 P2 提出请求 Request (1,2,2,2) 后，系统能否将资源分配给它？

P2的Allocation加上1 2 2 2为2 5 7 6，Need变为1 1 3 4， Available变为0 4 0 0
由(1)可知，此时系统资源无法满足任何一个进程，安全性检查不通过，无法分配资源

1
2

# 检测死锁

# 简化进程 - 资源分配图

# 各类资源只有一个

当各类资源只有一个的时候，可以把资源分配图化简为一个等待图（wait-for graph），比如说 A 进程请求 X 资源、X 资源被 B 进程占有，这个过程可以被简化为 A 进程等待 B 进程。比如说下面，左图被转化为对应的右图：

死锁定理：有环路，且每个类型的资源只有一个，则一定会出现死锁。

如果进程 - 资源分配图中无环路，则此时系统没有发生死锁。
如果进程 - 资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充分和必要条件，环路中的进程便为死锁进程。
如果进程 - 资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。

# 各类资源有多个

各类资源有多个的时候，我们可能需要根据给定表或给定图检测是否有死锁。对于前者，可以沿用之前的安全性算法进行检测；对于后者，可以尝试简化资源分配图。

给定一个资源分配图为例：

约定蓝色线为请求边，黑色线为分配边，资源中的一个圆点代表一个该类资源。那么 P1 占有两个 R1 资源，请求一个 R2 资源；P2 占有一个 R2 资源，一个 R1 资源，请求一个 R1 资源。

首先找出非阻塞非孤立的进程点。P1 P2 都不是孤立的，所谓非阻塞指的是进程请求的资源数量足够，比如说 P2 请求 R1，由于 R1 已经有两个被 P1 占有，一个被 P2 占有，无多余资源，所以 P2 是阻塞的；而 P1 请求 R2，因为 R2 只有一个被 P2 占有，有多余资源，P1 是非阻塞的。这样就找到了符合条件的进程点 P1
去除这样的点的所有边。那么就会去除 P1 的所有边，归还所有资源。P1 成为孤立点
重复第一步和第二步。此时，因为这次 P2 请求的 R2 资源是足够的（被 P1 释放了），所以 P2 是非阻塞非孤立的点，把他的全部边去除
由于图中所有的边都能被消除，所以称该图可以被简化，因此它不存在死锁（如果不可简化，则存在死锁）