操作系统【六】

四、死锁


1、什么是死锁

死锁(Deadlock),是指多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种状态时,若无外力作用,它们都将无法再向前推进。

2、资源和死锁原因

(1)资源

可重用性资源和消耗性资源

  • 可再用资源:可以被多个进程多次使用
    • 可抢占资源:CPU
    • 不可抢占资源:打印机
  • 消耗性资源:只可使用一次的资源;即由一个进程产生,被另一进程使用后就再也无用的资源,也称为临时性资源如信号量,中断信号,同步信号等(临时性资源)
    • “申请–分配–使用–释放”模式

可抢占(剥夺)和 不可抢占(非剥夺性)资源

系统有两类资源:可剥夺资源和非剥夺性资源。

  • 一类资源是可剥夺的,如处理机(高优先权的进程剥夺低优先权进程的处理机)和内存区(存储器管理程序可以把一个进程从一个存储区移至另一个存储区,甚至调出到外存上)。
  • 另一类资源是不可剥夺的,当系统把这类资源分配给某进程后.再不能强行收回,只能在进程用完后自动释放,如磁带机、打印机等。

(2)死锁原因

产生死锁的原因

==1、竞争不可抢占性资源引起死锁==

  • ==当系统中供多个进程所共享的资源,不足以同时满足它们的需要时,引起它们对资源的竞争而产生死锁。==

==2、竞争消耗性资源资源引起死锁==

==3、进程间推进顺序非法进程==

  • ==在运行过程中,请求和释放资源的顺序不当,导致了进程死锁。==
  • 参与死锁的进程最少是两个
  • 参与死锁的进程至少有两个已经占有资源
  • 参与死锁的所有进程都在等待资源
  • 参与死锁的进程是当前系统中所有进程的子集

(3)产生死锁的必要条件

  • ==互斥条件 :==进程对所分配到的资源进行排它性的使用
  • ==请求和保持条件:== 进程已经至少保持了一个资源,但又提出了新的资源请 求,而该资源又已被其他进程占有
  • ==不剥夺条件:== 进程已获得的资源在未使用完之前不能被剥夺
  • ==环路等待条件 :== 在发生死锁时,必然存在一个进程–资源循环等待的环形链 即进程集合(P0,P1,…,Pn)中的P0正在等待一个P1占用的资源;Pl正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

3、处理死锁的基本方法

1、预防死锁 通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或几个条件,来防止发生死锁。

  • 优点:容易实现,已被广泛使用;

  • 缺点:设置的限制条件往往太严格,有可能降低系统资源利用率和系统吞吐量。

    2、避免死锁 在资源动态分配过程中,用某种方法防止系统进入不安全状态,从而避免发生死锁,只需在事先加以较弱的限制条件。

  • 目前在较完善的系统中,常用此方法来避免发生死锁。

    3、检测死锁 允许系统在运行过程中发生死锁,及时检测出死锁的发生,采取措施将系统中的死锁清除。

4、 解除死锁 常用的实施方法是撤消或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。

死锁的检测和解除措施,有可能使系统获得较好的资源利用率和系统吞吐量,但实现难度最大。

4、预防死锁

①破坏“请求和保持”条件 :进程请求资源时,不能持有不可抢占资源。

  • 第一种协议(静态分配):所有进程在开始运行之前必须一次性的申请整个运行过程所需的全部资源。进程在运行期间不会再申请资源了
    • 简单、易于实现、安全
    • 资源浪费严重进程经常会发生饥饿现象
  • 第二种协议:允许一个进程只获得运行初期所需的资源后便开始运行,在运行过程中再逐步释放已获得的且已用完的全部资源,然后再请求新的所需资源。(磁带机、磁盘机、打印机)

破坏“不可抢占”条件 :当一个已经保持了某些不可抢占资源的进程,提出新的资源请求不能得到满足时,必须释放已经保持的所有资源,待以后需要时再重新申请。

  • 进程逐个地申请所需资源当一个已经保持了某些资源的进程申请新资源而不能得到满足时,必须放弃所有已保持的资源。容易造成进程前一阶段工作的失效,即使不失效也会使进程前后两次运行的信息不连续。
  • 缺点:实现复杂、代价高昂。反复申请和释放资源会导致进程的执行被无限的推迟,不仅延长了进程的周转时间,还增加了系统开销,降低了系统的吞吐量。

