操作系统之调度算法和死锁中的银行家算法习题答案

1、1.有三个批处理作业，第一个作业10:00到达，需要执行2小时；第二个作业在10:10到达，需要执行1小时；第三个作业在10:25到达，需要执行25分钟。分别采用先来先服务，短作业优先和最高响应比优先三种调度算法，各自的平均周转时间是多少？解：先来先服务：（结束时间=上一个作业的结束时间+执行时间周转时间=结束时间-到达时间=等待时间+执行时间）按到达先后，执行顺序：1->2->3作业到达时间结束时间1等待时间执行时间周转时间平均周转时间110:0012:000m120m120m156.7m210:1013:00110m60m170m310:2513:25155m25m180m短作

2、业优先：1）初始只有作业1,所以先执行作业1,结束时间是12:00,此时有作业2和3;2）作业3需要时间短，所以先执行；3）最后执行作业2作业到达时间结束时间等待时间执行时间周转时间平均周转时间110:0012:000m120m120m145m310:2512:2595m25m120m210:1013:25135m60m195m最高响应比优先：高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。1） 10:00只有作业1到达，所以先执行作业1;2） 12:00时有作业2和3,作业2:等待时间=12:00-10:10=110m;响应比=1+

3、110/60=2.8;作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8;所以先执行作业33）执行作业2作业到达时间结束时间等待时间执行时间周转时间平均周转时间110:0012:000m120m120m145m310:2512:2595m25m120m210:1013:25135m60m195m2.在一单道批处理系统中，一组作业的提交时刻和运行时间如下表所示。试计算一下三种作业调度算法的平均周转时间T和平均带权周转时间W。（1）先来先服务；（2）短作业优先（3）高响应比优先作业提交时刻和运行时间表作业提交时刻运行时间18.()L028.50.539.00.249J

4、0.1解:先来先服务：作业顺序：1,2,3,4作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时间平均带权周转时18;009:000m60m60m151m3.37528:309:3030m30m60m239:009:4230m12m42m3.549:069:4836m6m42m7短作业优先：作业顺序：1) 8:00只有作业1,所以执行作业1;2) 9:00有作业2和3,作业3短，所以先执行3;3) 9:12有作业2和4,作业4短，所以先执行4;4)执行作业2作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时间平均带权周转时18;009:000m60m60m140

5、.5m1.6539:009:120m12m12m149:069:186m6m12m228:309:4848m30m78m2.6高响应比优先：作业顺序：1) 8:00只有作业1,所以执行作业1;2) 9:00有作业2和3作业2等待时间=9:00-8:30=30m作业3等待时间=9:00-9:00=0m所以执行作业2;3)9:30有作业3和4作业3等待时间=9:30-9:00=30m作业4等待时间=9:30-9:06=24m,响应比=1+30/30=2;,响应比=1+0/12=1;,响应比=1+30/12=3.5;,响应比=1+24/6=5;所以执行作业44)执行作业3作业到达时间结束时间等待时间

6、执行时间周转时间带权周转时间平均周转时间平均带权周转时18;009:000m60m60m149.5m328:309:3030m30m60m249:069:3624m6m30m539:009:4836m12m48m43)设系统中有3种类型的资源(A,B,C)和5个进程(P1,P2,P3,P4,P5),A资源的数量为17,B资源的数量为5,C资源的数量为20。在T0时刻系统状态表如下表所示。TO时刻系统状态进程最大资源需求量已分配资源量ABCABCP1559112P2536402P34011405P4425204P5424314剩余资源数Ac233系统采用银行家算法试试死锁避免策略。(1)T0时刻

