【操作系统】浅谈死锁的产生、预防、避免、检测与解除

写在前面

• 关于文章

  在多道程序系统中,同时有多个进程并发运行,共享系统资源,从而提高了系统资源利用率，提高了系统的处理能力。但是,若对资源的管理、分配和使用不当,也会产生一种危险,即在一定条件下会导致系统发生一种随机性错误——死锁(Deadlock)。这是因为进程在运行时要使用资源,在一个进程申请与释放资源的过程中,其他的进程也不断地申请资源与释放资源。由于资源总是有限的,因而异步前进的诸进程会因申请,释放与资源顺序安排不当,造成一种僵局。

  • 上一篇文章：【操作系统】OS资源管理之设备管理 - 编程那点事儿 (imyjs.cn)

• 我的站点

  网络云书签-理想 (imyjs.cn)

  理想智能云解析 (imyjs.cn)

  任务墙 (imyjs.cn)

  LiXiang's Blog (gitee.io) 不再更文

  学编程那点事儿 (imyjs.cn)

• 联系我

  🐧：2410685763

  WeChat：Super_Baby_00

  公众号：编程那点事儿

基本概念

死锁

在多道程序系统中,一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源,这种现象称系统处于死锁状态,简称死锁。处于死锁状态的进程称为死锁进程。
当死锁发生后,死锁进程将一直等待下去,除非有来自死锁进程之外的某种干预。系统发生死锁时,死锁进程的个数至少为两个;所有死锁进程都在等待资源,并且其中至少有两个进程已占有资源。

活锁

如果进入临界区互斥的时间很短,而阻塞等待的时间开销很大,那么在某种情形下,可采用轮询(忙等待)原语进入临界区或存取资源。
假设有一对进程使用两种资源,每个进程需要两种资源,它们利用轮询原语enter_region去尝试取得必要的锁,如果尝试失败,则该进程继续尝试。如果进程A先运行并得到资源1,然后进程2运行且得到资源2,以后不管哪一个进程运行,都不会有任何进展,但是哪一个进程也没有被阻塞。结果是两个进程总是一再消耗完分配给它们的时间片,但是没有进展也没有阻塞。因此,没有出现死锁现象(因为没有进程阻塞),但是从现象上看,好像死锁发生了,这就是活锁( Livelock )。

饥饿

系统不能保证某个进程的等待时间上界，从而使该进程长时间等待，当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死。

饥饿现象可以通过先来先服务资源分配策略来避免。在这种机制下,等待得最久的进程会是下一个被调度的进程。随着时间的推移,所有进程都最终能够获得资源而完成。

资源

死锁是若干进程因使用资源不当而造成的现象。按照资源的使用性质,一般把系统中的资源分成两类:

• 永久性资源(可重用资源)

  系统中那些可供进程重复使用、长期存在的资源，如内存、外部设备,CPU等硬件资源,以及各种数据文件、表格、共享程序代码等软件资源。

• 临时性资源(消耗性资源)

  由某个进程所产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源,如I/О和时钟中断、同步信号、消息等。

死锁产生原因

产生死锁的原因主要有两个:

• 一是竞争资源,系统提供的资源数量有限,不能满足每个进程的需求;
• 二是多道程序运行时,进程推进顺序不合理。

常见死锁产生原因：

• 申请不同类资源产生死锁
• 申请同类资源产生死锁
• P、V操作使用不当产生死锁
• 对临对性资源的使用不加限制而引起的死锁

死锁产生必要条件

互斥条件

资源是独占的且排他使用。进程互斥使用资源,即任一时刻一个资源只能给一个进程使用，其他进程若请求一个资源而该资源被另一进程占有时,则申请者等待,直到资源被占用者释放。

不可剥夺条件

又称不可抢占或不可强占。进程所获得的资源在未使用完毕之前,不能被其他进程强行剥夺,而只能由获得该资源的进程自愿释放。

请求和保持条件

又称部分分配或占有申请。进程每次申请它所需要的一部分资源,在申请新的资源的同时，继续占用已分配到的资源。

循环等待条件

又称环路等待。在发生死锁时,必然存在一个进程等待队列{P1,P2.,…,Pn} ,其中P1等待P2占有的资源,P2,等待P3占有的资源…,Pn等待P1占有的资源,形成一个进程等待环路。环路中每一个进程已占有的资源同时被另一个进程所申请,即前一个进程占有后一个进程所请求的资源。

