问题
问答题
有5个任务A、B、C、D、E，它们几乎同时到达，预计它们的运行时间为10、6、2、4、8min。其优先级分别为3、5、2、1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间(进程切换开销可不考虑)。
(1)先来先服务(按A、B、C、D、E)算法。
(2)优先级调度算法。
(3)时间片轮转算法。
答案
参考答案：采用先来先服务(FCFS)调度算法时，5个任务在系统中的执行顺序、完成时间及周转时间如表3.24所示。
表3.24 采用先来先服务(FCFS)调度算法 min 执行次序| 到达时间 服务时间 开始执行时间 完成时间 周转时间 A 0 10 0 10 10 B 0 6 10 16 16 C 0 2 16 18 18 D 0 4 18 22 22 E 0 8 22 30 30
5个进程的平均周转时间T为：
T=(10+16+18+22+30)/5=19.2(min)
(2)采用最高优先级调度(HPF)算法时，5个任务在系统中的执行顺序、完成时间及周转时间如表3.3所示。
| 表3.25 采用最高优先级调度算法 min | |||||
| 执行次序 | 一到达时间 | 服务时间 | 开始执行时间 | 完成时间 | 周转时间 |
| B | 0 | 6 | 0 | 6 | 6 |
| E | 0 | 8 | 6 | 14 | 14 |
| A | 0 | 10 | 14 | 24 | 24 |
| C | 0 | 2 | 24 | 26 | 26 |
| D | 0 | 4 | 26 | 30 | 30 |
T=(6+14+24+26+30)/5=20(min)
(3)如果系统采用时间片轮转(RR)算法，令时间片为2分钟，5个任务轮流执行的情况为：
第1轮：(A，B，C，D，E)；
第2轮：(A，B，D，E)；
第3轮：(A，B，E)；
第4轮：(A，E)；
第5轮：(A)。
由于5个任务同时到达，所有任务到达时间都可以理解为0，因此，每个任务的周转时间为其最后一次获得的时间片及之前系统所有时间片之和。显然，5个进程的周转时间为：T1=30min、T2=22min、T3=6min、T4=16min、T5=28min。它们的平均周转时间T为：
T=(30+22+6+16+28)/5=20.4(min)
解析： 本题目考查三种进程调度算法的调度过程。本题目中，由于5个任务同时到达，所以所有任务的到达时刻都可以理解为O。