搜索
Unit5死锁操作系统原理——冯耀霖进程管理之四内容●什么是死锁●产生死锁的条件●死锁的应对§1什么是死锁◆产生死锁的原因◆死锁定义图5-1生活现实中的交通死锁造成这种死锁的根本原因是什么？竞争资源！在计算机系统中同样会发生类似交通死锁的线程死锁现象。例如，设有两个线程A和B，它们都要使用资源R1和R2来完成各自的任务，且用以下方式使用这两个资源：线程A线程B．．．．．．point1:申请R1申请R2．．．．．．point2:申请R2申请R1．．．．．．释放R1释放R2．．．．．．释放R2释放R1．．．．．．如果一个线程在另一个线程到达执行点point1之前率先到达执行点point2，那么它就能获得它所需要的第二个资源，从而可继续运行下去。但是，由于各线程都是异步前进的，如果没有一个线程先于另一个线程到达point1之前到达point2，即它们都处于point1和point2之间，此时任一线程到达point2都将相继被阻塞，它们都在等待获取对方已经占用了又无法释放的资源，于是线程A和B陷入了死锁。再考虑下面的线程通信例子，每个线程都试图接收另一个线程发来的消息，然后再给对方发送一则消息：线程A线程B．．．．．．receive(B,mes);receive(A,mes);．．．．．．send(B,mes);send(A,mes);．．．．．．这种设计错误导致任一线程执行receive操作时将被阻塞而无法去执行send操作，从而发生死锁。死锁（deadlock）定义：如果有一组线程，每个线程都在等待一个事件的发生，而这个事件只能由该组线程里面的另一个线程发出，则称这组线程发生了死锁。（这里的事件通常是指释放资源）在死锁状态下，没有线程可以执行或被唤醒，即该组线程陷入了相互永久阻塞的困局，其中的每个线程都必须在另一个线程向前推进之后才能继续推进，但每个线程又都无法推进，导致了系统的局部瘫痪，进而可能导致整个系统的瘫痪。§2产生死锁的条件◆必要条件◆充分必要条件2.1产生死锁的必要条件■条件1：资源互斥。即一组进程使用了必须互斥的临界资源。如果大家使用的是非临界资源，就不会发生相互等待现象，也就不会发生死锁。■条件2：请求和保持。即进程在请求使用新的资源的同时，保持对已获取资源的占有并不释放。■条件3：不可剥夺。即一进程所占有的资源是不可剥夺资源。如果占有的是可剥夺资源则不会发生死锁，例如，不会因为对CPU的争夺而产生死锁。■条件4：循环等待。即存在一个闭合的进程－资源环路，其中的每个进程已占有着某个（些）资源，同时又在等待获取被环路中另一个进程占有的资源。2.2充分必要条件假定在某个时刻一组线程使用一组资源的状态为S（S也称资源分配状态），一个RAG(ResourcesAllocationGraph)是该S所对应的有向图，如果：(1)该RAG中未出现任何环路，则S为非死锁状态，也称安全状态。(2)该RAG中出现了环路，但环路中的各资源不全为单单位资源，则S不一定是死锁状态。换言之，由若干不全为单单位资源构成的环路是S为死锁状态的必要条件但非充分条件。(3)该RAG中出现了环路，且环路中的各资源均为单单位资源，则S为死锁状态。换言之，由若干单单位资源构成的环路是S为死锁状态的充要条件。图5-2死锁定理(1)线程1线程2线程3是可完全化简图。安全状态！R1R2R3R4图5-3死锁定理(2)线程1线程2线程3构成不可化简图。死锁！R1R2R3R4死锁定理：在某个时刻的进程资源状态S为死锁状态的充分必要条件是当且仅当S的资源分配图（RAG）是不可完全化简的。§3死锁的应对◆忽略死锁策略◆检测并解除策略◆避免死锁策略◆预防死锁策略◆综合治理死锁是操作系统必须应对的问题，是无法回避的。那么如何应对死锁呢？从高级境界来看，只有两种对策：●允许死锁发生●不允许死锁发生这两种对策又各有两个策略。对于对策1，两个策略是：(1)回避死锁。即不予理睬，当死锁发生后就重启呗(2)检测并解除。即一旦发生死锁便能通过某种检测机制立即检测出来，并能精确地定位相关的进程和资源，然后采取适当措施解除死锁，使系统可继续运行。对于对策2，两个策略是：(1)预防死锁。即通过设置某些严格的限制条件来消除产生死锁的四个必要条件中的至少一个条件，从而杜绝死锁的发生。(2)避免死锁。与预防死锁方法不同的是，它无需预先设置严格的限制条件，而是在资源的动态分配过程中，通过使用某种只需施加较弱限制条件的方法来防止相关线程进入不安全状态，从而避免死锁的发生。3.1回避死锁策略这是人类面对难题时经常采取的办法，或者是大部分人遇到困难时所采取的办法，我们不想花力气解决难题，或者没有能力解决难题，或者认为解决难题的代价超过难题本身带来的后果。为此，我们可能采取视而不见的办法来处理各种棘手问题。此种策略就是操作系统不采取任何措施，任由死锁的发生。这看上去是一种非常糟糕的策略，很多人可能认为没有什么操作系统会采取这种策略。但这种策略真的很糟糕吗？如果很糟糕，就不会有很多人在面对问题时采取这种策略了。实际上，这种策略是大多数人在大多数情况下采取的策略。老子说过“无为而治”就是这个策略。你什么都不用做（实际上并不是什么都不做，而是尽量少做），事情慢慢就朝着有利的方向发展。从哲学角度来说，世界上本没有问题，是你认为有问题，才有问题。学生考试不及格，要补考，补考也不及格，毕不了业。毕不了业是问题吗？不尽然。只有你认为是问题时它才是问题。比尔盖茨大学没毕业，并不妨碍他成为世界首富。乔布斯大学也没毕业，LarryPage则是研究生没有毕业，前者创办了Apple，后者创办了Google。如果你毕业了，就不能成为比尔盖茨或乔布斯或LarryPage了，因为你毕业了，已经和他们不一样了。死锁也一样。只有你认为它是问题时它才是问题。而研究商业操作系统的人不认为这是什么大问题，因为经分析发现，死锁发生的频率不太高（当然这点有争议），所以不必管它。另外，死锁防止的代价很高，防止死锁比重启系统100次的代价还高，因此不如直接重启，即如果发生死锁的话，重启即可。这就是Windows等一些商业操作系统没有采取死锁防止措施的原因，这也是你的电脑经常死机的原因，甚至连Linux也没有采取死锁防止措施。在操作系统设计时常常不得不进行折中，是想尽量方便，偶尔出点错误呢？还是保证系统完全正确，但是费了很大力气？多数人选择的是前者。当然，如果涉及的是要求高可靠性的高端系统或实时控制系统，就另当别论了，那绝对不允许死锁。3.2检测并解除策略该策略也允许死锁发生，但系统定时地或当系统出现异常时执行一个“死锁检测程序”，用于判断系统是否已发生死锁，如果检测到已发生了死锁，则设法加以解除。1.检测死锁死锁检测算法的基本思路是：判断死锁定理是否成立。显然，这可利用有向图来实现，但算法的时间复杂度是O(n3)，开销过大，通常不予采用。下面是一种较实用的算法。设置2个矩阵。一个是资源占用矩阵U，列出了各进程占用资源的状态，如图5-4所示。一个是资源等待矩阵W，列出了各进程还需要的资源，如图5-5所示。R1R2R3R4R5Pro1_2132Pro27_325Pro346_32Pro4321_1Pro53543_图5-4资源占用矩阵R1R2R3R4R5Pro132210Pro206100Pro300311Pro411021Pro500002图5-5资源等待矩阵另设置2个向量。一个是系统资源总数向量T，如图5-6所示。另一个是当前可用资源向量C，如图5-7所示。R1R2R3R4R5系统总资源2020101510R1R2R3R4R5可用资源数35140图5-6系统资源总量图5-7当前可用资源算法的运算比较简单，把向量C依次与矩阵W的每一行进行比较：Cj－Wij。如果每一行中都出现了负数，即每个进程都有不能满足的资源，那就是发生了死锁。图5-4到图5-7表示的系统将要发生死锁。2.解除死锁通常可以采取下面两种可行的方法。(1)资源剥夺法由于死锁是因进程竞争资源而引起的，所以，从一些进程那里强行剥夺足够数量的资源再分配给死锁进程，就可以解除死锁状态。问题是选择哪个进程作为牺牲品？而这往往不是容易作出的决策。一种选择是剥夺占用资源最多的进程，以期尽可能多地释放资源，不过后果很难预料。每次剥夺后，需要再次调用死锁检测算法，若已成功解除死锁，则不需再剥夺。(2)撤消进程法该方法不光是剥夺某个进程的资源，而是将整个进程Kill。这其实并不会更加残忍，因为剥夺一个进程的资源有可能已经造成该进程无法在正确运行了，所以干脆Kill。其后果也难以预料。实际上，死锁的检测与解除策略可能根本就行不通。首先，使用资源占用矩阵和资源等待矩阵来检测死锁并不可靠，因为该算法依据的只是死锁的必要条件而非充要条件，即该算法的结果只能说明死锁有可能发生，但并不能肯定死锁必定发生。其次，在多用户系统中这个矩阵可能是一个巨大的矩阵，并且，资源每发生一下变化，就要更新这个矩阵，CPU开销也将很高。3.3避免死锁策略死锁的检测与解除是种亡羊补牢的策略，即使是检测出并解除了死锁，也已经浪费了时间，降低了效率，甚至造成了其他损失。而避免死锁策略则更加积极主动，它是在资源的动态分配过程中，通过使用某种方法来防止相关进程进入不安全状态，从而避免死锁的发生。Dijkstra提出的银行家算法是最著名的避免死锁算法。这一名称的来历是基于该算法把操作系统比做一个银行家，操作系统管理的各种资源比做银行的借贷资金，而申请系统资源的进程喻为借贷的客户。如果每个客户的借贷总额不超过银行的借贷资金总数，而且在有限的期限内可收回借出的全部贷款，那么银行就可以满足客户的借贷要求，同客户进行借贷交易，否则银行将拒绝借贷给客户。银行家算法的基本思想是，在每次进行资源分配时先进行安全性检查：如果满足此资源请求系统将进入到不安全状态，则拒绝分配；只有确保系统处于安全状态时才实施资源分配。所谓安全状态是指，对于一组进程系统能保证其中的每个进程都能在有限时间内获得各自所需的全部资源。否则，就是不安全状态。不安全状态并不是死锁状态，而是潜在的死锁状态，极有可能转化为死锁状态。例：安全状态例：不安全状态（见书Page110~111）避免死锁策略的优点是，在死锁有可能发生时采取先发制人的措施，断然拒绝可能引导系统进入潜在死锁的资源请求。由于系统从来不会进入到死锁状态，死锁带来的各种问题自然不复存在。但该策略的缺点也是十分明显的。首先，计算一个状态是否安全不是一件容易的事。从上面的例子也许觉得这种计算不是十分困难，问题是，这只是对一种资源及3个进程的超简单系统进行的计算，如果系统资源种类繁多，进程个数庞大，则这种计算将变得十分复杂和费时。其次，该策略要求事先知道每个进程的最大资源需求，这不是需要预测将来吗？这是非常困难的。只能采用粗略估算，但粗略估算往往是不可靠的。例如，2007~2008年度的美国次级贷就是这种错误估算的一个实例，因为他们算错了客户的信用额度，使得很多人还不起贷款，从而导致美国的金融危机。3.4预防死锁策略该策略的中心思想是清除死锁发生的土壤，而死锁发生的土壤就是死锁的4个必要条件，如果消除这4个必要条件中的任何一个，则死锁就不可能发生。1.消除资源互斥条件对有些临界资源可以将它们改造成逻辑上的非临界资源，例如，利用“假脱机”技术可将打印机改造成非临界资源。不过“假脱机”技术并不适应所有的临界资源，如键盘。2.消除保持和请求条件消除这个条件很简单，只要进程一次性请求它所需要的所有资源，由于一个进程一次就获得了其所需的所有资源，该进程自然就可以顺利运行，从而不会发生死锁。当然，如果系统不能一次性地满足一进程的所有资源，则阻塞该进程。这种策略的缺点是：一次性分配所有资源太过浪费，因为有的资源可能要到最后才使用，但却长时间闲置着又不能给其他进程使用；其次，一开始就需要知道一个进程所需要的所有资源，这个问题仍然无解。3.消除不可剥夺条件该策略可适用于某些资源，如剥夺一进程的CPU和内存空间。另外，可借助SPOOLing技术将某些