操作系统(3.1)--处理机调度和作业

一、处理机调度层次

1.高级调度(High Level Scheduling)

高级调度又称长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。

主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。

2.低级调度（Low Level Scheduling)

低级调度又称为进程调度或短程调度，其所调度的对象是进程(或内核级线程)。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。

3.中级调度(Intermediate Scheduling)

引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。

使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。

当这些进程重又具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

二、处理机调度算法的目标

1.处理机调度算法的共同目标

（1）资源利用率

CPU的利用率=(CPU有效工作时间) / (CPU有效工作时间+CPU空闲等待时间)

（2）公平性

使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。

（3）平衡性

尽可能保持系统资源使用的平衡性

（4）策略强制执行

2.批处理系统的目标

（1）平均周转时间短

周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）。

它包括四部分时间

• ①作业在外存后备队列上等待(作业)调度的时间，
• ②进程在就绪队列上等待进程调度的时间，
• ③进程在CPU上执行的时间，以及
• ④进程等待I/O操作完成的时间

平均周转时间：

带权周转时间是作业的周转时间T与系统为它提供服务的时间Ts之比，即T/Ts。

平均带权周转时间：

对用户而言，总希望自己作业的周转时间尽可能的少；对系统而言，则希望作业的平均周转时间尽可能的少。每个系统在选择作业调度算法时，既应考虑用户的要求，又能确保系统具有较高的效率。

(2）系统吞吐量高

吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度具有密切关系。尽量多的选择短作业运行。

(3）处理机利用率高

对于大、中型多用户系统，由于CPU价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标。尽量选择计算量大的作业运行。

3.分时系统的目标

(1）响应时间快

所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。

它包括三部分时间：

• ①从键盘输入的请求信息传送到处理机的时间，
• ②处理机对请求信息进行处理的时间，以及
• ③将所形成的响应信息回送到终端显示器的时间。

（2）均衡性

是指系统响应时间的快慢应与用户所请求服务的复杂性相适应。

4.实时系统的目标

（1）截止时间的保证

所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。

(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)接纳哪些作业

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

五、先来先服务和短作业(进程)优先算法

1.先来先服务调度算法

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

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

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

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

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

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

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

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