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

1. 有三个批处理作业，第一个作业 10:00 到达，需要执行 2 小时；第二个作业在 10:10 到达，需要执行 1 小时；第三个作业在 10:25 到达，需要执行 25 分钟。分别采用先来先服务，短作业优先和最高响应比优先三种调度算法，各自的平均周转时间是多少？解：先来先服务：（结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间）按到达先后，执行顺序：1-2-3作业到达时间结束时间等待时间执行时间周转时间平均周转时间110:0012:000m120m120m1567m210:1013:00110m60m170m310:2513:25155m25m180m短作业优先：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+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） 高响应比优先解：先来先服务：作业顺序：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.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等待时间=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。在 T0 时刻系统状态表如下表所示。系统采用银行家算法试试死锁避免策略。（ 1） T0 时刻是否为安全状态？若是，请给出安全序列。（ 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满足P1，P1结束,A(17,5,20)T0时刻是安全状态，存在安全序列P4,P5,P2,P3,P1.(2) 可用资源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剩余资源不能满足任意进程需求，进程将会死锁。4.某系统有 R1,R2,R3 共 3 类资源，在 T0 时刻 P1,P2,P3 和 P4 这 4 个进程对资源的占用和需求情况见下表，此刻系统可用资源向量为（ 2,1,2）。问题:（ 1）将系统中各种资源总量和此刻各进程对各资源的需求数目用向量或矩阵表示出来（ 2）如果此时 P1,P2 均发出资源请求向量 Request(1,0,1),为了保持系统的安全性应该如何分配资源？ 说明你所采用策略的原因。（ 3）如果（ 2）中两个请求立刻得到满足后，系统此刻是否处于死锁状态？解：(1)可用资源A(2,1,2); 资源总量E(9.3.6)需求资源R：(2)假设资源分配给P1则，A=(2,1,2)-(1,0,1)=(1,1,1)需求资源R：A不能满足任何进程的需求，所以进程死锁，所以拒绝P1的请求。假设资源分配给P2则，A=(2,1,2)-(1,0,1)=(1,1,1)需求资源R：A满足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：系统此刻并没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源请求没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状态5. 设有 3 个进程 P、 Q、 R，它们共享 10 个同类资源， P、 Q、 R 进程的资源最大需求量依次为 4、 7 和 8。现假定它们对资源的请示序列如下表所示：为了避免死锁，系统分配资源时采用银行家算法。如果申请资源得不到满足，进程就转入阻塞态。根据上述信息，试描述各步骤结束时，申请资源的进程是得到满足，还是转入阻塞状态，为什么？（起始状态：各进程均不拥有资源，无进程处于阻塞态）（如果剩余资源即可用资源大于当前状态任何进程的需求，则进程不会死锁，且安全序列任意，因为一旦满足某个进程的需求使其结束后，进程返还占用资源，剩余资源不变（返还资源为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，R(2,3,6)