破坏“循环等待”条件:系统将所有资源按类型分配序号并排队所有进程申请资源必须按序号递增的顺序

  • 资源利用率和系统吞吐量较高
  • 但在资源管理和资源申请方面仍有问题
    • 存在问题:资源的需求顺序不等于序号,仍存在资源浪费。
    • 另外假入某进程已请求到一些序号较高的资源,又想申请序号低的资源时,必须先释放更高序号的资源后,才能申请序号低的资源。
    • (1)资源所分配的序号,必须相对稳定,这就限制了新设备类型的增加。
    • (2)进程使用各资源的顺序,与系统规定的顺序不同,造成对资源的浪费。
    • (3)按规定次序申请资源的方法,必然会限制了用户简单、自主地编程。

5、避免死锁

避免死锁的核心在于,如果资源在分配给某个进程后会在将来导致死锁,那么就不同意资源请求,取消资源的分配。

(1)安全状态

在避免死锁的方法中,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次资源分配的安全性。 若此次分配不会导致系统进入不安全状态,则将资源分配给进程; 否则,令进程等待。

所谓安全状态,是指系统能按某种进程顺序(P1, P2, …,Pn)为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地完成。此时称(P1, P2, …, Pn)为安全序列。

如果系统无法找到这样一个安全序列,则称系统处于不安全状态

==P2—>P1—>P3的顺序可以使得进程顺利执行,所以为安全状态==

==没有序列使得三个进程能够顺利执行,为不安全状态。因为P2执行完毕后释放4个资源,而P1至少要5个P3只要要6个==

(2)银行家算法

假设系统中有 n 个进程,m 种资源,规定:

  • 每个进程在运行前先声明自己需要的最大资源数,用一个 n*m 的最大需求矩阵 Max 表示各个进程的需求情况,比如 Max[i][j]= K 就表示进程 i 需要 K 个 j 类型资源
  • 用一个 n*m 的分配矩阵 Allocation 表示各个进程的已分配资源情况
  • 用一个 n*m 的需求矩阵 Need 表示各个进程的最多还需要资源情况,Need = Max - Allocation
  • 用一个 m 长度的一维数组 Avaliable[k] 表示剩余K资源的数目
  • 用一个 m 长度的一维数组 Request_i[k] 表示某个进程 i 某次申请的资源K数目

按照之前说过的流程图,银行家算法的工作过程是:

  • 请求资源数是否超过最大资源数?Request_i[j]<=Need[i][j],则到下一步;否则出错
  • 请求资源数是否超过剩余资源数?Request_i[j]<=Available[j],则到下一步;否则说明资源不够,进程等待
  • 尝试进行资源分配。
    • 剩余资源减少:Available = Available - Request
    • 已分配资源增加:Allocation[i][j] = Allocation[i][j] + Request_i[j]
    • 需求资源减少:Need[i][j] = Need[i][j] - Request_i[j]
  • 对分配后的状态通过安全性算法进行预判:
    • 安全状态:不会发生死锁,可以分配资源
    • 不安全状态:可能发生死锁,不分配资源
安全性算法

==其实本质上就进行假设运行计算,看看能否成功分配资源==

(1) 设置两个向量:

① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,

Work := Available;

② Finish: 它表示系统是否有足够的资源分配给进程,使之运行完成。 开始时先做Finish[i] := false; 当有足够资源分配给进程时, 再令Finish[i] := true。

(2) 从进程集合中找到一个能满足下述条件的进程: ① Finish[i] = false; ② Need[i,j] ≤ Work[j]; 若找到, 执行步骤(3), 否则,执行步骤(4)。

(3) 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:

Work[j] := Work[i] + Allocation[i,j];

Finish[i] := true;

go to step 2;

(4) 如果所有进程的Finish[i] = true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。

注意:已经架设借出去了,修改了need和available,在此基础上进行安全检查

假如现在有 P0 ~ P4 共五个进程,ABC 三类资源,个数为(10,5,7)。在某一时刻,资源剩余量为(3,3,2),各个进程的最大需求量、已分配量和需求量如下图所示:

