精华内容
下载资源
问答
  • 死锁,死锁的四个必要条件以及处理策略

    万次阅读 多人点赞 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) 进程回退法。让一(多)个进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。


    展开全文
  • 系统中有许多不同类型的资源,其中可以引起死锁的主要是需要采用互斥访问、不可被抢占的资源,即临界资源; 可重用性资源和消耗性资源 可重用性资源是指可供用户重复使用多次的资源,它具有以下特点: 每一可...

    死锁概述


    系统中有许多不同类型的资源,其中可以引起死锁的主要是需要采用互斥访问、不可被抢占的资源,即临界资源;

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

    1. 可重用性资源是指可供用户重复使用多次的资源,它具有以下特点:

      1. 每一个可重用性资源中的单元只能分配给一个进程使用,不允许多个进程共享;
      2. 使用可重用性资源时需要按照以下顺序进行:请求资源、使用资源、释放资源;
      3. 系统中每一类可重用性资源中的单元数目相对固定,进程在运行期间不能创建也不能删除它;

      对资源的请求和释放通常是通过系统调用完成的;

    2. 消耗性资源又称为临时性资源,它是在进程运行期间由进程动态创建和消耗的,它具有以下特点:

      1. 可消耗性资源的数目在进程运行期间是不断变化的;
      2. 进程可以不断创造可消耗性资源,将其放置在该类资源的缓冲区中;
      3. 进程在运行过程中可以申请多个可消耗资源单元,用于自己进程的消耗,不再将其归还。

      可消耗性资源通常由创建者进程创建,由消耗者进程使用;

    可抢占性资源和不可抢占性资源

    1. 可抢占性资源是指,该资源在被进程使用时可以被优先级更高的进程抢夺;常见的可抢占性资源包括处理机和内存;当内存资源比较紧张时,可以将一些进程暂时移到外存中去,其实就是对内存资源的一种抢占;
    2. 不可抢占性资源是指,在该类资源使用过程中,其拥有者不会发生变化;例如打印机、刻录机等设备;

    计算机系统中的死锁

    引起死锁的原因

    死锁的起因通常是对多个资源的争夺,不仅对不可抢占资源的争夺会引起死锁,对可消耗资源的争夺也会引起死锁

    1. 竞争不可抢占资源引起死锁:比如两个写文件的进程A和B分别操作文件F1和F2,某一时刻,A请求了F1,B请求了F2并且都得到允许;此时如果A请求F2,B请求F1,那么AB两个进程都会被阻塞,即死锁;
    2. 竞争可消耗资源引起死锁:这种情况的死锁通常是因为使用资源的顺序不当,比如A需要x才发出y;而B需要y才发出x;这样就形成了一种互相等待;
    3. 进程的不当推进引起死锁:进程的不当推进引起死锁通常是因为对资源的请求和释放的顺序是否合法,不当的推进顺序可能造成A持有X,但是A却在使用完Y后才释放X;B持有Y,但是B只有在使用完X后才释放Y,这样由于释放和申请的顺序也会造成死锁现象;

    死锁的定义、必要条件和处理方法

    死锁,可以定义为一组进程中的每一个进程都在等待只有这组进程中的进程才能触发的事件;

    产生死锁的必要条件

    1. 互斥条件:进程对分配给它的资源进行排它性使用,即在一段时间内某一个资源只能由一个进程使用。如果其他进程申请使用该资源则必须等待,直到拥有者释放该资源;
    2. 请求和保持条件:进程已经只少保持了一个资源,但是又提出了新的资源请求,该资源又被其他进程占用,此进程被阻塞,但是并没有释放自己拥有的资源;
    3. 不可抢占条件:分配给进程的资源,除非进程自己释放,否则其他进程不可抢占;
    4. 循环等待:发生死锁时,必然存在一个进程-资源的循环链;

    只要破坏四个条件中的一个,就能阻止死锁情况的发生;

    处理死锁的方法

    处理死锁的方法一般分为四种

    1. 预防死锁:通过设置某些条件,破坏产生死锁的四个条件之一来预防死锁,死锁的预防比较容易实现,被广泛采用;
    2. 避免死锁:同样属于预先防范策略,但它不是通过各种限制条件以破坏四个必要条件,而是在资源的动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁;
    3. 检测死锁:事先无需采用任何限制性措施,允许进程在运行过程中出现死锁,但是通过死锁检测机构及时地检测出死锁的发生,然后采取适当的条件,将进程从死锁中解救出来;
    4. 接触思索:当检测到系统出现死锁时,采用相应策略,将进程从死锁状态解救出来,通常是撤销一些进程,回收它们的资源,然后将其分配给其他进程;

    上述四种方法,从上到下对死锁的防范程度越来越低,但是对应的资源利用率越来越高,以及进程因资源因素被阻塞的频度越来越低(即并发程度提高);

    预防死锁

    预防死锁通常是破坏死锁产生的必要条件之一;由于互斥是并发状态下对临界资源的访问方式,不但不能破坏还必须遵守,所以只能破坏后面三个条件;

    1. 破坏“请求和保持条件”

      为了能破坏该条件,需要保证当进程在请求资源时,它不能持有不可抢占资源;通常有两种方法:

      1. 第一协议:所有进程在开始运行之前,必须一次性申请它在运行时需要用到的资源,只要有一个资源不满足,那么它就不能获得任何资源;这样,如果系统有足够的资源,那么进程在运行之前就可以获得需要的全部资源,运行中自然也就不请求其他资源了,即破坏了请求条件;如果进程需要的资源不能被满足,那么它就不能获得任何资源,这样当进程在等待状态时自然有就没有“持有”任何资源了;

        优点是简单、易行;这种方式的缺点很明显:首先资源被严重浪费,一个进程可能长期拥有一个只使用一小会的资源或者在开始就拥有一个只有到结束才可能用到的资源,这于资源来讲是极大的浪费;进程会经常发生饥饿现象,由于某些资源被其他进程长期占用,所以即便该资源对于某一个进程来说只有最后才会用到,该进程也不得不一直阻塞;

      2. 第二协议:进程一开始可以不必获得所有的资源才能运行,但是在进程的运行过程中需要逐步释放分配给自己的且已使用完毕的资源,然后才能继续申请其他所需要的新资源;这样做的好处是,不仅能更快地完成任务,提高设备的利用率,还可以避免进程发生饥饿现象;但是该方法实现比较复杂。

    2. 破坏“不可抢占条件”

      当一个进程在申请某一资源时,如果该请求不能被满足,那么该进程则释放自己已持有的所有资源;这种方法不但实现比较复杂,而且可能会因为反复申请和释放资源导致一些进程的执行无限期推迟,不仅延长了进程的周转时间,而且也增加了系统开销,降低了系统吞吐量;

    3. 破坏“循环等待条件”

      一个能保证“循环等待条件”不满足的策略是:对所有系统资源类型进行编号并线性排序,进程按照序列号递增的顺序申请资源;当进程所持有的最大资源号为x时,当且仅当A资源的序号y>x时该进程才能申请A资源;如果进程申请A资源,但是y<x,那么进程就需要释放自己持有的所有序号大于y的资源;采用这种资源分配方式所形成的资源分配图中不可能出现环路,所以也就破坏了循环等待的条件;

      采用这种资源分配方式,一个问题就是对资源类型的编号需要符合大多数进程使用资源的顺序,比如依据输入-计算-输出这一顺序,输入设备应该具有较低的类型号;此种方法相比其他几种方法来说,系统资源利用率和系统吞吐量均得到提高,但是也存在以下问题:1、扩充资源类型不便;2、存在一些进程,使用资源的顺序与系统规定的资源类型序号的策略不同,这样可能造成资源的浪费;3、这种方法对于编程增加了额外的限制;

    避免死锁

    避免死锁也是一种预防策略,但是并不是事先采取某种措施,破坏死锁的必要条件,而是在进行资源分配时防止系统进入不安全状态以避免产生死锁现象。由于这种方法所施加的限制条件较弱,所以系统有较好的性能,目前普遍采用这种方式;

    在死锁避免方法中,系统有两种状态:安全状态和不安全状态;当系统处于安全状态时,可以避免进入死锁;当系统处于不安全状态时,有可能进入死锁;

    安全状态与非安全状态:所谓安全状态,是指系统能按照某种进程推进方式(某个进程序列)为每个进程分配其所需的资源,直至满足每个进程对资源的最大需求,使每个进程都可以顺利地完成;如果找到这样一个序列,则系统是处于安全状态;否则系统处于不安全状态;虽然系统处于不安全状态时不一定进入死锁,但是是存在这个可能的;因此避免死锁的实质在于,系统进行资源分配时,应使系统不进入不安全状态;

    在建立了系统安全状态的概念之后,便可知避免死锁的基本思想就是确保系统始终处于安全状态;当有进程请求一个可用资源时,系统需要对该进程的请求进行计算,如果将资源分配给进程之后,系统仍然处于安全状态,那么该资源才可以分配给进程;否则不进行分配;

    避免死锁的最有代表性的算法就是DijKstra的银行家算法。该算法涉及的数据结构以及伪算法如下:

    1. 银行家算法涉及的数据结构:

      1. 可用资源向量Available。Available[j]=k;表示编号为j的资源系统一共有k个;
      2. 最大需求矩阵Max。Max[n,j]=k;表示进程n对编号为j的资源的最大需求是k个;
      3. 分配矩阵Allocation。Allocation[n,j]=k;表示进程n已经获得编号为j的资源已经获得k个;
      4. 当前需求矩阵Need。Need[n,j]=k;表示进程n当前对资源编号为j的资源还需要k个;
    2. 银行家算法的伪算法:

      设request是编号为x的进程的请求向量;如果request[j]=k,表示进程x对编号为j的资源请求量为k;

      1. 如果request[j]<=need[x,j],转向2;否则请求出错,因为它申请的资源数量超过当前它需要的数量,认为这是一个失败的请求;

      2. 如果request[j]<=Available[j],转向3;否则表示系统当前没有足够的资源可以分配,x进程需要等待;

      3. 试着将编号为j的资源分配给进程x,更新相关数据结构:

        Available[j]=Available[j]-request[j];

        Allocation[x,j]=Allocation[x,j]+request[j];

        Need[x,j]=Need[x,j]-request[j];

      4. 进入安全性检测程序(该程序试图找到一个安全序列;如果找到,说明这次分配之后系统仍然是安全的,否则这次分配无效,因为系统进入了不安全状态)

    3. 安全性检测程序数据结构及其伪算法

      1. 设置两个向量:工作向量Work,表示系统可提供给进程继续运行所需的各类资源数目;初始值为Available;Finish[j]表示编号为j的进程是否有足够资源,使之完成运行;初始值为false;当有足够资源时设置为true;

      2. 从进程中找到一个满足下述条件的进程:

        1) Finish[j]=false;2)Need[x,j]<=work[j];如果找到执行步骤3;否则执行4;

      3. 当进程x获得资源后,可顺利执行完毕,所以将归还分配给它的资源,所以执行:

        Work[j]=Work[j]+Allocation[x,j];

        Finish[x]=true;

        go to 2;

      4. 如果所有进程的Finish[j]=true,则表示系统处于安全状态;则上次的资源分配可以进行;否则,不行啊;

      到这里我就想到一个问题,如果2中满足条件的有多个,那么是否可以任意选择呢?正当我码这些字的时候,我想通了:是可以的!因为一旦选择完一个进程后,就假设该进程执行完毕,那么它就要归还系统资源,即系统资源是不减的!也就是说,如果在某一次查找中,有x个进程满足条件,那么任意选择一个进程并且执行完3后再回到2时,原来满足条件的进程现在一定还是满足的,原来不满足的进程由于资源的不减,也有可能满足,所以,是可以任意选择的!

    死锁的检测和解除

    如果系统中既没有死锁预防措施也没有死锁避免措施,那么系统很有可能发生死锁;在这种情况下,需要系统提供以下两种算法:死锁检测算法和死锁解除算法;

    1. 死锁检测算法:为实现死锁检测算法,需要系统记录各种资源的使用情况以及进程对资源的请求情况,并且系统需要能根据这些信息检测系统是否进入死锁状态;一种常见的死锁检测方法是利用资源分配图。

      资源分配图是这样的有向图:它包含两类节点(资源节点和进程节点)和两类边(资源请求边,由进程节点出发,指向资源节点;资源分配边,由资源节点指向进程节点);利用资源图分配图检测死锁的原理如下:

      在资源分配图中找到一个既不阻塞也不独立的进程节点,然后为其分配所需的全部资源,使其得以运行结束,再释放其所占有的全部资源,这相当于消去所有经过该进程节点的边使之成为一个独立的点,然后更新资源数量;然后重复这个步骤;如果经过一系列简化后,所有边都被消去,即所有节点都是孤立的,那么系统就没有死锁;否则系统就是死锁状态;这一定理也被称为死锁定理;

      这里,不同的简化顺序最后得到的简化图是一样的,道理同上面提到的一样,因为每简化一次,资源数目是不减的;

    2. 死锁解除算法:死锁解除常使用两种方法:抢占资源和终止进程;

      终止进程的方法有一次性终止所有死锁进程,效果立竿见影,但是也意味着功亏一篑:许多进程都需要从头再来,并且有些情况下,数据可能无法还原,从而造成极大的破坏;还有就是逐个终止进程,释放资源,直到打破循环等待,将系统从死锁中解决出来;但是这里存在一个问题,该如何选择要终止的进程?常常需要考虑以下几点:

      1. 进程的优先级;
      2. 进程的运行时间以及还需要多少时间完成执行;
      3. 进程在运行中使用了多少资源以及还需要多少资源;
      4. 进程的性质是交互式还是批处理式;

      一种最小代价的死锁解除算法是:对于死锁状态的每一个进程,都计算一遍终止该进程所产生的代价,然后选择代价最小的一个进程终止,然后如果系统还处于死锁,那么重复前一个步骤;但是计算选择代价最小的进程这一步骤可能会有较大的代价!总体来说,还是让系统别进入死锁的好!对吧!把死锁扼杀在摇篮里!

    展开全文
  • 死锁的四个必要条件

    千次阅读 2017-03-16 10:35:12
    一. 什么是死锁?  如果一进程集合里面...1.因竞争资源发生死锁 现象:系统中供多进程共享资源数目不足以满足全部进程需要时,就会引起对诸资源竞争而发生死锁现象 (1)可剥夺资源和不可剥夺资

    一. 什么是死锁?

         如果一个进程集合里面的每个进程都在等待这个集合中的其他一个进程(包括自身)才能继续往下执行,若无外力他们将无法推进,这种情况就是死锁,处于死锁状态的进程称为死锁进程

    二. 死锁产生的原因?

    1.因竞争资源发生死锁 现象:系统中供多个进程共享的资源的数目不足以满足全部进程的需要时,就会引起对诸资源的竞争而发生死锁现象

    (1)可剥夺资源和不可剥夺资源:可剥夺资源是指某进程在获得该类资源时,该资源同样可以被其他进程或系统剥夺,不可剥夺资源是指当系统把该类资源分配给某个进程时,不能强制收回,只能在该进程使用完成后自动释放  

    (2)竞争不可剥夺资源:系统中不可剥夺资源的数目不足以满足诸进程运行的要求,则发生在运行进程中,不同的进程因争夺这些资源陷入僵局。

    举例说明:  资源A,B; 进程C,D

    资源A,B都是不可剥夺资源:一个进程申请了之后,不能强制收回,只能进程结束之后自动释放。内存就是可剥夺资源

    进程C申请了资源A,进程D申请了资源B。

    接下来C的操作用到资源B,D的资源用到资源A。但是C,D都得不到接下来的资源,那么就引发了死锁。

    (3)竞争临时资源

    2.进程推进顺序不当发生死锁

     

    三. 产生死锁的四个必要条件?

    (1)互斥条件:进程对所分配到的资源不允许其他进程进行访问,若其他进程访问该资源,只能等待,直至占有该资源的进程使用完成后释放该资源

    (2)请求和保持条件:进程获得一定的资源之后,又对其他资源发出请求,但是该资源可能被其他进程占有,此事请求阻塞,但又对自己获得的资源保持不放

    (3)不可剥夺条件:是指进程已获得的资源,在未完成使用之前,不可被剥夺,只能在使用完后自己释放

    (4)环路等待(循环等待)条件:是指进程发生死锁后,必然存在一个进程--资源之间的环形链,通俗讲就是你等我的资源,我等你的资源,大家一直等。

     

    四. 处理死锁的基本方法

    1.预防死锁:通过设置一些限制条件,去破坏产生死锁的必要条件,像银行家算法之类的。

    2.避免死锁:在资源分配过程中,使用某种方法避免系统进入不安全的状态,从而避免发生死锁

    3.检测死锁:允许死锁的发生,但是通过系统的检测之后,采取一些措施,将死锁清除掉

    4.解除死锁:该方法与检测死锁配合使用

    展开全文
  • 一. 什么是死锁?...1.因竞争资源发生死锁 现象:系统中供多进程共享资源数目不足以满足全部进程需要时,就会引起对诸资源竞争而发生死锁现象 (1)可剥夺资源和不可剥夺资源:可剥夺资源是

    一. 什么是死锁?

         如果一个进程集合里面的每个进程都在等待这个集合中的其他一个进程(包括自身)才能继续往下执行,若无外力他们将无法推进,这种情况就是死锁,处于死锁状态的进程称为死锁进程

    二. 死锁产生的原因?

    1.因竞争资源发生死锁 现象:系统中供多个进程共享的资源的数目不足以满足全部进程的需要时,就会引起对诸资源的竞争而发生死锁现象

    (1)可剥夺资源和不可剥夺资源:可剥夺资源是指某进程在获得该类资源时,该资源同样可以被其他进程或系统剥夺,不可剥夺资源是指当系统把该类资源分配给某个进程时,不能强制收回,只能在该进程使用完成后自动释放  

    (2)竞争不可剥夺资源:系统中不可剥夺资源的数目不足以满足诸进程运行的要求,则发生在运行进程中,不同的进程因争夺这些资源陷入僵局。

    举例说明:  资源A,B; 进程C,D

    资源A,B都是不可剥夺资源:一个进程申请了之后,不能强制收回,只能进程结束之后自动释放。内存就是可剥夺资源

    进程C申请了资源A,进程D申请了资源B。

    接下来C的操作用到资源B,D的资源用到资源A。但是C,D都得不到接下来的资源,那么就引发了死锁。

    (3)竞争临时资源

    2.进程推进顺序不当发生死锁

     

    三. 产生死锁的四个必要条件?

    (1)互斥条件:进程对所分配到的资源不允许其他进程进行访问,若其他进程访问该资源,只能等待,直至占有该资源的进程使用完成后释放该资源

    (2)请求和保持条件:进程获得一定的资源之后,又对其他资源发出请求,但是该资源可能被其他进程占有,此事请求阻塞,但又对自己获得的资源保持不放

    (3)不可剥夺条件:是指进程已获得的资源,在未完成使用之前,不可被剥夺,只能在使用完后自己释放

    (4)环路等待条件:是指进程发生死锁后,必然存在一个进程--资源之间的环形链

     

    四. 处理死锁的基本方法

    1.预防死锁:通过设置一些限制条件,去破坏产生死锁的必要条件

    2.避免死锁:在资源分配过程中,使用某种方法避免系统进入不安全的状态,从而避免发生死锁

    3.检测死锁:允许死锁的发生,但是通过系统的检测之后,采取一些措施,将死锁清除掉

    4.解除死锁:该方法与检测死锁配合使用

    展开全文
  • 1.死锁:如果一组进程中的每一进程都在等待仅由该组进程中的其它进程才能引发的事件,那么该组进程是死锁的。2.产生死锁的原因:(1)竞争不可抢占性资源。(2)竞争可消耗资源。当系统中供多进程共享的资源如...
  • 一、死锁概念 死锁是指两或多进程在执行过程中,因为竞争资源而造成互相等待现象,若无外力作用,它们都无法推进下去。 1.在等待对方时占有不可抢占资源 ...2.竞争可消耗资源引起死锁 有P1,P2,P3...
  • 死锁产生原因及四个必要条件

    千次阅读 2018-07-21 22:12:23
    一. 什么是死锁?...1.因竞争资源发生死锁 现象:系统中供多进程共享资源数目不足以满足全部进程需要时,就会引起对诸资源竞争而发生死锁现象 (1)可剥夺资源和不可剥夺资源:可剥夺资源是...
  • 1.因竞争资源发生死锁 现象:系统中供多进程共享资源数目不足以满足全部进程需要时,就会引起对诸资源竞争而发生死锁现象(1)可剥夺资源和不可剥夺资源:可剥夺资源是指某进程在获得该...
  • 二、产生死锁的必要条件 互斥条件(资源独占) 请求和保持条件 不可抢占条件(不可剥夺) 循环等待条件 三、处理死锁的方法 预防死锁 避免死锁 检测死锁 解除死锁 、预防死锁 破坏‘请求和保持’条件 破坏‘不可...
  • 死锁的必要条件

    2011-08-18 23:47:01
    假设死锁是由于进程竞争资源而引起的,我们下面给出死锁发生的四个必要条件,这四个条件是Coffman首先提出的,所以也称为Coffman条件:  (1) 资源独占(mutual exclusion): 一个资源在同一时刻只能分配给一个进程. ...
  • 产生死锁的必要条件及处理方法

    千次阅读 2018-10-08 15:08:37
    二、产生死锁的必要条件 互斥条件(资源独占) 请求和保持条件 不可抢占条件(不可剥夺) 循环等待条件 三、处理死锁的方法 预防死锁 避免死锁 检测死锁 解除死锁 、预防死锁 破坏‘请求和...
  • 二、产生死锁的必要条件 互斥条件(资源独占) 请求和保持条件 不可抢占条件(不可剥夺) 循环等待条件 三、处理死锁的方法 预防死锁 避免死锁 检测死锁 解除死锁 、预防死锁 破坏‘请求和保持’条件 破坏‘不可...
  • 什么叫死锁? 所谓死锁: 是指两个或两个以上的进程在执行过程中,因争夺...1、产生死锁的四个必要条件并举个例子说明死锁的产生 首先我们要明白死锁的定义,死锁是两个或多个进程对资源的需求引起的冲突,可以做个
  • 死锁

    2021-01-16 14:25:45
    更严谨一点说,在一个系统中以下四个条件同时成立,那么就能引起死锁: 互斥条件:至少有一个资源处于非共享模式,也就是某个资源一次只能被一个进程使用,如果另一进程申请该资源,那么申请进程应等到该资源被释放...
  • 进程的死锁

    2017-03-06 22:27:08
    产生死锁的四个条件同时具备:互斥条件、不可抢占条件、占有且申请条件、循环等待条件 为什么会有死锁:若干进程竞争有限资源,又推进顺序不当,从而构成无限循环等待的局面,这种状态叫做死锁。所谓死锁是指多个...
  • 关于死锁

    2020-10-07 20:47:58
    文章目录什么是死锁死锁产生的原因:产生死锁的四个必要条件:处理死锁的方法预防死锁避免死锁检测死锁解除死锁 什么是死锁 死锁是指两个或两个以上的进程(线程)在运行过程中因争夺资源而造成的一种僵局(Deadly-...
  • 操作系统——死锁

    2020-04-12 15:47:45
    资源问题 重用性资源和可消耗性资源 可抢占性资源和不可抢占性资源 计算机系统中死锁 竞争不可抢占性资源引起死锁 竞争可消耗资源引起死锁 进程推进顺序不当引起...产生死锁必须同时具备下面四个必要条件,只...
  • 操作系统 死锁

    2018-05-25 20:40:00
    死锁 定义:一组进程的每一进程都在等待仅有该组进程中的其他进程才能引发的...预防死锁:即破坏形成死锁的四必要条件之一就能避免死锁。破坏请求和保持,进程运行前请求所有需要的资源,如果不能申请到就阻...
  • 本文讲述了死锁的概念,产生死锁的四个必要条件,死锁的处理方式和在SQL Server中如何检测避免和处理死锁。死锁是由于阻塞引起的,了解这部分基本概念对于死锁方面的排错是非常必要的 简介  死锁的本质是...
  • 产生死锁

    2013-11-07 11:59:17
    计算机系统产生死锁的根本原因是资源有限且操作不当。... 产生死锁的四个必要条件:  1、互斥条件:在一段时间内,一个资源只能由一个进程独占使用,若别的进程也要求该资源,则须等待直至其占用者释放;  2.
  • 产生死锁的原因? 竞争不可抢占性资源引起死锁; 竞争可消耗资源引起死锁; 进程推进顺序不当引起死锁。...预防死锁:破坏产生死锁的四个必要条件中的一个或几个来预防产生死锁。 避免死锁:在资源的...
  • 关于计算机系统的死锁

    千次阅读 2011-04-18 08:34:00
     产生死锁的四个必要条件: 1、互斥条件:在一段时间内,一个资源只能由一个进程独占使用,若别的进程也要求该资源,则须等待直至其占用者释放; 2.不可抢占条件:进程所获得的资源在未使用完毕之前,资源申请者...

空空如也

空空如也

1 2 3
收藏数 43
精华内容 17
关键字:

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