精华内容
下载资源
问答
  • 死锁四个必要条件和解决办法

    万次阅读 多人点赞 2018-05-13 22:45:30
    死锁概念及产生原理 概念:多个并发进程因争夺系统资源而产生相互等待的现象。 原理:当一组进程中的每个进程都...死锁产生的4个必要条件 1、互斥:某种资源一次只允许一个进程访问,即该资源一旦分配给某个进程...
    死锁概念及产生原理
        概念: 多个并发进程因争夺系统资源而产生相互等待的现象。
        原理: 当一组进程中的每个进程都在等待某个事件发生,而只有这组进程中的其他进程才能触发该事件,这就称这组进程发生了死锁。
        本质原因:
            1)、系统资源有限。
            2)、进程推进顺序不合理。

    死锁产生的4个必要条件
        1、互斥: 某种资源一次只允许一个进程访问,即该资源一旦分配给某个进程,其他进程就不能再访问,直到该进程访问结束。
        2、占有且等待: 一个进程本身占有资源(一种或多种),同时还有资源未得到满足,正在等待其他进程释放该资源。
        3、不可抢占: 别人已经占有了某项资源,你不能因为自己也需要该资源,就去把别人的资源抢过来。
        4、循环等待: 存在一个进程链,使得每个进程都占有下一个进程所需的至少一种资源。
            当以上四个条件均满足,必然会造成死锁,发生死锁的进程无法进行下去,它们所持有的资源也无法释放。这样会导致CPU的吞吐量下降。所以死锁情况是会浪费系统资源和影响计算机的使用性能的。那么,解决死锁问题就是相当有必要的了。

    避免死锁的方法
    1、死锁预防 ----- 确保系统永远不会进入死锁状态
         产生死锁需要四个条件,那么,只要这四个条件中至少有一个条件得不到满足,就不可能发生死锁了。由于互斥条件是非共享资源所必须的,不仅不能改变,还应加以保证,所以,主要是破坏产生死锁的其他三个条件。
    a、破坏“占有且等待”条件
         方法1:所有的进程在开始运行之前,必须一次性地申请其在整个运行过程中所需要的全部资源。
             优点:简单易实施且安全。
             缺点:因为某项资源不满足,进程无法启动,而其他已经满足了的资源也不会得到利用,严重降低了资源的利用率,造成资源浪费。
                      使进程经常发生饥饿现象。
         方法2:该方法是对第一种方法的改进,允许进程只获得运行初期需要的资源,便开始运行,在运行过程中逐步释放掉分配到的已经使用完毕的资源,然后再去请求新的资源。这样的话,资源的利用率会得到提高,也会减少进程的饥饿问题。
    b、破坏“不可抢占”条件
          当一个已经持有了一些资源的进程在提出新的资源请求没有得到满足时,它必须释放已经保持的所有资源,待以后需要使用的时候再重新申请。这就意味着进程已占有的资源会被短暂地释放或者说是被抢占了。
          该种方法实现起来比较复杂,且代价也比较大。释放已经保持的资源很有可能会导致进程之前的工作实效等,反复的申请和释放资源会导致进程的执行被无限的推迟,这不仅会延长进程的周转周期,还会影响系统的吞吐量。
    c、破坏“循环等待”条件
         可以通过定义资源类型的线性顺序来预防,可将每个资源编号,当一个进程占有编号为i的资源时,那么它下一次申请资源只能申请编号大于i的资源。如图所示:
    这样虽然避免了循环等待,但是这种方法是比较低效的,资源的执行速度回变慢,并且可能在没有必要的情况下拒绝资源的访问,比如说,进程c想要申请资源1,如果资源1并没有被其他进程占有,此时将它分配个进程c是没有问题的,但是为了避免产生循环等待,该申请会被拒绝,这样就降低了资源的利用率
    2、避免死锁 ----- 在使用前进行判断,只允许不会产生死锁的进程申请资源
    的死锁避免是利用额外的检验信息,在分配资源时判断是否会出现死锁,只在不会出现死锁的情况下才分配资源。
    两种避免办法:
        1、如果一个进程的请求会导致死锁,则不启动该进程
        2、如果一个进程的增加资源请求会导致死锁 ,则拒绝该申请。
    避免死锁的具体实现通常利用银行家算法
         银行家算法
    a、银行家算法的相关数据结构
        可利用资源向量Available:用于表示系统里边各种资源剩余的数目。由于系统里边拥有的资源通常都是有很多种(假设有m种),所以,我们用一个有m个元素的数组来表示各种资源。数组元素的初始值为系统里边所配置的该类全部可用资源的数目,其数值随着该类资源的分配与回收动态地改变。
        最大需求矩阵Max:用于表示各个进程对各种资源的额最大需求量。进程可能会有很多个(假设为n个),那么,我们就可以用一个nxm的矩阵来表示各个进程多各种资源的最大需求量
        分配矩阵Allocation:顾名思义,就是用于表示已经分配给各个进程的各种资源的数目。也是一个nxm的矩阵。
        需求矩阵Need:用于表示进程仍然需要的资源数目,用一个nxm的矩阵表示。系统可能没法一下就满足了某个进程的最大需求(通常进程对资源的最大需求也是只它在整个运行周期中需要的资源数目,并不是每一个时刻都需要这么多),于是,为了进程的执行能够向前推进,通常,系统会先分配个进程一部分资源保证进程能够执行起来。那么,进程的最大需求减去已经分配给进程的数目,就得到了进程仍然需要的资源数目了。

    银行家算法通过对进程需求、占有和系统拥有资源的实时统计,确保系统在分配给进程资源不会造成死锁才会给与分配。
    死锁避免的优点:不需要死锁预防中的抢占和重新运行进程,并且比死锁预防的限制要少。
    死锁避免的限制:
        必须事先声明每个进程请求的最大资源量
        考虑的进程必须无关的,也就是说,它们执行的顺序必须没有任何同步要求的限制
        分配的资源数目必须是固定的。
        在占有资源时,进程不能退出
    3、死锁检测与解除 ----- 在检测到运行系统进入死锁,进行恢复。
         允许系统进入到死锁状态
        死锁检测
    下图截自《操作系统--精髓与设计原理》


         死锁的解除
    如果利用死锁检测算法检测出系统已经出现了死锁 ,那么,此时就需要对系统采取相应的措施。常用的解除死锁的方法:
    1、抢占资源:从一个或多个进程中抢占足够数量的资源分配给死锁进程,以解除死锁状态。
    2、终止(或撤销)进程:终止或撤销系统中的一个或多个死锁进程,直至打破死锁状态。
        a、终止所有的死锁进程。这种方式简单粗暴,但是代价很大,很有可能会导致一些已经运行了很久的进程前功尽弃。
         b、逐个终止进程,直至死锁状态解除。该方法的代价也很大,因为每终止一个进程就需要使用死锁检测来检测系统当前是否处于死锁状态。另外,每次终止进程的时候终止那个进程呢?每次都应该采用最优策略来选择一个“代价最小”的进程来解除死锁状态。一般根据如下几个方面来决定终止哪个进程:
        进程的优先级
        进程已运行时间以及运行完成还需要的时间
        进程已占用系统资源
        进程运行完成还需要的资源
        终止进程数目
        进程是交互还是批处理

    展开全文
  • 操作系统死锁 四个必要条件

    千次阅读 2020-07-27 18:01:05
    操作系统死锁 四个必要条件 操作系统中有若干进程并发执行,它们不断申请、使用、释放系统资源,虽然系统的进 程协调、通信机构会对它们进行控制,但也可能出现若干进程都相互等待对方释放资源才能 继续运行,否则就...

    操作系统死锁 四个必要条件

    1. 死锁:如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件,那么该组进程是死锁的。

    2. 产生死锁的原因:

    (1)竞争不可抢占性资源。

    (2)竞争可消耗资源。

    当系统中供多个进程共享的资源如打印机,公用队列等,其数目不足以满足诸进程的需要时,会引起诸进程对资源的竞争而产生死锁。
    

    (3)进程推进顺序不当。

     进程在运行过程中,请求和释放资源的顺序不当,也同样会导致产生进程死锁。
    

    如果系统资源充足,进程的资源请求都能够得到满足,死锁出现的可能性就很低,否则就会因争夺有限的资源而陷入死锁。其次,进程运行推进顺序与速度不同,也可能产生死锁。

      一个线程也可引起死锁。
    

    3. 产生死锁的四个必要条件:

    (1) 互斥条件:一个资源每次只能被一个进程使用。

    (2) 请求和保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。

    (3) 不可抢占条件:进程已获得的资源,在末使用完之前,不能强行剥夺,只能在进程使用完时由自己释放。

    (4) 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

    这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之一不满足,就不会发生死锁。因此可以写下如下的预防死锁的方法。

    4.避免死锁的方法:

    (1)破坏“互斥”条件:就是在系统里取消互斥。若资源不被一个进程独占使用,那么死锁是肯定不会发生的。但一般“互斥”条件是无法破坏的。因此,在死锁预防里主要是破坏其他三个必要条件,而不去涉及破坏“互斥”条件。

    (2)破坏“请求和保持”条件:在系统中不允许进程在已获得某种资源的情况下,申请其他资源。即要想出一个办法,阻止进程在持有资源的同时申请其他资源。

    方法一:所有进程在运行之前,必须一次性地申请在整个运行过程中所需的全部资源。这样,该进程在整个运行期间,便不会再提出资源请求,从而破坏了“请求”条件。系统在分配资源时,只要有一种资源不能满足进程的要求,即使其它所需的各资源都空闲也不分配给该进程,而让该进程等待。由于该进程在等待期间未占有任何资源,于是破坏了“保持”条件。

    该方法优点:简单、易行且安全。

    缺点:

    1. 资源被严重浪费,严重恶化了资源的利用率。

    2. 使进程经常会发生饥饿现象。

    方法二:要求每个进程提出新的资源申请前,释放它所占有的资源。这样,一个进程在需要资源S时,须先把它先前占有的资源R释放掉,然后才能提出对S的申请,即使它可能很快又要用到资源R。

    (3)破坏“不可抢占”条件:允许对资源实行抢夺。
    方法一:如果占有某些资源的一个进程进行进一步资源请求被拒绝,则该进程必须释放它最初占有的资源,如果有必要,可再次请求这些资源和另外的资源。
    方法二:如果一个进程请求当前被另一个进程占有的一个资源,则操作系统可以抢占另一个进程,要求它释放资源。只有在任意两个进程的优先级都不相同的条件下,该方法才能预防死锁。

    (4)破坏“循环等待”条件:将系统中的所有资源统一编号,进程可在任何时刻提出资源申请,但所有申请必须按照资源的编号顺序(升序)提出。这样做就能保证系统不出现死锁。

    利用银行家算法避免死锁:

    银行家算法:

    设进程i提出请求Request[j],则银行家算法按如下规则进行判断。

    (1) 如果Request[j]≤Need[i,j],则转向(2),否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

    (2) 如果Request[j]≤Available[j],则转向(3);否则表示尚无足够资源,Pi需等待。

    (3) 假设进程i的申请已获批准,于是修改系统状态:

    Available[j]=Available[j]-Request[i]

    Allocation[i,j]=Allocation[i,j]+Request[j]

    Need[i,j]=Need[i,j]-Request[j]

    (4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。

    安全性算法:

    (1) 设置两个工作向量Work=Available;Finish[i]=False

    (2) 从进程集合中找到一个满足下述条件的进程,

     Finish [i]=False;
    
     Need[i,j]≤Work[j];
    
     如找到,执行(3);否则,执行(4)
    

    (3) 设进程获得资源,可顺利执行,直至完成,从而释放资源。

    Work[j]=Work[j]+Allocation[i,j];
    
    Finish[i]=True;
    
    Go to step 2;
    

    (4) 如所有的进程Finish[i]=true,则表示安全;否则系统不安全。

    5. 死锁的解除:

    一旦检测出死锁,就应立即釆取相应的措施,以解除死锁。死锁解除的主要两种方法:

    1. 抢占资源。从一个或多个进程中抢占足够数量的资源,分配给死锁进程,以解除死锁状态。

    2. 终止(或撤销)进程。终止(或撤销)系统中的一个或多个死锁进程,直至打破循环环路,使系统从死锁状态解脱出来。

    总结:

      一般情况下,如果同一个线程先后两次调用lock,在第二次调用时,由于锁已经被占用,该线程会挂起等待别的线程释放锁,然而锁正是被自己占用着的,该线程又被挂起而没有机会释放锁,因此就永远处于挂起等待状态了,这叫做死锁(Deadlock)。另⼀一种典型的死锁情形是这样:线程A获得了锁1,线程B获得了锁2,这时线程A调⽤用lock试图获得锁2,结果是需要挂起等待线程B释放锁2,而这时线程B也调⽤用lock试图获得锁1,结果是需要挂起等待线程A释放锁1,于是线程A和B都永远处于挂起状态了。

    注意:

      写程序时应该尽量避免同时获得多个锁,如果一定有必要这么做,则有一个原则:如果所有线程在需要多个锁时都按相同的先后顺

    展开全文
  • 死锁死锁四个必要条件以及处理策略

    万次阅读 多人点赞 2018-03-19 16:57:02
    一、什么是死锁 二、死锁与饥饿 三、资源的类型 3.1 可重用资源和消耗性资源 3.1.1 可重用资源(永久性资源) 3.1.2 消耗性资源(临时性资源) 3.2 可抢占资源和不可抢占资源 ...五、产生死锁四个必...

    一、什么是死锁

    多线程以及多进程改善了系统资源的利用率并提高了系统 的处理能力。然而,并发执行也带来了新的问题——死锁。
    死锁是指两个或两个以上的进程(线程)在运行过程中因争夺资源而造成的一种僵局(Deadly-Embrace) ) ,若无外力作用,这些进程(线程)都将无法向前推进。

    下面我们通过一些实例来说明死锁现象。

    先看生活中的一个实例,2个人一起吃饭但是只有一双筷子,2人轮流吃(同时拥有2只筷子才能吃)。某一个时候,一个拿了左筷子,一人拿了右筷子,2个人都同时占用一个资源,等待另一个资源,这个时候甲在等待乙吃完并释放它占有的筷子,同理,乙也在等待甲吃完并释放它占有的筷子,这样就陷入了一个死循环,谁也无法继续吃饭。。。
    在计算机系统中也存在类似的情况。例如,某计算机系统中只有一台打印机和一台输入设备,进程P1正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2 所占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。

    关于死锁的一些结论:

    • 参与死锁的进程数至少为两个
    • 参与死锁的所有进程均等待资源
    • 参与死锁的进程至少有两个已经占有资源
    • 死锁进程是系统中当前进程集合的一个子集
    • 死锁会浪费大量系统资源,甚至导致系统崩溃。

    二、死锁与饥饿

    饥饿(Starvation)指一个进程一直得不到资源。

    死锁和饥饿都是由于进程竞争资源而引起的。饥饿一般不占有资源,死锁进程一定占有资源。

    三、资源的类型

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

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

    可被多个进程多次使用,如所有硬件。

    • 只能分配给一个进程使用,不允许多个进程共享。
    • 进程在对可重用资源的使用时,须按照请求资源、使用资源、释放资源这样的顺序。
    • 系统中每一类可重用资源中的单元数目是相对固定的,进程在运行期间,既不能创建,也不能删除。

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

    又称临时性资源,是由进程在运行期间动态的创建和消耗的。

    • 消耗性资源在进程运行期间是可以不断变化的,有时可能为0。
    • 进程在运行过程中,可以不断地创造可消耗性资源的单元,将它们放入该资源类的缓冲区中,以增加该资源类的单元数目。
    • 进程在运行过程中,可以请求若干个可消耗性资源单元,用于进程自己消耗,不再将它们返回给该资源类中。

    可消耗资源通常是由生产者进程创建,由消费者进程消耗。最典型的可消耗资源是用于进程间通信的消息。

    3.2 可抢占资源和不可抢占资源

    3.2.1 可抢占资源

    可抢占资源指某进程在获得这类资源后,该资源可以再被其他进程或系统抢占。对于这类资源是不会引起死锁的。

    CPU 和主存均属于可抢占性资源。

    3.2.2 不可抢占资源

    一旦系统把某资源分配给该进程后,就不能将它强行收回,只能在进程用完后自行释放。

    磁带机、打印机等属于不可抢占性资源。

    四、死锁产生的原因

    • 竞争不可抢占资源引起死锁
      通常系统中拥有的不可抢占资源,其数量不足以满足多个进程运行的需要,使得进程在运行过程中,会因争夺资源而陷入僵局,如磁带机、打印机等。只有对不可抢占资源的竞争 才可能产生死锁,对可抢占资源的竞争是不会引起死锁的。
    • 竞争可消耗资源引起死锁
    • 进程推进顺序不当引起死锁
      进程在运行过程中,请求和释放资源的顺序不当,也同样会导致死锁。例如,并发进程 P1、P2分别保持了资源R1、R2,而进程P1申请资源R2,进程P2申请资源R1时,两者都会因为所需资源被占用而阻塞。
      信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息,结果也会使得这 些进程间无法继续向前推进。例如,进程A等待进程B发的消息,进程B又在等待进程A 发的消息,可以看出进程A和B不是因为竞争同一资源,而是在等待对方的资源导致死锁。

    4.1 竞争不可抢占资源引起死锁

    如:共享文件时引起死锁
    系统中拥有两个进程P1和P2,它们都准备写两个文件F1和F2。而这两者都属于可重用和不可抢占性资源。如果进程P1在打开F1的同时,P2进程打开F2文件,当P1想打开F2时由于F2已结被占用而阻塞,当P2想打开1时由于F1已结被占用而阻塞,此时就会无线等待下去,形成死锁。
    这里写图片描述

    4.2 竞争可消耗资源引起死锁

    如:进程通信时引起死锁
    系统中拥有三个进程P1、P2和P3,m1、m2、m3是3可消耗资源。进程P1一方面产生消息m1,将其发送给P2,另一方面要从P3接收消息m3。而进程P2一方面产生消息m2,将其发送给P3,另一方面要从P1接收消息m1。类似的,进程P3一方面产生消息m3,将其发送给P1,另一方面要从P2接收消息m2。
    如果三个进程都先发送自己产生的消息后接收别人发来的消息,则可以顺利的运行下去不会产生死锁,但要是三个进程都先接收别人的消息而不产生消息则会永远等待下去,产生死锁。
    这里写图片描述

    4.3 进程推进顺序不当引起死锁

    这里写图片描述
    上图中,如果按曲线1的顺序推进,两个进程可顺利完成;如果按曲线2的顺序推进,两个进程可顺利完成;如果按曲线3的顺序推进,两个进程可顺利完成;如果按曲线4的顺序推进,两个进程将进入不安全区D中,此时P1保持了资源R1,P2保持了资源R2,系统处于不安全状态,如果继续向前推进,则可能产生死锁。

    五、产生死锁的四个必要条件

    5.1 互斥条件:

    进程要求对所分配的资源(如打印机)进行排他性控制,即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源,则请求进程只能等待。

    5.2 不可剥夺条件:

    进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的进程自己来释放(只能是主动释放)。

    5.3 请求与保持条件:

    进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。

    5.4 循环等待条件:

    存在一种进程资源的循环等待链,链中每一个进程已获得的资源同时被 链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, …, pn},其中Pi等 待的资源被P(i+1)占有(i=0, 1, …, n-1),Pn等待的资源被P0占有,如图2-15所示。

    直观上看,循环等待条件似乎和死锁的定义一样,其实不然。按死锁定义构成等待环所 要求的条件更严,它要求Pi等待的资源必须由P(i+1)来满足,而循环等待条件则无此限制。 例如,系统中有两台输出设备,P0占有一台,PK占有另一台,且K不属于集合{0, 1, …, n}。

    Pn等待一台输出设备,它可以从P0获得,也可能从PK获得。因此,虽然Pn、P0和其他 一些进程形成了循环等待圈,但PK不在圈内,若PK释放了输出设备,则可打破循环等待, 如图2-16所示。因此循环等待只是死锁的必要条件。

    这里写图片描述

    资源分配图含圈而系统又不一定有死锁的原因是同类资源数大于1。但若系统中每类资 源都只有一个资源,则资源分配图含圈就变成了系统出现死锁的充分必要条件。

    以上这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之一不满足,就不会发生死锁。

    产生死锁的一个例子:

    /**
     * 一个简单的死锁类
     * 当DeadLock类的对象flag==1时(td1),先锁定o1,睡眠500毫秒
     * 而td1在睡眠的时候另一个flag==0的对象(td2)线程启动,先锁定o2,睡眠500毫秒
     * td1睡眠结束后需要锁定o2才能继续执行,而此时o2已被td2锁定;
     * td2睡眠结束后需要锁定o1才能继续执行,而此时o1已被td1锁定;
     * td1、td2相互等待,都需要得到对方锁定的资源才能继续执行,从而死锁。
     */
    public class DeadLock implements Runnable {
        public int flag = 1;  
        //静态对象是类的所有对象共享的  
        private static Object o1 = new Object(), o2 = new Object();  
        @Override  
        public void run() {  
            System.out.println("flag=" + flag);  
            if (flag == 1) {  
                synchronized (o1) {  
                    try {  
                        Thread.sleep(500);  
                    } catch (Exception e) {  
                        e.printStackTrace();  
                    }  
                    synchronized (o2) {  
                        System.out.println("1");  
                    }  
                }  
            }  
            if (flag == 0) {  
                synchronized (o2) {  
                    try {  
                        Thread.sleep(500);  
                    } catch (Exception e) {  
                        e.printStackTrace();  
                    }  
                    synchronized (o1) {  
                        System.out.println("0");  
                    }  
                }  
            }  
        }  
    
        public static void main(String[] args) {
            DeadLock td1 = new DeadLock();
            DeadLock td2 = new DeadLock();
            td1.flag = 1;
            td2.flag = 0;
            //td1,td2都处于可执行状态,但JVM线程调度先执行哪个线程是不确定的。  
            //td2的run()可能在td1的run()之前运行  
            new Thread(td1).start();  
            new Thread(td2).start();
        }  
    }  

    六、处理死锁的方法

    • 预防死锁:通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或几个条件,来防止死锁的发生。
    • 避免死锁:在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免死锁的发生。
    • 检测死锁:允许系统在运行过程中发生死锁,但可设置检测机构及时检测死锁的发生,并采取适当措施加以清除。
    • 解除死锁:当检测出死锁后,便采取适当措施将进程从死锁状态中解脱出来。

    6.1 预防死锁

    1. 破坏“互斥”条件:
      就是在系统里取消互斥。若资源不被一个进程独占使用,那么死锁是肯定不会发生的。但一般来说在所列的四个条件中,“互斥”条件是无法破坏的。因此,在死锁预防里主要是破坏其他几个必要条件,而不去涉及破坏“互斥”条件。

      注意:互斥条件不能被破坏,否则会造成结果的不可再现性。

    2. 破坏“占有并等待”条件:
      破坏“占有并等待”条件,就是在系统中不允许进程在已获得某种资源的情况下,申请其他资源。即要想出一个办法,阻止进程在持有资源的同时申请其他资源。
      方法一:创建进程时,要求它申请所需的全部资源,系统或满足其所有要求,或什么也不给它。这是所谓的 “ 一次性分配”方案。
      方法二:要求每个进程提出新的资源申请前,释放它所占有的资源。这样,一个进程在需要资源S时,须先把它先前占有的资源R释放掉,然后才能提出对S的申请,即使它可能很快又要用到资源R。

    3. 破坏“不可抢占”条件:
      破坏“不可抢占”条件就是允许对资源实行抢夺。
      方法一:如果占有某些资源的一个进程进行进一步资源请求被拒绝,则该进程必须释放它最初占有的资源,如果有必要,可再次请求这些资源和另外的资源。
      方法二:如果一个进程请求当前被另一个进程占有的一个资源,则操作系统可以抢占另一个进程,要求它释放资源。只有在任意两个进程的优先级都不相同的条件下,方法二才能预防死锁。

    4. 破坏“循环等待”条件:
      破坏“循环等待”条件的一种方法,是将系统中的所有资源统一编号,进程可在任何时刻提出资源申请,但所有申请必须按照资源的编号顺序(升序)提出。这样做就能保证系统不出现死锁。

    6.2 避免死锁

    理解了死锁的原因,尤其是产生死锁的四个必要条件,就可以最大可能地避免、预防和解除死锁。所以,在系统设计、进程调度等方面注意如何让这四个必要条件不成立,如何确定资源的合理分配算法,避免进程永久占据系统资源。此外,也要防止进程在处于等待状态的情况下占用资源。因此,对资源的分配要给予合理的规划。

    预防死锁和避免死锁的区别:
    预防死锁是设法至少破坏产生死锁的四个必要条件之一,严格的防止死锁的出现,而避免死锁则不那么严格的限制产生死锁的必要条件的存在,因为即使死锁的必要条件存在,也不一定发生死锁。避免死锁是在系统运行过程中注意避免死锁的最终发生。

    6.2.1 常用避免死锁的方法

    6.2.1.1 有序资源分配法

    这种算法资源按某种规则系统中的所有资源统一编号(例如打印机为1、磁带机为2、磁盘为3、等等),申请时必须以上升的次序。系统要求申请进程:
      1、对它所必须使用的而且属于同一类的所有资源,必须一次申请完;
      2、在申请不同类资源时,必须按各类设备的编号依次申请。例如:进程PA,使用资源的顺序是R1,R2; 进程PB,使用资源的顺序是R2,R1;若采用动态分配有可能形成环路条件,造成死锁。
      采用有序资源分配法:R1的编号为1,R2的编号为2;
      PA:申请次序应是:R1,R2
      PB:申请次序应是:R1,R2
      这样就破坏了环路条件,避免了死锁的发生。
      

    6.2.1.2 银行家算法

    详见银行家算法.

    6.2.2 常用避免死锁的技术

    1. 加锁顺序(线程按照一定的顺序加锁)
    2. 加锁时限(线程尝试获取锁的时候加上一定的时限,超过时限则放弃对该锁的请求,并释放自己占有的锁)
    3. 死锁检测

    6.2.2.1 加锁顺序

    当多个线程需要相同的一些锁,但是按照不同的顺序加锁,死锁就很容易发生。

    如果能确保所有的线程都是按照相同的顺序获得锁,那么死锁就不会发生。看下面这个例子:

    Thread 1:
    lock A
    lock B
    Thread 2:
    wait for A
    lock C (when A locked)
    Thread 3:
    wait for A
    wait for B
    wait for C

    如果一个线程(比如线程3)需要一些锁,那么它必须按照确定的顺序获取锁。它只有获得了从顺序上排在前面的锁之后,才能获取后面的锁。

    例如,线程2和线程3只有在获取了锁A之后才能尝试获取锁C(译者注:获取锁A是获取锁C的必要条件)。因为线程1已经拥有了锁A,所以线程2和3需要一直等到锁A被释放。然后在它们尝试对B或C加锁之前,必须成功地对A加了锁。

    按照顺序加锁是一种有效的死锁预防机制。但是,这种方式需要你事先知道所有可能会用到的锁(译者注:并对这些锁做适当的排序),但总有些时候是无法预知的。

    6.2.2.2 加锁时限

    另外一个可以避免死锁的方法是在尝试获取锁的时候加一个超时时间,这也就意味着在尝试获取锁的过程中若超过了这个时限该线程则放弃对该锁请求。若一个线程没有在给定的时限内成功获得所有需要的锁,则会进行回退并释放所有已经获得的锁,然后等待一段随机的时间再重试。这段随机的等待时间让其它线程有机会尝试获取相同的这些锁,并且让该应用在没有获得锁的时候可以继续运行(译者注:加锁超时后可以先继续运行干点其它事情,再回头来重复之前加锁的逻辑)。

    以下是一个例子,展示了两个线程以不同的顺序尝试获取相同的两个锁,在发生超时后回退并重试的场景:

    Thread 1 locks A
    Thread 2 locks B
    Thread 1 attempts to lock B but is blocked
    Thread 2 attempts to lock A but is blocked
    Thread 1’s lock attempt on B times out
    Thread 1 backs up and releases A as well
    Thread 1 waits randomly (e.g. 257 millis) before retrying.
    Thread 2’s lock attempt on A times out
    Thread 2 backs up and releases B as well
    Thread 2 waits randomly (e.g. 43 millis) before retrying.

    在上面的例子中,线程2比线程1早200毫秒进行重试加锁,因此它可以先成功地获取到两个锁。这时,线程1尝试获取锁A并且处于等待状态。当线程2结束时,线程1也可以顺利的获得这两个锁(除非线程2或者其它线程在线程1成功获得两个锁之前又获得其中的一些锁)。

    需要注意的是,由于存在锁的超时,所以我们不能认为这种场景就一定是出现了死锁。也可能是因为获得了锁的线程(导致其它线程超时)需要很长的时间去完成它的任务。

    此外,如果有非常多的线程同一时间去竞争同一批资源,就算有超时和回退机制,还是可能会导致这些线程重复地尝试但却始终得不到锁。如果只有两个线程,并且重试的超时时间设定为0到500毫秒之间,这种现象可能不会发生,但是如果是10个或20个线程情况就不同了。因为这些线程等待相等的重试时间的概率就高的多(或者非常接近以至于会出现问题)。
    (译者注:超时和重试机制是为了避免在同一时间出现的竞争,但是当线程很多时,其中两个或多个线程的超时时间一样或者接近的可能性就会很大,因此就算出现竞争而导致超时后,由于超时时间一样,它们又会同时开始重试,导致新一轮的竞争,带来了新的问题。)

    这种机制存在一个问题,在Java中不能对synchronized同步块设置超时时间。你需要创建一个自定义锁,或使用Java5中java.util.concurrent包下的工具。写一个自定义锁类不复杂,但超出了本文的内容。后续的Java并发系列会涵盖自定义锁的内容。

    6.2.2.3 死锁检测

    死锁检测是一个更好的死锁预防机制,它主要是针对那些不可能实现按序加锁并且锁超时也不可行的场景。

    每当一个线程获得了锁,会在线程和锁相关的数据结构中(map、graph等等)将其记下。除此之外,每当有线程请求锁,也需要记录在这个数据结构中。

    当一个线程请求锁失败时,这个线程可以遍历锁的关系图看看是否有死锁发生。例如,线程A请求锁7,但是锁7这个时候被线程B持有,这时线程A就可以检查一下线程B是否已经请求了线程A当前所持有的锁。如果线程B确实有这样的请求,那么就是发生了死锁(线程A拥有锁1,请求锁7;线程B拥有锁7,请求锁1)。

    当然,死锁一般要比两个线程互相持有对方的锁这种情况要复杂的多。线程A等待线程B,线程B等待线程C,线程C等待线程D,线程D又在等待线程A。线程A为了检测死锁,它需要递进地检测所有被B请求的锁。从线程B所请求的锁开始,线程A找到了线程C,然后又找到了线程D,发现线程D请求的锁被线程A自己持有着。这是它就知道发生了死锁。

    下面是一幅关于四个线程(A,B,C和D)之间锁占有和请求的关系图。像这样的数据结构就可以被用来检测死锁。

    这里写图片描述

    6.3 检测死锁

    一般来说,由于操作系统有并发,共享以及随机性等特点,通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销,而且不能充分利用资源。为此,一种简便的方法是系统为进程分配资源时,不采取任何限制性措施,但是提供了检测和解脱死锁的手段:能发现死锁并从死锁状态中恢复出来。因此,在实际的操作系统中往往采用死锁的检测与恢复方法来排除死锁。
    死锁检测与恢复是指系统设有专门的机构,当死锁发生时,该机构能够检测到死锁发生的位置和原因,并能通过外力破坏死锁发生的必要条件,从而使得并发进程从死锁状态中恢复出来。
    这时进程P1占有资源R1而申请资源R2,进程P2占有资源R2而申请资源R1,按循环等待条件,进程和资源形成了环路,所以系统是死锁状态。进程P1,P2是参与死锁的进程。
    下面我们再来看一看死锁检测算法。算法使用的数据结构是如下这些:
    占有矩阵A:n*m阶,其中n表示并发进程的个数,m表示系统的各类资源的个数,这个矩阵记录了每一个进程当前占有各个资源类中资源的个数。
    申请矩阵R:n*m阶,其中n表示并发进程的个数,m表示系统的各类资源的个数,这个矩阵记录了每一个进程当前要完成工作需要申请的各个资源类中资源的个数。
    空闲向量T:记录当前m个资源类中空闲资源的个数。
    完成向量F:布尔型向量值为真(true)或假(false),记录当前n个并发进程能否进行完。为真即能进行完,为假则不能进行完。
    临时向量W:开始时W:=T。
    算法步骤:
    (1)W:=T,
    对于所有的i=1,2,…,n,
    如果A[i]=0,则F[i]:=true;否则,F[i]:=false
    (2)找满足下面条件的下标i:
    F[i]:=false并且R[i]〈=W
    如果不存在满足上面的条件i,则转到步骤(4)。
    (3)W:=W+A[i]
    F[i]:=true
    转到步骤(2)
    (4)如果存在i,F[i]:=false,则系统处于死锁状态,且Pi进程参与了死锁。什么时候进行死锁的检测取决于死锁发生的频率。如果死锁发生的频率高,那么死锁检测的频率也要相应提高,这样一方面可以提高系统资源的利用率,一方面可以避免更多的进程卷入死锁。如果进程申请资源不能满足就立刻进行检测,那么每当死锁形成时即能被发现,这和死锁避免的算法相近,只是系统的开销较大。为了减小死锁检测带来的系统开销,一般采取每隔一段时间进行一次死锁检测,或者在CPU的利用率降低到某一数值时,进行死锁的检测。

    6.4 解除死锁

    一旦检测出死锁,就应立即釆取相应的措施,以解除死锁。
    死锁解除的主要方法有:
    1) 资源剥夺法。挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源,而处于资源匮乏的状态。
    2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
    3) 进程回退法。让一(多)个进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。


    展开全文
  •  死锁是指两或两以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为...

    什么是死锁?

      死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。

      例如,在某个计算机系统中只有一台打印机和一台输入 设备,进程P1正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2 所占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。

     

    死锁产生的原因:

    1.系统资源的竞争

      当系统中供多个进程共享的资源如打印机、公用队列的等,其数目不足以满足诸进程的需要时,会引起诸进程对资源的竞争而产生死锁。

    2.进程运行推进顺序不当引起死锁

      ● 进程推进顺序合法
      当进程P1和P2并发执行时,如果按照下述顺序推进:P1:Request(R1); P1:Request(R2); P1: Relese(R1);P1: Relese(R2); P2:Request(R2); P2:Request(R1); P2: Relese(R2);P2: Relese(R1);这两个进程便可顺利完成,这种不会引起进程死锁的推进顺序是合法的。
      ● 进程推进顺序非法
      若P1保持了资源R1,P2保持了资源R2,系统处于不安全状态,因为这两个进程再向前推进,便可能发生死锁。例如,当P1运行到P1:Request(R2)时,将因R2已被P2占用而阻塞;当P2运行到P2:Request(R1)时,也将因R1已被P1占用而阻塞,于是发生进程死锁。
     

    产生死锁的四个必要条件:

      ● 互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。

      ● 请求与保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源 已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。

      ● 不可剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能 由获得该资源的进程自己来释放(只能是主动释放)。

      ● 循环等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

      这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之一不满足,就不会发生死锁。

     

    死锁的避免与预防

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

      理解了死锁的原因,尤其是产生死锁的四个必要条件,就可以最大可能地避免、预防和解除死锁。只要打破四个必要条件之一就能有效预防死锁的发生:

      ● 打破互斥条件:改造独占性资源为虚拟资源,大部分资源已无法改造。

      ● 打破不可抢占条件:当一进程占有一独占性资源后又申请一独占性资源而无法满足,则退出原占有的资源。

      ● 打破占有且申请条件:采用资源预先分配策略,即进程运行前申请全部资源,满足则运行,不然就等待,这样就不会占有且申请。

      ● 打破循环等待条件:实现资源有序分配策略,对所有设备实现分类编号,所有进程只能采用按序号递增的形式申请资源。

     

    死锁避免和死锁预防的区别

      死锁预防是设法至少破坏产生死锁的四个必要条件之一,严格的防止死锁的出现;而死锁避免则不那么严格的限制产生死锁的必要条件的存在,因为即使死锁的必要条件存在,也不一定发生死锁。死锁避免是在系统运行过程中注意避免死锁的最终发生。

     

     

    实例演示

    下面通过一个例子对安全状态和不安全状态进行更深的了解 :
      

      如上图所示系统处于安全状态,系统剩余3个资源,可以把其中的2个分配给P3,此时P3已经获得了所有的资源,执行完毕后还能还给系统4个资源,此时系统剩余5个资源所以满足(P2所需的资源不超过系统当前剩余量与P3当前占有资源量之和),同理P1也可以在P2执行完毕后获得自己需要的资源。 
      如果P1提出再申请一个资源的要求,系统从剩余的资源中分配一个给进程P1,此时系统剩余2个资源,新的状态图如下:那么是否仍是安全序列呢那我们来分析一下 
      

      系统当前剩余2个资源,分配给P3后P3执行完毕还给系统4个资源,但是P2需要5个资源,P1需要6个资源,他们都无法获得资源执行完成,因此找不到一个安全序列。此时系统转到了不安全状态。

     

    转载于:https://www.cnblogs.com/Kevin-ZhangCG/p/9038223.html

    展开全文
  • 男孩子手里有小汽车,女孩子想玩汽车,但又不想把洋娃娃让给男孩子,男孩子想玩洋娃娃,但也不想把汽车给女孩子玩,他们两就这样僵持阻塞下去…这种情况就是资源死锁,洋娃娃和汽车就相当于是一资源,...
  • 死锁产生的原因及四个必要条件

    千次阅读 2018-07-21 22:12:23
    一. 什么是死锁?...1.因竞争资源发生死锁 现象:系统中供多进程共享的资源的数目不足以满足全部进程的需要时,就会引起对诸资源的竞争而发生死锁现象 (1)可剥夺资源和不可剥夺资源:可剥夺资源是...
  • 死锁形成的原因和四个必要条件

    千次阅读 2019-11-24 21:38:23
    死锁是指两或两以上的进程(线程)在运行过程中因争夺资源而造成的一种僵局,若无外力作用,这些进程(线程)都将无法向前推进 ,这时就形成了死锁。处于死锁状态的进程称为死锁进 比如一扇门,你要出我要进,你...
  • 死锁及其四个必要条件

    千次阅读 2018-07-08 00:59:33
      死锁是指两或两以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程...
  • 《“死锁四个必要条件的合理解释》分为三个部分: 【1】“死锁”的含义 【2】“死锁”的原因及四个必要条件的合理解释 【3】“死锁”的预防和解除 1.“死锁”的含义 所谓死锁:是指两个或两个以上的进程在...
  • 死锁是指两或两以上的进程(线程)在运行过程中因争夺资源而造成的一种僵局(Deadly-Embrace) ) ,若无外力作用,这些进程(线程)都将无法向前推进。 下面我们通过一些实例来说明死锁现象。 先看生活中的一...
  • 一. 什么是死锁?...1.因竞争资源发生死锁 现象:系统中供多进程共享的资源的数目不足以满足全部进程的需要时,就会引起对诸资源的竞争而发生死锁现象 (1)可剥夺资源和不可剥夺资源:可剥夺资源是
  • 《“死锁四个必要条件的合理解释》分为三个部分: 【1】“死锁”的含义 【2】“死锁”的原因及四个必要条件的合理解释 【3】“死锁”的预防和解除 1.“死锁”的含义 所谓死锁: 是指两个或两个以上的进程...
  • 一、什么是死锁? 两个线程或两个以上线程都在等待对方执行完毕才能继续往下执行的时候就发生了死锁。...二、产生死锁四个必要条件 ● 互斥条件:指进程对所分配到的资源进行排它性使用,即在一段
  • 在多道程序环境中,多进程可以竞争有限数量的资源。当一进程申请资源时,如果这时没有可用资源,那么这进程进入等待状态。有时,如果所申请的资源被其他等待进程占有,那么该等待进程有可能再也无法改变状态。...
  • 当系统中供多进程共享的资源如打印机,公用队列等,其数目不足以满足诸进程的需要时,会引起诸进程对资源的竞争而产生死锁。 (3)进程推进顺序不当。 进程在运行过程中,请求和释放资源的顺序不当,也同样会导致...
  • 系统中有许多不同类型的资源,其中可以引起死锁的主要是需要采用互斥访问、不可被抢占的资源,即临界资源; 可重用性资源和消耗性资源 可重用性资源是指可供用户重复使用多次的资源,它具有以下特点: 每一可...
  • 转载来自:... 一、什么是死锁 二、死锁与饥饿 三、资源的类型 3.1 可重用资源和消耗性资源 3.1.1 可重用资源(永久性资源) 3.1.2 消耗性资源(临时性资源) 3.2 可抢占资源...
  • 死锁: 我们先来思考一问题:我们加锁以后,再次进行加锁,这样会发生什么? 当我们第二次申请锁的时候,这时候锁已经被占用了,该线程就会被挂起,但是刚好这线程就是拥有锁...2.死锁产生的必要条件: (1) 互
  • 什么是死锁死锁是指多进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。例如,在某一计算机系统中只有一台打印机和一台输入 设备,进程P1正占用输入设备,同时又提出使用...
  • 死锁是指两或两以上的进程(线程)在运行过程中因争夺资源而造成的一种僵局(Deadly-Embrace) ) ,若无外力作用,这些进程(线程)都将无法向前推进。 下面我们通过一些实例来说明死锁现象。 先看生活中的一...
  • 一、死锁概念 死锁是指两或多进程在执行的过程中,因为竞争资源而造成互相等待的现象,若无外力作用,它们都无法推进下去。 1.在等待对方时占有不可抢占的资源 ...2.竞争可消耗资源引起死锁 有P1,P2,P3...
  • 1.死锁产生的必要条件是什么? 死锁是两或两以上的进程(或线程)在执行过程中,互相占用对方所需的资源,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去; 互斥:每资源要么已经...
  • (2) 理解产生死锁必要条件–以下四个条件同时具备:互斥条件、不可抢占条件、占有且申请条件、循环等待条件。 (3) 记住解决死锁的一般方法,掌握死锁的预防和死锁的避免二者的基本思想。 (4) 掌握死锁的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,718
精华内容 5,887
关键字:

引起死锁的四个必要条件是