操作系统快速复习（死锁）

按照惯例，先通过知识架构图认识本小节内容，对学习本小节起个提纲作用：

一、死锁概念

1.1 死锁定义

• 多个进程因竞争资源而造成的一种僵局（相互等待）
  若无外力作用，这些进程都将无法向前推进

例如：某计算机系统中只有一台打印机和一.台输入设备，进程P1 正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2所占用，而P2在未释放打印机之前，又提出请求使用正被P1 占用的输入设备。这样，两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。

1.2 死锁产生的原因

• 系统资源的竞争

• 进程推进顺序非法

• 死锁产生的必要条件

  1. 互斥条件：进程要求对所分配的资源进行排他性控制。
  2. 不剥夺条件：资源未使用完，不能被其他进程强行夺走，只能由该进程自己释放（主动释放）。
  3. 请求保持条件：进程至少保持了一个资源，但又提出了新的资源请求。
  4. 循环等待条件：存在一种进程资源循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

二、死锁处理策略

2.1 死锁预防

设置限制条件，破坏死锁产生的4个必要条件之一。

1. 互斥条件一般无法破坏

2. 破坏不剥夺条件
   规定一个已经保持资源的进程在提出新的请求时若不能立即满足，则释放其所有资源

3. 破坏请求保持条件
   规定所有进程都必须一次性申请其在运行过程中所需的全部资源
   简单易行，但可能会造成资源严重浪费

4. 破坏循环等待条件
   将系统中的资源按类型赋予不同的序号，并规定所有的进程必须严格按照序号递增的顺序申请资源

2.2 避免死锁

• 在资源的动态分配过程中，用某种方法防止系统进入不安全状态。

2.2.1 系统安全状态

所谓安全状态，是指系统能按某种进程推进顺序(P1, P… P,)为每个进程P;分配其所需的
资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称P1, P…, P,为
安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。
实例：

• 假设系统中有三个进程P1,P2和P3，共有12台磁带机。进程P1共需要10台磁带机，P2和P3分别需要4台和9台。假设在To时刻，进程P, P2和P3;已分别获得5台、2台和2台，尚有3台未分配，见表。
  在To时刻是安全的，因为存在一个 安全序列P2, PI,P3，只要系统按此进程序列分配资源，那么每个进程都能顺利完成。也就是说，当前可用磁带机为3台，先把3台磁带机分配给P2以满足其最大需求，P2 结束并归还资源后，系统有5台磁带机可用;接下来给P1分配5台磁带机以满足其最大需求, P1结束并归还资源后，剩余10台磁带机可用;最后分配7台磁带机给P3，这样P3也能顺利完成。
• 若在To时刻后，系统分配1台磁带机给P3，系统剩余可用资源数为2，此时系统进入不安全状态，因为此时已无法再找到一个安全序列。当系统进入不安全状态后，便可能导致死锁。例如，把剩下的2台磁带机分配给P2, 这样，P2完成后只能释放4台磁带机，既不能满足P1又不能满足P3， 致使它们都无法推进到完成，彼此都在等待对方释放资源，陷入僵局，即导致死锁。

注意：

• 安全状态下一定不会发生死锁
• 不安全状态下可能发生死锁
• 死锁一定发生在不安全状态下

2.2.2 银行家算法

2.3 死锁的检查与解除

• 资源分配图
  系统死锁可利用资源分配图来描述。如图所示，用圆圈代表一个进程，用框代表一类资源。 从进程到资源的有向边称为请求边,表示该进程申请一个单位的该类资源;从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。

进程P1 已经分得了两个R1资源，并又请求一个R2资源;进程P2分得了一个R1资源和一个R2资源，并又请求一个R1资源。

• 死锁定理

  S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。
  依次消除与不阻塞进程相连的边，直到无边可消。判断某种资源是否有空间，应用它的资源数量减去它在资源分配图中的出度。

• 死锁解除

  • 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。
    但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。
  • 撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以
    按进程优先级和撤销进程代价的高低进行。
  • 进程回退法：让一(或多) 个进程回退到足以回避死锁的地步，进程回退时自愿释放资
    源而非被剥夺。要求系统保持进程的历史信息，设置还原点。

死锁处理策略比较：