【系统架构设计师】操作系统 - 进程管理 ⑤ ( 进程死锁 | 死锁 四大条件 | 死锁资源数计算 )

一、进程 死锁

1、死锁 概念

死锁 概念 : 两个或两个以上的进程 , 在执行过程中 , 因 争夺资源 而造成的一种 互相等待的现象 , 如果没有外力作用 , 所有进程都无法继续执行 , 进程 等待 不可能发生的条件 , 就会产生 " 死锁 " ;

死锁 进程 : 多个进程产生 " 死锁 " , 就会造成 " 系统死锁 " , 这些 永远在互相等待的进程称为 " 死锁进程 " ;

2、死锁 案例 ( 重点 )

进程死锁 案例 : 进程 1 和 进程 2 都在运行 ;

• 进程 1 需要 资源 A 和 资源 B , 已经持有 资源 A , 等待 资源 B ;
• 进程 2 需要 资源 B 和 资源 A , 已经持有 资源 B , 等待 资源 A ;
• 两个进程 都不释放 已有资源 ;
• 系统 不剥夺 每个进程的 已有资源 ;
• 这里 产生了 环路等待 ;

这样就产生了死锁 , 如下图所示 :

3、死锁 四大条件

" 死锁 " 形成 需要满足以下 四大条件 :

• 互斥条件 ( Mutual Exclusion ) : 资源具有排他性 , 即 一个资源每次只能被一个进程独占使用 , 造成 死锁 的资源 是 " 互斥 " 的 , 同一时间只能有一个进程访问该资源 ;
• 占有且等待 ( Hold and Wait ) : 进程 已持有至少一个资源 , 同时又在 请求其他资源 , 且请求的资源被其他进程占有 , 进程 会 " 保持 " 当前 已经拥有的资源 , 并且保持等待状态 ;
• 不可剥夺 ( No Preemption ) : 进程 已获得的资源在未使用完毕前 , 不能被强制剥夺 , 只能由进程主动释放 , 进程 " 不剥夺 " 其它进程 占有的 本应用急需的 资源 ;
• 循环等待 ( Circular Wait ) : 存在一个 进程等待链 , 每个进程都在等待 下一个进程 持有的资源 , 形成环路 , 多个进程 等待的 资源 形成环路 ;

4、解除死锁 - 破坏 死锁 四大条件

上述 四大条件 只要打破任意一个 , 就可以解除 " 死锁 " 状态 , 破坏死锁条件的方式 :

• 互斥条件 ( Mutual Exclusion ) : 允许资源共享 , 多个进程可共享同一资源 ;
• 占有且等待 ( Hold and Wait ) : 进程执行前需要 一次性申请所有资源 , 避免进程 占有资源却不执行 和 无限期等待申请不到的资源 ;
  • 银行家算法 就是 破坏该条件 的解决方案 ;
• 不可剥夺 ( No Preemption ) : 允许强制回收资源 , 该操作可能导致进程执行失败 ;
• 循环等待 ( Circular Wait ) : 有序分配算法 就是 破坏该条件 的解决方案 ;

5、解除死锁 - 有序分配

有序分配法是一种通过破坏 " 循环等待 ( Circular Wait ) " 条件来避免死锁的方法 , 该算法的核心思想是要求 所有进程必须按照 相同的顺序 申请资源 ;

• 资源排序 : 对所有可申请的 资源 进行排序 , 每个进程在申请资源时必须严格按照这个顺序进行 ;
• 进程申请 : 当进程需要申请多个资源时 , 它必须 首先申请 序号最小的资源 , 然后申请 序号更大的资源 ;
• 避免环路 : 由于所有进程都按照相同的顺序申请资源 , 因此不会出现一个进程持有另一个进程所需的资源 , 同时又在等待第三个进程释放它所持有的资源的情况 , 从而避免了环路等待条件 ;

有序分配法通过 循环等待 ( Circular Wait ) 条件来避免死锁 , 实现简单但 资源利用率低、灵活性差 ;

6、解除死锁 - 银行家算法

银行家算法 是一种更为复杂但更为有效的避免死锁的方法 , 它以银行借贷系统的 分配策略 为基础 , 通过模拟资源分配的情况来确保系统始终处于安全状态 ;

系统模拟资源分配过程 , 试图找到一个安全进程序列 , 按照这个序列分配资源后 , 每个进程都能顺利完成 ;

如果能找到这样的安全序列 , 则系统处于安全状态 ; 否则 , 系统处于不安全状态 ;

银行家算法 虽然实现复杂 , 但能够 动态地分配资源 , 并提高资源的利用率 ;

二、软考考点

1、死锁资源数计算 案例

操作系统 中 有 3 个进程 , 每个进程都需要 5 个系统资源 , 系统资源数为 n , 分析系统中资源数量 与 死锁 的关联 ;

• n < 5 的情况 : 系统肯定死锁 ; 假如 系统只有 4 个资源 , 则任何一个进程无都法执行 , 整个系统死锁 ;
• n = 5 的情况 : 大概率造成死锁 ;
  • 最好情况 : 每次将所有资源分配给一个进程 , 3 个进程是有可能执行完毕的 ;
  • 最坏情况 : 假如 三个进程 分别持有若干资源不释放 , 则有可能造成死锁 ;
• 5 < n <= 12 的情况 : 可能死锁 ;
  • n = 12 的最坏情况 : 三个进程平均分配资源 , 每个进程分配到 4 个资源 , 也会造成死锁 ;
• n >= 13 的情况 : 不可能死锁 ;
  • 只要在 n = 12 的情况下 , 再多增加一个资源 , 就会有一个进程可以执行完毕 , 释放出全部资源 , 死锁解除 ;

2、死锁资源数计算公式 1

进程个数 m 个 , 每个进程需要资源数 w 个资源 , 则资源数 n >= m (w - 1) + 1 可以保证系统无法死锁 ;

3、死锁资源数计算公式 2

进程个数 m 个 , 每个进程需要资源数 wi 个资源 ( i = 1, 2, … , m ) ,

• 第 1 个进程需要 w1 个资源 ;

• 第 2 个进程需要 w2 个资源 ;

  …

• 第 m 个进程需要 wm 个资源 ;

则资源数 $$n\ge \sum _{i=1}^m(w_i-1)+1$$ 可以保证系统无法死锁 ;

4、鸽巢原理

死锁资源数计算 的 底层原理 是 鸽巢原理 ;

鸽巢原理 :

将 n + 1 个物体 放到 n 个盒子 中 , 则

一定存在一个盒子 中 至少 含有 2 个 或 2 个以上的物体 ;

这个存在的一个盒子 就是 为 " 进程 " 分配了 满足执行的所有资源 ;

鸽巢原理 实际上是 多对少 的配置 , 至少存在一个多对一的情况 ;

参考 :

• 【组合数学】鸽巢原理 ( 鸽巢原理简单形式 | 鸽巢原理简单形式示例 1、2、3 )
• 【组合数学】鸽巢原理 ( 鸽巢原理简单形式示例 4、5 )

博客 ;