作业与作业调度

作业与作业调度

在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存再一个后备作业队列中。再由作业调度程序将其从外存调入内存。

批处理系统中的作业

1. 作业和作业步

(1) 作业(Job)。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。

(2) 作业步(Job Step)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步的输入。例如，一个典型的作业可分成：“编译”作业步，“链接装配”作业步和“运行”作业步。

2. 作业控制块(Job Control Block,JCB)

为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB,它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。 通常在JCB中包含的内容有：作业标识、用户名称、用户账号、作业类型(CPU繁忙型、/O繁忙型、批量型、终端型)、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小等)、资源使用情况等。 每当一个作业进入系统时，便由“作业注册”程序为该作业建立一个作业控制块JCB。再根据作业类型，将它放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法来调度它们，被调度到的作业将被装入内存。在作业运行期间，系统就按照JCB中的信息和作业说明书对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收已分配给它的资源，撒销该作业控制块。

3. 作业运行的三个阶段和三种状态

作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。

(1) 收容阶段。操作员把用户提交的作业通过某种输入方式或SPOOLing系统输入到硬盘上，再为该作业建立JCB,并把它放入作业后备队列中。相应地，此时作业的状态为“后备状态”。

(2) 运行阶段。当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态”。 (3) 完成阶段。当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。此时系统中的“终止作业”程序将会回收已分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。

作业调度的主要任务

作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度(Admission Scheduling)。在每次执行作业调度时，都需做出以下两个决定。

1. 接纳多少个作业

在每一次进行作业调度时，应当从后备队列中选取多少作业调入内存，取决于多道程序度(Degree of Multiprogramming,即允许多少个作业同时在内存中运行。对系统来说，希望装入较多的作业，有利于提高CPU的利用率和系统的吞吐量。但如果内存中同时运行的作业太多时，进程在运行时因内存不足所发生的中断就会急别增加。这将会使平均周转时间显著延长，影响到系统的服务质量。因此，多道程序度的确定是根据计算机的系统规模、运行速度、作业大小，以及能否获得较好的系统性能等情况作出适当的抉择的。

2. 接纳哪些作业

应选择后备队列中的哪些作业调入内存，取决于所采用的调度算法。最简单的是先来先服务调度算法，它是将最早进入外存的作业优先调入内存。较常用的一种算法是短作业优先调度算法，是将外存上所需执行时间最短的作业优先调入内存。另一种较常用的是基于作业优先级的调度算法，该算法是将外存上作业优先级最高的作业优先调入内存。比较好的一种算法是“响应比高者优先”的调度算法。我们将在后面对上述的几种算法作较详细的介绍。

在批处理系统中，作业进入系统后，总是先驻留在外存的作业后备队列上，因此需要有作业调度，以便将它们分批地装入内存。然而在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等都被直接送入内存，因而无需配置上述的作业调度机制，但也需要有某种接纳控制措施来限制进入系统的用户数目。即如果系统尚有能力处理更多的任务，将会接纳授权用户的请求，否则，便拒绝接纳。类似地，在实时系统中也不需要作业调度，而必需具有接纳控制措施。

先来先服务(FCFS)和短作业优先(SJF)调度算法

1.先来先服务(first-come first--served,FCFS)调度算法

FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。

当在进程调度中采用FC℉S算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。

顺便说明，FCFS算法在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用，形成一种更为有效的调度算法。例如，可以在系统中按进程的优先级设置多个队列，每个优先级一个队列，其中每一个队列的调度都基于FCFS算法。

2.短作业优先(short job first,SJF)的调度算法

由于在实际情况中，短作业（进程）占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。

• 短作业优先算法

SJF算法是以作业的长短来计算优先级,作业越短,其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时,它将从外存的作业后备队列中选择若干个估计运行时间最短的作业,优先将它们调入内存运行。

• 短作业优先算法的缺点

SJF调度算法较之FCFS算法有了明显的改进,但仍然存在不容忽视的缺点:

(1) 必须预知作业的运行时间。在采用这种算法时,要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间,如果估计过低,系统就可能按估计的时间终止作业的运行,但此时作业并未完成,故一般都会偏长估计。

(2)对长作业非常不利,长作业的周转时间会明显地增长。更严重的是,该算法完全忽视作业的等待时间,可能使作业等待时间过长,出现饥线现象。

(3)在采用FCFS算法时,人一机无法实现交互。

(4)该调度算法完全未考虑作业的紧迫程度,故不能保证紧迫性作业能得到及时处理。

优先级调度算法和高响应比优先调度算法

1. 优先级调度算法(priority-scheduling algorithm, PSA)

我们可以这样来看作业的优先级,对于先来先服务调度算法,作业的等待时间就是作业的优先级,等待时间越长,其优先级越高。对于短作业优先调度算法,作业的长短就是作业的优先级,作业所需运行的时间越短,其优先级越高,但上述两种优先级都不能反映作业的紧迫程度。而在优先级调度算法中,则是基于作业的紧迫程度,由外部赋予作业相应的优先级,调度算法是根据该优先级进行调度的。这样就可以保证紧追性作业优先运行。

优先级调度算法可作为作业调度算法,也可作为进程调度算法。当把该算法用于作业调度时,系统是从后备队列中选择若干个优先级最高的作业装入内存。

2. 高响应比优先调度算法(Highest Response Ratio Next, HRRN)

在批处理系统中, FCFS算法所考虑的只是作业的等待时间,而忽视了作业的运行时间。 而SJF算法正好与之相反,只考虑作业的运行时间,而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间,又考虑作业运行时间的调度算法,因此既照顾了短作业,又不致使长作业的等待时间过长,从而改善了处理机调度的性能。

高响应比优先算法是如何实现的呢?如果我们能为每个作业引入一个动态优先级,即优先级是可以改变的,令它随等待时间延长而增加,这将使长作业的优先级在等待期间不断地增加,等到足够的时间后,必然有机会获得处理机。该优先级的变化规律可描述为:

优先权=(等待时间+要求服务时间) / 要求服务时间

由于等待时间与服务时间之和就是系统对该作业的响应时间,故该优先级又相当于响应比Rp。据此,优先又可表示为:

Rp=(等待时间+要求服务时间) / 要求服务时间 = 响应时间 / 要求服务时间

由上式可以看出：

① 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于SF算法，有利于短作业。

② 当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于FCFS算法。

③ 对于长作业的优先级，可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机。因此该算法实现了较好的折中。当然在利用该算法时，每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。