题目
假设某计算机系统有4个进程，各进程的预计运行时间和到达就绪队列的时刻见表2-11(相对时间，单位为“时间配额[1]”)。试用可抢占式短进程优先调度算法和时间片[2]轮转调度[3]算法进行调度(时间配额为2)。分别计算各个进程的调度次序及平均周转时间。 表2-11 进程调度表 进程 到达就绪队列时刻 预计运行时间 P1 0 8 p2 1 4 P3 2 9 P4 3 5
假设某计算机系统有4个进程，各进程的预计运行时间和到达就绪队列的时刻见表2-11(相对时间，单位为“时间配额[1]”)。试用可抢占式短进程优先调度算法和时间片[2]轮转调度[3]算法进行调度(时间配额为2)。分别计算各个进程的调度次序及平均周转时间。 表2-11 进程调度表 进程 到达就绪队列时刻 预计运行时间 P1 0 8 p2 1 4 P3 2 9 P4 3 5
题目解答
答案
1)按照可抢先式短进程优先调度算法进程运行时间见下表。进程 到达就绪队列时刻 预计执行时间 执行时间段 周转时间 P1 0 8 0～1:10～17 17 P2 1 4 1～5 4 P3 2 9 17～26 24 P4 3 5 5～10 7 时刻0，进程P1到达并占用处理器运行。 时刻1，进程P2到达，因其预计运行时间短，故抢夺处理器进入运行，P1等待。 时刻2，进程P3到达，因其预计运行时间长于正在运行的进程，进入就绪队对等待。 时刻3，进程P4到达，因其预计运行时间长于正在运行的进程，进入就绪队列等待。 时刻5，进程P2运行结束，调度器在就绪队列中选择短进程，P4符合要求，进入运行，进程P1和进程P3则还在就绪队列等待。 时刻10，进程P4运行结束，调度器在就绪队列中选择短进程，P1符合要求，再次进入运行，而进程P3则还在就绪队列等待。 时刻17，进程P1运行结束，只剩下进程P3，调度其运行。 时刻26，进程P3运行结束。 平均周转时间=[(17-0)+(5-1)+(26-2)+(10-3)]/4=13。 2)按照时间片轮转调度算法进程时间分配见下表。 进程 到达就绪队列时刻 预汁执行时间 执行时间段 剧转时间 P1 0 8 0～2；8～10；16～18；21～23 23 p2 1 4 2～4；10～12 11 P3 2 9 4～6；12～14；18～20；23～25；25～26 24 P4 3 5 6～8；14～16；20～21 18 平均周转时间=((23-0)+(12-1)+(26-2)+(21-3))/4=19。
解析
步骤 1：可抢占式短进程优先调度算法
1. 时刻0，进程P1到达并占用处理器运行。
2. 时刻1，进程P2到达，因其预计运行时间短，故抢夺处理器进入运行，P1等待。
3. 时刻2，进程P3到达，因其预计运行时间长于正在运行的进程，进入就绪队对等待。
4. 时刻3，进程P4到达，因其预计运行时间长于正在运行的进程，进入就绪队列等待。
5. 时刻5，进程P2运行结束，调度器在就绪队列中选择短进程，P4符合要求，进入运行，进程P1和进程P3则还在就绪队列等待。
6. 时刻10，进程P4运行结束，调度器在就绪队列中选择短进程，P1符合要求，再次进入运行，而进程P3则还在就绪队列等待。
7. 时刻17，进程P1运行结束，只剩下进程P3，调度其运行。
8. 时刻26，进程P3运行结束。
步骤 2：时间片轮转调度算法
1. 时刻0，进程P1到达并占用处理器运行。
2. 时刻2，P1运行时间片结束，P2到达，P2运行。
3. 时刻4，P2运行时间片结束，P3到达，P3运行。
4. 时刻6，P3运行时间片结束，P4到达，P4运行。
5. 时刻8，P4运行时间片结束，P1运行。
6. 时刻10，P2运行时间片结束，P3运行。
7. 时刻12，P3运行时间片结束，P4运行。
8. 时刻14，P4运行时间片结束，P1运行。
9. 时刻16，P3运行时间片结束，P4运行。
10. 时刻18，P1运行时间片结束，P3运行。
11. 时刻20，P4运行时间片结束，P1运行。
12. 时刻21，P4运行时间片结束，P1运行。
13. 时刻23，P1运行时间片结束，P3运行。
14. 时刻25，P3运行时间片结束，P3运行。
15. 时刻26，P3运行时间片结束，P3运行结束。
步骤 3：计算平均周转时间
1. 可抢占式短进程优先调度算法：平均周转时间=[(17-0)+(5-1)+(26-2)+(10-3)]/4=13。
2. 时间片轮转调度算法：平均周转时间=((23-0)+(12-1)+(26-2)+(21-3))/4=19。
1. 时刻0，进程P1到达并占用处理器运行。
2. 时刻1，进程P2到达，因其预计运行时间短，故抢夺处理器进入运行，P1等待。
3. 时刻2，进程P3到达，因其预计运行时间长于正在运行的进程，进入就绪队对等待。
4. 时刻3，进程P4到达，因其预计运行时间长于正在运行的进程，进入就绪队列等待。
5. 时刻5，进程P2运行结束，调度器在就绪队列中选择短进程，P4符合要求，进入运行，进程P1和进程P3则还在就绪队列等待。
6. 时刻10，进程P4运行结束，调度器在就绪队列中选择短进程，P1符合要求，再次进入运行，而进程P3则还在就绪队列等待。
7. 时刻17，进程P1运行结束，只剩下进程P3，调度其运行。
8. 时刻26，进程P3运行结束。
步骤 2：时间片轮转调度算法
1. 时刻0，进程P1到达并占用处理器运行。
2. 时刻2，P1运行时间片结束，P2到达，P2运行。
3. 时刻4，P2运行时间片结束，P3到达，P3运行。
4. 时刻6，P3运行时间片结束，P4到达，P4运行。
5. 时刻8，P4运行时间片结束，P1运行。
6. 时刻10，P2运行时间片结束，P3运行。
7. 时刻12，P3运行时间片结束，P4运行。
8. 时刻14，P4运行时间片结束，P1运行。
9. 时刻16，P3运行时间片结束，P4运行。
10. 时刻18，P1运行时间片结束，P3运行。
11. 时刻20，P4运行时间片结束，P1运行。
12. 时刻21，P4运行时间片结束，P1运行。
13. 时刻23，P1运行时间片结束，P3运行。
14. 时刻25，P3运行时间片结束，P3运行。
15. 时刻26，P3运行时间片结束，P3运行结束。
步骤 3：计算平均周转时间
1. 可抢占式短进程优先调度算法：平均周转时间=[(17-0)+(5-1)+(26-2)+(10-3)]/4=13。
2. 时间片轮转调度算法：平均周转时间=((23-0)+(12-1)+(26-2)+(21-3))/4=19。