计算机操作系统 死锁 -- 产生死锁的必要条件、死锁的处理方法（鸵鸟策略、死锁检测与死锁恢复、死锁预防、死锁避免）

文章目录

• 1. 什么是死锁
• 2. 产生死锁的必要条件
• 3. 死锁的处理方法
• • 3.1 鸵鸟策略
  • 3.2 死锁检测与死锁恢复
  • • 3.2.1 每种类型一个资源的死锁检测
    • 3.2.2 每种类型多个资源的死锁检测
  • 3.3 死锁预防
  • • 3.3.1 破坏互斥条件
    • 3.3.2 破坏请求并持有条件
    • 3.3.3 破坏不可剥夺条件
    • 3.3.4 破坏循环等待条件
  • 3.4 死锁避免
  • • 3.4.1 安全状态
    • 3.4.2 单个资源的银行家算法
    • 3.4.3 多个资源的银行家算法

1. 什么是死锁

两个及两个以上进程分别等待对方所占的资源，于是两者都不能执行而处于永远等待状态，这种现象称为死锁。

2. 产生死锁的必要条件

产生死锁必须同时满足以下四个条件：

• 互斥条件：每个资源要么已经分配给了一个进程，要么就是可用的。
• 请求并持有条件：已经得到了某个资源的进程可以再请求新的资源。
• 不可剥夺条件：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
• 循环等待条件（环路等待条件）：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

3. 死锁的处理方法

3.1 鸵鸟策略

鸵鸟在遇到危险时会把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

3.2 死锁检测与死锁恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

3.2.1 每种类型一个资源的死锁检测

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

3.2.2 每种类型多个资源的死锁检测

上图中，有三个进程四个资源，每个数据代表的含义如下：

• E 向量：资源总量
• A 向量：资源剩余量
• C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
• R 矩阵：每个进程请求的资源数量

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
3. 如果没有这样一个进程，算法终止。

3.3 死锁预防

死锁预防即是在程序运行之前预防发生死锁。这就要求破坏至少一种产生死锁的必要条件。

3.3.1 破坏互斥条件

如果允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。

3.3.2 破坏请求并持有条件

釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。

3.3.3 破坏不可剥夺条件

当一个进程持有了一些资源，当它继续去执行进程的时候，如果发现资源不够，应该将已有的资源暂时释放，等到以后需要再次申请。

3.3.4 破坏循环等待条件

给资源统一编号，进程只能按编号顺序来请求资源。

3.4 死锁避免

死锁避免是在程序运行时避免发生死锁。

3.4.1 安全状态

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

定义：如果没有死锁发生，并且存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

3.4.2 单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

比如上面的c就是不安全状态，单个资源的银行家算法会拒绝c的请求。

3.4.3 多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

1. 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
2. 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
3. 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！