【校招VIP】操作系统--死锁- 校招VIP

转载声明：文章来源https://blog.csdn.net/Huangmiaomiao1/article/details/123827973

资源

进程：一个具有独立功能的程序关于某个数据集合的一次运行活动，程序在并发环境中的执行过程。

资源的使用模式

一个进程在使用资源前要申请资源，用完后要释放资源。进程是按照它完成任务所需的资源情况来申请资源的。

● 申请：若所申请的资源被其他进程占用不能立即得到，那么需要等待

● 使用：进程对该资源进行操作

● 释放：进程释放它以前申请且分配到的资源

上述操作都是通过系统调用实现的，系统需要设立若干个表格，记载资源的申请和分配情况。

可抢占资源 & 不可抢占资源

可抢占资源：另外进程可以从拥有她的进程那里把他抢占过去占为己用，并且不会产生任何不良影响

不可抢占资源：不能从当前占有她的资源中强行抢占资源，必须由拥有者自动释放，否则会引起相关的计算的失效

死锁与不抢占资源有关，而与可抢占资源有关的潜在死锁问题可以通过进程间重新分配资源来化解。

资源的分类：

● 按照组成情况和功能：

○ 硬件资源：CPU、内存、外设

○ 软件资源：信号量、消息、文件

● 按使用性质分：

○ 可再用资源：一次仅供一个进程使用，并且可以由多个进程重复使用的资源

○ 消耗性资源：被动态创建和毁坏的资源

死锁

在一个进程集合中，每个进程都在等待仅由该集合中的另一个进程才能引发的事件，而无限期僵持下去的局面

产生死锁的原因

根本原因：资源有限且操作不当

● 系统提供的资源太少，远不能满足并发进程对资源的需求

● 由于资源推进顺序不合适而引发死锁

资源太少不一定会产生死锁

死锁的条件

同时具备以下四个条件才会发生死锁，这四个条件也不是完全无关的，比如循环等待条件就隐含着前面三个条件

互斥条件：独占资源在一段时间内只能由一个进程所占有

占有且等待条件：进程已经有占有一个资源，但又申请新的资源

不可抢占条件：一个进程所占的资源在用完之前，别的进程不能强行夺走该资源，只能等该资源主动释放

循环条件：存在一个进程等待序列

环路 & 死锁

在每个资源实体只有一个的情况下，出现环就是出现死锁的充要条件

每个资源实体不止一个，出现环路是死锁存在的必要但不是充分条件

如果没有环路，不会陷入死锁状态；如果存在环路，则有可能出现死锁

如何判断一开始到底有无死锁？

a. 假设在这种状态之后没有新的请求，每个可运行的进程都以最有利的方式前进，那么非封锁状态的进程总可以进行下去直至完成，最后释放它所占用的资源。

b. 这些释放的资源又可唤醒等待它的进程，使后者也活动起来

c. 这样可造成两种结局：一种是还剩下若干封锁进程，另一种是系统中全部进程执行完毕；由此可断定之前是否有死锁

处理方法

利用某些协议预防或避免死锁，保证系统不会进入死锁状态

允许系统进入死锁状态，然后设法发现并解决它

忽略这个问题，好像系统中从来不会出现死锁

死锁的预防

死锁产生的条件必须同时具备四个条件，设法保证至少一个条件不具备，就破坏了产生了死锁的条件，从而预防了它的发生，由此可根据产生死锁的四个必要条件提出预防措施

破坏互斥条件

a. 一般来说这个方法并不能用来预防死锁，因为某些资源的固有属性就是独占的

b. 独占资源必定有互斥条件；可共享的资源不需要互斥存取，也不会包含在死锁中；一个进程从来不会在一个可共享资源上一直等待下去

破坏占有且等待条件（进程已经有占有一个资源，但又申请新的资源）

a. 需要保证，一个进程无论何时都可以申请他没有占有的任何资源

b. 方法：

