《操作系统习题chapter 05》由会员分享，可在线阅读，更多相关《操作系统习题chapter 05（70页珍藏版）》请在金锄头文库上搜索。
1、第五章 死锁与饥饿 死锁的概念 死锁的条件 死锁的处理 资源分配图 死锁的预防 死锁的避免 死锁的发现 死锁的恢复 饥饿与活锁年 操作系统 09级网络1、2班学习目标 1.掌握死锁的定义,死锁的条件，死锁的处理 以及处理死锁的算法银行家算法。 2.理解资源分配图。 学习要点 本章的重点在于掌握死锁的处理方法，会用 银行家算法计算是否发生死锁。年 操作系统 09级网络1、2班第五章 死锁与饥饿 一个进程需要使用独占型资源必须有一定的次序： 申请资源 使用资源 释放资源 1968年Havender在评论OS/360操作系统时说：“ 原先多任务的概念是让多个任务不加限制的竞争资源，但是随着系统的发展
2、，很多任务被锁在系统中 了。” 1971年Lynch说：“1962年我们设计Exec2系统时并 没有认识到死锁的问题，系统中也没有任何防范措施，结果现在一些程序中已被锁在系统中了。”年 操作系统 09级网络1、2班死锁产生的原因和必要条件死锁现象年 操作系统 09级网络1、2班5.1 死锁产生的原因1、进程推进顺序不当产生死锁。设系统有打印机、读卡机各一台，它们被进程P和Q共享 。两个进程并发执行，它们按下列次序请求和释放资源 ：进程P 进程Q请求读卡机 请求打印机请求打印机 请求读卡机释放读卡机 释放读卡机释放打印机 释放打印机年 操作系统 09级网络1、2班例2： R1和R2为可再用资源;
3、进程Q1和Q2共享两个资源R1 和R2。s1和s2分别代表资源R1和R2能否被使用的信号量，由 于R1和R2是共享的，必须使用互斥。因而s1和s2的初值为1 。假定两个进程都要求使用两个资源，它们的程序如下： 进程Q1：P(s1)P(s2)使用R1和R2V(s1)V(s2)进程Q2：P(s2)P(s1)使用R1和R2V(s2)V(s1)5.1 死锁产生的原因2、PV操作使用不当产生死锁年 操作系统 09级网络1、2班5.1 死锁产生的原因3、同类资源分配不当引起死锁 若系统中有m个资源被n个进程共享，当每个进 程都要求k个资源。而m；说一个进程 序列 是安全的, 如果对于每一个进程 pi(1i
4、n), 它以后尚需要的资源数量不超过系统当前剩 余资源数量与所有进程pj(jp1请求：Request1=(1,0,2)年 操作系统 09级网络1、2班年 操作系统 09级网络1、2班(2) (2) P P1 1请求资源请求资源：P1发出请求向量Request(1，0，2)，系统按银行家算法进行检查： Request(1, 0, 2)Need(1, 2, 2) Request(1, 0, 2)Available(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量 再利用安全性算法检查此时系统是否安全。 年 操作系统 09级网络1、2班
5、银行家算法例子Claim Allocation Need Available Work Finish A B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 2 3 0 3 2 2 3 0 2 0 2 0 9 0 2 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3 1 P0: p1: p2: p3: p4:假定分配：安全进程序列： p4请求：Request4=(3,3,0), 能否满足？ p0请求：Request0=(0,2,0), 能否满足？ 年 操作系统 09级网络1、2班(3) (3) p4请求资源请求资
6、源： p4发出请求向量Request(3，3，0)，系统按银行家算法进行检查： Request(3, 3, 0)Need(4, 3, 1); Request(3, 3, 0) Available(2, 3, 0)，让p4等待。 (4) (4) p0请求资源请求资源： p0发出请求向量Requst(0，2，0)，系统按银行家算法进行检查： Request(0, 2, 0)Need(7, 4, 3); Request(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可为p0分配资源，并修改有关数据年 操作系统 09级网络1、2班银行家算法的保守性例子：R=A,B, 申请a,
7、b; 释放a, bP=p1,p2, p1: a b a b; p2:b b b a a bClaim Allocation Need Available Work FinishA B A B A B A B A B p1：1 1 0 0 1 1 1 1 p2：1 1 0 0 1 1Request1=(1,0), 安全，分配。年 操作系统 09级网络1、2班银行家算法的保守性Request2=(0,1), 不安全，不分配，（分配不导致死锁）Claim Allocation Need Available Work FinishA B A B A B A B A B p1：1 1 1 0 0 1 0
8、 1 p2：1 1 0 0 1 1分配后：年 操作系统 09级网络1、2班练习：某系统中有10台打印机，有三个进程P1、P2、P3分别 需要8台、7台和4台。若P1、P2、P3已申请到4台、2 台和2台。试问：按银行家算法能安全分配吗？请说明 分配过程。年 操作系统 09级网络1、2班练习1：某系统有ABCD这4类资源供5个进程共享，进程对资源的 需求和分配情况如下表所示。现在系统还剩资源A类1个，B类5个 ，C类2个和D类0个，请按银行家算法回答下面问题：进程已占资源数最大需求数A B C D A B C DP10 0 1 2 0 0 1 2P21 0 0 0 1 7 5 0P31 3 5
9、4 2 3 5 6P40 6 3 2 0 6 5 2P50 0 1 4 0 6 5 61、现在系统是否处于安全状态？2、如果现在进程P2提出需要（0，4，2，0）个资源的要求，系统能否满 足它的请求？年 操作系统 09级网络1、2班例2：假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数 量分别为9、3、6），在t0时刻的资源分配情况如下表所示：资源情况 claim allocation need available 进程 R1R2R3 R1R2R3 R1R2R3 R1R2R3P1 3 2 2 1 0 0 2 2 2 1 1 2P2 6 1 3 5 1 1 1 0 2
10、 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0 试问:(1)t0时刻系统是否安全？ (2)P2发出请求向量request2(1,0,1),系统能否将资源分配给它？ (3)在P2申请资源后，若P1发出请求向量request1(1,0,1),系统能否将资源分配给它？年 操作系统 09级网络1、2班5.8 死锁检测考虑因素：死锁发生频度；死锁影响进程。1. 等待时检测：发现早，恢复代价小，开销大（overhead)。2. 定时检测：3. 资源（eg. CPU）利用率下降时检测。年 操作系统 09级网络1、2班5.8.1 死锁检测算法数据结构：Available:
11、 array1mof integer;Allocation: array1n,1mof integer;Request: array1n,1mof integer;临时变量：Work: array1mof integer;Finish: array1nof boolean;年 操作系统 09级网络1、2班5.8.1 死锁检测算法Work:=Available; Finish:=false;有满足条件的i: Finishi=false RequestiWorkFinishi=true;Work:=Work+AllocationiTi ,finishi=trueTFF无死锁死锁FinishI=tr
12、ue for allocationI=0年 操作系统 09级网络1、2班Remarks1. 上述算法可以检测到参与死锁的全部进程，包括占有资源和不占有资源的进程。2. 如果希望只检测占有资源的进程，初始化时：Finishi=true, for AllocationI=0年 操作系统 09级网络1、2班死锁例子例子：R=A(7),B(2),C(6); P=p0,p1,p2,p3,p4Allocation Request Available Work FinishA B C A B C A B C A B C p0: 0 1 0 0 0 0 0 0 0 p1: 2 0 0 2 0 2 p2: 3 0 3 0 0 0 p3: 2 1 1 1 0 0 p4: 0 0 2 0 0 2 未死锁。此时，Request2=(0,0,1), 死锁，参与死锁进程p1,p2,p3,p4年 操作系统 09级网络1、2班5.9 死锁的恢复1. 重新启动简单，代价大，涉及未参与死锁的进程。2. 终止进程(process termination)通过终止参与死锁的进程并收回它们所占有的资源, 死锁
