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

1、操作系统之调度算法和死锁中 的银行家算法习题答案1. 有三个批处理作业，第一个作业10:00到达，需要执行2小时；第二个作业在10:10到 达，需要执行1小时；第三个作业在10:25到 达，需要执行25分钟。分别采用先来先服 务，短作业优先和最高响应比优先三种调度算 法，各自的平均周转时间是多少？解：先来先服务：（结束时间=上一个作业的结束时间+执行时间周转时间=结束时间-到达时间=等待时间+执 行时间）按到达先后，执行顺序：1->2->3作 业到达 时间结束 时间等待 时间执行 时间周转 时间平均周 转时间110:00，12:00 0m120m120m156. 7m210:10，

2、13:00 110m60m170m310:25，13:25 155m25m180m短作业优先：1）初始只有作业1，所以先执行作业1,结束时 间是12:00，此时有作业2和3；2）作业3需要时间短，所以先执行；3)最后执行作业2作 业到达 时间结束 时间等待 时间执行 时间周转 时间平均周 转时间110:00，12:00 0m120m120m145m310:25，12:25 9!5m25m120m210:10，13:25 1；35m60m195m最高响应比优先：高响应比优先调度算法既考虑作业的执行时间 也考虑作业的等待时间，综合了先来先服务和最 短作业优先两种算法的特点。1) 10:00只有作业

3、1到达，所以先执行作业1；2) 12:00时有作业2和3，作业2：等待时间=12:00-10:10=110m;响应比=1+110/60=2.8 ；作业3:等待时间=12:00-10:25=95m，响应比 = 1+95/25=4.8 ；所以先执行作业33)执行作业2作 业到达 时间结束 时间等待 时间执行 时间周转 时间平均周 转时间110:00 112:00 0i120m120m310:25，12:25 9!5m25m120m145m210:10，13:25 1；35m60m195m2. 在一单道批处理系统中，一组作业的提交时 刻和运行时间如下表所示。试计算一下三种 作业调度算法的平均周转时间

4、 T和平均带权周 转时间W。（1）先来先服务；（2）短作业优先（3） 高响应比优先作业提交时刻利运行时间表作业提交吋刻运行时间18.01.0&50.539.00.249 J0解：先来先服务：作业顺序：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:1

5、2有作业2和4,作业4短，所以先执行4;4) 执行作业2作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时间平均带权周转时18;009:000m60m60m140.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，响应比 =1+30/30=2 ；作业3等待时间=9:00-9:00=0m，响应比 =1+0/12=1 ；所以执行作业2；3) 9:30有作业3和4作业 3等待

6、时间=9:30-9:00=30m，响应比 =1+30/12=3.5 ；作业 4等待时间=9:30-9:06=24m，响应比 = 1+24/6=5;所以执行作业44）执行作业3作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时间平均带权周转时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。在TO时刻系统状态表如

7、下表所示。TO时刻系统狀态进程最大资瀝需求星已分配資源呈ACAHCP155921P2536402P340J1405P4斗75204P5424314剩余资源ABC数233系统采用银行家算法试试死锁避免策略。（1）TO时刻是否为安全状态？若是，请给出 安全序列。(2) 在TO时刻若进程P2请求资源(0,3,4 ),是否能实施资源分配？为什么？3)在(2 )的基础上，若进程P4请求资源(2,0,1(4)在 源(0,2,0 解： 现有资源： 可用资源：)，是否能实施资源分配？为什么？(3 )的基础上，若进程P1请求资 )，是否能实施资源分配？为什么？E (17, 5, 20)A (2, 3, 3)进程

8、所需资源ABCP1347P2134P3006P4221P5110 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满足 P1，P1 结束,A(17,5,20)TO时刻是安全状态，存在安全序列P4,P5,P2,P3,P1.(2) 可用资源A (2, 3, 3) <(0,3,4)不能满足P2需求，所以不能实施分配。(3) 可用资源A (2, 3, 3)>(2,0,1)，假设分配给 P4,A ' (0,3,2)，进程所需资源ABCP1

9、347P2134P3006P4020P5110存在安全序列：P4,P2,P3,P5,P1所以可以分配资源。(4)可用资源：A(0,3,2)>(0,2,0)能满足 P1需求，假设分配，A (0,1,2)，进程所需资源ABCP1327P2134P3006P4020P5110剩余资源不能满足任意进程需求，进程将会死 锁。4.某系统有R1,R2,R3共3类资源，在TO时刻 P1,P2,P3和P4这4个进程对资源的占用和 需求情况见下表，此刻系统可用资源向量为（2,1,2 ）。10时剣系统状态摄X妊源需求时已仆配資源数量KIR2H3K1R2R3pi329W100*2C13411P33L1211P1

10、422002问题：（1）将系统中各种资源总量和此刻各进程对各 资源的需求数目用向量或矩阵表示出来（2 ）如果此时P1,P2均发出资源请求向量 Request（1,0,1）,为了保持系统的安全性应该如 何分配资源？ 说明你所采用策略的原因。（3 ）如果（2 ）中两个请求立刻得到满足后,系统此刻是否处于死锁状态？解：可用资源A(2,1,2);资源总量E(9.3.6)需求资源R:22 220 210 342 0(2)假设资源分配给 P1则，A =(2,1,2)-(1,0,1)=(1,1,1)需求资源R':1 2 12 0 21 034 2 0A'不能满足任何进程的需求，所以进程死锁，

11、 所以拒绝P1的请求。假设资源分配给 P2 则，A =(2,1,2)-(1,0,1)=(1,1,1)需求资源R':2 2 21 0 11034 2 0A'满足 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)需求资源R':1 2 11 0 110 34 20系统此刻并没有立即进入死锁状态，因为这时 所有进程没有提出新的资源申请， 全部进程均 没有因资源请求没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都

12、进入 阻塞状态时，系统才处于死锁状态5.设有3个进程P、Q、R，它们共享10个 同类资源，P、Q、R进程的资源最大需求 量依次为4、7和8。现假定它们对资源的 请示序列如下表所示：进程运存也用及申请低源怙况步骤进龍申请资源敌1P22Q43R24Q25R26P2为了避免死锁，系统分配资源时采用银行 家算法。如果申请资源得不到满足，进程就转 入阻塞态。根据上述信息，试描述各步骤结束 时，申请资源的进程是得到满足，还是转入阻 塞状态，为什么？(起始状态：各进程均不拥 有资源，无进程处于阻塞态)(如果剩余资源即可用资源大于当前状态任 何进程的需求，则进程不会死锁，且安全序列 任意，因为一旦满足某个进程的需求使其结束 后，进程返还占用资源，剩余资源不变(返还 资源为0)或增多，以此类推即可)需求资源R(4,7,8)资源总数E=10,也是可用资源步骤1:满足P,剩余资源可使各进程运行结 束，所以P得到2个资源，E ' =8, R (2,7,8) 步骤2:满足Q,剩余资源可使各进程运行结 束，所以Q得到4个资源，E' =4, R' (2,3,8) 步骤3,满足R,剩余资源可使各进程运行结 束，所以R得到2个资源，E' =2