一. 基础概念
死锁的定义
在多道程序系统中，由于进程的并发执行，提升了系统效率，但是多个进程并发执行带来新的问题——死锁。
- 死锁：由于多个进程因竞争资源而造成的一种僵局（互相等待对方手里的资源），使得各个进程都被阻塞。若无外力干涉，这些进程都无法向前推进。
- 例如：某计算机系统只有一台打印机和一台输入设备，进程 P1 正在占用打印机，进程 P2 正在占用输入设备。两个进都提出请求需要使用对方手中的资源，则这两个进程将无休止等待，陷入死锁状态。
死锁与饥饿
- 死锁原因：一组进程内每个进程都在等待一个事件，该事件只可能由组内另一个进程产生。
- 饥饿原因：进程在信号量内无穷等待。
- 当系统中有多个进程同时申。请某类资源，由分配策略确定资源分配次序，有的分配策略不能保证等待时间的上界存在。这种情况即使未发生死锁，某些进程需要长时间等待。当等待时间给进程带来明显影响时候，就发生“饥饿”现象，甚至最终“饿死”。
- 饥饿不表示一定死锁，但至少有一个进程的执行被无限期推迟。
- 相同点：都是进程无法顺利向前推进的现象。
- 差别
- 发生饥饿的进程可能只有一个；而发生死锁现象的进程 ≥2 个。
- 发生饥饿的进程可以处于阻塞态或就绪态（长期得不到 CPU，如 SJF 算法的问题）。
- 发生死锁的进程必定处于阻塞态。
- 死锁，饥饿与死循环
死锁产生原因
- 系统资源的竞争
- 由于不可剥夺资源（如磁带机，打印机等）数量有限，不能满足多个进程的需要。
- 对于可剥夺资源（如 CPU 和主存）的竞争不会引起死锁。
- 进程推进顺序非法
- 请求和释放资源的顺序不当。
某计算机系统只有一台打印机和一台输入设备，进程 P1 正在占用打印机，进程 P2 正在占用输入设备。两个进都提出请求需要使用对方手中的资源，此时就会造成死锁。
- 信号量使用不当：进程彼此相互等待对方发来的消息，使得进程都无法向前推进。
如：进程 A 等待进程 B 发来的消息，进程 B 又在等待进程 A 发来的消息。可以看出，进程 A 和 B 不是因为竞争同一资源，而是在等待对方的资源导致死锁。
死锁产生的必要条件
- 互斥条件
- 进程对分配的资源进行排他性使用，一段时间内仅允许一个进程占有。
- 此时请求资源使用的进程必须等待。
- 不可剥夺条件
- 进程获得 的资源未使用完之前，不能被其他进程夺走，只能由该进程自己主动释放。
- 请求并保持条件
- 进程已经持有一个资源，但是又提出了新的资源请求，而该资源被其他进程占有。
- 此时请求进程被阻塞，但是不放弃自己已经持有的资源。
- 循环等待条件
- 存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程请求。如下图：
资源分配圈：循环等待 VS 死锁
参考上图所示资源分配圈
- 循环等待：资源分配圈中 Pn 进程需要的资源不必须只能由 P(n+1) 进程来提供，也可以获得圈外其他同类资源。【即系统中同类资源数量>1】
- 死锁：资源分配圈中 Pn 进程需要的资源必须只能由 P(n+1) 进程来提供，要求更严格。【系统中同类资源数量=1】
死锁处理策略
- 死锁预防：设置某些限制条件，破坏产生死锁的四个必要条件中一个或多个。
- 避免死锁：资源动态分配过程中，使用某种方法防止系统进入不安全状态。
- 死锁的检测及解除：不采取限制措施，允许死锁的发生。通过检测机构检测出死锁发生，然后采取某种措施解除死锁。
- 对比：
二. 死锁预防
预防死锁，只需要破坏产生死锁的四个必要条件之一即可。
破坏互斥条件
- 原理：将只能互斥访问的资源改造为允许共享使用，这样就可以避免系统进入死锁。
如：操作系统可以使用 SPOOLing 技术将独立设备改造为共享设备。
- 弊端：有些资源（如打印机等临界资源）只能互斥使用，因此该方法不太可行；而且，为了 系统安全，很多时候必须保护互斥性。
破坏不可剥夺条件
- 原理：当进程占有某些资源，但是请求某些新的资源不能得到满足时候，必须放弃已占有资源，待以后重新申请。
- 弊端：
- 实现起来比较复杂。
- 释放已获得资源可能造成前一段工作失效。
因此 常用于 状态易于保存和恢复的资源，如：CPU 的寄存器及内存资源。
一般不能用于打印机之类的资源：反复申请和释放资源既影响进程推进速度，又增加系统开销，进而降低系统吞吐量。
破坏请求并保持条件
- 采用预先静态分配法：进程运行前一次申请完它所需要的全部资源。资源未被满足之前，不让它投入运行，进程运行期间，不提出资源分配请求。【从而破坏”请求“条件；等待期间不占用任何资源，破坏”保持“条件。】优点：实现简单。
- 优点：实现简单。
- 缺点：系统资源被严重浪费，有些资源可能仅在运行初期或快结束才使用，而且还会导致“饥饿”现象：个别资源长期被其他进程占用，导致等待该资源的进程长时间得不到运行。
- 允许进程只获得运行初期所需资源后，即可开始运行。运行过程中逐步释放分配给自己且已使用完毕的全部资源后，才能请求新的资源。
- 特点：改进了方法一缺点。
破坏循环等待条件
- 方法：顺序资源分配法：给系统中各类资源编号，规定每个进程必须按编号递增顺序请求资源，同类资源（编号相同）一次申请完。
一个进程只有在已经占有小编号的资源时，才有资格申请更大编号的资源。已有大编号资源，不能逆向请求小编号资源，避免了循环等待。
- 缺点：
- 编号必须相对稳定，不便于增加新类型设备。
- 进程实际使用资源的顺序可能与编号次序不一样，造成资源浪费。
- 必须按规定次序申请资源，给用户编程带来麻烦。
三. 死锁的避免
避免死锁属于事先预防策略，允许进程动态申请资源，在每次分配资源前，分析此次资源分配结果是否会带来死锁风险；只有在不产生死锁的前提下，系统才会分配资源。否则让进程等待。
限制条件较弱，有利于获得较好的系统性能。
系统安全状态
- 安全状态：是指系统能按照某种进程推进顺序（P1，P2…Pn）为每个进程 Pi 分配所需资源，直至满足每个进程对资源的最大需求，使得每个进程都可顺利完成。此时称 P1，P2，P3…Pn 为安全序列（可能有多个）。若系统无法找到一个安全序列，则称系统处于不安全状态。
- 如果系统处于安全状态，则一定不会发生死锁；反之有可能发生死锁。
银行家算法
- 核心思想：在每次分配资源前，分析此次资源分配结果是否会带来死锁风险，由此决定是否分配资源**。**
四. 死锁检测和解除
死锁避免 VS 死锁检测
- 死锁避免：需要保证进程运行过程一直不出现死锁；需要知道进程从开始到结束的所有资源请求。
- 死锁检测：检测某个时刻是否发生死锁，不需要知道进程整个生命周期的资源请求，只需要知道对应时刻的资源请求。
死锁检测
死锁解除
- 资源剥夺法
- 挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程。
- 应防止挂起时间过长导致长时间处于资源匮乏状态。
资源分配图中，用死锁定理简化后，还有边相连的进程就是死锁进程。
撤销进程法
- 强制撤销部分、甚至全部死锁进程并剥夺进程的资源。
- 撤销原则
- 按进程优先级
- 按撤销进程代价高低
- 实现简单，付出的代价可能很大。【有些进程可能已经接近结束，一旦终止，以后需要从头再来】
- 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。
- 回退时自愿释放资源 而并非剥夺。
- 要求系统保持进程的历史信息，设置还原点。
