第三章有关作业和进程调度算法的习题

1. 有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用抢占式的优先级调度算法，在下表的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。

（1）列出所有作业进入内存时间及结束时间。

（2）计算这批作业的平均周转时间及平均带权周转时间。解：

作业执行过程如下：

8:00 A 到达，内存空，A 进入内存，无竞争开始运行；

8:20 B 到达，进入内存，优先数为2，由于A 的优先数为4，相比B 优先级低，被剥夺处理器，B 开始运行； 8:30 A 到达，内存满，不可进入内存；

8:50 B 运行结束，同时D 到达，同C 争夺内存，由于D 运行时间短，按照短作业优先的调度算法，D 被调入内存；D 与A 的优先数相比，A 的优先级别高，获得处理器继续运行；

9:10 A 运行结束，C 进入内存，C 的优先级别高于D ，C 开始运行； 10:00 C 运行结束，D 开始运行； 10:20 D 运行结束。

1）所有作业进入内存时间及结束时间如下表所示：

2）作业周转时间=作业结束时间-作业到达时间

这批作业的平均周转时间=(70+30+90+90)/4=70分钟这批作业的平均带权周转时间=(7/4+1+9/5+9/2)/4=2.26

2. 有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出：

采用短作业优先调度算法，作业被调入系统后中途不会退出，但作业运行时可被更短作业抢占。（1）分别给出6个作业的开始执行时间、作业完成时间、作业周转时间。（2）计算这批作业的平均周转时间。解答：

作业执行过程如下：

8:00 J1到达，内存空，无竞争, 进入内存开始运行； 8:20 J1运行20分钟，剩余40分钟；

J2到达，运行时间为35分钟，小于J1，取代J1开始运行。 8:25 J1剩40分钟，J2剩30分钟；

J3到达，运行时间为20分钟，小于J2，取代J2开始运行。 8:30 J1剩40分钟，J2剩30分钟；J3剩15分钟；

J4到达，运行时间为25分钟，大于J3， J3继续运行。

8:35 J3剩10分钟；

J5到达，运行时间为5分钟，尽管时间最短，但是内存中已有四道作业，因此，J5，不可进入内存，J3继续运行。

8:40 J3剩5分钟；J6到达，同理不可进入内存，J3继续运行。 8:45 J3运行结束；J5最短，进入内存并开始执行。

8:50 J5运行结束；J6进入内存，运行时间10分钟，为最短，开始执行。 9:00 J6运行结束，J1剩40分钟，J2剩30分钟；J4剩25分钟；J4最短，开始运行。

9:25 J4运行结束， J2最短，开始运行。 9:55 J2运行结束， J1开始运行。 10:35 J1运行结束。

1）所有作业的开始执行时间、作业完成时间、作业周转时间，如下表所示：

2）作业周转时间=作业结束时间-作业到达时间

这批作业的平均周转时间=(155+95+20+55+15+20)/6=60分钟这批作业的平均带权周转时间=(155/60+195/35+1+11/5+3+2)/4=4.01

第三章 有关作业和进程调度算法的习题