【操作系统】死锁相关知识点

1. 死锁基本概念

多个并发进程中&＃xff0c;如果每个进程持有某种资源而又等待其它进程释放其他资源&＃xff0c;在未改变这种状态之前都不能向前推进&＃xff0c;称这一组进程产生了死锁。通俗的讲就是 多个进程无限期相互等待 的一种状态。

2. 死锁的四个必要条件

死锁产生的 4 个条件&＃xff08;有一个条件不成立&＃xff0c;则不会产生死锁&＃xff09;&＃xff1a;

• 互斥&＃xff1a;一个资源一次只能被一个进程使用
• 请求与保持&＃xff1a;一个进程因请求资源而阻塞时&＃xff0c;对已获得资源保持不放
• 非抢占&＃xff1a;进程获得的资源&＃xff0c;在未完全使用完之前&＃xff0c;不能强行抢占
• 循环等待&＃xff1a;若干进程之间形成一种头尾相接的环形等待资源关系

抢占资源和非抢占资源&＃xff1a;

• 可抢占资源&＃xff1a;可以从拥有它的进程中抢占而不产生副作用。
• 不可抢占资源&＃xff1a;不引起相关的计算失败的情况下&＃xff0c;无法把它从占有它的进程处抢占过来。

一般来说&＃xff0c;可抢占资源不会引起死锁&＃xff0c;可以在进程间重新分配资源而得到解决。

资源分配图&＃xff08;RAG&＃xff09;&＃xff1a;用有向图描述系统资源和进程的状态。

进程 P1 已经分得了两个 R1 资源&＃xff0c;并又请求一个 R2 资源&＃xff1b;进程 P2 分得了一个 R1 和一个 R2 资源&＃xff0c;并又请求一个 R1 资源。

死锁发生时&＃xff0c;系统中一定有由两个或以上的进程组成的一条环路&＃xff0c;该环路中的每个进程都在等待着下一个进程所占有的资源。用一个有向图来表示资源分配的情况。用圆形节点表示进程&＃xff0c;方形表示资源。从 资源节点到进程节点的有向边表示该资源被请求、并被进程占用&＃xff0c;从 进程到资源节点的有向边表示进程正在请求该资源&＃xff0c;并且因为请求资源而导致进程被阻塞&＃xff0c;处于等待该资源的状态。一旦在某个时候有向图中出现了 两个或两个以上进程组成的环路&＃xff0c;就会导致死锁的发生。

死锁定理&＃xff1a;如果资源分配图中没有环路&＃xff0c;则系统中没有死锁&＃xff0c;如果图中存在环路则系统中可能存在死锁&＃xff1b;如果每个资源类中只包含一个资源实例&＃xff0c;则环路是死锁存在的充分必要条件。

3. 死锁处理方法

死锁的四个处理方法&＃xff1a;

• 鸵鸟策略&＃xff1a;忽略掉死锁&＃xff0c;视而不见
• 死锁检测与恢复&＃xff1a;允许死锁发生&＃xff0c;检测它们是否发生&＃xff0c;一旦发生死锁&＃xff0c;就采取行动解决问题
• 死锁避免&＃xff1a;仔细对资源进行分配&＃xff0c;动态地避免死锁&＃xff0c;银行家算法是避免死锁的经典算法
• 死锁预防&＃xff1a;破坏引起死锁的 4 个必要条件

3.1 鸵鸟策略

把头埋在沙子里&＃xff0c;假装根本没发生问题。

因为解决死锁问题的代价很高&＃xff0c;因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响&＃xff0c;或发生死锁的概率很低&＃xff0c;就可以采用鸵鸟策略。

大多数操作系统&＃xff0c;包括 Unix&＃xff0c;Linux 和 Windows&＃xff0c;处理死锁问题的办法仅仅是忽略它。

3.2 死锁检测与恢复

不试图阻止死锁&＃xff0c;而是当检测到死锁发生时&＃xff0c;采取措施进行恢复。

死锁检测&＃xff1a;

• 每种类型一个资源的死锁检测&＃xff1a;检测有向图中是否存在环。从一个节点出发进行深度优先搜索&＃xff0c;对访问过的节点进行标记&＃xff0c;如果访问了已经标记的节点&＃xff0c;就表示有向图存在环&＃xff0c;也就是检测到了死锁。
• 每种类型多个资源的死锁检测&＃xff1a;每个进程最开始时都不被标记&＃xff08;未执行状态&＃xff09;&＃xff0c;执行过程有可能被标记。当算法结束时&＃xff0c;任何没有被标记的进程都是死锁进程。

三个典型的检测时机&＃xff1a;

• 当进程由于资源请求不满足而等待时检测死锁&＃xff0c;缺点是系统开销大
• 定时检测
• 系统资源利用率下降时检测死锁