ⅰ. 预分资源策略：在一个进程开始之前就申请并分配所有所需要的全部资源，在执行过程中无需额外申请。在实现时，一个进程申请资源的系统调用先于其他系统的调用–资源的静态分配

ⅱ. 空手申请资源策略：每个进程仅在它不占有资源的时候才能申请资源。

c. 缺点：

ⅰ. 进程在执行过程中是动态的、不可预测的，在执行之前不可能知道它所需要的所有资源

ⅱ. 资源利用率低

ⅲ. 降低进程的并发性

ⅳ. 有进程总得不到运行机会的饥饿状况，如果一个进程需要很多资源，他们又都是进程争用的资源，那么这个进程必然无期限地等待下去，因为她所需要的资源总是被别的进程所占用

破坏非抢占条件

a. 隐式抢占方式：如果一个进程占有某些资源，还要申请别的被占有的资源，那就处于等待状态，此时它所占的全部资源都可被占。也就是这些资源都隐式释放了，该进程的资源申请表中加上该被剥夺的资源。仅当它获得所有所需资源的时候，才会被重新启动。

b. 抢占等待者的资源：若一个进程申请某些资源，首先应该检查他所需要的资源是否可供使用

ⅰ. 如果可以使用，则分给该进程

ⅱ. 如果不可使用，就应该查看，这些资源是否已经分开另外的某个正等待附加资源的进程。如果是这样的话，就从等待进程那儿抢占过来，分给申请他们的进程；如果不是的话，就必须等待

ⅲ. 该进程在等待时，她的资源可以被抢占过去，但是仅当另外的进程需要他们的时候才会这样

c. 这些方法常用于资源状态以保留和恢复的环境，如CPU和内存，不适用于打印机和磁带机

破坏循环等待条件

a. 资源有序分配：把全部资源事先按类编号，然后依序分配，是进程申请、占用资源不会形成环路

b. 先弃大，再取小；无论何时，一个进程申请资源rj，他应该释放所有满足F(ri)>=F(rj)关系的资源ri

c. 提高了资源的利用率和系统的吞吐量

d. 限制了进程对资源的请求，同时给系统中所有资源合理编号有困难，会增加系统开销；为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，增加了进程对资源的占用时间

死锁的避免

死锁的预防是排除死锁的静态策略，这种方式会导致资源的利用率降低和减少系统的吞吐量

死锁的避免是动态策略，不限制进程的有关申请资源的命令，而是对进程发出的每个申请都加以检查，根据检查结果进行分配。

关键：确定资源分配的安全性

安全状态

安全序列：针对目前的分配状态来说，系统至少能够按照某种次序为每个进程分配资源（直至最大需求），并且使他们能够依次运行到结束，这种进程序列称为安全序列；

如果存在这样的一个安全序列，则系统此时的分配状态是安全的，否则是不安全的。

在安全序列一定不会有死锁发生，但是系统进入不安全序列也未必产生死锁；当然系统产生死锁后，系统一定处于不安全状态。

死锁是不安全状态中的特例

资源分配图算法

如果系统中某类资源只有一个单位，则成为单体资源类

如果某类资源具有多个单位，则成为多体资源类

如果系统中都是单体资源类，则可以利用资源分配图来避免死锁。

银行家算法

思想：若用户申请一组资源时，系统必须做出判断；如果这些资源分配出去会处于不安全状态则申请暂不满足；反之可以将资源分配出去

死锁的恢复与检测

由于操作系统有并发、共享、随机等特点，通过避免和预防来排除死锁是非常困难的，这不仅需要较大的开销，而且不能充分利用资源，一种简便的方法是：系统为进程分配资源的时候，不采取任何限制性措施，但是提供检测和解脱死锁的手段，即能够发现死锁和从死锁状态中解脱出来

死锁的检测和恢复指设有专门的机构，当死锁发生的时候，机构能够检测死锁发生的位置和原因，且通过外力破坏死锁发生的必要条件，从而使并发进程从死锁的状态中挣脱出来。

