精华内容
下载资源
问答
  • 如何在线程避免发生死锁

    千次阅读 2019-03-09 14:11:09
    死锁:在多道程序设计环境下,个进程可能竞争一定数量的资源,。一个进程申请资源,如果资源不可用,那么进程进入等待状态。如果所申请的资源被其他等待进程占有,那么该等待的进程有可能无法改变状态,这种情况下...

    牛客网上的题目死锁:在多道程序设计环境下,多个进程可能竞争一定数量的资源,。一个进程申请资源,如果资源不可用,那么进程进入等待状态。如果所申请的资源被其他等待进程占有,那么该等待的进程有可能无法改变状态,这种情况下称之为死锁。
    死锁的四个条件:
    互斥:至少有一个资源必须处在非共享模式,即一次只能有一个进程使用,如果另一进程申请该资源,那么申请进程必须延迟直到该资源释放为止。
    占有并等待:一个进程必须占有至少一个资源,并等待另一个资源,而该资源为其他进程所占有。
    非抢占:资源不能被抢占
    循环等待:有一组进程{P0,P1,…Pn},P0等待的资源被P1占有,P1等待的资源被P2占有,Pn-1等待的资源被Pn占有,Pn等待的资源被P0占有。
    形成死锁必须要满足这四个条件。那么违背这几个条件中的任何一个就不会形成死锁,这种方式成为 死锁预防,而死锁避免是动态的检测分配资源的状态是否安全

    • 死锁解决方式
    1. 死锁预防
    2. 死锁避免
    3. 死锁检测并恢复
      三者处理死锁的方式可以类比为:死锁预防,直接铲平坑;死锁避免,直接跳过坑;死锁检测并恢复,摔到坑里,修正一下继续前行。
      对于互斥而言:有的资源本身就是互斥的,所以通常无法破坏这一必要条件。
      对于占有并等待:破坏它,可以指定这样的规则(协议):每一个进程执行前一次性申请完所有资源。或者 每个进程申请当前所需要的资源,当需要使用其他资源时,需要把之前申请的资源释放掉。前者可以理解为破坏等待,后者可以理解为破坏占有。这样做使得资源得利用率很低(最后阶段可能需要用一下打印机,而将其在整个运行期占有);对于优先级低得进程来说,多次释放资源很容易造成它们饥饿。
      对于非抢占:破坏它,即对于已经分配的资源可以进行抢占。当一个优先级比较低,那么它的资源往往会被优先级高得剥夺,导致它饥饿。
      对于循环等待:对所有资源类型进排序,要求每个进程按照资源编号递增顺序申请资源。可以用反证法证明。简要描述一下,在进程按照资源编号递增顺序申请资源的条件下,假设一个循环等待存在,即有一组进程{P0,P1,…Pn},P0等待的资源被P1占有,P1等待的资源被P2占有,Pn-1等待的资源被Pn占有,Pn等待的资源被P0占有。那么Pi+1占有了Ri资源,同时又申请Ri+1,所以资源Ri的编号必然小于Ri+1,那么R0的编号小于R1的…Rn资源的编号小于R0资源的编号(Pn进程)。根据传递性,R0的编号小于R0的编号,显然矛盾,因此,在上述条件下,不会产生循环等待。

    参考:《操作系统概念》

    展开全文
  • 操作系统中死锁

    千次阅读 2019-06-19 14:31:26
    转自:https://blog.csdn.net/weixin_39754631/article/details/91347058 死锁1 死锁的基本概念2 资源分...

    转自:https://blog.csdn.net/weixin_39754631/article/details/91347058

    1 死锁的基本概念

    死锁的定义:一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程。如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃

    从死锁的定义中可以得到几个推论:参与死锁的所有进程都在等待资源;参与死锁的进程是当前系统中所有进程的子集。

    资源数量有限、锁和信号量错误使用都可能导致死锁,锁和信号量的使用可能是开发人员编程导致的,下面着重介绍一下有限资源导致的死锁问题。在操作系统中资源使用的一般模式是:进程提出申请,操作系统进行相应的分配,如果进程所需要的资源不能满足的话,这个进程就进入阻塞或者等待状态,如果可以满足的话进程就直接使用资源,当进程使用完毕之后就释放资源。由于资源的使用方式就是申请-分配-使用-释放,因此有些进程得不到资源就会处理阻塞等待状态,资源有限的话就有可能出现死锁。

    从死锁的角度可以把资源分为两类:一类是可重用资源,即可被多个进程多次使用。可重用资源包括处理器、I/O部件、内存、文件、数据库、信号量等,可重用资源又可以进一步划分为可抢占资源与不可抢占资源,例如cpu就是可抢占资源,进程在cpu上运行的时候允许比它优先级更高的进程抢占cpu,还有一些资源例如打印机是不可抢占的;另一类资源是可消耗资源,即只可使用一次、可创建和销毁的资源,包括信号、中断、消息等。下面讨论的死锁主要针对于可重用资源。

    活锁和饥饿
    活锁的情况是先对资源进行加锁,获得另外一个资源的锁时需要轮询,情况就是每个进程可以上cpu执行,cpu时间片执行完了之后又下cpu,进程既没有进展也不产生阻塞,这种现象就是活锁,而死锁是进程进入等待状态无法获取cpu的执行权。饥饿往往是由于资源分配的策略所决定等待,某个进程一直得不到cpu的使用权,就会造成饥饿。

    产生死锁的必要条件
    (1)互斥使用(资源独占):一个资源每次只能给一个进程使用
    (2)占有且等待(请求和保持,部分分配):进程在申请新的资源的同时保持对原有资源的占有
    (3)不可抢占(不可剥夺):资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放
    (4)循环等待:存在一个进程等待队列 {P1 , P2 , … , Pn},其中P1等待P2占有的资源,P2等待P3占有的资源,…,Pn等待P1占有的资源,形成一个进程等待环路。
    当死锁产生的时候一定会有这四个条件,有一个条件不成立都不会造成死锁。

    2 资源分配图(RAG)

    用有向图描述系统资源和进程的状态,从图的角度为解决死锁提供理论和依据。定义一个二元组G=(V,E)有两个集合组成。其中V是结点的集合,分为P(进程),R(资源)两部分,P = {P1, P2, … , Pn},R = {R1, R2, … , Rm}。E是有向边的集合,其元素为有序二元组,可以是进程节点指向资源节点的有向边后者资源节点指向进程节点的有序边。

    资源分配图图画法说明
    系统由若干类资源构成,一类资源称为一个资源类;每个资源类中包含若干个同种资源,称为资源实例。使用用方框表示资源类;用方框中的黑圆点表示资源实例;用圆圈中加进程名表示进程。分配边是资源实例指向的进程有向边,而申请边是进程指向资源实例的有向边。
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190608202024535.png由资源分配图得到的死锁定理:如果资源分配图中没有环路,则系统中没有死锁,如果图中存在环路则系统中可能存在死锁;如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件。
    在这里插入图片描述
    可以对资源分配图进行化简来查看是否有死锁产生,简化步骤:(1)找一个非孤立、且只有分配边的进程结点去掉分配边,将其变为孤立结点;(2)再把相应的资源分配给一个等待该资源的进程即将该进程的申请边变为分配边。反复进行(1)(2)直到找不到满足非孤立并且只有分配边的进程节点,简化之后如果系统中的进程节点都是孤立的,那么系统中既没有死锁发生;否则系统中一定有环路存在。

    3 处理死锁的方法

    目前处理死锁的方法可以归纳为如下:
    (1)不考虑此问题(鸵鸟算法):把头埋在沙子里,假装根本没发生问题。因为解决死锁问题的代价很高,因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响,或发生死锁的概率很低,可以采用鸵鸟策略。大多数操作系统,包括 Unix,Linux 和 Windows,处理死锁问题的办法仅仅是忽略它。

    (2)不让死锁发生,分为以下两种:

    • 死锁预防:不让死锁发生的静态策略,通过设计合适的资源分配算法,由资源分配策略保证不让死锁发生
    • 死锁避免:不让死锁发生的动态策略,以不让死锁发生为目标,跟踪并评估资源分配过程,根据评估结果决策是否分配

    (3)让死锁发生
    通过死锁的检测判断死锁是否真的发生,然后采用一些方法来解除死锁的问题。

    总体解决锁死发生的方法可以分为四类:鸵鸟算法、死锁预防、死锁避免以及死锁检测与解除。

    3.1 死锁预防

    在设计系统时,通过确定资源分配算法,排除发生死锁的可能性。具体做法是防止产生死锁的四个必要条件中任何一个条件发生即破坏产生死锁的四个条件之一。

    (1)破坏“互斥使用/资源独占”条件
    资源本身的特性是独占的,是排他性使用的,所以要使用一种资源转换技术,把独占资源变为共享资源。例如针对于打印机,SPOOLing技术的引入解决不允许任何进程直接占有打印机的问题。设计一个“守护进程/线程”负责管理打印机,进程需要打印时,将请求发给该daemon,由它完成打印任务。

    (2)破坏“占有且等待”条件
    指一个进程占有了一部分资源,在申请其他资源的时候由于得不到满足而进入等待状态。有下面两种方案实现:

    • 实现方案1:要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配。这种实现会使得资源的利用率很低,当一个进程所需要的资源不能同时满足的情况下可能一直处于等待状态,会产生饥饿现象。
    • 实现方案2:在允许进程动态申请资源前提下规定,一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请。

    (3)破坏“不可抢占”条件
    实现方案是当一个进程申请的资源被其他进程占用时,可以通过操作系统抢占这一资源(两个进程优先级不同)。这种方法具有局限性,适用于状态易于保存和恢复的资源,如CPU、内存资源。

    (4)破坏“循环等待”条件
    主要思想是通过定义资源类型的线性顺序实现,实现方案是资源有序分配法,把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。实现资源的有序分配时需要考虑如何对资源进行编号,通常可以利用资源使用的频繁性进行排序。

    假如有P1,P2…Pn共n个进程,每个进程都需要一定的资源,一定可以找到某个进程所需要申请的资源的序号是最大的这个进程,从这个进程开始执行;这个进程执行完之后再继续找下一个所需要资源序号最大的进程,以此类推,因此使用资源的有序分配法一定可以解决死锁问题。

    3.2 死锁避免

    通过一个例子来讨论死锁避免的设计思想,如下图(a)有两个进程P和Q,系统中一共有M个资源,假设A为进程P对资源需求的最大量,B是进程Q对资源需求的最大量,如果P进程对资源的占用量超过X则Q进程无法运行,如果Q进程对资源的占用量超过Y,则P进程无法运行。
    (b)中X1为进程P的资源占用量,Y1是Q进程的占有量,那么剩余的资源能满足P或Q进程对资源的需求量;©中X2为进程P的资源占用量,Y1是Q进程的占有量,那么剩余的资源可以满足P进程对资源的最大需求量,等P进程释放资源后Q进程就可以继续执行,这时对资源的分配就是有条件的;(d)中剩余资源既不能满足P进程也不能满足Q进程对资源的最大需求量。

    在这里插入图片描述
    根据以上分析,在进程执行过程中,提出资源申请时,操作系统应该根据当时系统所处的状态或者把资源分配给该进程后进入的一个新的状态来调整资源分配策略。具体分析如下:
    OXO3Y区域,P进程Q进程提出申请资源时操作系统都可以满足;XAO2O3区域内,如果P进程提出申请可以无条件满足,Q进程提出申请总数只要不超过Y就可以满足;同时操作系统应该控制不要让资源的申请分配出现在O1O2O3区域,否则系统剩余的资源数量既不能满足P进程也不能满足Q进程,会导致死锁。
    在这里插入图片描述

    通过上面的例子可以给出死锁避免的设计思想:在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统发生死锁或可能发生死锁,则不予分配,否则予以分配,即在资源动态分配过程中,防止系统进入不安全状态,以避免死锁的发生

    安全状态:如果系统中存在一个由所有进程构成的安全序列P1,…,Pn,则称系统处于安全状态。
    安全序列:一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1≤i≤n),它以后还需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和,则称系统处于安全状态。
    注意:安全状态一定没有死锁发生
    不安全状态:系统中不存在一个安全序列。不安全状态一定导致死锁,但是可能目前还没有进入死锁,死锁是不安全状态的一个子集。

    利用银行家算法避免死锁
    银行家算法是仿照银行发放贷款时采取的控制方式而设计的一种死锁避免算法,起这样的名字是因为该算法原本是为银行系统设计的,以确保银行在发放贷款时,不会发生不满足客户需要的情况,在操作系统中也可以用它来避免死锁。

    为实现银行家算法,每一个进程进入系统时,他它须申明在运行过程中,可能需要每种资源类型的最大数目,其数目不能超过系统所拥有的资源总量。当进程请求一组资源时,系统必须首先确定是否有足够的资源分配给该进程。若有,再进一步计算在将这资源分配给进程后,是否会使系统处于不安全状态。如果不会,才将资源分配给它,否则让进程等待。

    应用条件如下:

    • 在固定数量的进程中共享数量固定的资源
    • 每个进程预先指定完成工作所需的最大资源数量
    • 进程不能申请比系统中可用资源总数还多的资源
    • 进程等待资源的时间是有限的
    • 如果系统满足了进程对资源的最大需求,那么,进程应该在有限的时间内使用资源,然后归还给系统

    3.3 死锁检测与解除

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

    检测死锁是否发生有三个典型的检测时机:(1)当进程由于资源请求不满足而等待时检测死锁,缺点是系统开销大;(2)定时检测;(3)系统资源利用率下降时检测死锁。

    一个简单的死锁检测算法
    给每个进程、每个资源指定唯一编号;设置一张资源分配表记录各进程与其占用资源之间的关系;设置一张进程等待表记录各进程与要申请资源之间的关系。从资源等待表出发,看有没有形成等待的环路。即可以利用资源分配图的思想来检测是否有死锁发生。

    死锁避免
    死锁避免的重要是以最小的代价恢复系统的运行,具体的死锁解除的方法有几个:(1)撤消所有死锁进程,代价较大;(2)进程回退(Roll back)再启动,进程在执行过程中,系统会为进程记录一些中间节点,当出现死锁的时候进行回退再一起重新运行,由于需要记录每个进程的现场,所以系统代价也比较大;(3)按照某种原则逐一撤消死锁进程,直到没有死锁;(4)按照某种原则逐一抢占资源(资源被抢占的进程必须回退到之前的对应状态),直到没有死锁。

    4 哲学家就餐问题

    下面以哲学家就餐问题来总结归纳解决死锁问题的各种方法。哲学家就餐问题是一个经典的进程之间同步互斥问题,问题描述为:有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子;每个哲学家的行为是思考,感到饥饿,然后吃通心粉;为了吃通心粉,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左边或右边去取筷子。在解决哲学家就餐问题的时候,要考虑到筷子的互斥使用、不能出现死锁现象。

    哲学家就餐问题的问题模型是:应用程序中并发线程执行时,协调处理共享资源。

    下面是一种错误的解法,考虑到如果所有哲学家同时拿起左手边的筷子,那么就无法拿起右手边的筷子,造成死锁。

    void philosopher(int i) {
        while(TRUE) {
            think();
            take(i);       // 拿起左边的筷子
            take((i+1)%N); // 拿起右边的筷子
            eat();
            put(i);
            put((i+1)%N);
        }
    }
    

    为了防止死锁的发生,可以设置两个条件:必须同时拿起左右两根筷子;只有在两个邻居都没有进餐的情况下才允许进餐。

    #define LEFT (i + N - 1) % N // 左邻居
    #define RIGHT (i + 1) % N    // 右邻居
    #define THINKING 0
    #define HUNGRY   1
    #define EATING   2
    typedef int semaphore;
    int state[N];                // 跟踪每个哲学家的状态
    semaphore mutex = 1;         // 临界区的互斥
    semaphore s[N];              // 每个哲学家一个信号量
    
    void philosopher(int i) {
        while(TRUE) {
            think();
            take_two(i);
            eat();
            put_two(i);
        }
    }
    
    void take_two(int i) {
        down(&amp;mutex);
        state[i] = HUNGRY;
        test(i);
        up(&amp;mutex);
        down(&amp;s[i]);
    }
    
    void put_two(i) {
        down(&amp;mutex);
        state[i] = THINKING;
        test(LEFT);
        test(RIGHT);
        up(&amp;mutex);
    }
    
    void test(i) {         // 尝试拿起两把筷子
        if(state[i] == HUNGRY &amp;&amp; state[LEFT] != EATING &amp;&amp; state[RIGHT] !=EATING) {
            state[i] = EATING;
            up(&amp;s[i]);
        }
    }
    
    

    参考资料:
    视频资料:操作系统原理(北京大学)
    书籍:《计算机操作系统》第四版 汤小丹;《现代操作系统》第四版 陈向群译
    参考博客:CS-Notes/操作系统

    展开全文
  • 分布式系统中死锁处理

    千次阅读 2017-05-26 16:04:30
    分布式系统中死锁处理1死锁发生的条件分布式计算机系统是一种具有处理器并且各个处理器之间通过互连网络构建成一个具有整体功能的计算机系统系统具有的优点是加快了处理的速度,简化了主机的逻辑结构,同时...

    分布式系统中的死锁处理

    1死锁发生的条件

    分布式计算机系统是一种具有多处理器并且各个处理器之间通过互连网络构建成一个具有整体功能的计算机系统。系统具有的优点是加快了处理的速度,简化了主机的逻辑结构,同时具有成本低和易于维护的特点,并且成为计算机应用领域发展中的一个重要方向。但是,在分布式环境下,由于通讯延迟的不确定性、地域的分布性以及资源和数据的高度共享性等影响因素的存在,使得死锁预防和检测变得极为困难。在分布式计算系统中,有两个以上的进程在并发执行,每个进程都在等待被其它的进程所占用的系统资源而不能继续运行,即导致系统中任何一个进程都无法运行下去(死循环),这就产生了死锁。

    当且仅当以下四个条件同时成立时,死锁才会发生:

    1) 互斥。同一个资源在同一时刻最多只能被一个进程占用。

    2) 占有并等待。必然有一个进程至少占用了系统中的一个资源,同时在等待获取被其他进程占用的资源。

    3) 不可剥夺。一个进程不能剥夺被其他进程占用的资源。

    4) 循环等待。在等待图中有一个循环。

    2 处理死锁的策略

    有三种处理死锁的策略:

    1) 预防死锁。限制请求,保证前文提到的四个死锁条件中至少有一个不能发生, 从而预防死锁;

    2) 避免死锁。如果结果状态是安全的, 就将资源动态地分给进程。如果至少有一个执行序列使所有的进程都能完成运行, 那么这个状态就是安全的;

    3) 检测死锁和从死锁中恢复, 允许死锁发生, 然后发现并解除死锁。

    死锁预防和避免采用一种悲观方法,即认为死锁会经常发生并试图阻止或避免它。虽然死锁避免策略在集中式系统中广为应用,并且有许多算法,但是在分布式系统中很少使用。这是因为在分布式系统中没有全局时钟,检查安全性状态会涉及到大量进程和资源的计算,从而引起昂贵的开销。死锁检测和恢复使用乐观方法,然而这种方法对于死锁发生频繁的应用程序可能并不有效。

    3 死锁的AND条件和OR条件

    一般地,有两种死锁:资源死锁和通信死锁。在通信死锁中,进程等待的资源就是报文。资源死锁和通信死锁的真正区别在于资源死锁通常使用AND条件,而通信死锁通常使用OR条件。所谓AND条件就是当进程取得所有所需资源时,它才能继续执行;所谓OR条件就是当进程得到至少一个所需资源,它就能继续执行。由于多数分布式控制结构是不确定的,一个进程可能在等待来自多个进程的报文,而不能确定将被收到的报文究竟来自那个进程,需要每收到一个报文就进行处理,所以通信死锁使用OR条件。

    在使用AND条件的系统中,死锁条件是在等待图中存在回路。但是在使用OR条件的系统中,等待图中的回路未必会引发死锁。在使用OR条件的系统中,死锁条件是存在结(knot)。

    4 死锁的预防

    死锁预防算法通过限制进程的资源请求方法来预防死锁。死锁预防通常通过下列方法之一来实现。它们都基于打破四个死锁条件中的一种:

    1)静态分配资源。要求进程必须在开始执行前就申请它所需要的全部资源,并且只有当系统能满足进程的资源申请要求并把资源分配给进程之后,该进程才开始执行。这种策略可以预防死锁的发生是由于其破坏了“占有且等待资源”和“循环等待资源”的条件,从而系统中的所有进程必然不会发生死锁。

    2)按序分配资源。在系统中的每一个资源都会给出一个编号。分配资源的时候作了以下规定:任何进程在申请两个以上资源时,总是按照编号的大小顺序申请。这种策略可以预防死锁的发生是由于其破坏了“循环等待资源”的条件,从而系统中的所有进程必然不会发生死锁。

    3)剥夺式分配资源。当一个进程申请资源得不到满足时,可从另一个拥有这种资源的进程那里去抢夺,然后继续运行。这种策略可以预防死锁的发生是由于其破坏了“非抢夺式分配”的条件,从而系统中的所有进程必然不会发生死锁。

    4.1 等待-死亡方案(Wait-die Scheme)

    该方案是基于非剥夺方法。当进程Pi请求的资源正被进程Pj占有时,只有当Pi的时间戳比进程Pj的时间戳小时,即Pi比Pj老时,Pi才能等待。否则Pi被卷回(roll-back),即死亡。一个进程死亡后会释放他所占用的所有资源。在这里假定死亡的进程将带着同样的时间戳重新运行。由于具有较小时间戳的进程才等待具有较大时间戳的进程,因此很显然死锁不会发生。当进程在等待特定的资源时,不会释放资源。一旦一个进程释放一个资源,与这个资源相联系的等待队列中的一个进程将被激活。

    4.2 伤害-等待方案(Wound-wait Scheme)

    它是一种基于剥夺的方法。当进程Pi请求的资源正被进程Pj占有时,只有当进程Pi的时间戳比进程Pj的时间戳大时,即Pi比Pj年轻时,Pi才能等待。否则Pj被卷回(roll-back),即死亡。只要被卷回的进程重新启动时,使用原有的时间戳,这两种方案都能避免死锁和饿死现象。由于时间戳总是增加的,被卷回的进程最终将具有最小的时间戳。

    5 死锁的检测

    为了降低系统开销,在分配资源时会不加限制,只要系统中有剩余的资源,总是把资源分配给申请者。显然,这样的结果是可能会出现死锁。那么,为了使系统能够正常工作,在系统中会采用定时运行一个“死锁检测”程序的方法,当检测到死锁时该程序将会设法将其排除。在分布式系统中的死锁检测法不会造成很多不必要的进程流产,但是也会增加了系统的额外开销和复杂度。

    5.1集中式死锁检测

    在分布式系统中,每个站点都有一个本地死锁检测程序,其任务是判断在其站点所有潜在的全局死锁;其方法是:在站点的输入端口开始,沿本地等待图反向搜索,如果最终会搜索到输出端口,就说明具有潜在的全局死锁。

    5.2分布式死锁检测

    分布式死锁检测和集中式的主要差别是:在集中式方案中全部潜在的死锁循环都发送给某个指定的站点,而在分布式检测方案中则没有这种站点。分布式死锁检测机构中没有本地和非本地死锁检测程序的任何区别,每个站点具有同样的责任。在分布式方案中,死锁检测程序需要一种规则来决定应该把潜在的死锁循环发送给哪个站点,这种规则必须保证能最终检测到全局死锁,并且必须尽量减小传送的信息量。

    Knapp将分布式死锁检测算法分为以下四类:

    (1)路径推动算法(path-pushing algorithm)。先在每个机器上建立形式简单的全局等待图。每当进行死锁检测时,各个机器就将等待图的拷贝送往一定数量的邻居节点。局部拷贝更新后又被传播下去。这一过程重复进行直到某个节点获得了足够的信息来构造一个等待图以便做出是否存在死锁的结论。不幸的是,这类算法中的许多算法在实际中是错误的。主要原因是传输过程中的部分等待图并不能代表整个全局等待图,因为各个节点采集数据的方法是异步的。

    (2)边跟踪算法(edge-chasing algorithm)。分布式网络结构图中的回路可以通过沿图的边传播一种叫探测器的特殊信息来检测。当一个发起者得到一个与自己发送的探测器相匹配的探测器时,它就知道它在图中的一个回路里。

    (3)扩散计算(diffusing computation)。怀疑有死锁发生时,事务管理器通过向依赖于它的进程发送查询启动一个扩散进程。这里不会生成全局等待图。发送查询信息时,扩散计算就增长;接收回答后,扩散计算就缩减。根据所得信息,发起者会检测到死锁的发生。典型情况是,扩散进程动态地生成等待图的一个子树。

    (4)全局状态检测(global state detection)。这个方法基于Chandy和Lamport 的快照方法。可以通过建立一个一致的全局状态而无需暂停当前的计算来生成一个一致的全局等待图。2 处理死锁的策略

    转载:http://blog.csdn.net/wxl612/article/details/53008579

    展开全文
  • 假如系统为进程分配资源,不采取任何限制性措施来避免和预防死锁,减少因避免和预防死锁策略带来的开销,同时本着提高资源利用率的原则分配资源,但操作系统在运行过程,不断地监督 进程的执行和资源占用状态,...

    以上小节讨论了死锁预防和死锁避免的几种方法,但是这些方法都比较保守,并且都是以牺牲系统效率和浪费资源为代价的,这恰恰与操作系统设计目标相违背。假如系统为进程分配资源时,不采取任何限制性措施来避免和预防死锁,减少因避免和预防死锁策略带来的开销,同时本着提高资源利用率的原则分配资源,但操作系统在运行过程中,不断地监督 进程的执行和资源占用状态,判定死锁是否真的发生;并且,一旦死锁发生,则釆取专门的 措施解除死锁,并以最小代价使整个系统恢复正常,这就是死锁的检测和解除。

    一、 死锁检测的时机

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

    通常,死锁检测可以在任何一次资源分配后,也可以在每次调度后,或者利用定时器定 时运行检测,还有一种方法是当系统中某个进程长期位于阻塞态或阻塞进程过多时,启动死 锁检测程序。

    二、 死锁检测的算法

    死锁检测的算法依不同的系统而不同,下面介绍一种死锁检测的算法。

    (1)为每个进程和每个资源指定唯一编号

    (2)设置一张资源分配状态表,每个表目包含“资源号”和占有该资源的“进程号”两 项,资源分配表中记录了每个资源正在被哪个进程所占有

    (3)设置一张进程等待分配表,每个表目包含“进程号”和该进程所等待的“资源号” 两项

    (4)算法规则:当任一进程P,申请一个已被其他进程占用的资源时,进行死锁检测。 检测算法通过反复查找资源分配表和进程等待表,来确定进程P,.对资源I的请求是否导致形成环路,若是,便确定出现死锁

    【例7】进程死锁检测算法。

    系统中有进程P1、P2和P3共享资源r1、r2和r3。在某一时刻资源使用情况如图5-9a所 示。此后依次发生P1请求r1,P2请求r3, P3请求r1。当执行死锁检测算法后,得到图5-9b; 再执行死锁检测算法,得到图5-9c;再执行死锁检测算法,得到图5-9d。检查图5-9d与图 5-9a,确定是否出现死锁。

    三、死锁的解除方法

    一旦检测到死锁,便要立即设法解除死锁。一般说来,只要让某个进程释放一个或多个资源就可以解除死锁。死锁解除后,释放资源的进程应恢复它原来的状态,才能保证该进程 的执行不会出现错误。因此,死锁解除实质上就是如何让释放资源的进程能够继续运行。

    为解除死锁就要剥夺资源,此时,需要考虑以下几个问题。

    (1)选择一个牺牲进程,即要确定剥夺哪个进程的哪些资源。

    (2)重新运行或回退到某一点开始继续运行。若从一个进程那里剥夺了资源,要为该进程做些什么事情?显然,这个进程是不能继续正常执行了。必须将该进程回退到起点或某个 状态,以后再重新开始执行。令进程夭折的方法虽然简单,但代价大;而更有效的方法是只 让它退回到足以解除死锁的地步即可。那么,问题转换成进程回退的状态由什么组成?怎样 才能方便地确定该状态,这就要求系统保持更多的有关进程运行的信息。

    (3)怎样保证不发生“饿死”现象,即如何保证并不总是剥夺同一进程的资源,而导致 该进程处于“饥饿”状态。

    (4)“最小代价”,即最经济合算的算法,使得进程回退带来的开销最小。但是,“最小 开销”是很不精确的,进程重新运行的开销包括很多因素。

    ①进程的优先级。

    ②进程已经运行了多长时间,该进程完成其任务还需要多长时间?

    ③该进程使用的资源种类和数量?这些资源能简单地剥夺吗?

    ④为完成其任务,进程还需要多少资源?

    ⑤有多少进程要被撤销?

    ⑥该进程被重新启动运行的次数。

    一旦决定一个进程必须回退,就一定要确定这个进程回退多少。最简单的办法是从头来,让其重新运行,这将会使一个进程的工作“前功尽弃”。

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

    1、剥夺资源

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

    由于死锁是由进程竞争资源而引起的,所以,可以从一些进程那里强行剥夺足够数量的 资源分配给死锁进程,以解除死锁状态。剥夺的顺序可以是以花费最小资源数为依据。每次 剥夺后,需要再次调用死锁检测算法。资源被剥夺的进程为了再得到该资源,必须重新提出 申请。为了安全地释放资源,该进程就必须返回到分配资源前的某一点。经常使用的方法如 下。

    (1)还原算法,即恢复计算结果和状态

    (2)建立检查点主要是用来恢复分配前的状态。这种方法对实时系统和长时间运行的数 据处理来说是一种常用技术。在实时系统中,经常在某些程序地址插人检查的程序段,即采 用检查点的技术来验证系统的正确性,如发现故障,可从检查点重新启动。因此,在有些实 时系统中,一旦发现死锁,可以在释放某进程的资源后,从检查点重新启动。

    2、撤销进程

    撤销死锁进程,将它们占有的资源分配给另一些死锁进程,直到死锁解除为止。

    可以撤销所有死锁进程,或者逐个撤销死锁进程,每撤销一个进程就检测死锁是否继续 存在,若已没有死锁,就停止进程的撤销。

    如果按照某种顺序逐渐地撤销已死锁的进程,直到获得为解除死锁所需要的足够可用的 资源为止,那么在极端情况下,这种方法可能造成除一个死锁进程外,其余的死锁进程全部 被撤销的局面。

    按照什么原则撤销进程?较实用而又简便的方法是撤销那些代价最小的进程,或者使撤 销进程的数目最小。以下几点可作为衡量撤销代价的标准。

    (1)进程优先数,即被撤销进程的优先数

    (2)进程类的外部代价。不同类型的进程可以规定出各自的撤销代价。系统可根据这些 规定,撤销代价最小的进程,达到解除死锁的目的。

    (3)运行代价,即重新启动进程并运行到当前撤销点所需要的代价。这一点可由系统记 账程序给出。

    撤销法的优点是简单明了,但有时可能不分青红皂白地撤销一些甚至不影响死锁的进程。

    当死锁的进程中包含有操作系统的进程单元时,死锁会变得复杂,采用上述方法可能导致系统重新启动,从而付出较高代价。

    展开全文
  • 如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃 从死锁的定义可以得到几个推论:参与死锁的所有进程都在等待资源;参与死锁的进程是当前系统中所有进程的子集。 资源数量有限、锁和信号量错误使用都可能...
  • 进程与线程 PCB TCB 进程挂起 用户线程 内核线程 轻量级进程 僵尸队列操作系统(八)CPU调度 短剩余时间 吞吐量 轮循 实时调度 处理器调度 (清华 向勇 陈渝版)正文9-1 同步互斥、临界区、死锁、互斥概念等等个...
  • 操作系统——死锁

    千次阅读 2017-06-28 10:05:46
    多道程序并发执行个进程因竞争资源而造成的僵局(互相等待),无外力作用的情况下,这些进程无法向前推进。​ 例子:进程P1正在占用打印机,此时请求输入设备,进程P2正在占用输入设备,请求打印机。他们都...
  • Java 程序死锁问题原理及解决方案

    千次阅读 2016-07-09 11:19:46
    我们发现,死锁虽然是较早就被发现的问题,但是很情况下我们设计的程序里还是经常发生死锁情况。我们不能只是分析如何解决死锁这类问题,还需要具体找出预防死锁的方法,这样才能从根本上解决问题。总的来说,还是...
  • 死锁

    千次阅读 2018-07-29 20:52:12
    目录 一、什么是死锁 ...所谓死锁是指个并发进程,各自持有资源又都等待别的进程释放所拥有的资源,在未改变这种状态之前不能向前推进,这种状态称为死锁死锁产生的根本原因是系统资源不足。 二、死锁的...
  • 程序死循环、死锁问题定位

    千次阅读 2019-06-11 11:47:19
    在开发过程,可能由于代码设计问题导致出现了死循环或者死锁的问题,使服务器CPU负载飙高从而导致系统运行缓慢,因此要特别注意防止死循环和死锁发生。如监控服务器状态,如果发现CPU负载或利用率飙得很高,这...
  • 线程程序里不准使用fork :为什么??? UNIX上C++程序设计守则3 准则3:线程程序里不准使用fork 在线程程序里,在”自身以外的线程存在的状态”下一使用fork的话,就可能引起各种各样的问题.比较典型的...
  • 死锁(操作系统

    千次阅读 2015-09-21 20:58:13
    多道程序系统中,由于个进程的并发执行,改善了系统资源的利用率并提高了系统 的处理能力。然而,个进程的并发执行也带来了新的问题——死锁。所谓死锁是指个进 程因竞争资源而造成的一种僵局(互相等待),...
  • 死锁(deadlock)和活锁(livelock)是并发应用程序经常发生的问题,也是线程编程的重要概念, 以下是对死锁和活锁的形象描述。 现有个过道,两个人宽,两侧迎面走来两个人A和B。 死锁的情况: A和B都...
  • 计算机操作系统-死锁详解

    千次阅读 2020-10-09 11:29:13
    操作系统-死锁 (充分了解死锁) 在线博主,及时解答~
  • 线程程序里不准使用fork :为什么??? UNIX上C++程序设计守则3 准则3:线程程序里不准使用fork 在线程程序里,在”自身以外的线程存在的状态”下一使用fork的话,就可能引起各种各样的问题.比较典型的...
  • 写一个死锁程序

    千次阅读 2018-05-15 22:50:19
    写一个死锁程序 什么是死锁死锁是指两个或两个以上的进程在执行过程,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了...
  • 数据毁坏或一个死锁几乎是一个线程应用中发生的最坏的问题,它具有非常恶毒的和敏感的形式但相当困难重新或者被跟踪。由于这种原因,强烈推荐你在这些情况发生之前分析你的线程应用程序可能的死锁条件并检查和...
  • 学习如何使用 IBM® WebSphere® Application Server V6.1 的线程转储工具了解您的系统环境,检查是否发生死锁以及提取信息来帮助避免或解决自己应用程序的死锁情况。引言当两个或个线程彼此形成循环依赖关系...
  • 在Java程序中处理数据库超时与死锁

    千次阅读 2017-12-13 10:01:27
     每个使用关系型数据库的程序都可能遇到数据死锁或不可用的情况,而这些情况需要在代码编程来解决;本文主要介绍与数据库事务死锁等情况相关的重试逻辑概念,此外,还会探讨如何避免死锁等问题,文章以DB2(版本9)...
  • 死锁概念 死锁严格意义上的含义这里引用维基百科的解释: 在并发计算,死锁是一种...在操作系统中,当进程或线程进入等待状态时发生死锁,因为所请求的系统资源由另一个等待进程保持,而另一个等待进程又等待...
  • 什么是死锁?如何避免死锁? 以及实现线程死锁程序
  • 产生死锁的原因:(1)竞争系统资源 (2)进程的推进顺序不当   产生死锁的必要条件: 互斥条件:进程要求对所分配的资源进行排它性控制,即...环路等待条件:在发生死锁时,必然存在一个进程--资源的环形链。...
  • 操作系统7-死锁的检测和解除

    千次阅读 2018-07-23 12:15:29
    允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生 一旦死锁发生则采取专门的措施,解除死锁并以最小的代价恢复操作系统运行 7.1.1 检测时机 定时检测 当进程阻塞检测死锁(其缺点是系统的开销...
  • 线程应用程序中检查死锁的方法 WIN32 API的好的特性就是能够让你所有可能引起死锁的资源。在上面的WINDOWS3.1的例子,硬盘驱动器制造商,应用程序员,WINDOWS开发人员都不可能预测到死锁,因为这个死锁包含了几...
  • 线程中死锁的排查

    千次阅读 2019-04-29 16:32:03
    线程编程过程总是会遇到死锁的情况,但是死锁一旦出现,并不报错,也没提示,这种情况下,我们就得学会在线程出现死锁的时候进行排查。 什么叫做死锁死锁是指两个或两个以上的进程在执行过程,由于竞争...
  • 如何避免线程中死锁?

    千次阅读 2017-09-08 23:23:09
    死锁 一个经典的线程问题。 当一个线程永远地持有一个锁,并且其他线程...在数据库系统的设计中考虑了监测死锁以及从死锁中恢复,数据库如果监测到了一组事物发生了死锁,将选择一个牺牲者并放弃这个事物。J

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,818
精华内容 40,327
关键字:

多道程序系统中发生死锁时