The Processor Scheduling

处理机调度的层次 Process Scheduling Levels

概述 Overview

处理机是计算机系统中的重要资源,在多道程序环境下，进程数目通常多于处理机的数目,系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程;处理机利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度

• WHAT：按什么原则分配 CPU 调度算法
• WHEN：何时分配 CPU 调度的时机
• HOW：如何分配 CPU 调度过程及进程的上下文切换

作业 JOB

作业是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合
作业是一个比程序更广泛的概念，可以包含多个程序和数据，还配有一份作业说明书，系统根据作业说明书来对作业中的程序进行控制。在批处理系统中，以作业为单位从外存调入内存
用户为了让计算机完成某个特定任务，首先编写成源程序，然后提交给计算机通过编译或汇编、连接、装配、运行等步骤，最终由计算机输出用户所需要的运行结果。从计算机管理的角度看，上述一系列的由计算机执行的任务的集合就是作业。

Job and task are today vague, ambiguous terms, especially task. A “job” often means a set of processes, while a “task” may mean a process, a thread, a process or thread, or, distinctly, a unit of work done by a process or thread.
job, task and process, what’s the difference

作业步 Job Step

计算机完成作业是通过执行一系列有序的工作步骤进行的，每个步骤完成作业的一部分特定工作;把计算机系统完成一个作业所需的一系列有序的相对独立的工作步骤称为作业步
作业的各个作业步虽然功能相对独立，但它们之间相互关联，往往是一个作业步的执行需要使用上一个作业步的执行结果。

从用户把源程序提交给计算机系统到得出运算结果要经过若干个工作步骤，首先计算机系统要对用户的源程序进行编辑工作来进行语法检查，再由编译或汇编工作生成目标代码。由连接工作形成装入模块，然后通过装入工作将装入模块装入内存。最后由运行工作得出运行结果。5 个步骤，每步都完成一项相对独立的工作

作业状态转换 Job State Transition

JCB

作业提交给系统进入后备状态后，系统将为每个作业建立一个作业控制块 JCB。
JCB 在作业的整个运行过程中始终存在，并且其内容与作业的状态同步地动态变化。只有当作业完成并退出系统时，JCB 才被撤消。可以说，JCB 是一个作业在系统中存在的唯一标志，系统根据 JCB 才感知到作业的存在
作业控制块 JCB 中包含了对作业进行管理的必要信息，JCB 中的信息一部分是从用户提供的作业控制卡或作业说明书中得到，另一部分是记录作业运行过程中的动态信息

处理机调度的层次

• 在多道程序系统中，一个作业从提交到执行，通常都要经历多级调度,如高级调度、低级调度、中级调度以及 I/O 调度等
• 系统的运行性能在很大程度上取决于调度,如吞吐量的大小、周转时间的长短、响应的及时性等
• 调度是多道系统的关键

类型	运行频率	运行时间	算法复杂性	存储	OS
进程调度	高	短	低	内存中	批处理,实时,分时
中程调度	中	较短	中	内外存互换	批处理,实时,分时
作业调度	低	长	高	外存到内存	批处理

高级调度 High Scheduling

高级调度 High Scheduling：又称作业调度、准入调度、长程调度或接纳调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存;它发生在一批作业完成，重新调入一批作业到内存的时候，执行频率低。批处理系统需要有作业调度，分时和实时系统无需此调度。主要用于批处理系统。其设计目标是最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行;

对资源需求不同的作业进行合理搭配

• 科学计算属于 CPU 密集型，主要依赖处理器运算，对 I/O 设备需求较少；
• 数据处理多为 I/O 密集型，计算逻辑相对简单（占用 CPU 时间少），但需要频繁进行数据读写操作；
• 部分递归计算属于内存密集型，运算过程中会产生大量中间结果，需要占用较多内存空间存储。

若能将这些作业合理调度搭配，例如让 CPU 密集型作业占用处理器时，I/O 密集型作业进行数据读写，内存密集型作业处理内存数据，使各类作业在时间上错开对同一资源的竞争，就能提高系统的资源利用率和吞吐量

调度评价指标

多道程序度 Degree Of Multiprogramming：即允许多少个作业同时在内存中运行。
周转时间 Turnaround Time：指从作业被提交给系统开始，到作业完成为止的这段时间间隔,也称为作业周转时间
带权周转时间 Weighted Turnaround Time：作业的周转时间 T 与系统为它提供服务的时间 TS 之比,称为带权周转世界,$WTT=\frac{T_{\text{周转时间}}}{T_{\text{预计运行时间}}}$
响应比 Response Ratio：$RR=\frac{T_{\text{等待时间}} + T_{\text{预计运行时间}}}{T_{\text{预计运行时间}}}=\frac{T_{\text{响应时间}}}{T_{\text{预计运行时间}}}$,注意 RR>=1

低级调度 Low Scheduling

低级调度又称为进程调度或短程调度，它所调度的对象是进程。三种类型 OS 都必须配置这级调度(最基本调度);低级调度用于决定就绪队列中的哪个进程应获得处理机，然后由分派进程 Dispatcher执行把分配处理机给相应进程的具体操作。其时间尺度通常是毫秒级的,且是系统中最频繁的调度,要求在实现时做到高效

低级调度基本机制

1. 排队器为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列。
2. 分派器(调度程序) 分派器把由进程调度程序所选定的进程从就绪队列中取出，然后进行上下文切换，将处理机分配给它。
3. 上下文切换机制当对处理机进行切换时，会发生两对上下文切换操作。

低级调度功能

1. 按某种算法选取进程（调度）。
2. 保存处理机的现场信息（上下文切换第一步骤）
3. 恢复新进程的 CPU 现场,从而把处理器分配给新进程（上下文切换第二步骤）。

中级调度 Intermediate-Level Scheduling

中级调度 Intermediate-Level Scheduling,又称中程调度(Medium-Term Scheduling);
主要目的：为了提高内存利用率和系统吞吐量。
具体实现：

• 使那些暂时不能运行的进程不再占用宝贵的内存资源，而将其调至外存的交换区(swap space)去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。
• 当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

调度模型 Scheduling Model

三级调度都涉及进程的队列。可以形成以下三种调度队列模型

• 仅有进程调度(低级调度)
• 具有高级和低级调度
• 具有三级调度

仅有进程调度

在分时系统中，通常仅设有进程调度,系统把这些进程组织成一个就绪队列,每个进程在执行时，可能有以下几种情况

• 进程获得 CPU 正在执行；
• 任务在给定时间片内已完成，释放处理机后为完成状态；
• 任务在时间片内未完成，进入就绪队列末尾；
• 在执行期间因某事件而阻塞。
  

具有高级和低级调度

在批处理系统中，不仅需要进程调度，而且还要有作业调度
就绪队列的形式:在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队列首进程
设置多个阻塞队列:根据事件的不同设置多个队列提高效率

同时具有三级调度的调度队列模型

在 OS 中引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。同样，阻塞状态进一步分成内存阻塞和外存阻塞两种状态。
在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；
在中级调度的作用下，又可使外存就绪转为内存就绪。