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

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

2、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、 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） 短作

4、业优先 （ 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作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时

5、间平均带权周转时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

6、等待时间 =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 时刻系统状态表如下 表所示。系统采用银行家算法试试死锁避

7、免策略。（ 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结束

8、,A(7,4,11);A满足 P2，P2结束 ,A(11,4,13);A满足 P3，P3结束 ,A(15,4,18);P4,P5,P2,P3,P1.A满足 P1，P1结束 ,A(17,5,20) T0 时刻是安全状态，存在安全序列(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) ，进程所需资 源ABCP1327P21

9、34P3006P4020P5110剩余资源不能满足任意进程需求，进程将会死锁。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

10、,1,2); 资源总量 E(9.3.6) 需求资源 R：222202103420(2) 假设资源分配给 P1则， A=(2,1,2)-(1,0,1)=(1,1,1) 需求资源 R：121202103420A不能满足任何进程的需求，所以进程死锁，所以拒绝P1 的请求。假设资源分配给 P2则， A=(2,1,2)-(1,0,1)=(1,1,1)需求资源 R：222101103420A满足 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 。现假定它们对资源的请示序列如下表所示：为了避免死锁，系统分配资源时采用银行家算法。如果申请资源得不到满足，进程就转入阻塞态。根据上述信息，试描述各步骤结束时，申请资源的进程是得到满足，还是转入阻塞状态，为什么？(起始状态：各进程

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