第四章 处理机调度与死锁(续)课件.ppt
《第四章 处理机调度与死锁(续)课件.ppt》由会员分享,可在线阅读,更多相关《第四章 处理机调度与死锁(续)课件.ppt(69页珍藏版)》请在三一办公上搜索。
1、第四章(续) 死锁,死锁的基本概念死锁的解决方案 (预防,避免,检测及解除)资源分配图,死锁的现象,一、死锁的基本概念,1.死锁的定义 一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程,死锁(Deadlock)饥饿(Starvation),参与死锁的进程最少是两个 (两个以上进程才会出现死锁)参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注:如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃,关于死锁的一些结论,2. 产生死锁的原因,1、争夺资源引起
2、死锁 例1:P1,P2两个进程争夺打印机和读卡机。,P1,P2,打印机, P1已经申请到打印机, 又申请读卡机。 P2已经申请到读卡机, 又申请打印机。,打印机和读卡机为非剥夺性资源。,读卡机,例2、 P1,P2,P3 三个进程之间通信: P1产生消息S1,接收P3产生的消息S3; P2产生消息S2,接收P1产生的消息S1; P3产生消息S3,接收P2产生的消息S2;,按以下次序运行:P1:Request(S3);Release(S1)P2:Request(S1);Release(S2)P3:Request(S2);Release(S3),2、进程推动顺序不当引起的死锁,P1,P3,S2,S3
3、,S1,P1,P2,P3,按照以上的顺序执行会产生死锁吗?,Si临时性资源,获得A,获得B,获得A,获得B,释放A,释放B,释放B,释放A,P请求A,P请求B,Q请求A,Q请求B,死锁区,P,Q都申请A,P,Q都申请B,资源,永久性资源:可以被多个进程多次使用(可再用资源)* 可抢占资源不可抢占资源临时性资源:只可使用一次的资源;如信号量,中断信号,同步信号等(可消耗性资源)“申请-分配-使用-释放”模式,3. 产生死锁的四个必要条件,互斥使用(资源独占)不可强占(不可剥夺)请求和保持(部分分配,占有申请)循环等待,1) 互斥使用(资源独占)一个资源每次只能给一个进程使用2) 不可强占(不可剥
4、夺) 资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放,3) 请求和保持(部分分配,占有申请)一个进程在申请新的资源的同时保持对原有资源的占有(只有这样才是动态申请,动态分配),4) 循环等待 存在一个进程等待队列 P1 , P2 , , Pn, 其中P1等待P2占有的资源,P2等待P3占有的资源,Pn等待P1占有的资源,形成一个进程等待环路,二、死锁的解决方案,1. 产生死锁的例子 申请不同类型资源产生死锁,P1:申请打印机申请扫描仪使用释放打印机释放扫描仪,P2:申请扫描仪申请打印机使用释放打印机释放扫描仪,申请同类资源产生死锁(如内存) 设有资源R,R有m个分配单位
5、,由n个进程P1,P2,Pn(n m)共享。假设每个进程对R的申请和释放符合下列原则: * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放,m=2,n=3资源分配不当导致死锁产生,2. 解决死锁的方法,鸵鸟策略 不理睬死锁。从工程角度考虑死锁概率及解决的代价预防策略 破坏死锁的四个必要条件之一避免策略 采用某种算法判断资源申请是否满足,以动态地回避死锁检测和解除 检测出发生的死锁并采取措施予以解除,3. 死锁预防,定义: 在系统设计时确定资源分配算法,保证不发生死锁 具体的做法是破坏产生死锁的四个必要条件之一,死锁预防,破坏“不可剥夺”条件 在允许进程动态申请资源前提下
6、规定,一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请,破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配,死锁预防,破坏“循环等待”条件 采用资源有序分配法: 把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配,死锁预防,如何证明按资源有序分配法进行分配肯定不会产生死锁?,i j 表示:资源 Ri 先于资源 Rj假设进程A和B处于死锁状态,因为A已经拥有了Ri并申请Rj;同时B已经拥有了Rj并申请Ri。即:PA: Ri Rj
7、即有 i jPB: Rj Ri 即有 j i,破坏“循环等待”条件,回顾,进程调度调度算法死锁预防破环必要条件,4. 死锁避免,允许死锁前三个条件的成立,但作一定的判断选择以确保永远不会达到死锁点采用某种算法动态判断当前资源分配请求是否有可能导致死锁,如可能导致死锁,则拒绝本次资源申请要求或是中止该进程的运行,死锁避免定义,定义: 在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统可能发生死锁,则不予分配,否则予以分配死锁避免和死锁预防的区别?,安全状态与不安全状态,安全状态: 如果存在一个由系统中所有进程构成的安全序列P1,P
8、n,则系统处于安全状态,死锁避免,安全序列: 一个进程序列P1,Pn是安全的,如果对于每一个进程Pi(1in),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和,系统处于安全状态 (安全状态一定是没有死锁发生的),安全状态与不安全状态,不安全状态:不存在一个安全序列,不安全状态可能导致死锁,目前占有量,最大需求量,尚需要量,P1,5,10,5,P2,2,4,2,P3,2,9,7,系统剩余量,3,共有12台磁带机 T0时刻分配情况如下:,T0时刻是否安全?如果此时P3又请求一台磁带机,又是否安全?,银行家算法,n:系统中进程的总数m:资源类总数Avail
9、able: ARRAY1.m of integer;Max: ARRAY1.n,1.m of integer;,银行家算法,Allocation: ARRAY1.n,1.m of integer;Need: ARRAY1.n,1.m of integer;Request: ARRAY1.n,1.m of integer;,银行家算法,简记符号:AvailableMaxiAllocationiNeediRequesti,必须满足的关系,1、资源总数 = 可用资源数 + 已分配资源数Ri = Available + Allocationi2、申请量不能超过需求量Requesti= Needi3、已
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四章 处理机调度与死锁续课件 第四 处理机 调度 死锁 课件
链接地址:https://www.31ppt.com/p-1825708.html