一道题浅谈【作业调度】与【进程调度】

题目：（北京大学1993考研）

一个批处理系统中，有两个作业进程。有一个作业序列，到达时间和估计服务时间如下。系统采用最高响应比优先的作业调度算法，作业进程的调度采用短作业优先的抢占式调度算法。请列出各作业的执行情况表。

====================================================================

进程调度分为

长程调度，又称作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行

短程调度，又称进程调度，用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程的具体操作

中程调度，从就绪挂起到就绪，从阻塞挂起到阻塞，引入中程调度的主要目的，是为了提高内存利用率和系统吞吐量（这里不谈）

进程调度图：

一个作业到达时首先被放进后备队列。

作业调度按一定的算法从后备队列中选择到达的资源能得到满足的作业装入内存，使作业有机会去占用处理器执行。

所谓的有机会，是因为此后还需要进程调度程序来进行调度，决定哪个进程优先获得CPU，什么时候获得CPU，分配多少CPU时间片，能不能抢占等等，也就是说，调度程序才是大脑，CPU只是一个执行部件而已。

于是，作业调度选中了一个作业且把它装入内存时，就会为该作业创建一个进程，若有多个作业被装入内存，则内存中同时存在多个进程，这些进程的初始状态为就绪状态，放在就绪队列中，然后，由进程调度程序根据自己的调度算法来选择当前可占用处理器的进程，进程运行中会出现各种状态，有以下些状态会引起调度程序的重新调度决策：

1.在创建一个新进程时之后，需要决定运行父进程还是子进程

2.在一个进程运行结束让出CPU使用权的时候，需要重新调度一个进程给CPU

3.当一个进程阻塞在I/O信号或者信号量或其他上面时，必须选择另外一个进程运行。

4.在一个I/O中断发生时，某些被阻塞的等待该I/O的程序可能已经进入就绪态，需要重新决策。

调度算法分为抢占式和非抢占式算法两类，这里区分一下：

非抢占式：意味着调度程序调度某进程运行，分配时间片，直到时间片完或者该进程自己由于某些原因阻塞才回打断其执行，否则调度程序不能因为优先级等原因强行调度另一个进程来抢占原有进程的CPU资源。

抢占式：意味着调度程序虽然调度了某个进程运行，但是此后调度程序随时可以根据其算法让另一个符合优先执行的进程强制剥夺其CPU资源。

如此，作业调度与进程调度相互配合实现多道作业的并行执行。

那么为什么要制定作业调度算法呢？为什么要搞一个后备队列呢？一个作业到来后直接把它扔到就绪队列中不就好了？实际上我们不这样做的原因是就绪队列的空间可能是有限的。比如题目说的有两个作业进程，说明就绪队列的容量是2，一个作业运行，一个作业就绪。由于不是每个作业都能迅速达到就绪态，所以就需要作业调度来选择进入系统（就绪态）的作业。

解如下：

10:00    作业A到达，由于就绪队列空，作业调度进系统，进程调度执行

10:10    作业B到达，就绪队列未满，作业调度进系统，由于B此时是最短作业，所以进程调度A到就绪态，调度B执行

            作业A已运行10分钟，剩余25分钟

10:15    作业C到达，响应比为1，等待作业调度进系统

            作业B继续执行，已运行5分钟，剩余25分钟

            作业A剩余25分钟，位于就绪队列

10:20    作业D到达，响应比为1，等待作业调度进系统

            作业C等待5分钟，响应比R=1+5/45 = 1.11

            作业B继续执行，已运行10分钟，剩余20分钟

            作业A剩余25分钟，位于就绪队列

10:30    作业E到达，响应比为1，等待作业调度进系统

            作业D等待10分钟，响应比R=1+10/20 = 1.5

            作业C等待15分钟，响应比R=1+15/45 = 1.3

            作业B继续执行，已运行20分钟，剩余10分钟

            作业A剩余25分钟，位于就绪队列

10:40    作业E等待10分钟，响应比R=1+10/30 = 1.3

            作业D等待20分钟，响应比R=1+20/20 = 2.0

            作业C等待25分钟，响应比R=1+25/45 = 1.6

            作业D具有最高响应比，D被作业调度进系统，由于是最短作业，进程调度D执行

            作业B运行结束

            作业A剩余25分钟，位于就绪队列

11:00    作业E等待30分钟，响应比R=1+30/30 = 2.0

            作业C等待45分钟，响应比R=1+45/45 = 2.0

            两者响应比相同，由于C先到达，所以作业调度C进系统

            作业D运行20分钟，运行结束

            作业A剩余25分钟，服务时间比C小，进程调度A执行

11:25    作业E等待55分钟，响应比R=1+55/30 = 2.8，作业调度进系统

            作业C剩余45分钟，位于就绪队列

            作业A运行25分钟，运行结束

            因为C服务时间比E长，所以进程调度E执行

11:55    作业C剩余45分钟，位于就绪队列

            作业E运行30分钟，运行结束

12:40    作业C运行结束

各作业运行时间段为：

A    10:00-10:10   11:00-11:25

B    10:10-10:40

C    11:55-12:40

D    10:40-11:00

E    11:25-11:55