问答题
在一个单处理器的计算机系统中，有四个进程P1，P2，P3，P4的到达时间和所需要的运行时间如下表所示(时间单位：小时，以十进制计算)，请问
(1)分别写出采用“先来先服务”调度算法、“短进程优先”和“响应比高者优先”调度算法选中进程运行的次序。
(2)分别计算上述三种算法使各进程在就绪队列中的平均等待时间以及三种算法下的平均周转时间。
(3)是否存在缩短平均周转时间的调度策略，如果存在，请提出来，写出选中进程运行的次序，并计算在就绪队列中的平均等待时间以及平均周转时间。
(1)分别写出采用“先来先服务”调度算法、“短进程优先”和“响应比高者优先”调度算法选中进程运行的次序。
(2)分别计算上述三种算法使各进程在就绪队列中的平均等待时间以及三种算法下的平均周转时间。
(3)是否存在缩短平均周转时间的调度策略，如果存在，请提出来，写出选中进程运行的次序，并计算在就绪队列中的平均等待时间以及平均周转时间。
|
进程
|
到达时间
|
运行时间
|
|
|
P1
|
0.0
|
8.0
|
|
|
P2
|
0.4 |
4.0
|
|
|
P3
|
1.0
|
1.0
|
|
|
P4
|
4.0
|
3.0
|
|
【正确答案】
【答案解析】先来先服务，调度次序为P1，P2，P3．P4。
[解析] 先来先服务就是按照到达的次序依次执行。到达次序为P1，P2，P3，P4，所以调度次序也为P1，P2，P3，P4。
短进程优先，调度次序为P1，P3，P4，P2。
[解析] 开始只有P1所以执行P1，P1执行完时，P2，P3，P4都已经到达，服务时间短的优先，所以是P3，P4，P2。
响应比高者优先．调度次序为P1，P3，P2，P4。 [解析] 开始只有P1所以执行P1，P1执行完时．P2，P3，P4都已经到达，响应比等 于(等待时间+服务时间)/服务时间，则P2的响应比为(7.6+4)/4=2.9，P3的响应比为(7+1)/1=8，P4的响应比为(4+3)/3=2.3，P3的响应比最高，所以第二个执行P3，P3完成时，时间为9.0，此时P2的响应比为(8.6+4)/4=3.15，P4的响应比为(5+3)/3=2.6，P2的响应比最高，所以第三个执行P2，最后执行P4。
(2)从上面表格中可看出：
先来先服务算法的平均等待时间为：(0+7.6+11+9)/4=6.9
平均周转时间为：(8+11.6+12+12)/4=10.9
短进程优先算法的平均等待时间为：(0+11.6+7+5)/4=5.9
平均周转时间为：(8+15.6+8+8)/4=9.9
高响应比者优先算法的平均等待时间为：(0+8.6+7+9)/4=6.15
平均周转时间为：(8+12.6+8+12)/4=10.15
[解析] 周转时间等于进程到达到服务完成的这段时间，平均周转时间就是每个进程的 周转时间相加取平均。
等待时间是进程处于就绪队列中的时间，在前面三个非抢占式调度算法中等于开始运行 时间减去到达时间这一段时间。平均等待时间就是每个进程的等待时间相加取平均。
(3)可采用抢占式短作业优先算法。执行过程如图：
[解析] 先来先服务就是按照到达的次序依次执行。到达次序为P1，P2，P3，P4，所以调度次序也为P1，P2，P3，P4。
|
进程
|
P1
|
P2
|
P3
|
P4
|
|
到达时间
|
0.0
|
0.4
|
1.0
|
4.0
|
|
服务时间
|
8.0
|
4.0
|
1.0
|
3.0
|
|
开始运行时间
|
0.0
|
8.0
|
12.0
|
13.0
|
|
完成时间
|
8.0
|
12.0
|
13.0
|
16.0
|
|
周转时间
|
8.0
|
11.6
|
12.0
|
12.0
|
|
等待时间
|
0.0
|
7.6
|
11.0
|
9.0
|
|
进程
|
P1
|
P2
|
P3
|
P4
|
|
到达时间
|
0.0
|
0.4
|
1.0
|
4.0
|
|
服务时间
|
8.0
|
4.0
|
1.0
|
3.0
|
|
开始运行时间
|
0.0
|
12.0
|
8.0
|
9.0
|
|
完成时间
|
8.0
|
16.0
|
9.0
|
12.0
|
|
周转时间
|
8.0
|
15.6
|
8.0
|
8.0
|
|
等待时间
|
0.0
|
11.6
|
7.0
|
5.0
|
|
进程
|
P1
|
P2
|
P3
|
P4
|
|
到达时间
|
0.0
|
0.4
|
1.0
|
4.0
|
|
服务时间
|
8.0
|
4.0
|
1.0
|
3.0
|
|
开始运行时间
|
0.0
|
9.0
|
8.0
|
13.0
|
|
完成时间
|
8.0
|
13.0
|
9.0
|
16.0
|
|
周转时间
|
8.0
|
12.6
|
8.0
|
12.0
|
|
等待时间
|
0.0
|
8.6
|
7.0
|
9.0
|
先来先服务算法的平均等待时间为：(0+7.6+11+9)/4=6.9
平均周转时间为：(8+11.6+12+12)/4=10.9
短进程优先算法的平均等待时间为：(0+11.6+7+5)/4=5.9
平均周转时间为：(8+15.6+8+8)/4=9.9
高响应比者优先算法的平均等待时间为：(0+8.6+7+9)/4=6.15
平均周转时间为：(8+12.6+8+12)/4=10.15
[解析] 周转时间等于进程到达到服务完成的这段时间，平均周转时间就是每个进程的 周转时间相加取平均。
等待时间是进程处于就绪队列中的时间，在前面三个非抢占式调度算法中等于开始运行 时间减去到达时间这一段时间。平均等待时间就是每个进程的等待时间相加取平均。
(3)可采用抢占式短作业优先算法。执行过程如图：