Chapter 5 死锁
5.1 进程饥饿
系统不能保证进程的等待时间上限，从而使该进程长时间等待，当等待时间给进程推进和响应带来明显不利影响时，称发生了进程饥饿。
5.2 死锁的概念
死锁是指两个或多个进程已经陷入阻塞，都在无限期地等待永远不会发生的条件的一种系统状态。进程进入死锁之后，永远都被阻塞而无法运行。
死锁的另一种定义是在两个或多个进程中，每一个进程都已经持有某一些资源，而在申请其他进程持有的资源。每一个进程都拥有部分资源，但又不足以运行，导致每一个进程都不能向前推进。
5.3 死锁的起因
5.3.1 资源的分类
将系统中的资源分为两类：可抢占资源和不可抢占资源。
可抢占资源指的是该类资源可以被多个进程同时访问，即被一个进程占用使用完之前可以被其他进程抢占，但不影响进程运行结果。如CPU和内存。
不可抢占资源指的是该资源被一个进程占用之后除非该进程已经使用完毕，否则其他进程不能强行抢占该资源，否则进程运行可能会出错。如大多数硬件和软件资源。
5.3.2 死锁的起因
引起系统死锁的原因：
- 系统资源不足，这是引起死锁的根本原因。
- 进程并发推进顺序不当。
关于死锁的一些结论：
- 陷入死锁的进程至少有2个。
- 参与死锁的进程至少有2个已经占有资源。
- 参与死锁的所有进程都在等待资源。
- 参与死锁的进程是当前所有进程的子集。
- 死锁会浪费大量系统资源，甚至导致系统崩溃。
5.3.3 死锁的必要条件
死锁的必要条件：
- 互斥条件，即进程竞争的资源均为不可抢占资源，进程需要互斥地使用这些资源。
- 不剥夺条件，进程释放资源之前不能被其他任何进程剥夺。
- 部分分配条件，进程运行全过程的所需的资源逐步分配，每一个资源在访问之前临时申请。
- 环路条件，多个进程因为资源的申请和占用的关系构成一个逻辑环路，如进程A占用进程B需要的资源，进程B占用进程C需要的资源，进程C占用进程A需要的资源。
5.4 死锁的解决
5.4.1 解决死锁的4种方法
- 预防：通过设置多个限制条件，使得死锁发生的必要条件中有几条不成立。其中破坏互斥条件几乎不可能，破坏不剥夺条件花销较大，破坏部分分配条件需要将资源进行预先静态分配，破坏环路条件需要资源的有序分配。但由于限制过于严格，导致资源利用率和吞吐量降低。
- 避免：用某种方法分析某种分配方式是否会造成死锁，可能导致算法过于复杂而不实用。
- 检测：检测当前系统中是否有发生死锁，难度和复杂程度较大。
- 恢复：撤销或者挂起一些进程以回收一些资源，实现难度大。
5.4.2 预先静态分配法
预先静态分配法破坏了部分分配条件，保证死锁不会发生。其采用全部分配法的策略，在进程运行之前就将其所需的资源一次性全部分配给它。如果资源不够则该进程无法运行。
缺点：浪费资源且资源利用率低，需要资源多的进程可能会被推迟，适应性有局限（某些进程需要如信号量这样的同步信号资源无法提前准备），应用程序设计开销较大。
5.4.3 有序资源分配法
有序资源分配法破坏环路条件，使得环路无法构成。采用的策略是给系统中的每一个资源分配一个序号，且进程每一次申请资源时只能申请比上次申请的资源的序号更大的资源。由于每一个进程只能按照资源序号递增顺序申请资源，因此系统对资源编号时可以按照从小到大的顺序编号，一般是输入设备较小，输出设备较大。
缺点：资源浪费，资源编号不易合理化（难以保证资源使用顺序满足每一个进程的资源使用顺序）
5.4.4 鸵鸟算法
一句话，不管，如果真的发生了死锁，可以由用户手动去清除。