本系列文章为408考研操作系统知识点整理仅涉及到一些重要的考研知识点并不是完全系统全面的知识，参考书目和视频资料：汤小丹 计算机操作系统（第四版），操作系统考研复习指导，B站王道考研操作系统视频课。

2.4.1 死锁的概念

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

区分几个概念

死锁：各个进程互相等待对方手中的资源，导致各进程都阻塞，无法向前推进
饥饿：由于长期得不到想要的资源，某进程无法向前推进。比如短进程优先算法中，如果有源源不断的短进程到来，则长进程会一直得不到处理机
死循环：某进程执行过程中一直跳不出循环。有时是因为逻辑bug导致，有时是故意而为之

发生死锁的必要条件

死锁必须同时满足以下四个条件才会发生

互斥条件：是指只有对必须互斥使用的资源抢夺时才可能导致死锁。比如打印机设备就可能导致互斥，但是像内存、扬声器则不会。

持有并等待条件：是指进程已经至少保持了一个资源，但又提出了新的资源请求，但是该资源又被其他进程占有，此时请求进程被阻塞，但是对自己持有的资源保持不放
不可剥夺条件：是指进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
循环等待条件（注意发生死锁一定有循环等待，但是发生循环等待未必死锁）

循环剥夺条件：是指存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

死锁产生的原因

对不可剥夺资源的不合理分配，可能会导致死锁
对系统资源的争夺
进程推进顺序非法
信号量使用不当

死锁处理策略

预防死锁：破坏死锁产生的四个必要条件中的一个或几个
避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁。例如银行家算法
死锁的检测和解除：允许死锁产生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解决死锁

2.4.2 死锁预防

破坏互斥条件：如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。但并不是所有资源都可以改造为成共享使用的资源的，而且为了系统安全性，很多地方也是禁止改造的，所以互斥条件一般无法破坏。

破坏不可剥夺条件：可以有以下两种方案
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放
方案二：当某个进程需要的资源被其他进程占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各个进程的优先级

实现起来比较复杂
释放已获得的资源可能造成前一阶段工作的失效，所以这种方法一般只适用于易保存和恢复状态的资源，比如CPU
反复申请和释放资源会增加系统开销，降低系统吞吐量
若采用方法一，意味着只要暂时得不到某个资源，之前获得的那些资源都需要放弃，以后再重新申请，容易导致进程饥饿。

破坏持有并等待条件：可以采用静态分配方法。进程在运行前一次申请完它所需要的全部资源，在它的资源未得到满足前，不允许投入运行；一旦投入运行，这些资源就一直归它所有，该进程不会再请求别的任何资源。
有些资源可能只需要使用很短的时间，因比如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低，并且该策略也有可能导致饥饿现象

破坏循环等待条件：可以采用顺序资源分配方法。首先给系统中的资源进行编号，规定每个进程必须按照编号递增的顺序请求资源，编号相同的资源（也就是同类资源）一次申请完

不方便增加新的设备，因为可能需要重新分配所有的编号
进程实际使用资源的顺序可能和编号递增顺序不一致，造成资源浪费
必须按规定次序申请资源，为用户编程带来了麻烦

2.4.3 死锁避免

安全状态 安全序列

避免死锁：允许进程动态申请资源，但系统在进行资源分配的时候，应该先计算此次分配的安全性，如若此次分配不会导致系统进入不安全状态，则允许分配，否则等待
安全状态和安全序列：是指系统能按照某种进程推进顺序(P1,P2,P3)为每个进程分配其所需要的资源，直到满足每个进程资源的最大需求，使每个进程都可以额顺序完成。其中(P1,P2,P3)称之为安全序列。
只要能找出一个安全序列，系统就是安全状态；分配资源后若找不出任何一个安全序列，则系统进入了不安全状态
安全序列可能有多个

注意：并非所有的不安全状态都是死锁状态，但是当系统进入不安全状态，就有可能进入死锁状态；而如果系统处于安全状态，则一定不会进入死锁状态


银行家算法

具体来说，操作系统按照银行家制定的规则为进程分配资源，进程运行之前先要声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。如果超过则拒绝分配：如果没有超过则测试系统现存资源能否满足该进程尚需的最大资源量，若能满足则按当前申请量分配，不满足则推迟分配。

2.4.4 死锁检测和解除

死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来

死锁检测

资源分配图

两种结点
进程结点：对应一个进程
资源结点：对应一类资源，其数量可能有多个
两种边
进程结点—>资源结点：进程想要申请多少个资源，每条边代表一个
资源结点—>进程结点：表示已经为进程分配了多少个资源，每条边代表一个

死锁定理

判断是否发生死锁：如果系统中的可用资源数目满足进程的需求，那么这个进程暂时是不会被阻塞的，可以顺利执行；如果这个进程结束后将资源归还给了系统，就可能使某些正在等待资源的进程被激活，并顺利执行下去。

可完全简化：如果能够消除所有的边，就称此资源图可完全简化，此时一定没有发生死锁，相当于可以找到一个安全序列。如果不能消除所有边，此时就发生了死锁，而目最终还连着边的那些进程就是处于死锁状态的进程。

死锁解除

解除死锁：一旦检测出死锁发生，就应该立即解除死锁。注意并不是系统中所有的进程都是死锁状态，使用死锁检测算法化简资源分配图后，还连着边的那些进程就是需要进行解除的死锁进程。解除方法主要有：
资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
撤销进程法（终止进程法）：强制撤销部分，甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能性会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这样就要求系统要记录进程的历史信息，设置还原点。

死锁处理策略比较