第7章 处理机调度与死锁2

17.3死锁的概念7.3.1死锁的定义可重用资源(reusableresource):各个进程可以轮流使用，如处理机、内存、I/0外设、文件等都是可重用资源，在使用可重用资源时可能出现的死锁（Deadlock）。通常是由于各进程巳拥有部分资源，同时请求其他进程已占有的资源，从而造成永远等待。可消耗资源(consumableresource):是指可以动态生成和动态消耗的资源，一般不限制数量，如中断、信号量、消息、缓冲区等都是可消耗资源。由于可消耗资源的生成和消耗存在依赖关系，因此他们的使用也可能因为双方都等待对方生成资源而形成死锁。2S2P1S3P3S1P2图7-1进程之间通信时的死锁3死锁的定义:死锁是一组并发进程,它们共享系统的某些资源,该组进程中每个进程都已经占有了部分资源,但都在不释放自己占有资源的情况下要求获得被其它进程已经占有的资源,从而造成它们相互等待,永远不能继续推进的状态.说明：①参与死锁的进程最少是两个（两个以上进程才会出现死锁）。②参与死锁的进程至少有两个已经占有资源。③参与死锁的所有进程都在等待事件。④参与死锁的进程是当前系统中所有进程的子集。47.3.2资源分配图(2)凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi,rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e={rj,pi}是资源分配边，由资源rj指向进程pi,它表示把一个单位的资源rj分配给进程pi。P1P2r1r2该图是由一组结点V和一组边E所组成的：G=（V，E），具有以下形式的定义和限制：（1）V被分为两个互斥的子集，一组进程结点P={p1,p2,…,pn},一组资源结点R={r1,r2,…rn},57.3.3产生死锁的原因产生死锁的根本原因是:⒈资源不足，引起资源竞争⒉进程推进顺序不合理6例:设有两个进程Pa和Pb,它们都需要使用系统内的打印机和输入机.它们的算法设计如下:设信号量s1代表输入机资源可用数量,s1=1设信号量s2代表打印机资源可用数量,s2=1Pa:P(s2)…P(s1)…V(s2)…V(s1)Pb:P(s1)…P(s2)…V(s1)…V(s2)77.3.4死锁产生的必要条件⑴互斥条件。进程要求对所分配的资源进行排他性使用，即在一段时间内某资源仅为一个进程所占用。⑵不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。⑶请求和保持条件。进程每次申请所需要的一部分资源，在等待新资源的同时，进程继续占有已分配到的资源。⑷循环等待条件。存在进程资源的循环等待链，链中的每一个进程已获得资源，同时被链中的下一个进程所请求。87.4预防死锁解决死锁问题的基本方法有：预防死锁、避免死锁、检测死锁和解除死锁。除此之外还有鸵鸟算法和综合措施。预防死锁是指通过某种策略来限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。就是在设计操作系统时，通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁，使系统能预先排除死锁的可能性。97.4.1摒弃请求和保持条件采用设备的静态预先分配办法,具体作法:作业调度程序在选择作业时,只选择那些系统能满足其运行时所需的全部资源的作业投入运行,并且在作业运行前,将其所需的全部资源一次性地分配给该作业.该方法的优点和缺点如下：①简单、安全、易于实现。②程序在运行之前很难提出将要使用的全部设备。③直到所有资源满足才能运行，实际上某些资源可能要到运行后期才会用到。④一个进程运行期间，对某些设备的使用时间很短，甚至不会用到。⑤作业的周转时间被加长,系统资源的使用率被降低107.4.2摒弃不剥夺条件为了破坏不可剥夺条件，我们采用这样的策略，一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源，以后需要时再重新申请。拥有资源的进程在运行过程中其资源可能被剥夺，从而破坏了不可剥夺条件。该方法实现复杂，被剥夺资源的进程前期工作失效，重复申请和释放资源给系统增加了开销，系统要付出很大的代价。117.4.3摒弃环路等待条件为了破坏环路等待条件，采用有序资源分配策略。对申请资源的进程规定：同类资源需一次申请，在获得资源后，只能申请较高级号的资源，无权申请低级号资源和同类资源。对于低级号资源和同类资源申请，必须先释放所有高级号的资源，然后再申请，否则不予分配。优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。缺点：进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费，系统增加新设备较困难。127.4.4摒弃互斥条件互斥条件是由于设备本身特性所决定的,不能简单的把其打破;只有通过改造设备特性实现.具体办法采用Spooling技术,把独占设备改造成共享设备来实现.137.5避免死锁死锁的避免是动态的预防措施,系统允许进程动态地申请资源,如果措施得当,可以使系统获得较为满意的系统性能.具体的办法是:系统为进程分配资源之前,首先对系统的安全性进行计算,如果为进程分配了所需资源后,系统仍处于安全状态,那么就把资源分配给该进程,反之则不为该进程分配资源.银行家算法:该问题是研究一个银行家如何将其总数一定的现金,安全的借给若干个顾客,使这些顾客既能满足对资金的要求又能完成其交易,也使银行家可以收回自己的资金不至于破产.147.5.1系统的安全状态和不安全状态安全状态:是指系统能按某种进程推进顺序(p1,p2,…pn),来为每个进程分配其所需资源,直至最大需求,使每个进程都能顺利完成其任务.只要系统存在这样的安全序列p1,p2,…pn,则系统处于安全状态.7.5.2安全状态的例子假定系统有三个进程p1,p2和p3,共有12台磁带机,进程p1、p2、p3分别要求10台、4台和9台，设在T0时刻p1、p2、p3已分别获得5台、2台和2台，尚有3台空闲磁带机未分配出去，分配情况如下所示：15进程最大需求已分配可用磁带机P11053P242P392经分析，在T0时刻系统是安全的，因为存在一个安全序列p2,p1,p3向不安全状态的转换若在T0时刻，p3请求1台磁带机，若满足其要求，则系统进入不安全状态。167.5.3利用银行家算法避免死锁⒈银行家算法中的数据结构①可利用资源向量Available(R1,R2…Rm)。它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。②最大需求矩阵Max。这是—个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]＝k，表示进程Pi需要Rj类资源的最大数目为k。③分配矩阵Allocation。这是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocation[i，j]＝k，表示进程Pi当前已分得Rj类资源的数目为k。④需求矩阵：Need。它是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数，如果Need[i，j]＝k，表示进程Pi还需要Rj类资源k个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i，j]=Max[i，j]-Allocation[i，j]17⒉银行家算法设Requesti（r1,r2,…rm)是进程Pi的请求向量。如果Requesti[j]＝k，表示进程Pi只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：①如果Requesti=Needi，则执行步骤②；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。②如果Requesti，=Availablei，则执行步骤③；否则，表示系统中尚无足够的资源，Pi等待。③系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：Available[j]=Available[j]-Requesti[j]；Allocation[i，j]=Allocation[i，j]+Requesti[j]；Need[i，j]=Need[i，j]-Requesti[j]；④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。18⒊安全性算法系统所执行的安全性算法可描述如下：①设置两个工作向量，工作向量Work。它含有m个元素，它表示系统可提供给进程继续运行所需要的各类资源数目，初值Work=Available。完成标志工作向量Finish。它含有n个元素，它表示系统是否有足够的资源分配给进程，使之运行完成，当有足够资源分配给进程时，Finish[i]=true，初值Finish[i]=false。②从进程集合中找到一个能满足下述条件的进程：Finish[i]=false；Needi=Work；如找到，执行步骤③；否则，执行步骤④。③当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，系统回收这些资源，故修改下面数据结构中的数值：Work[j]=Work[j]+Allocation[i，j]；Finish[i]=true；转步骤②。④如果所有进程的Finish[i]=true，则表示存在这样一个安全序列，系统处于安全状态；否则，系统处于不安全状态。19⒋银行家算法之例如表7-4所示T0时刻的资源分配表，假定系统中有五个进程{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7。20如表7-5所示，对T0时刻进行安全性检查，可以找到一个安全序列{P1，P3，P4，P2，P0}，系统是安全的。21⑴P1发出请求Request(1，0，2)，执行银行家算法。如表7-6所示，进行安全性检查，通过第一步和第二步检查，并找到一个安全序列{P1，P3，P4，P2，P0}，系统是安全的，可以分配P1的请求。2223⑵P4发出请求Request(3，3，0)，执行银行家算法。Available=(2，3，0)，不能通过第二步检查（Request[i]≤Available），所以P4等待。⑶P0请求资源，Request（0，2，0），执行银行家算法。进行安全性检查，通过第一步和第二步检查，如表7-7所示，Available{2，1，0}已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配。247.6检测死锁并解除死锁7.6.1鸵鸟算法7.6.1检测死锁（这是一种事后处理的措施）1、检测死锁的时机1）当进程等待时检测死锁2)定时检测3系统资源利用率下降时检测死锁252、利用资源分配图检测263、死锁定理1）、死锁定理：S为死锁状态的充分必要条件是当且仅当S状态的资源分配图是不可化简的。2）、资源分配图的化简原则：(1)在资源分配图中，找出一个既不阻塞又非独立的进程结点pi。在顺利情况下，pi可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全部资源。这相当于消去pi所有的请求边和分配边，使之成为孤立的结点。27（2）p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出它所占有的全部资源，而形成图（c)所示的情况。（3）、在进行一系列简化后，若能消去图中所有边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。28假定某系统当时的资源分配图如下所示：（1）分析当时系统是否存在死锁。（2）若进程P3再申请R3时，系统将发生什么变化，说明原因。294.死锁检测中的数据结构(1)可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。(2)把不占用资源的进程(向量Allocation∶=0)记