操作系统 课后答案(1)(3)

T2=b+(b+a)+(b+a+c)=3b+2a+c ②

令②-①式得到：

T2-T1=b-a>0

可见，采用短作业优先算法调度才能获得最小平均作业周转时间。 6 若有一组作业J1，?，Jn，其执行时间依次为S1，?，Sn。如果这些作业同时到

达系统，并在一台单CPU处理器上按单道方式执行。试找出一种作业调度算法，使得平均作业周转时间最短。 答：首先，对n个作业按执行时间从小到大重新进行排序，则对n个作业：J1’，?，Jn’，它们的运行时间满足：S1’≤ S2’≤? ≤S(n-1)’≤Sn’。那么有：

T=[S1’ +( S1’+S2’)+ (S1’ + S2’+ S3’)+?+(S1’ + S2’+ S3’+?+ Sn’)]/n =[n×S1’ +( n-1)×S2’+ (n-3)×S3’]+?+ Sn’]]/n

=(S1’ + S2’+ S3’+?+ Sn’)-[0×S1’+1×S2 ’ +2×S3’ +?+(n-1) Sn’]/n

由于任何调度方式下，S1’ + S2’+ S3’+?+ Sn’为一个确定的数，而当S1’≤ S2’≤? ≤S(n-1)’≤Sn’ 时才有：0×S1’+1×S2 ’ +2×S3’ +?+(n-1) Sn’的值最大，也就是说，此时T值最小。所以，按短作业优先调度算法调度时，使得平均作业周转时间最短。 7 假定执行表中所列作业，作业号即为到达顺序，依次在时刻0按次序1、2、3、4、

5进入单处理器系统。

1） 分别用先来先服务调度算法、时间片轮转算法、短作业优先算法及非强占优先权调度算法算出各作业的执行先后次序(注意优先权高的数值小)； 2） 计算每种情况下作业的平均周转时间和平均带权周转时间。

作业号 执行时间 优先权 1 2 3 4 5 答：

10 1 2 1 5 3 1 3 4 2 7

《操作系统教程》（第三版）CH1应用题参考答案

(1) 采用FCFS算法调度作业，运作情况：

执行次序 执行时间 等待时间 开始时间 完成时间 周转时间 带权周转时间 1 10 0 0 10 10 1 2 1 10 10 11 11 11 3 2 11 11 13 13 6.5 4 1 13 13 14 14 14 5 5 14 14 19 19 3.8 作业平均周转时间 T=(10+11+13+14+19)/5=13.4 作业平均带权周转时间 W=(1+11+6.5+14+3.8)/5=7.26

(2) 采用RR算法调度作业，若令时间片长=1，各作业执行情况为：1、2、3、4、5、

1、3、5、1、5、1、5、1、5、1、1、1、1、1。

作业 执行时间 提交时间 完成时间 周转时间 带权周转时间

(3) 采用SJF算法调度作业，运作情况：

1 10 0 19 19 1.9 2 1 0 2 2 2 3 2 0 7 7 3.5 4 1 0 4 4 4 5 5 0 14 14 2.8 作业平均周转时间 T=(19+2+7+4+14)/5=9.2 作业平均带权周转时间 W=(1.9+2+3.5+4+2.8)/5=2.84

(4) 采用非剥夺优先权算法调度作业，运作情况：

执行次序 执行时间 等待时间 开始时间 完成时间 周转时间 带权周转时间 2 1 0 0 1 1 1 4 1 1 1 2 2 2 3 2 2 2 4 4 2 5 5 4 4 9 9 1.8 1 10 9 9 19 19 1.9 作业平均周转时间 T=(1+2+4+9+19)/5=7 作业平均带权周转时间 W=(1+2+2+1.8+1.9)/5=1.74 8

《操作系统教程》（第三版）CH1应用题参考答案

8

执行次序 优先数 执行时间 等待时间 周转时间 带权周转时间 2 1 1 0 1 1 5 2 5 1 6 1.2 1 3 10 6 16 1.6 3 3 2 16 18 9 4 4 1 18 19 19 作业平均周转时间 T=(1+6+16+18+19)/5=12 作业平均带权周转时间 W=(1+1.2+1.6+9+19)/5=6.36 对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T。一次进程切换的系统开销时间为S。若采用时间片长度为Q的时向片轮转法，对下列各种情况算出CPU利用率。

1）Q＝∞ 2）Q＞T 3）S＜Q＜T 4＝Q＝S 5＝Q接近于0 答：

1）Q=∞ CPU利用率=T/（T+S） 2）Q>T CPU利用率=T/（T+S） 3）T>Q>S CPU利用率=Q/（Q+S） 4) Q=S CPU利用率=50% 5) Q→0 CPU利用率→0

9

有5个待运行的作业，各自预计运行时间分别是：9、6、3、5和x，采用哪种运行次序使得平均响应时间最短？

答：按照最短作业优先的算法可以使平均响应时间最短。X取值不定，按照以下情况讨论：

1） x≤3 次序为：x，3，5，6，9 2） 3

10 有5个批处理作业A到E均已到达计算中心，其运行时间分别2、4、6、8和10

分钟；各自的优先级分别被规定为1、2、3、4和5，这里5为最高级。对于1）时间片轮转算法、2）优先数法、3）短作业优先算法、4）先来先服务调度算法(按到达次序C、D、B、E、A)，在忽略进程切换时间的前提下，计算出平均作业周转时间。（对1）每个作业获得相同的2分钟长的时间片；对2）到4）采用单道运行，直到结束。） 答：

(1)FCFS调度算法 执行次序 执行时间 等待时间 周转时间 带权周转时间 C 6 0 6 1 D 8 6 9 14 1.75 B 4 14 18 4.5 E 10 18 28 2.8 A 2 28 30 15 《操作系统教程》（第三版）CH1应用题参考答案

(2)优先级调度算法

执行次序 执行时间 等待时间 周转时间 带权周转时间 E 10 0 10 1 D 8 10 18 2.25

C 6 18 24 4

B 4 24 28 7 A 2 28 30 15

作业平均周转时间 T=(10+18+24+28+30)/5=22

作业平均带权周转时间 W=(1+2.25+4+7+15)/5=5.85

(3)时间片轮转法 按次序A B C D E B C D EC D …… 此处隐藏：1182字，全部文档内容请下载后查看。喜欢就下载吧 ……