封面《絆きらめく恋いろは》

死锁的概念

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

死锁产生的原因

系统资源不足
程序执行的顺序有问题
资源分配不当等

死锁产生的必要条件

产生死锁必须满足四个必要条件，任意一个条件不成立，死锁就不会发生。

互斥条件

在某一段时间内，资源仅被一个进程占有。若有其他进程请求该资源，则请求进程只能等待。

不剥夺条件

进程所获得的资源在未使用完之前，不能被其他进程强行夺走，只能由获得该资源的进程自己来释放。

请求并保持条件

进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此时请求进程被阻塞，但对自己获得的资源保持不放。

循环等待条件

存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

处理死锁

死锁预防

破坏死锁的 4 个必要条件

破坏互斥条件

有些资源必须互斥使用，因此无法破坏互斥条件。

破坏不剥夺条件

当进程请求新资源得不到满足时，必须释放已经持有的资源，重新申请。这个策略实现起来比较复杂，反复的申请和释放会导致系统开销增加，降低系统吞吐量。这种方式适用于容易保存和恢复的资源，例如 CPU 的寄存器和内存资源，一般不能用于打印机之类的资源。

破坏请求与保持条件

采用预先静态分配方法，进程在运行之前申请完它所需的所有资源，在使用过程中，这些资源一直归它所有。

容易发生两个问题：1. 导致部分进程饥饿现象，永远申请不满资源。2. 导致资源浪费，有些资源只在运行初期或者结束时候使用。

破坏循环等待条件

为了破坏循环等待条件，可以采用顺序资源分配法。给资源编号，进程按照编号递增的顺序请求资源。

容易造成资源使用的浪费和用户编程的麻烦。

死锁避免

在使用前进行判断，只允许不会产生死锁的进程申请资源
死锁避免是利用额外的检验信息，在分配资源时判断是否会出现死锁，只在不会出现死锁的情况下才分配资源
各种死锁防止方法能够防止发生死锁，但必然会降低系统并发性，导致低效的资源利用率

安全状态

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

银行家算法

银行家算法的主要思想是避免死锁进入不安全状态。每次进行资源分配时，它先检查系统是否有足够的资源满足要求，若有则先进行分配，并对分配后的新状态进行安全性检查。若新状态安全，则正是分配上述资源，否则拒绝分配上述资源。然后回收已分配的资源，进行下一轮分配。这样能保证资源始终处于安全状态，从而避免死锁发生。

上图 c 为不安全状态，因此算法会拒绝进入图 c 请求