linux处理机调度与死锁2

1、linux处理机调度与死锁2S2P1S3P3S1P2图 7-1 进程之间通信时的死锁 n死锁的定义:死锁是一组并发进程,它们共享系统的某些资源,该组进程中每个进程都已经占有了部分资源,但都在不释放自己占有资源的情况下要求获得被其它进程已经占有的资源,从而造成它们相互等待,永远不能继续推进的状态.n说明：n参与死锁的进程最少是两个（两个以上进程才会出现死锁）。n参与死锁的进程至少有两个已经占有资源。n参与死锁的所有进程都在等待事件。n参与死锁的进程是当前系统中所有进程的子集。7.3.2 资源分配图(2) 凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi, rj是资源请求边

2、，由进程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,7.3.3 产生死锁的原因 n产生死锁的根本原因是:n资源不足，引起资源竞争n进程推进顺序不合理例:设有两个进程Pa和Pb,它们都需要使用系统内的打印机和输入机.它们的算法设计如下:设信号量s1代表输入机资源可用数量,s1=1设信号量s2代表

3、打印机资源可用数量,s2=1Pa:P(s2)P(s1)V(s2)V(s1)Pb:P(s1)P(s2)V(s1)V(s2)7.3.4 死锁产生的必要条件n互斥条件。进程要求对所分配的资源进行排他性使用，即在一段时间内某资源仅为一个进程所占用。n不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。n请求和保持条件。进程每次申请所需要的一部分资源，在等待新资源的同时，进程继续占有已分配到的资源。n循环等待条件。存在进程资源的循环等待链，链中的每一个进程已获得资源，同时被链中的下一个进程所请求。7.4 预防死锁n解决死锁问题的基本方法有：预防死锁、

4、避免死锁、检测死锁和解除死锁。除此之外还有鸵鸟算法和综合措施。n预防死锁是指通过某种策略来限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。n就是在设计操作系统时，通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁，使系统能预先排除死锁的可能性。 摒弃请求和保持条件n采用设备的静态预先分配办法,具体作法:作业调度程序在选择作业时,只选择那些系统能满足其运行时所需的全部资源的作业投入运行,并且在作业运行前,将其所需的全部资源一次性地分配给该作业.n该方法的优点和缺点如下：n简单、安全、易于实现。n程序在运行之前很难提出将要使用的全部设备。n直到所有资源满足才能

5、运行，实际上某些资源可能要到运行后期才会用到。n一个进程运行期间，对某些设备的使用时间很短，甚至不会用到。n作业的周转时间被加长,系统资源的使用率被降低摒弃不剥夺条件n为了破坏不可剥夺条件，我们采用这样的策略，一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源，以后需要时再重新申请。拥有资源的进程在运行过程中其资源可能被剥夺，从而破坏了不可剥夺条件。该方法实现复杂，被剥夺资源的进程前期工作失效，重复申请和释放资源给系统增加了开销，系统要付出很大的代价。摒弃环路等待条件n为了破坏环路等待条件，采用有序资源分配策略。 n对申请资源的进程规定：同类资源需一次

6、申请，在获得资源后，只能申请较高级号的资源，无权申请低级号资源和同类资源。对于低级号资源和同类资源申请，必须先释放所有高级号的资源，然后再申请，否则不予分配。n优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。n缺点：进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费，系统增加新设备较困难。摒弃互斥条件n互斥条件是由于设备本身特性所决定的,不能简单的把其打破;只有通过改造设备特性实现.具体办法采用Spooling技术,把独占设备改造成共享设备来实现.7.5 避免死锁n死锁的避免是动态的预防措施,系统允许进程动态地申请资源,如果措施得当,可以使系统获得较为满意的系统性能

