即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

简谈死锁

编程语言 persistence_s 26℃ 0评论

什么死锁:


是两个或者两个以上的进程由于竞争资源而造成的的一种相互等待的线性,如无外力作用,这些进程将永远不能再向前推进。


陷入死锁状态的进程称为死锁进程,所占用的资源或者需要他们进行某种合作的进程就会相继陷入死锁,最终可能导致整个系统瘫痪

死锁的常见情形:


一般情况下,如果同一个线程先后两次调用lock,在第二次调用时,由于锁已经被占用,该线程会挂起等待别的线程释放锁,然而锁正是被自己占用着的,该线程又被挂起而没有机会释放锁, 因此 就永远处于挂起等待状态了,这叫做死锁(Deadlock)。但只有一个线程一般情况下是不会去加锁的。

另一种典型的死锁情形是这样:线程A获得了锁1,线程B获得了锁2,这时线程A调用lock试图获得锁2,结果是需要挂起等待线程B释放锁2,而这时线程B也调用lock试图获得锁1,结果是需要挂起等待线程A释放锁1,于是线 程A和B都 永远处于挂起状态了。这样就是一个环路等待,产生了死锁。

资源的分类:


根据资源的性质:可剥夺(抢占)和不可剥夺(抢占)资源


可抢占资源:一资源占有进程虽然需要使用该资源,但另一个进程却强行把资源从占有进程中抢占过来。(cpu,主存,硬盘)


不可抢占资源;除了占有进程主动释放资源外,其他进程不得在占有进程使用资源的时候强行抢占。(打印机,读卡器)

产生死锁的必要条件:


1、互斥条件:


一个进程一次只能被一个进程所使用


2、不可抢占条件:


一个资源仅能被它的占有进程所释放,不能被别的进程抢占。


3、请求和保持条件:


进程至少已经保持了至少一个资源,但又提出了新的资源要求,而该资源又被其他进程所占用,此时请求进程阻塞,但是又对它已经获得的资源部释放,此时别的进程如果申请它的资源就也会出现阻塞。


4、环路等待条件:


当每类资源只有一个的时候,在发生死锁的时候,必然会出现一个资源的环形链。P1在等待P2占有的一个资源S2,P2在等待P1占有的一个资源S1;

看资源分配图判断是否发生死锁


看是否存在环路


如果根本不存在环路,那么这个系统中没有死锁发生


如果存在环路,并且每个资源只有一个实例,那么一定有死锁发生


如果存在环路,但是每个资源有多个实例,那么不一定有死锁发生


找一个既不处于阻塞也不处于孤立点的点没有任何连接的),把和他相关联的边都擦掉,循环直到所有点都成为孤立点的时候,在这种情况下没有死锁发生。


如果找不到则肯定有死锁发生。

这里写图片描述

这里写图片描述

这里写图片描述


在之前信号量里如果不加标记P,V操作可能引发死锁

避免死锁的方法:


1、鸵鸟算法


当死锁在计算机中很少出现的时候,人们就不需要花费更多的精力去解决,而是采用鸵鸟一样的办法忽略它(UNIX常采用这种机制)比如计算机死机,可能是发生了死锁,于是直接重启。


2、预防死锁


静态方法:在进程执行前采取措施, 通过设置某些限制条件,去破坏死锁产生的四个必要条件之一,防止发生死锁。(互斥条件是不能破坏的,相反还要加以保护,所以其实只破坏了三个条件)


2.1破坏请求和保持条件:


系统要求任一进城必须预先申请他所需要的全部资源,而且仅当该进程的全部资源要求得到满足时,系统才会给予一次性分配,然后启动该进程运行,但是在分配的时候只要有一种资源不满足,系统就不会给该进程分配资源,于是只要进程运行了,在它运行期间绝对不可能去请求新的资源。


但是它的资源严重浪费,其他进程延迟进行,(尽管一部分资源虽然拿到了没有用,别的进程也只能等待)把原本可以并发的一些进程,只能等待它。


2.2破坏环路等待条件


采用资源顺序是用法,把所有资源类型先行排队,并按递增顺序赋予每类资源一个唯一的编号。要求每个进程在获得了某级资源后,他才能申请更高级的资源,如果他要申请比它级数低的资源,则必须释放所有大于这个低级资源的所有资源。


优点:资源利用率和系统吞吐量有明显的改善


缺点:位系统中各种类型的资源所分配的序号必须稳定,这就限制新设备的增加,到底归类为第几级资源。实际使用资源的顺序可能和系统规定的顺序不同而造成浪费。比如申请了但是没有用。


2.3不剥夺条件:


采用的策略:一个已经保持了某些资源的进程,当它在提出新的资源请求而不能立即得到满足,必须释放它所有已经保持的资源,代价太大。


由于要静态满足一些条件,因此代价太大。


3、避免死锁


该方法是允许进程动态的申请资源,系统在进行资源分配的时候,先计算资源分配的安全性,若此次分配不会导致系统从安全状态 想不安全状态转换,变可将资源分配给该进程,否则不分配该资,进程必须阻塞等待,从而避免发生死锁。著名的算法银行家算法(该算法用于银行系统现金贷款的发放而得名,在银行家算法里调用了安全序列算法)和安全序列算法。安全状态是指系统的一种状态。


4、检测和解除死锁


死锁的检测预先并不采用任何限制措施。允许系统在运行过程中发生死锁,但可能通过系统检测及时的检测死锁的发生,如果检测到死锁,则采用撤销进程等死锁解除方法使系统正常工作。


检测:根据资源分配图的简化来检测,上面已经叙述过。


死锁定理:进程死锁状态的充分条件是:仅当该进程的资源分配图是不可完全简化的,该充分条件成为死锁定理。


死锁检测的数据和算法类似于银行家算法。

死锁的解除:


第一种:强制性的撤销一个或多个死锁进程,来断开这个循环等待链,并收回给它分配的资源。


撤销哪一个或者哪一些死锁进程:


1、撤销全部的死锁进程


2、逐个撤销死锁进程直至断开这个循环等待链

第1个代价太大。


第2个撤销刚运行的死锁进程和占用了过多的资源的进程但是都是存在代价的。

另一种方法:使用有效的挂起和解除机制来挂起一些死锁的进程。

如果有错误,希望大家看过之后能给我指出来,让我及时的改正~

转载请注明:CodingBlog » 简谈死锁

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情