操作系统(3.2)--作业和作业调度

批处理系统中的作业

1.作业和作业步

(1)作业(Job)。包含了通常的程序和数据，而且还应配有一份作业说明书。在批处理系统中，是以作业为基本单位从外存调入内存的。

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

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

JCB是作业在系统中存在的标志，保存了系统对作业进行管理和调度所需的全部信息。

JCB通常应包含的内容有:

• 作业标识、用户名称、用户帐户、
• 作业类型(CPU繁忙型、I/O 繁忙型、批量型、终端型)、
• 作业状态、调度信息(优先级、作业已运行时间)、
• 资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、
• 进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等

1. 每当作业进入系统时，系统便为每个作业建立一个JCB,根据作业类型将它插入相应的后备队列中，
2. 作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。
3. 在作业运行期间，系统就按照JCB中的信息对作业进行控制。
4. 当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。

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

三个阶段:收容、运行和完成

三种状态:后备状态、运行状态和完成状态

(1)收容阶段:把作业输入到硬盘，再为该作业建立JCB，放入后备队列中。此时的作业状态为“后备状态”

(2)运行阶段:当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。“运行状态”

(3)完成阶段:当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段。“ 完成状态”

作业调度的主要任务

作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。

有时也把作业调度称为接纳调度(Admission Scheduling)。

每次作业调度必须做出如下决定：

(1)接纳多少个作业

作业调度每次要接纳多少个作业进入内存，取决于多道程序度(Degree of Multiprogramming)，即允许多少个作业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，比如，使周转时间太长。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。

(2)接纳哪些作业

应将哪些作业从外存调入内存，这将取决于所采用的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存；较常用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是“响应比高者优先”的调度算法

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

1.先来先服务调度算法

先来先服务（FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。当在进程调度中采用该算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。

2.短作业(进程)优先调度算法

短作业(进程)优先调度算法SJ(P)F，是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。它们可以分别用于作业调度和进程调度。

SJ(P)F调度算法也存在不容忽视的缺点：

(1）必须预知作业的运行时间。

(2）对长作业非常不利。如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列（就绪队列），由于调度程序总是优先调度那些(即使是后进来的）短作业(进程），将导致长作业(进程)长期不被调度，出现饥饿现象。

(3)采用SJF算法时，人一机无法实现交互。

(4）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。

优先级调度算法和相应比优先调度算法

1.优先级调度算法(PSA)

基于作业的紧迫程度，由外部赋予作业相应的优先级调度算法根据该优先级进行调度。

对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。

对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。

优先级调度算法（PSA）是一种进程调度算法，它根据每个进程的优先级来决定哪个进程应该被执行。优先级是一个整数，通常从0到127，数值越大表示优先级越高。

PSA有两种实现方式：非抢占式和抢占式。在非抢占式PSA中，一旦一个进程开始执行，它会一直运行直到完成或者阻塞。在抢占式PSA中，更高优先级的进程可以抢占正在运行的低优先级进程，以便立即执行。

优缺点

PSA的优点：能够保证高优先级进程的及时执行，避免了低优先级进程长时间占用CPU的情况。

缺点：首先，如果优先级设置不当，可能会导致低优先级进程无法得到执行，从而出现饥饿现象。其次，如果进程的优先级一直保持不变，可能会导致优先级反转问题，即低优先级进程等待高优先级进程释放资源，但高优先级进程由于等待其他资源而无法释放该资源。

综上所述，PSA是一种简单且常用的进程调度算法，但需要根据具体情况进行合理的优先级设置，并注意解决饥饿和优先级反转问题。

2.高相应比优先算法(HRRN)

为每个作业引入一个动态优先级，它随着等待时间延长而增加。优先权的计算为:

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

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

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

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

(2)当要求服务的时间相同时，作业的优先权决定于其等.待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3)对于长作业的优先级，随等待时间的增加而增加，当其等待时间足够长时，也可获得处理机。

优缺点

HRRN算法的优点是简单易实现，能够保证公平性和高吞吐量，但是它对于长作业响应时间较长，容易导致短作业等待时间过长，因此在实际应用中需要综合考虑各种因素来选择合适的作业调度算法。