如何检测当前是否处于安全状态呢?尝试寻找安全序列:

  • 当前剩余资源(3,3,2),无法满足 P0 需要的(7,4,3),所以不能首先分配给 P0;但是可以满足 P1 需要的(1,2,2),P3 需要的(0,1,1),所以可以分配给 P1 和 P3,P1 和 P3 进入安全序列。
  • P1 和 P3 执行完之后,归还资源,剩余资源(3,3,2)+(2,0,0)+(2,1,1)=(7,4,3),可以满足 P0 需要的(7,4,3),P2 需要的(6,0,0),P4 需要的(4,3,1),所以 P0、P2、P4 依次进入安全序列
  • 所以存在安全序列 P1->P3->P0->P2->P4 ,使得按照这个顺序分配资源后,每个进程都能拿到需要的资源并顺利完成,所以该状态是安全状态。

看另一种情况。假如现在有 P0 ~ P4 共五个进程,ABC 三类资源,个数为(10,5,7)。在某一时刻,资源剩余量为(3,3,2),各个进程的最大需求量、已分配量和需求量如下图所示:

当尝试寻找安全序列的时候,容易发现 P1 P3 可以满足,所以 P1 P3 进入安全序列,此后剩余资源为(7,4,3)。又由于 P0 P2 P4 都是无法满足的,所以实际上并不存在一个安全序列使得所有进程都能被分配资源。因此状态是不安全状态,可能发生死锁,取消资源分配。

6、检测和解除死锁

由于死锁发生的频率并不太高,所以商业操作系统的设计者认为死锁不是什么大问题,所以不用去管它!防止死锁的代价很高,比重启机器100次代价还高,因此不如直接重启。

允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生一旦死锁发生则采取专门的措施,解除死锁并以最小的代价恢复操作系统运行

(1)资源分配图(Resource Allocation Graph)

资源类:用方框表示(资源的不同类型)

资源实例:用方框中的圆点表示(存在于每个资源中)

进程 :用圆圈中加进程名表示

分配边:资源实例——>进程的一条有向边

申请边:进程——>资源类的一条有向边

如果资源分配图中没有环路,则系统中没有死锁,如果图中存在环路则系统中==可能==存在死锁。

==如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件。==

资源分配图化简
  • 首先找出非阻塞非孤立的进程点。P1 P2 都不是孤立的,所谓非阻塞指的是进程请求的资源数量足够,比如说 P2 请求 R1,由于 R1 已经有两个被 P1 占有,一个被 P2 占有,无多余资源,所以 P2 请求的资源数量不够,P2 是阻塞的;而 P1 请求 R2,因为 R2 只有一个被 P2 占有,所以有多于资源,P1 请求的资源数量足够,P1 是非阻塞的。这样就找到了符合条件的进程点 P1
  • 去除这样的点的所有边。那么就会去除 P1 的所有边,归还所有资源。P1 成为孤立点。
  • 重复第一步和第二步。此时,因为这次 P2 请求的 R2 资源是足够的(被 P1 释放了),所以 P2 是非阻塞非孤立的点,把他的全部边去除
  • 由于图中所有的边都能被消除,所以称该图可以被简化,因此它不存在死锁(如果不可简化,则存在死锁)

==在进行一系列化简后若能消去图中所有的边,使所有进程结点成为孤立结点,则称该图是可完全简化的;否则是不可完全简化的==

==已经证明:所有的化简顺序都得到相同的不可简化图==

==同样可以证明,S为死锁的充分条件是:当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理==

当发现有进程死锁后,便应立即把它从死锁状态中解脱出来,重要的是以最小的代价恢复系统的运行。方法如下:

  • 重新启动
    • 最简单,最常用的方法就是进行系统的重新启动,不过这种方法代价很大,它意味着在这之前所有的进程已经完成的计算工作都将付之东流,包括参与死锁的那些进程,以及未参与死锁的进程。
  • 撤消进程
  • 剥夺资源
  • 进程回退
    • 进程回退策略,即让参与死锁的进程回退到没有发生死锁前某一点处,并由此点处继续执行,以求再次执行时不再发生死锁。
    • 虽然这是个较理想的办法,但是操作起来系统开销极大,要有堆栈这样的机构记录进程的每一步变化,以便今后的回退,有时这是无法做到的。

7、总结

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~