等待图检测死锁

如果系统中所有类型的资源都只有一个单位（单体资源类），可以采用一种较快的死锁检测算法，即资源分配图的变形–等待图。

pi -> pj ：表示pi等待pj释放pi所需的资源

当且仅当等待图中有环路，系统存在死锁。

为了检测思索，需要建立等待图并适时进行修改，定期调用搜索图中的搜索环路算法

对于多体资源类的死锁检测算法

从死锁中恢复

抢占资源

○ 临时性的将资源从当前占有它的进程哪里拿过来，分给另外的某些进程，直至死锁环路被打破。

○ 但在很多情况下，需要人工干预，特别是大型主机上的批处理系统，往往由管理员强行把某些资源从资源的占用进程那里取过来，分配给其他进程

○ 从哪里抢占资源，通常按最小代价原则处理，考虑代价的因素包括进程占有多少资源，以及运行了多少时间

○ 能否做道抢占资源且在不影响原进程的执行的情况下返回，取决于资源的属性，一般来说，实现起来是很困难的，甚至不大可能

回退执行

○ 回退方法由管理员做出安排，定期对系统中的各个进程进行检查，并将检查点的有关信息（进程状态、资源状态）写入文件，以备重启时使用。当检测到死锁时，就让某个占有的必要资源的进程回退到他取得另外某个资源之前的一个检查点，从而打破死锁。

○ 系统中应该保存一系列检查点的文件，以便前后各个检查点的文件不应被覆盖，因为往往需要回退多级

○ 回退进程要被重置为先前他们有占用资源时的情况，如果回退进程试图再次获得该资源，就必须等待，直到该资源被别的进程所释放，成为可用资源

○ 一旦决定要回退一个特定的进程，一定要确定这个进程后退多远，最简单的方法是让整个进程重新运行，即终止进程并重新启动他；更有效的方法是，回退到恰好解除死锁的地方，然而这要求系统保存有关运行进程状态的更多信息。还有一种全体回退的方式，即每个死锁进程都回退到前面定义的某个监测点，然后重新启动所有的进程。这需要系统又重启和回退的机制。当然这种方法有再次陷入死锁的风险，而并发处理的不确定性，往往能够保证不再出现同样的情况。

杀掉进程

○ 两种方式：

■ 终止所有的进程

■ 一次种植一个进程，直至消除所有的死锁环路

○ 如何确定终止某个进程带来的开销最小，一般考虑以下的因素

○处理死锁的三种基本方式对比

针对不同情况采用不同的策略：

把所有资源组合成若干资源类

为了预防资源类之间因循环等待二出现死锁，预先采用线性排序策略对他们进行编号

在一个资源内部，采用最适合于该类的资源算法

饥饿 & 活锁

饥饿

在可以预计的时间内，某个或某些进程永远得不到完成工作的机会，因为他们所需要的资源总是被其他进程所抢占，这种情况被称作饥饿或者饿死—无限期被延迟，尽管他从未被阻塞

饥饿不同于死锁，但与死锁相近，死锁的进程必定处于阻塞状态，而饥饿的进程不一定被阻塞，而刻意处于就绪状态

来利用先来先服务的资源策略可以避免饥饿现象

活锁

一个或多个进程在轮询的等待某个不可能为真的条件，导致一直重复尝试、失败，但始终无法完成，处于活锁的进程没有被阻塞，可以被调度运行，因而会导致CPU的资源耗尽，使系统性能大大下降。

活锁可以仅涉及一个实体，往往涉及多个实体。

活锁与饥饿的区别

处于活锁的实体是在不断地改变状态，并未封锁，是可以活动的；而处于死锁的实体表现为等待、静止不动

活锁可以自行解开的，而死锁不行

活锁是忙式等待，占用CPU且不会让出CPU，而饥饿时调度时总是让出CPU，造成无限期的等待下去。