资源预览内容
第1页 / 共33页
第2页 / 共33页
第3页 / 共33页
第4页 / 共33页
第5页 / 共33页
第6页 / 共33页
第7页 / 共33页
第8页 / 共33页
第9页 / 共33页
第10页 / 共33页
亲,该文档总共33页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
3.5 死锁n在多道程序系统中,多个进程并发执行可改善 系统资源利用率,提高系统的吞吐量,但也有可 能发生一种危险-死锁。一、死锁的概念 例1:n两个小孩在一起玩耍,一个在玩皮球,另一 个玩自动步枪,如果这两个小孩都要对方手 中的玩具,而又不肯先放掉自己拿着的玩具 ,这时就发生了僵持局面。1n例2:系统有一台打印机和一台扫描仪,进程P1、P2 并发执行,在执行过程中均需使用打印机和扫描仪 。Cobegin Process P1() Process P2() Request(打印机) Request(扫描仪) Request(扫描仪) Request(打印机) Coendn当P1、P2并发执行时,可能出现如下序列:P1占用打印机, P2占用扫描仪。在以后某时刻P1又要申请扫描仪,但由于扫 描仪被P2占用,P1只有等待;P2又申请打印机,但由于打印 机被P1占用,P2只有等待。如此两进程均不能执行而处于永 远等待状态,这种现象称为死锁。21.死锁的定义n在一组进程中,每个进程都等待被该组进 程中其他进程所占有的资源,从而无限期 陷入僵持的局面,这种现象称为死锁。n如果死锁发生,会浪费大量系统资源,甚 至导致系统崩溃。2.产生死锁的原因n竞争资源n进程间推进顺序不当33.产生死锁的必要条件n1971年Coffman总结了系统产生死锁的四个 必要条件:n互斥条件:系统中存在临界资源,进程应互 斥地使用这些资源。n占有和等待条件:进程在请求资源得不到满 足而等待时,不释放已占有的资源。n不剥夺条件:进程已占有的资源只能由属主 释放,不能强行剥夺。n循环等待条件:存在循环等待链,链中的每 一个进程都在等待下一进程所持有的资源。 44.处理死锁的基本方法(1)死锁防止(deadlock prevention)n通过设置某些限制条件,去破坏死锁四个必 要条件中的一个或多个,来防止死锁。n较易实现,广泛使用,但由于所施加的限制 往往太严格,可能导致系统资源利用率和系 统吞吐量的降低。5(2)死锁避免n不事先采取限制措施去破坏产生死锁的条件 ,而是在资源的动态分配过程中,用某种方 法去防止系统进入不安全状态,从而避免死 锁的发生。n只需事先施加较弱的限制条件,可获得较高 的资源利用率和系统吞吐量,但在实现上有 一定难度。在较完善的系统中常用此方法。6(3)检测死锁n事先并不采取任何限制,允许死锁发生,但 可通过检测机构及时检测出死锁的发生,并 精确确定与死锁有关的进程和资源。(4)解除死锁n与检测死锁相配套,当检测到发生死锁时, 采用一定的方法解除死锁。n实现难度大,但可获得较好的资源利用率和 系统吞吐量。 7二、死锁防止n设法破坏产生死锁的四个必要条件之一。n条件1(互斥条件)是由设备的固有特性所决 定的,不仅不能改变,还应加以保证。8破坏条件2(占有和等待条件)n采用资源的静态分配策略。n静态分配是指进程必须在执行前一次性地申请所需 的全部资源,若系统有足够资源则完全分配。若分 配时只要有一种资源不能满足,则不分配任何资源 ,而让进程等待。优点:简单、易于实现且安全。 缺点:资源严重浪费,严重降低资源的利用率;使进程延迟运行。 9破坏条件3(不剥夺条件)n采用剥夺式调度方法。n占有资源的进程,再提出新资源请求时,若 有则分配,否则剥夺此进程已占有的所有的 资源,并让进城进入等待状态,资源充足后 再唤醒它重新申请所需资源。n实现复杂、要付出很大的代价。 10破坏条件4(循环等待条件)n资源按序分配:把系统中的所有资源编号,所有分 配请求必须以序号上升的次序进行。n例如:系统中有下列设备:输入机(1),打印机( 2),穿孔机(3),磁带机(4),磁盘(5)。有 一进程要先后使用输入机、磁盘、打印机,则它申 请设备时要按输入机、打印机、磁盘的顺序申请。n优点:同前两法相比,其资源利用率和系统吞吐量 有较明显的改善。n缺点:进程实际需要资源的顺序不一定与资源的编 号一致,因此仍会造成资源浪费。11三、死锁避免n各种死锁防止方法能够防止死锁发生,但 由于所加限制条件太严格,会导致系统资 源利用率和系统吞吐量的降低。n另一种解决死锁问题的方法称为避免死锁 。n避免死锁基本思想:把系统状态分为安全 状态和不安全状态,只要系统一直处于安 全状态即可避免死锁的发生。121.系统状态(1)安全状态n如果系统能按某种进程顺序(如P1,P2,,Pn) 为每个进程分配其所需的资源,直至所有进程都能 运行完成,此时称系统处于安全状态。进程序列 称为安全序列。 (2)不安全状态n若不存在这样一个安全序列称系统处于不安全状态 。n系统进入不安全状态后,就有可能进而进入死锁状 态,反之,只要系统处于安全状态,便可避免进入 死锁状态。 不安全状态 安全状态死锁 13例:有三个进程p1,p2,p3,有12台磁带机。P1共 要求10台,P2共要求4台,P3共要求9台。T0时刻:p1,p2,p3分别获得5、2、2台,尚有3台 空闲。系统状态见下图:进程最大需求已分配还需可用p110553 p2422 p3927T0时刻系统是否安全? 经分析,在T0时刻,系统是安全的。 因为存在一个安全序列p2、p1、p3。14nT1时刻:P3请求1台磁带机,若系统分给它一台, 分配后系统状态如下图。进程最大需求已分配还需可用p110552 p2422 p3936T1时刻系统的安全性? TI时刻系统进入不安全状态。因为找不到安全序列。 可见当P3申请资源时,尽管系统中有资源也不能分配。在资源动态分配过程中,若资源分配不当,就会使 系统由安全状态进入不安全状态。 15死锁避免实质:允许进程动态地申请资源,但系统在资源分配前先检查此次分配后系统的安全性, 若分配后系统仍处于安全状态,则将资源分 配给进程,否则不分配,令进程等待。162.银行家算法n最有代表性的避免死锁算法,由Dijkstra提出。n银行家算法u银行家拥有有限周转资金u客户要求分期贷款,如果客户能够得到各 期贷款,就一定能够归还贷款,否则就一定不 能归还贷款u银行家应谨慎的贷款,防止出现坏帐n用银行家算法避免死锁u操作系统(银行家)u操作系统管理的资源(周转资金)u进程(要求贷款的客户)17(1)银行家算法中的数据结构n考虑一个系统有n个进程(P1,P2,.,Pn)和m类资 源(r1,r2,rm) a.每类资源总数向量ResourceResource=(R1,R2,Rm) b.每类资源可用数向量AvilableAvilable=(V1,V2,Vm) c.最大需求矩阵Claim -每个进程对每类资源的最大 需求量,Cij表示进程Pi需r类资源最大数Claim =C11C12C1m C21 C22C2 mCn1 Cn1Cn m 18d.分配矩阵Allocation表示进程当前已分得的资源 数,Aij表示进程Pi已分到rj类资源的个数.Need=N11N12N1mN21N21N21Nn1Nn1Nnm e.需求矩阵Need 表示每个进程还需要各类资 源数。 Nij=Cij-AijAllocation=A11A12A1mA21A21A21An1An1Anm 19(2)银行家算法描述n基本思想:nRequesti是进程Pi的请求向量,当进程pi提出资源申请 时,系统执行下列步骤: a.若Requesti* Needi,*转(2);否则错误返回, 因为它所需要的资源已超过所宣布的最大值。 b.若Requesti* Available*转(3);否则表示尚无 足够资源,Pi需等待。 c.系统对Pi进程请求资源进行试探性分配,执行:Allocationi,*:=Allocationi,*+ Requesti*; Available * := Available * - Requesti*;Needi,*:= Needi,* - Requesti*; d.执行安全性测试算法,检查此次资源分配后系统是否安 全,若安全则分配完成,若不安全,则本次试探分配作 废,恢复原状态,进程Pi等待。20(3)安全性测试算法 a.定义工作向量currentavail、布尔型标志possible和进 程集合rest; b.初始化:rest设为全部进程, currentavail*= Available * ,possible=true; c.从进程集合rest找出满足下列条件的一个进程Pk:Needk,*Available(2,3,0) 由于可用资源不足,申请被系统拒绝,令进程P4等待。26(4)进程P0请求资源request0(0,2,0),系统按银行家算法检查: a.request0(0,2,0)Need0(7,4,3) b.request0(0,2,0) Available(2,3,0) c.系统进行试探性分配:修改相关数据。进程AllcationClaimNeedAvailable ABCABC1ABCABC P00 3 07 5 37 2 32 1 0 P13 0 2 3 2 20 2 0 P23 0 29 0 26 0 0 P32 1 12 2 20 1 1 P40 0 24 3 34 3 1d.进行安全性检查:可用资源Available(2,1,0)已 不能满足任何进程的需求,故系统处于不安全状态,不 能为P0分配资源。27n以上讨论的各种处理死锁的技术均是事先预 防的方法,保证系统不会发生死锁。n死锁的检测和解除技术允许死锁发生,操作 系统不断监视系统进展情况,判断死锁是否 发生,一旦死锁发生则采取专门的措施,解 除死锁并以最小的代价恢复操作系统运行。四、 死锁的检测和解除281.死锁的检测 (1)进程-资源分配图 用有向图描述系统状态,准确、形象方框表示一类资源,方框中的黑圆点表 示此类资源的个数。RjPi圆圈表示进程资源请求边,表示进程Pi申请Rj 类资源一个PiRjPiRj资源分配边,表示Rj类中的一个 资源已分配给进程Pi29例:R1R2PiPj30a.如果进程-资源分配图中无环路,则此时系统没有 发生死锁。b.如果进程-资源分配图中有环路,且每个资源类中 仅有一个资源,则系统中发生了死锁,此时,环路 是系统发生死锁的充要条件,环路中的进程便为死 锁进程。c.如果进程-资源分配图中有环路,且涉及的资源类 中有多个资源,则环路的存在只是产生死锁的必要 条件而不是充分条件。未必发生死锁。(2)死锁检测系统状态和资源分配图一一对应,可通过资源 分配图检测系统是否发生死锁。31进程-资源分配图化简n在进程-资源分配图中找出一个即不阻塞又非独立 的进程,消去此进程的所有请求边和分配边,成为 孤立结点。重复上述过程,经一系列简化,使所有 进程成为孤立结点,则该图是可完全简化的;否则 则称该图是不可完全简化的。死锁定理n系统为死锁状态的充分条件是:当且仅当该状态的 进程-资源分配图是不可完全简化的。该充分条件 称为死锁定理。32二、死锁的解除n结束所有进程的执行,重新启动操作系统。方法简单,但以 前工作全部作废,损失很大。n撤销陷于死锁的所有进程,解除死锁继续运行。n逐个撤销陷于死锁
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号