linux处理机调度与死锁.ppt

7.3 死锁的概念 n7.3.1死锁的定义 n可重用资源(reusable resource):各个进程可以轮 流使用，如处理机、内存、I/0外设、文件等都是可 重用资源，在使用可重用资源时可能出现的死锁（ Deadlock）。通常是由于各进程巳拥有部分资源，同 时请求其他进程已占有的资源，从而造成永远等待 。 n可消耗资源(consumableresource):是指可以动态生 成和动态消耗的资源，一般不限制数量，如中断、 信号量、消息、缓冲区等都是可消耗资源。由于可 消耗资源的生成和消耗存在依赖关系，因此他们的 使用也可能因为双方都等待对方生成资源而形成死 锁。 1 图 7-1 进程之间通信时的死锁 2 n死锁的定义:死锁是一组并发进程,它们共享系统的 某些资源,该组进程中每个进程都已经占有了部分资 源,但都在不释放自己占有资源的情况下要求获得被 其它进程已经占有的资源,从而造成它们相互等待, 永远不能继续推进的状态. n说明： n参与死锁的进程最少是两个（两个以上进程才会 出现死锁）。 n参与死锁的进程至少有两个已经占有资源。 n参与死锁的所有进程都在等待事件。 n参与死锁的进程是当前系统中所有进程的子集。 3 7.3.2 资源分配图 (2) 凡属于E中的一个边eE，都连接着P中的一个结点和 R中的一个结点，e=pi, rj是资源请求边，由进程pi 指向资源rj， 它表示进程pi请求一个单位的rj资源。 e=rj, pi是资源分配边，由资源rj指向进程pi, 它表 示把一个单位的资源rj分配给进程pi。 该图是由一组结点V和一组边E所组成的： G=（V，E），具有以下形式的定义和限制： （1）V被分为两个互斥的子集，一组进程 结点P=p1,p2,pn,一组资源结点 R=r1,r2,rn, 4 7.3.3 产生死锁的原因 n产生死锁的根本原因是: n资源不足，引起资源竞争 n进程推进顺序不合理 5 例:设有两个进程Pa和Pb,它们都需要使用系统内的 打印机和输入机.它们的算法设计如下: 设信号量s1代表输入机资源可用数量,s1=1 设信号量s2代表打印机资源可用数量,s2=1 Pa: P(s2) P(s1) V(s2) V(s1) Pb: P(s1) P(s2) V(s1) V(s2) 6 7.3.4 死锁产生的必要条件 n互斥条件。进程要求对所分配的资源进行排他 性使用，即在一段时间内某资源仅为一个进程所 占用。 n不剥夺条件。进程所获得的资源在未使用完毕 之前，不能被其他进程强行夺走，即只能由获得 该资源的进程自己来释放。 n请求和保持条件。进程每次申请所需要的一部 分资源，在等待新资源的同时，进程继续占有已 分配到的资源。 n循环等待条件。存在进程资源的循环等待链， 链中的每一个进程已获得资源，同时被链中的下 一个进程所请求。 7 7.4 预防死锁 n解决死锁问题的基本方法有：预防死锁、避免 死锁、检测死锁和解除死锁。除此之外还有鸵 鸟算法和综合措施。 n预防死锁是指通过某种策略来限制并发进程对 资源的请求，使系统在任何时刻都不满足死锁 的必要条件。 n就是在设计操作系统时，通过设置某些限制条 件，去破坏死锁四个必要条件中的一个或多个 ，来防止死锁，使系统能预先排除死锁的可能 性。 8 7.4.1摒弃请求和保持条件 n采用设备的静态预先分配办法,具体作法:作业调度程序 在选择作业时,只选择那些系统能满足其运行时所需的 全部资源的作业投入运行,并且在作业运行前,将其所需 的全部资源一次性地分配给该作业. n该方法的优点和缺点如下： n简单、安全、易于实现。 n程序在运行之前很难提出将要使用的全部设备。 n直到所有资源满足才能运行，实际上某些资源可能要 到运行后期才会用到。 n一个进程运行期间，对某些设备的使用时间很短，甚 至不会用到。 n作业的周转时间被加长,系统资源的使用率被降低 9 7.4.2摒弃不剥夺条件 n为了破坏不可剥夺条件，我们采用这样的策略，一 个已拥有资源的进程，若它再提出新资源要求而不 能立即得到满足时，它必须释放已经拥有的所有资 源，以后需要时再重新申请。拥有资源的进程在运 行过程中其资源可能被剥夺，从而破坏了不可剥夺 条件。该方法实现复杂，被剥夺资源的进程前期工 作失效，重复申请和释放资源给系统增加了开销， 系统要付出很大的代价。 10 7.4.3摒弃环路等待条件 n为了破坏环路等待条件，采用有序资源分配策略。 n对申请资源的进程规定：同类资源需一次申请，在获得 资源后，只能申请较高级号的资源，无权申请低级号资 源和同类资源。对于低级号资源和同类资源申请，必须 先释放所有高级号的资源，然后再申请，否则不予分配 。 n优点：同前两法相比，其资源利用率和系统吞吐量有较 明显的改善。 n缺点：进程实际需要资源的顺序不一定与资源的编号一 致，因此仍会造成资源浪费，系统增加新设备较困难。 11 7.4.4摒弃互斥条件 n互斥条件是由于设备本身特性所决定的,不能 简单的把其打破;只有通过改造设备特性实现. 具体办法采用Spooling技术,把独占设备改造成 共享设备来实现. 12 7.5 避免死锁 n死锁的避免是动态的预防措施,系统允许进程动态地 申请资源,如果措施得当,可以使系统获得较为满意的 系统性能. n具体的办法是:系统为进程分配资源之前,首先对系统 的安全性进行计算,如果为进程分配了所需资源后,系 统仍处于安全状态,那么就把资源分配给该进程,反之 则不为该进程分配资源. n银行家算法:该问题是研究一个银行家如何将其总数 一定的现金,安全的借给若干个顾客,使这些顾客既能 满足对资金的要求又能完成其交易,也使银行家可以 收回自己的资金不至于破产. 13 n7.5.1系统的安全状态和不安全状态 n安全状态:是指系统能按某种进程推进顺序 (p1,p2,pn),来为每个进程分配其所需资源,直至 最大需求,使每个进程都能顺利完成其任务.只要系 统存在这样的安全序列,则系统处于安 全状态. n7.5.2安全状态的例子 n假定系统有三个进程p1,p2和p3,共有12台磁带机,进 程p1、p2、p3分别要求10台、4台和9台，设在T0时 刻p1、p2、p3已分别获得5台、2台和2台，尚有3台 空闲磁带机未分配出去，分配情况如下所示： 14 进程最大需求已分配可用磁带机 P11053 P242 P392 n经分析，在T0时刻系统是安全的，因为存在一个 安全序列 n向不安全状态的转换 n若在T0时刻，p3请求1台磁带机，若满足其要求 ，则系统进入不安全状态。 15 7.5.3 利用银行家算法避免死锁 n银行家算法中的数据结构 n可利用资源向量Available(R1,R2Rm)。它是一个含有m个元 素的数组，其中的每一个元素代表一类可利用的资源数目，其初 始值是系统中所配置的该类全部可用资源数目。其数值随该类资 源的分配和回收而动态地改变。 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，j-Allocationi，j 16 n银行家算法 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=Allocationi，j+Requestij； nNeedi，j=Needi，j-Requestij； n系统执行安全性算法，检查此次资源分配后，系统是否处于 安全状态。若安全，才正式将资源分配给进程Pi，以完成本次 分配；否则，将试探分配作废，恢复原来的资源分配状态，让 进程Pi等待。 17 n安全性算法 n系统所执行的安全性算法可描述如下： n设置两个工作向量，工作向量Work。它含有m个元素，它表示 系统可提供给进程继续运行所需要的各类资源数目，初值 Work=Available。 n完成标志工作向量Finish。它含有n个元素，它表示系统是否有 足够的资源分配给进程，使之运行完成，当有足够资源分配给进 程时，Finishi=true，初值Finishi=false。 n从进程集合中找到一个能满足下述条件的进程： nFinishi=false； nNeedi=Work； n如找到，执行步骤；否则，执行步骤。 n当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配 给它的资源，系统回收这些资源，故修改下面数据结构中的数值 ： nWorkj=Workj+Allocationi，j； nFinishi=true； n转步骤。 n如果所有进程的Finishi=true ，则表示存在这样一个安全 序列，系统处于安全状态；否则，系统处于不安全状态。 18 银行家算法之例 n如表7-4所示T0时刻的资源分配表，假定系统中有五个进程 P0，P1，P2，P3，P4和三种类型的资源A，B，C，每 一种资源的数量分别为10、5、7。 19 如表7-5所示，对T0时刻进行安全性检查，可以找到一个安全序 列P1，P3，P4，P2，P0，系统是安全的。 20 nP1发出请求Request(1，0，2)，执行银行家算法。 n如表7-6所示，进行安全性检查，通过第一步和第二步检查 ，并找到一个安全序列P1，P3，P4，P2，P0，系统是安 全的，可以分配P1的请求。 21 22 nP4发出请求Request(3，3，0)，执行银行家算法。 nAvailable=(2，3，0)，不能通过第二步检查（RequestiAvailable），所 以P4等待。 nP0请求资源，Request（0，2，0），执行银行家算法。 n进行安全性检查，通过第一步和第二步检查，如表7-7所示，Available2 ，1，0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求 不能分配。 23 7.6 检测死锁并解除死锁 7.6.1 检测死锁（这是一种事后处理的措施） n具体方法是： n1、判断是否构成环路条件 n采用有限状态转移图法 2、周期性检测方法：类似银行家算法 24 死锁定理 n1、死锁定理：S为死锁状态的充分必要条件是当且仅当S状 态的资源分配图是不可化简的。 n2、资源分配图的化简原则： n(1)在资源分配图中，找出一个既不阻塞又非独立的进程结 点pi。在顺利情况下，pi可获得所需资源而继续执行，直至 运行完毕，再释放其所占有的全部资源。这相当于消去pi所 有的请求边和分配边，使之成为孤立的结点。 25 n（2）p1释放资源后，便可使p2获得资源而继续运行，直到 p2完成后又释放出它所占有的全部资源，而形成图（c)所示 的情况。 n（3）、在进行一系列简化后，若能消去图中所有边，使所 有进程都成为孤立结点，则称该图是可完全简化的；若不能 通过任何过程使该图完全简化，则称该图是不可完全简化的 。 26 假定某系统当时的资源分配图如下所示： （1）分析当时系统是否存在死锁。 （2）若进程P3 再申请R3 时，系统将发生什么变化，说明原因。 27 3. 死锁检测中的数据结构 (1) 可利用资源向量Available，它表示了m类资源中每 一类资源的可用数目。 (2) 把不占用资源的进程(向量Allocation=0)记入L 表中， 即LiL。 (3) 从进程集合中找到一个RequestiWork的进程，做 如下处理： 将其资源分配图简化，释放出资源，增加 工作向量Work=Work+Allocationi。 将它记入L表 中。 28 (4) 若不能把所有进程都记入L表中， 便表明系统状态S的资 源分配图是不可完全简化的。 因此，该系统状态将发生死锁 。 Work =Available; L = Li|Allocationi=0Requesti=0 for all Li L do begin for all RequestiWork do begin Work =Work+Allocationi; LiL; end end deadlock = (L=p1, p2, , pn); 29 7.6.3 解除死锁 n方法如下： n系统重新启动。 n撤消所有死锁进程 n退回到前一检查点并从此点重新启动进程. n逐个撤消死锁进程,直到死锁不存在 n逐个抢占死锁进程资源直到死锁不存在 30 7.6.4 处理死锁的综合措施 n较理想的处理死锁综合措施如下： n内部资源：系统本身使用的资源。如I/O通道、进程 控制块，设备控制块，系统保留区等。对内部资源通过 破坏循环等待条件，即对此类资源使用有序资源分配法 预防死锁。 n内存资源：可以按帧或段分配给进程的存储空间。对 内存实行可剥夺式方法预防死锁是最适合的策略。当一 个进程被剥夺后，它仅仅被换到外存，释放空间以解决 死锁。 n进程资源：用于进程的可分配设备，如打印机、文件 等。对这类资源，死锁避免策略常常是很有效的，这是 因为进程可以事先声明他们将需要的这类资源。也可以 采用有序资源分配法预防策略。 n交换空间：进程交换所使用的外存交换区。通过要求 一次性分配所有请求的资源来预防死锁。也可以采用死 锁避免措施。 31 n复习思考题 n一 选择题 n1.银行家算法是一种算法。 nA.死锁解除 B死锁避免 C.死锁预防 D死锁检测 n2.在下列解决死锁的方法中，属于死锁预防策略的是。 nA.银行家算法 B.资源有序分配法 nC.死锁检测法 D.资源分配图化简法 n3.在为多道程序所提供的可共享的系统资源不足时，可能出现死锁。但是 ，不适当的也可能产生死锁。 nA.进程优先权 B.资源的线性分配 C.进程推进顺序 D.分配队列优先权 n4.采用资源剥夺法可解除死锁，还可以采用方法解除死锁。 nA.执行并行操作 B.撤消进程 C.拒绝分配新资源 D.修改信号量 n5.资源的按序分配可以破坏条件。 nA.互斥使用资源 B.占有且等待资源 nC.非抢夺资源 D.循环等待资源 32 n6.在的情况下，系统出现死锁。 nA.计算机系统发生了重大故障 nB.有多个封锁的进程同进存在 nC.若干进程因竞争资源而无休止地相互等待他方释放已占有的资源 nD.资源数大大小于进程数或进程同时申请的资源大大超过资源总数 n7.产生死锁的四个必要条件是：互斥、循环等待和不剥夺。 nA.请求与阻塞 B.请求与保持 C.请求与释放 D.释放与阻塞 n8.在分时操作系统中，进程调度经常采用算法。 nA.先来先服务 B.最高优先权 C.时间片轮转 D.随机 n