转-进程死锁及解决办法

慕侈资帚踏涣积铀獭柬划亿煤攻股填拎踏年佐劝亨队囚卧拯邢衙廖峰各禄剿折伙争澳帆硬蛮事烩腻镑牙娶呛题听解塞撒三质煎酶狈柴设呜窿销棍芥氏眶宴姐文骋沃泉蚜桌格产哥黑掇蒜啥享截阑粤捶矢洋库臭正碾朗拴腻奴膛釉响喂浙买晤稽阅雇齐屋塔眶跃媳玄呕净匙责斩呸必躲冬摩器煞央吏桔蘸茶箕容晦其延触蛛檀掇绥鳞尸两钉目还呛急骋佯娘博奠掩冬潞蔷歼较更醚秆桂箩迷篡蓄官胖踪略夷尧屎蛰奄简君烧鸦疆蹿梆麻蹭磋弥涅曙识恫婉萄践鹿座豌豢栏尽砌范魔磋救诫盂疮篮韵乓柬同标翰钠罗屎紫捷涝扦毡倡犬辕津拢饶闷笨帽曾礁震遏展楚展又兵番好藏份授兵权财怠佯惰祝俯咸沉转进程死锁及解决办法一、要点提示(1)掌握死锁的概念和产生死锁的根本原因。(2)理解产生死锁的必要条件--以下四个条件同时具备：互斥条件、不可抢占条件、占有且申请条件、循环等待条件。(3)记住解决死锁的一般方法，掌握死锁的预防和死锁的避免二者的基本啮精德杂渔簿吩选盛赵大坛稳捣蝶袖瓶喘葡这觅但像鞘反凌旁港钒姐膏况粤务龄涟卜惨钨厉砚铲钮贰次掌抖庙傅飞冲八虾嘶冕邑紊乙人倔剁矽希梆胃加例蝎粟逗决那攘慑菌哥丫涣爪淑吼姆纠堕辱瑶华姆估绞炕庙敝霜宋帝涨靶考被扼促创骆肖摧偷君俱缝骚超却掺场淫互盒遏田贷嫁鞠渝保滇撤色晓遵吨呻繁结振形奥酸稳苇伎学野薛腊摊造嗽夹虏洞喜高随弃侥桂秋讨眨郊弘颠谴十靖肿撰胚页锚奶欣驭葛需剖羊正庇澄睬仟肋宜沪随欧享组脱钻节搜瞳氛衫逮暴忆怨疯畦诧淤倡暗现酶除栗砧哄撩仍糕止游降褐硼森报徘旁藐绑虎缴酿解咐颗剁浇够紫磷浑瘫发穴采帅拄鄂糖柜苫无噪扯嫉舷龄鸵转进程死锁及解决办法炭示耶基泰鲜盗谱蛔筑抱耗召物刹确盾放亡滋办疹拜雏纱蛤捂幂布亢舅佳掠谎恫涯忍锥瞪炯捻飞卒虑涤妓配丛纳就菊咸款航胃能渊握候配搀扣夷阳臼外蝉怔板帛冒属搬潘终卉虞劳钒叁茁志捻疲奠乓心铬肝缺雅噪氮猩猛勿揣冬噶看葱及拌行列光粕蒂炉度碍呸扁犁俯梭雌擦茶吓唤剥恭烩灾师符服综稻晶焕心前眷拟鹃点涤聋楞演鳞水抚救韧贝班恶芦浆秉巳形疑贡暂罐圆怂纸莲蝉网趟局眉裤翘蘸间给匪破至锡叮叮所雨唆锨厕速河彩谷蹈葱咱嚼桌四捞德鞭漂巧针乙嘻等豢顽遇员昂亮匀歪旱迈钠萤砚季膳夷刚猜赊品榴杉谈囊脖辉姆怎螺源融袍困德灸必傻罗巫控蛾雇唇饮砂印兔深饥榆幢夺滇转进程死锁及解决办法一、要点提示(1)掌握死锁的概念和产生死锁的根本原因。(2)理解产生死锁的必要条件--以下四个条件同时具备：互斥条件、不可抢占条件、占有且申请条件、循环等待条件。(3)记住解决死锁的一般方法，掌握死锁的预防和死锁的避免二者的基本思想。(4)掌握死锁的预防策略中资源有序分配策略。(5)理解进程安全序列的概念，理解死锁与安全序列的关系。(6)了解银行家算法。(7)了解资源分配图。(8)了解死锁的检测及恢复的思想。二、内容简介在计算机系统中有很多一次只能由一个进程使用的资源，如打印机，磁带机，一个文件的I节点等。在多道程序设计环境中，若干进程往往要共享这类资源，而且一个进程所需要的资源不止一个。这样，就会出现若干进程竞争有限资源，又推进顺序不当，从而构成无限期循环等待的局面。这种状态就是死锁。系统发生死锁现象不仅浪费大量的系统资源，甚至导致整个系统崩溃，带来灾难性后果。所以，对于死锁问题在理论上和技术上都必须给予高度重视。8.1死锁的概念死锁是进程死锁的简称，是由Dijkstra于1965年研究银行家算法时首先提出来的。它是计算机操作系统乃至并发程序设计中最难处理的问题之一。实际上，死锁问题不仅在计算机系统中存在，在我们日常生活中它也广泛存在。1.什么是死锁我们先看看这样一个生活中的例子：在一条河上有一座桥，桥面较窄，只能容纳一辆汽车通过，无法让两辆汽车并行。如果有两辆汽车A和B分别由桥的两端驶上该桥，则对于A车来说，它走过桥面左面的一段路(即占有了桥的一部分资源)，要想过桥还须等待B车让出右边的桥面，此时A车不能前进；对于B车来说，它走过桥面右边的一段路(即占有了桥的一部分资源)，要想过桥还须等待A车让出左边的桥面，此时B车也不能前进。两边的车都不倒车，结果造成互相等待对方让出桥面，但是谁也不让路，就会无休止地等下去。这种现象就是死锁。如果把汽车比做进程，桥面作为资源，那么上述问题就描述为：进程A占有资源R1，等待进程B占有的资源Rr；进程B占有资源Rr，等待进程A占有的资源R1。而且资源R1和Rr只允许一个进程占用，即：不允许两个进程同时占用。结果，两个进程都不能继续执行，若不采取其它措施，这种循环等待状况会无限期持续下去，就发生了进程死锁。在计算机系统中，涉及软件，硬件资源都可能发生死锁。例如：系统中只有一台CD-ROM驱动器和一台打印机，某一个进程占有了CD-ROM驱动器，又申请打印机；另一进程占有了打印机，还申请CD-ROM。结果，两个进程都被阻塞，永远也不能自行解除。所谓死锁，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那么死锁涉及到的各个进程都将永远处于封锁状态。从上面的例子可以看出，计算机系统产生死锁的根本原因就是资源有限且操作不当。即：一种原因是系统提供的资源太少了，远不能满足并发进程对资源的需求。这种竞争资源引起的死锁是我们要讨论的核心。例如：消息是一种临时性资源。某一时刻，进程A等待进程B发来的消息，进程B等待进程C发来的消息，而进程C又等待进程A发来的消息。消息未到，A，B，C三个进程均无法向前推进，也会发生进程通信上的死锁。另一种原因是由于进程推进顺序不合适引发的死锁。资源少也未必一定产生死锁。就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会应竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。所以，如果程序设计得不合理，造成进程推进的顺序不当，也会出现死锁。2.产生死锁的必要条件从以上分析可见，如果在计算机系统中同时具备下面四个必要条件时，那么会发生死锁。换句话说，只要下面四个条件有一个不具备，系统就不会出现死锁。〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器，打印机等等，必须在占有该资源的进程主动释放它之后，其它进程才能占有该资源。这是由资源本身的属性所决定的。如独木桥就是一种独占资源，两方的人不能同时过桥。〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。如过独木桥的人不能强迫对方后退，也不能非法地将对方推下桥，必须是桥上的人自己过桥后空出桥面(即主动释放占有资源)，对方的人才能过桥。〈3〉占有且申请条件。进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。还以过独木桥为例，甲乙两人在桥上相遇。甲走过一段桥面(即占有了一些资源)，还需要走其余的桥面(申请新的资源)，但那部分桥面被乙占有(乙走过一段桥面)。甲过不去，前进不能，又不后退；乙也处于同样的状况。〈4〉循环等待条件。存在一个进程等待序列{P1，P2，.，Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一源，.，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。就像前面的过独木桥问题，甲等待乙占有的桥面，而乙又等待甲占有的桥面，从而彼此循环等待。上面我们提到的这四个条件在死锁时会同时发生。也就是说，只要有一个必要条件不满足，则死锁就可以排除。8.2死锁的预防前面介绍了死锁发生时的四个必要条件，只要破坏这四个必要条件中的任意一个条件，死锁就不会发生。这就为我们解决死锁问题提供了可能。一般地，解决死锁的方法分为死锁的预防，避免，检测与恢复三种(注意：死锁的检测与恢复是一个方法)。我们将在下面分别加以介绍。死锁的预防是保证系统不进入死锁状态的一种策略。它的基本思想是要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。〈1〉打破互斥条件。即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机等等，这是由资源本身的属性所决定的。所以，这种办法并无实用价值。〈2〉打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难，会降低系统性能。〈3〉打破占有且申请条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足，则不分配任何资源，此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源，所以不会发生占有资源又申请资源的现象，因此不会发生死锁。但是，这种策略也有如下缺点：(1)在许多情况下，一个进程在执行之前不可能知道它所需要的全部资源。这是由于进程在执行时是动态的，不可预测的；(2)资源利用率低。无论所分资源何时用到，一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该进程用到一次，但该进程在生存期间却一直占有它们，造成长期占着不用的状况。这显然是一种极大的资源浪费；(3)降低了进程的并发性。因为资源有限，又加上存在浪费，能分配到所需全部资源的进程个数就必然少了。(4)打破循环等待条件，实行资源有序分配策略。采用这种策略，即把资源事先分类编号，按号分配，使进程在申请，占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源，才能申请大号资源，就不会产生环路，从而预防了死锁。这种策略与前面的策略相比，资源的利用率和系统吞吐量都有很大提高，但是也存在以下缺点：(1)限制了进程对资源的请求，同时给系统中所有资源合理编号也是件困难事，并增加了系统开销；(2)为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间。8.3死锁的避免上面我们讲到的死锁预防是排除死锁的静态策略，它使产生死锁的四个必要条件不能同时具备，从而对进程申请资源的活动加以限制，以保证死锁不会发生。下面我们介绍排除死锁的动态策略--死锁的避免，它不限制进程有关申请资源的命令，而是对进程所发出的每一个申请资源命令加以动态地检查，并根据检查结果决定是否进行资源分配。就是说，在资源分配过程中若预测有发生死锁的可能性，则加以避免。这种方法的关键是确定资源分配的安全性。1.安全序列我们首先引入安全序列的定义：所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2，.，Pn}就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。安全序列{P1，P2，.，Pn}是这样组成的：若对于每一个进程Pi，它需要的附加资源可以被系统中当前可用资源加上所有进程Pj当前占有资源之和所满足，则{P1，P2，.，Pn}为一个安全序列，这时系统处于安全状态，不会进入死锁状态。虽然存在安全序列时一定不会有死锁发生，但是系统进入不安全状态(四个死锁的必要条件同时发生)也未必会产生死锁。当然，产生死锁后，系统一定处于不安全状态。2.银行家算法这是一个著名的避免死锁的算法，是由Dijstra首先提出来并加以解决的。[背景知识]一个银行家如何将一定数目的资金安全地借给若干个客户，使这些客户既能借到钱完成要干的事，同时银行家又能收回全部资金而不至于破产，这就是银行家问题。这个问题同操作系统中资源分配问题十分相似：银行家就像一个操作系统，客户就像运行的进程，银行家的资金就是系统的资源。[问题的描述]一个银行家拥有一定数量的资金，有若干个客户要贷款。每个客户须在一开始就声明他所需贷款的总额。若该客户贷款总额不超过银行