每种类型多个资源的死锁检测算法&＃xff1a;

1. 寻找一个没有标记的进程 Pi&＃xff0c;要求它所请求的资源小于等于剩余资源量。
2. 如果找到了这样一个进程&＃xff0c;就将其占有的资源量加到剩余资源量中&＃xff0c;并标记该进程&＃xff0c;转回第 1 步。
3. 如果没有找到这样一个进程&＃xff0c;说明发生死锁。

死锁恢复&＃xff1a;

• 抢占恢复&＃xff08;资源剥夺&＃xff09;&＃xff1a;死锁发生的必要条件&＃xff0c;其中一个就是不可抢占。如果允许抢占&＃xff0c;那么就可以破坏死锁条件。
• 回滚恢复&＃xff08;进程回退&＃xff09;&＃xff1a;周期性对进程进行检查点检查&＃xff0c;一旦发现了死锁&＃xff0c;就回滚到一个较早的检查点上。
• 杀死进程恢复&＃xff08;撤销进程&＃xff09;&＃xff1a;杀死一个进程可以释放它占有的资源&＃xff0c;如果仍然不行那么久继续杀死其他进程直到打破死锁。

3.3 死锁避免

在程序运行时避免发生死锁&＃xff0c;包括两种方法&＃xff1a;1&＃xff09;资源轨迹图&＃xff0c;2&＃xff09;银行家算法。

1. 资源轨迹图

如果知道了进程在各个阶段需要哪些资源&＃xff0c;那么可以在图中进程标注。两个进程的交叠区域就是一个会造成死锁的区域。进程在图中只能向右或者向上前进&＃xff0c;一旦进入了危险区&＃xff0c;那么就可能发生死锁。为了避免死锁&＃xff0c;应当在合适的时间阻塞某个进程&＃xff0c;使得运行避开这个区域。

2. 银行家算法

银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时&＃xff0c;它首先检查系统是否有足够的资源满足要求&＃xff0c;如果有&＃xff0c;则先进行分配&＃xff0c;并对分配后的新状态进行安全性检查。如果新状态安全&＃xff0c;则正式分配上述资源&＃xff0c;否则就拒绝分配上述资源。这样&＃xff0c;它保证系统始终处于安全状态&＃xff0c;从而避免死锁现象的发生。

安全状态

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

安全状态与不安全状态的区别是&＃xff0c;从安全状态出发&＃xff0c;系统能够保证所有的进程都能完成&＃xff1b;而从不安全状态出发&＃xff0c;没有这样的保证。

单个资源的银行家算法

一个小城镇的银行家&＃xff0c;他向一群客户分别承诺了一定的贷款额度&＃xff0c;算法要做的是对每一个请求进行检查&＃xff0c;检查如果满足了这一需求是否会达到安全状态。如果能&＃xff0c;那么满足该需求&＃xff1b;如果不能&＃xff0c;就推迟对这一请求的满足。

银行家算法可以推广到多个资源的情况&＃xff0c;此时可以写成矩阵的形式&＃xff0c;每次判断一行是否满足&＃xff0c;即一个进程的多个资源都进行检查。

多个资源的银行家算法

检查一个状态是否安全的算法&＃xff1a;

• 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行&＃xff0c;那么系统将会发生死锁&＃xff0c;状态是不安全的。
• 假若找到这样一行&＃xff0c;将该进程标记为终止&＃xff0c;并将其已分配资源加到 A 中。
• 重复以上两步&＃xff0c;直到所有进程都标记为终止&＃xff0c;则状态时安全的。

如果一个状态不是安全的&＃xff0c;需要拒绝进入这个状态。

实际上&＃xff0c;死锁避免是非常困难的&＃xff0c;无论是资源轨迹图还是银行家算法&＃xff0c;都需要事先知道进程运行的过程中需要的最大资源数&＃xff0c;这几乎是不可能实现的。

3.4 死锁预防

死锁预防就是在程序运行之前预防发生死锁&＃xff0c;即破坏发生死锁的 4 个必要条件。死锁避免可以认为是在程序执行中动态地避免死锁发生&＃xff0c;而死锁预防可以说是静态的方式&＃xff0c;杜绝死锁发生的可能性。

1. 破坏互斥条件&＃xff1a;尽量使得资源不被某个进程独占。

但有些资源不能同时访问&＃xff0c;如打印机等临界资源只能互斥使用。所以在某些场合应该保护这种互斥性。

2. 破坏占有和等待条件&＃xff1a;禁止已经持有资源的进程再等待其他资源。一种方式是&＃xff0c;在进程开始执行前请求所需的全部资源&＃xff08;预先静态分配的方法&＃xff09;&＃xff0c;如果不能满足&＃xff0c;那么就不分配资源&＃xff0c;进行等待。这种方式的问题在于&＃xff0c;类似银行家算法&＃xff0c;事先不知道需要多少资源&＃xff0c;而且资源利用率不高。另一种方式就是&＃xff0c;当一个进程请求资源时&＃xff0c;先暂时释放其当前所占用的所有资源&＃xff0c;然后再尝试一次获取所需的全部资源。