7、是否为安全状态？若是，请给出安全序列。(2)在T0时刻若进程P2请求资源(0,3,4)，是否能实施资源分配？为什么？(3)在(2)的基础上，若进程P4请求资源(2,0,1),是否能实施资源分配？为什么?(4)在(3)的基础上，若进程P1请求资源(0,2,0),是否能实施资源分配？为什么?解：现有资源：E(17,5,20)可用资源：A(2,3,3)进程所需资源ABCP1347P2134P3006P4221P5110(1)A满足P4,P4结束,A(4,3,7);A满足P5,P5结束,A(7,4,11);A满足P2,P2结束,A(11,4,13);A满足P3,P3结束,A(15,4,18);A满足P

8、1,P1结束,A(17,5,20)T0时刻是安全状态，存在安全序列P4,P5,P2,P3,P1.(2)可用资源A(2,3,3)<(0,3,4)不能?t足P2需求，所以不能实施分配。(3)可用资源A(2,3,3)>(2,0,1)，假设分配给P4,A'(0,3,2),进程所需资源ABCP1347P2134P3006P4020P5110存在安全序列：P4,P2,P3,P5,P1所以可以分配资源。(4)可用资源：A(0,3,2)>(0,2,0)能满足P1需求，假设分配，A'(0,1,2),进程所需资源ABCP1327P2134P3006P4020P5110剩余资源不能

9、满足任意进程需求，进程将会死锁。4)某系统有R1,R2,R3共3类资源，在T0时刻P1,P2,P3和P4这4个进程对资源的占用和需求情况见下表，此刻系统可用资源向量为(2,1,2)。rn时刻系统状态最大资源需求量已分配资源数量RR2l?3RR3PL322100P2613411P33I4211P442202问题：(1)将系统中各种资源总量和此刻各进程对各资源的需求数目用向量或矩阵表示出来(2)如果此时P1,P2均发出资源请求向量Request(1,0,1),为了保持系统的安全性应该如何分配资源？说明你所采用策略的原因。(3)如果(2)中两个请求立刻得到满足后，系统此刻是否处于死锁状态？解：(1)

10、可用资源A(2,1,2);资源总量E(9.3.6)需求资源R:222202103?20一(2)假设资源分配给P1则，A=(2,1,2)-(1,0,1)=(1,1,1)需求资源R':121202103420一A不能满足任何进程的需求，所以进程死锁，所以拒绝P1的请求。假设资源分配给P2则，A=(2,1,2)-(1,0,1)=(1,1,1)需求资源R':222101M03?2JA满足P2要求，P2完成，A'(6,2,3);存在安全序列：P2,P1,P3,P4.所以答应P2的请求。(3)假设资源分配给P1则，A=(2,1,2)-(1,0,1)-(1,0,1)=(0,1,0)需

11、求资源R'121101103420一系统此刻并没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源请求没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状态5.设有3个进程P、Q、R,它们共享10个同类资源，P、Q、R进程的资源最大需求量依次为4、7和8。现假定它们对资源的请示序列如下表所示：进程运行顺序及申请资源情况步骤进程申请资源数1P22Q43R24Q25R26p2为了避免死锁，系统分配资源时采用银行家算法。如果申请资源得不到满足，进程就转入阻塞态。根据上述信息，试描述各步骤结束时，申请资源的进程是得到满足，还是

12、转入阻塞状态，为什么？(起始状态：各进程均不拥有资源，无进程处于阻塞态)(如果剩余资源即可用资源大于当前状态任何进程的需求，则进程不会死锁，且安全序列任意，因为一旦满足某个进程的需求使其结束后，进程返还占用资源，剩余资源不变(返还资源为0)或增多，以此类推即可)需求资源 R(4,7,8)资源总数E=10,也是可用资源步骤1:满足P,剩余资源可使各进程运行结束， 步骤2:满足Q,剩余资源可使各进程运行结束, 步骤3,满足R,剩余资源可使各进程运行结束， 步骤4:阻塞Q,若答应请求，则剩余资源为 步骤5:阻塞R,若答应请求，则剩余资源为所以P得到2个资源，E' =8, R' (2,7,8) 所以Q得到4个资源，E' =4, R&#