7、.n具体的办法是:系统为进程分配资源之前,首先对系统的安全性进行计算,如果为进程分配了所需资源后,系统仍处于安全状态,那么就把资源分配给该进程,反之则不为该进程分配资源.n银行家算法:该问题是研究一个银行家如何将其总数一定的现金,安全的借给若干个顾客,使这些顾客既能满足对资金的要求又能完成其交易,也使银行家可以收回自己的资金不至于破产.n系统的安全状态和不安全状态 n安全状态:是指系统能按某种进程推进顺序(p1,p2,pn),来为每个进程分配其所需资源,直至最大需求,使每个进程都能顺利完成其任务.只要系统存在这样的安全序列,则系统处于安全状态.n安全状态的例子 n假定系统有三个进程p1,p2和

8、p3,共有12台磁带机,进程p1、p2、p3分别要求10台、4台和9台，设在T0时刻p1、p2、p3已分别获得5台、2台和2台，尚有3台空闲磁带机未分配出去，分配情况如下所示：进程最大需求已分配可用磁带机P11053P242P392n经分析，在T0时刻系统是安全的，因为存在一个安全序列n向不安全状态的转换n若在T0时刻，p3请求1台磁带机，若满足其要求，则系统进入不安全状态。7.5.3 利用银行家算法避免死锁n银行家算法中的数据结构n可利用资源向量Available(R1,R2Rm)。它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源

9、数目。其数值随该类资源的分配和回收而动态地改变。n最大需求矩阵Max。这是个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，jk，表示进程Pi需要Rj类资源的最大数目为k。n分配矩阵Allocation。这是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocationi，jk，表示进程Pi当前已分得Rj类资源的数目为k。n需求矩阵：Need。它是一个nm的矩阵，用以表示每一个进程尚需的各类资源数，如果Needi，jk，表示进程Pi还需要Rj类资源k个，方能完成其任务。n上述三个矩阵间存在下述关系：nNeedi，j=Maxi，

10、j-Allocationi，jn银行家算法n设Requesti（r1,r2,rm)是进程Pi的请求向量。如果Requestijk，表示进程Pi只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：n如果Requesti=Needi，则执行步骤；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。n如果Requesti，=Availablei，则执行步骤；否则，表示系统中尚无足够的资源，Pi等待。n系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：nAvailablej=Availablej-Requestij；nAllocationi，j=Allocat

11、ioni，j+Requestij；nNeedi，j=Needi，j-Requestij；n系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。n安全性算法n系统所执行的安全性算法可描述如下：n设置两个工作向量，工作向量Work。它含有m个元素，它表示系统可提供给进程继续运行所需要的各类资源数目，初值Work=Available。n完成标志工作向量Finish。它含有n个元素，它表示系统是否有足够的资源分配给进程，使之运行完成，当有足够资源分配给进程时，Finishi=tr

12、ue，初值Finishi=false。n从进程集合中找到一个能满足下述条件的进程：nFinishi=false；nNeedi=Work；n如找到，执行步骤；否则，执行步骤。n当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，系统回收这些资源，故修改下面数据结构中的数值：nWorkj=Workj+Allocationi，j；nFinishi=true；n转步骤。n如果所有进程的Finishi=true ，则表示存在这样一个安全序列，系统处于安全状态；否则，系统处于不安全状态。银行家算法之例n如表7-4所示T0时刻的资源分配表，假定系统中有五个进程P0，P1，P2，P3，P4和三

13、种类型的资源A，B，C，每一种资源的数量分别为10、5、7。 如表7-5所示，对T0时刻进行安全性检查，可以找到一个安全序列P1，P3，P4，P2，P0，系统是安全的。 nP1发出请求Request(1，0，2)，执行银行家算法。n如表7-6所示，进行安全性检查，通过第一步和第二步检查，并找到一个安全序列P1，P3，P4，P2，P0，系统是安全的，可以分配P1的请求。nP4发出请求Request(3，3，0)，执行银行家算法。nAvailable=(2，3，0)，不能通过第二步检查（RequestiAvailable），所以P4等待。nP0请求资源，Request（0，2，0），执行银行家算法

