2.6 死锁

死锁的定义、产生原因与四个必要条件；死锁预防（破坏四个条件）、死锁避免（安全状态与银行家算法）、死锁检测（资源分配图与死锁定理）与死锁解除。

死锁的概念

死锁：多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。例如某计算机系统中只有一台打印机和一台输入设备，进程 P1 正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程 P2 所占用，而 P2 在未释放打印机之前，又提出请求使用正被 P1 占用的输入设备。

死锁产生的原因：

1. 系统资源的竞争：通常系统中拥有的不可剥夺资源（如磁带机、打印机）的数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源（如 CPU、主存）的竞争是不会引起死锁的；
2. 进程推进顺序非法：请求和释放资源的顺序不当，也同样会导致死锁。信号量使用不当也会造成死锁（如生产者-消费者问题中 P 操作顺序颠倒）。

死锁的处理策略

死锁预防：破坏必要条件

• 破坏互斥条件：若允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行（SPOOLing 技术可以把独占设备改造成逻辑上的共享设备）；
• 破坏不剥夺条件：当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。常用于状态易于保存和恢复的资源，如 CPU 的寄存器及内存资源；
• 破坏请求并保持条件：采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。缺点：系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用；还会导致”饥饿”现象；
• 破坏循环等待条件：采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。缺点：编号必须相对稳定，限制了新类型设备的增加；作业使用资源的顺序与系统规定顺序不同，会造成资源的浪费；按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。

死锁避免：安全状态与银行家算法

死锁避免同样属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。

• 安全状态：系统能按某种进程推进顺序（P1, P2, …, Pn）为每个进程 Pi 分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称 P1, P2, …, Pn 为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态；
• 并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。

银行家算法的数据结构：可利用资源向量 Available、最大需求矩阵 Max、分配矩阵 Allocation、需求矩阵 Need = Max − Allocation。当进程 Pi 发出请求向量 Request_i：

安全性算法：设置 Work = Available，Finish 全为 false；从进程集合中找到一个满足 Finish[i] = false 且 Need_i ≤ Work 的进程，令 Work = Work + Allocation_i，Finish[i] = true，重复此步；若所有进程的 Finish 都为 true，则系统处于安全状态，否则处于不安全状态。

死锁检测与解除

资源分配图：用圆圈代表一个进程，用框代表一类资源（框中的一个圆点代表一个资源）。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。

死锁定理：简化资源分配图可检测系统状态 S 是否为死锁状态：① 在资源分配图中，找出既不阻塞又不孤点的进程 Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源数量），消去它所有的请求边和分配边，使之成为孤立的结点；② 进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程，继续化简。S 为死锁的条件是当且仅当 S 状态的资源分配图是不可完全简化的，该条件为死锁定理。

死锁解除：

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

即时练习