这种方式实现简单&＃xff0c;但缺点也显而易见&＃xff0c;系统资源被严重浪费&＃xff0c;其中有些资源可能仅在运行初期或运行快结束时才使用&＃xff0c;甚至根本不使用。而且还会导致“饥饿”现象&＃xff0c;当由于个别资源长期被其他进程占用时&＃xff0c;将致使等待该资源的进程迟迟不能开始运行。

3. 破坏不可抢占条件&＃xff1a;允许资源抢占即可。当然&＃xff0c;有的时候资源应当是不可抢占的。

该策略释放已获得的资源可能造成前一阶段工作的失效&＃xff0c;反复地申请和释放资源会增加系统开销&＃xff0c;降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源&＃xff0c;如 CPU 的寄存器及内存资源&＃xff0c;一般不能用于打印机之类的资源。

4. 破坏环路等待&＃xff1a;一种方法是对资源进行编号&＃xff0c;进程在任何时候都可以请求资源&＃xff0c;但是所有的请求必须按照资源编号的顺序&＃xff08;升序&＃xff09;提出。

这种方法存在的问题是&＃xff0c;编号必须相对稳定&＃xff0c;这就限制了新类型设备的增加&＃xff1b;尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序&＃xff0c;但也经常会发生作业使甩资源的顺序与系统规定顺序不同的情况&＃xff0c;造成资源的浪费&＃xff1b;此外&＃xff0c;这种按规定次序申请资源的方法&＃xff0c;也必然会给用户的编程带来麻烦。

3.5 死锁处理策略比较

4. 其他相关

4.1 活锁

活锁指进程并没有被阻塞&＃xff0c;但由于某些条件没有满足&＃xff0c;导致一直重复尝试、失败、尝试、失败。进程仍可以在 CPU 上活动&＃xff0c;但 CPU 时间片执行完了之后又下了 CPU&＃xff0c;进程没有任何进展但也没有阻塞。

活锁和死锁的区别&＃xff1a;

• 活锁有可能自行解开&＃xff0c;而死锁不能
• 活锁有 CPU 执行权&＃xff0c;而死锁进程是无法获得 CPU 执行权的

4.2 饥饿

饥饿&＃xff1a;进程无限等待的情况。饥饿 ≠ 死锁&＃xff0c;但是饥饿至少有一个进程的执行被无限期推迟。

产生饥饿的原因&＃xff1a;往往是由于资源分配策略的 “不公平性” 导致的&＃xff0c;比如短作业优先。此时系统虽然没有发生死锁&＃xff0c;某些进程也可能会一直得不到 CPU 的使用权而长时间等待。当 “饥饿” 到一定程度&＃xff0c;进程任务即使完成也不再具有实际意义时称该进程被 “饿死”。

饥饿与死锁都是由于 资源竞争 而引起的。

饥饿与死锁的差别&＃xff1a;

• 进入“饥饿”状态的进程可以只有一个&＃xff0c;而由于循环等待条件而进入死锁状态的进程却必须大于或等于两个。
• 处于“饥饿”状态的进程可以是一个就绪进程&＃xff0c;如静态优先权调度算法时的低优先权进程&＃xff0c;而处于死锁状态的进程则必定是阻塞进程。
• 死锁进程等待的是永远不会被释放的资源&＃xff0c;而饿死进程等待的是会释放但不会分配给自己的资源。
• 死锁一定发生了循环等待&＃xff0c;而饿死不一定。可以通过资源分配图检测是否死锁&＃xff0c;但不能检测是否有进程饿死。

4.3 通信死锁

当一个进程 A 向 B 发送信息后挂起&＃xff0c;需要 B 进程的回复唤醒时&＃xff0c;如果请求信息丢失&＃xff0c;A 就会被阻塞以等待回复&＃xff0c;B 会阻塞等待一个向其发送命令的请求&＃xff0c;因而发生死锁。

4.4 两阶段加锁

这是针对数据库的一种方法。第一阶段中&＃xff0c;进程试图对 所有需要更新的记录 进行加锁&＃xff0c;一旦某个记录已经被加锁&＃xff0c;就释放之前的锁&＃xff0c;从头进行重试。只有当第一阶段所有获取锁的行为都成功&＃xff0c;才进行第二阶段的更新&＃xff0c;否则放弃所有的锁。

参考文章&＃xff1a;
《计算机操作系统》总结五&＃xff08;死锁&＃xff09;
死锁 作者&＃xff1a;luStar
CS-Notes&＃xff1a;死锁