14、。n进行安全性检查，通过第一步和第二步检查，如表7-7所示，Available2，1，0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配。7.6 检测死锁并解除死锁7.6.1 检测死锁（这是一种事后处理的措施）n具体方法是：n1、判断是否构成环路条件n采用有限状态转移图法2、周期性检测方法：类似银行家算法死锁定理 n1、死锁定理：S为死锁状态的充分必要条件是当且仅当S状态的资源分配图是不可化简的。n2、资源分配图的化简原则：n(1)在资源分配图中，找出一个既不阻塞又非独立的进程结点pi。在顺利情况下，pi可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全部资源。这相当

15、于消去pi所有的请求边和分配边，使之成为孤立的结点。n（2）p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出它所占有的全部资源，而形成图（c)所示的情况。n（3）、在进行一系列简化后，若能消去图中所有边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。假定某系统当时的资源分配图如下所示：（1）分析当时系统是否存在死锁。（2）若进程P3 再申请R3 时，系统将发生什么变化，说明原因。3. 3. 死锁检测中的数据结构死锁检测中的数据结构 (1) 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目

16、。 (2) 把不占用资源的进程(向量Allocation=0)记入L表中， 即LiL。 (3) 从进程集合中找到一个RequestiWork的进程，做如下处理： 将其资源分配图简化，释放出资源，增加工作向量Work=Work+Allocationi。 将它记入L表中。 (4) 若不能把所有进程都记入L表中， 便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。 Work =Available; L =Li|Allocationi=0Requesti=0 for all Li L do begin for all RequestiWork do begin Work =W

17、ork+Allocationi; LiL; end end deadlock = (L=p1, p2, , pn); 7.6.3 解除死锁n方法如下：n系统重新启动。n撤消所有死锁进程n退回到前一检查点并从此点重新启动进程.n逐个撤消死锁进程,直到死锁不存在n逐个抢占死锁进程资源直到死锁不存在7.6.4 处理死锁的综合措施n较理想的处理死锁综合措施如下：n内部资源：系统本身使用的资源。如I/O通道、进程控制块，设备控制块，系统保留区等。对内部资源通过破坏循环等待条件，即对此类资源使用有序资源分配法预防死锁。n内存资源：可以按帧或段分配给进程的存储空间。对内存实行可剥夺式方法预防死锁是最适合的策

18、略。当一个进程被剥夺后，它仅仅被换到外存，释放空间以解决死锁。n进程资源：用于进程的可分配设备，如打印机、文件等。对这类资源，死锁避免策略常常是很有效的，这是因为进程可以事先声明他们将需要的这类资源。也可以采用有序资源分配法预防策略。n交换空间：进程交换所使用的外存交换区。通过要求一次性分配所有请求的资源来预防死锁。也可以采用死锁避免措施。n复习思考题复习思考题n一 选择题n1.银行家算法是一种算法。nA.死锁解除 B死锁避免 C.死锁预防 D死锁检测n2.在下列解决死锁的方法中，属于死锁预防策略的是。nA.银行家算法 B.资源有序分配法nC.死锁检测法 D.资源分配图化简法n3.在为多道程序

19、所提供的可共享的系统资源不足时，可能出现死锁。但是，不适当的也可能产生死锁。nA.进程优先权 B.资源的线性分配 C.进程推进顺序 D.分配队列优先权n4.采用资源剥夺法可解除死锁，还可以采用方法解除死锁。nA.执行并行操作 B.撤消进程 C.拒绝分配新资源 D.修改信号量n5.资源的按序分配可以破坏条件。nA.互斥使用资源 B.占有且等待资源nC.非抢夺资源 D.循环等待资源n6.在的情况下，系统出现死锁。nA.计算机系统发生了重大故障nB.有多个封锁的进程同进存在nC.若干进程因竞争资源而无休止地相互等待他方释放已占有的资源nD.资源数大大小于进程数或进程同时申请的资源大大超过资源总数n7.产生死锁的四个必