死锁解决方法

用于解决死锁的方法有两类，一类是不让死锁发生;另一类是让死锁发生,再加以解决，具体为以下四种:

• (1）预防死锁。通过设置某些严格限制,破坏产生死锁的条件(除第一个条件外的其他条件)以防止死锁发生。这一方法会导致系统资源利用率过低。
• (2）避免死锁。在资源的动态分配过程中,采取某种方法防止系统进入不安全状态,从而避免死锁的发生。这种方法只需以较弱的限制条件为代价,并可获得较高的资源利用率。
• (3）检测死锁。允许系统运行过程中发生死锁,即事先不采取任何预防、避免措施。但通过在系统中设置检测机构,可以及时检测出死锁是否真的发生,并能精确地确定与死锁有关的进程与资源,然后采取措施解除死锁。
• (4）解除死锁。这是与死锁检测相配套的措施,用于将进程从死锁状态下解脱出来。

死锁预防

在系统设计时确定资源分配算法,限制进程对资源的申请,从而保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。

破坏“互斥条件”

如果资源不被一个进程所独占,那么死锁肯定不会产生。资源是否属于临界资源属性与资源本身性质有关，一般不可修改。所以，破坏“互斥条件”一般不可行。

破坏“不可剥夺”条件

在允许进程动态申请资源的前提下规定:一个进程在申请新资源的要求不能立即得到满足时便处于等待状态,而一个处于等待状态的进程的全部资源可以被剥夺。也就是说,这些资源隐式地释放了,被剥夺的资源重新加入到资源表中。仅当该进程重新获得它原有的资源以及得到新申请的资源时,才能重新启动执行。

具体实施方案为若一个进程申请某些资源,首先系统应检查这些资源是否可用,如果可用,就分配给该进程。否则,系统检查这些资源是否分配给另外某个等待进程。若是,则系统将剥夺所需资源,分配给这个进程。如果资源没有被等待进程占有,那么该进程必须等待。在其等待过程中,其资源也有可能被剥夺。

破坏不可剥夺条件以预防死锁的方法适用于这样一些资源,它们的状态是容易保存和恢复的,例如CPU、内存等。
这种策略实现起来较复杂,而且代价太大。因为,一个资源在使用一段时间后被强行剥夺，会造成前阶段工作失效。而且,在极端情况下,可能出现某个进程反复申请和释放资源,使进程执行无限推迟,还增加系统开销,延长了进程的周转时间,降低系统的吞吐量和性能。

破坏“请求和保持”条件

• 第一种方法是每个进程必须在开始执行前就中请它所需要的全部资源,仅当系统能满足进程的资源申请要求且把资源―次性分配给进程后,该进程才能开始执行。

  这是静态分配资源策略,而资源的动态分配是指进程需要使用资源时才提出申请,系统再进行分配。

  采用静态分配资源的策略后,进程在执行过程中不再申请资源,故不可能出现占有了某些资源再等待其他资源的情况,即“请求和保持”的条件不成立,从而防止死锁的发生。

  静态分配资源策略的优点是简单、安全、容易实施;但其缺点是严重浪费系统资源,会造成一些资源在很长时间内得不到使用,降低资源利用率。

  另外,因为当进程获得其所需全部资源后方能开始运行。但由于有些进程长期占用资源,致使进程推迟,甚至得不到运行。

• 第二种方法是仅当进程没有占用资源时才允许它去申请资源,如果进程已经占用了某些资源而又要再申请资源,则它应先归还所占的资源后再申请新资源。

  这种资源分配策略仍会使进程处于等待状态,这是因为进程所申请的资源可能已被其他进程占用,只能等占用者归还资源后才可分配给申请者,但是,申请者是在归还资源后才申请新资源的,故不会出现占有了部分资源再等待其他资源的现象。这种方法也存在着资源利用率低的缺点。

破坏“循环等待”条件

采用资源有序分配策略,其基本思想是将系统中所有资源顺序编号,一般原则是,较为紧缺、稀少的资源的编号较大。进程申请资源时,必须严格按照资源编号的顺序进行,否则系统不予分配。即一个进程只有得到编号小的资源,才能申请编号较大的资源;释放资源时,应按编号递减的次序进行。

一般,为了提高资源的利用率,通常应当按照大多数进程使用资源的次序对资源进行编号。先使用者编号小,后使用者编号大。

这种硬性规定申请资源的方法,会给用户编程带来限制,按照编号顺序申请资源增加了资源使用者的不便;此外,如何合理编号是一件困难的事情,特别当系统添加新设备类型时,会造成不灵活、不方便;如果有进程违反规定,则仍可能发生死锁。

资源有序分配法与资源静态分配策略相比,显然提高了资源利用率,进程实际需要申请的资源不可能完全与系统所规定的统一资源编号一致,为遵守规定,暂不需要的资源也要提前申请,仍然会造成资源的浪费。

死锁避免

死锁避免的基本思想是:系统对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源;如果分配后系统可能发生死锁,则不予分配,否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

死锁避免和死锁预防的区别在于,死锁预防是设法至少破坏产生死锁的四个必要条件之一，严格地防止死锁的出现。而死锁避免则不那么严格地限制产生死锁的必要条件的存在,因为即使死锁的必要条件存在,也不一定发生死锁。

安全状态

由于在避免死锁的策略中允许进程动态地申请资源,因而,系统需提供某种方法在进行资源分配之前先分析资源分配的安全性,当估计到可能有死锁发生时就应设法避免死锁的发生。

如果操作系统能保证所有的进程在有限时间内得到所需的全部资源,则称系统处于“安全状态”,否则说系统是不安全的。

银行家算法

操作系统按照银行家的规定为进程分配资源,进程首先提出对资源的最大需求量,当进程在执行中每次申请资源时,系统测试该进程已占用的资源与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则系统再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。这样做,能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行结束,执行结束后归还的资源加入到系统的剩余资源中,这些资源又至少可以满足另一个进程的最大需求……于是,可以保证系统中所有进程都能在有限的时间内得到需要的全部资源。

银行家算法是通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的,在能确保系统处于安全状态时才把资源分配给申请者,从而避免系统发生死锁。由于银行家算法是在系统运行期间实施的,要花费相当多的时间,该算法需要mxn²操作。

银行家算法要求每类资源的数量是固定不变的,而且必须事先知道资源的最大需求量,这难以做到。不安全状态并非一定是死锁状态,如果一个进程申请的资源当前是可用的,但该进程必须等待,这样资源利用率会下降。

死锁检测与解除

死锁预防和死锁避免的几种方法都比较保守,并且都是以牺牲系统效率和浪费资源为代价的,这恰恰与操作系统的设计目标相违背。

假如系统为进程分配资源时,不采取任何限制性措施来保证系统不进入死锁状态,即允许死锁发生,但操作系统不断地监督进程的进展路径,判定死锁是否真的发生,并且,一旦死锁发生,则采取专门的措施解除死锁,并以最小代价使整个系统恢复正常,这就是死锁检测和解除。

操作系统可定时运行一个“死锁检测”程序,该程序按一定的算法去检测系统中是否存在死锁。检测死锁的实质是确定是否存在“循环等待”条件,检测算法确定死锁的存在并识别出与死锁有关的进程和资源,以供系统采取适当的解除死锁措施。

死锁解除法可归纳为两大类。

• 剥夺资源
  使用挂起/激活机制挂起一些进程,剥夺它们占有的资源给死锁进程,以解除死锁,待以后条件满足时,再激活被挂起的进程。

  由于死锁是由进程竞争资源而引起的,所以,可以从一些进程那里强行剥夺足够数量的资源分配给死锁进程,以解除死锁状态。剥夺的顺序可以是以花费最小资源数为依据。

• 撤销进程
  撤销死锁进程,将它们占有的资源分配给另一些死锁进程,直到死锁解除为止。
  可以撤销所有死锁进程,或者逐个撤销死锁进程,每撤销一个进程就检测死锁是否继续存在,若已没有死锁,就停止进程的撤销。

  以下几点可作为衡量撤销代价的标准:

  • (1）进程优先数,即被撤销进程的优先数。
  • (2）进程类的外部代价。不同类型的进程可以规定出各自的撤销代价。系统可根据这些规定,撤销代价最小的进程,达到解除死锁的目的。
  • (3）运行代价,即重新启动进程并运行到当前撤销点所需要的代价。这一点可由系统记账程序给出。

微信关注

WeChat