处理机的调度

标签（空格分隔）：进程调度调度算法操作系统

基本概念

定义
: 操作系统管理了系统的有限资源，当有多个进程（或多个进程发出的请求）要使用这些资源时，因为资源的有限性，必须按照一定的原则选择进程（请求）来占用资源, 我们称之为调度。

其目的是控制资源使用者的数量,选取资源使用者许可占用资源或占用资源。处理机调度的三个层次:

高级调度:作业调度, 调度对象为作业.
中级调度:内存调度(实质是存储器的对换功能)
低级调度:进程调度, 调度对象为进程或内核级线程

作业调度的算法也适用于进程调度

服务时间$T_s$: 系统为作业或进程提供服务的时间
周转时间$T_i$: 作业或进程被提交给系统到作业或进程完成为止的时间间隔.
通常包括:

作业在外存后备队列上等待调度的时间.
进程在就绪队列上等待进程调度的时间.
进程在cpu上执行的时间.
进程等待I/O操作完成的时间.

平均周转时间:
\[T = \frac{\sum_{i=1}^n T_i}{n}\]
带权周转时间: 作业的周转时间与为它提供服务的时间之比
\[W_i = \frac{T_i}{T_s}\]
平均带权周转时间:
\[W = \frac{\sum_{i=1}^n \frac{T_i}{T_s}}{n}\]

调度时机、切换与过程

进程调度和切换程序是操作系统内核程序。当请求调度的事件发生后，才可能会运行进程调度程序，当调度了新的就绪进程后，才会去进行进程间的切换。理论上这三件事情应该顺序执行，但在实际设计中，在操作系统内核程序运行时，如果某时发生了引起进程调度的因素，并不一定能够马上进行调度与切换。

现代操作系统中，不能进行进程的调度与切换的情况有以下几种情况:

在处理中断的过程中：中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。
进程在操作系统内核程序临界区中：进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放。
其他需要完全屏蔽中断的原子操作过程中：如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。

如果在上述过程中发生了引起调度的条件，并不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。

应该进行进程调度与切换的情况有：

当发生引起调度条件，且当前进程无法继续运行下去时，可以马上进行调度与切换。如果操作系统只在这种情况下进行进程调度，就是非剥夺调度。
当中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。如果操作系统支持这种情况下的运行调度程序，就实现了剥夺方式的调度。

进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入到当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

调度的方式

非抢占方式
一旦处理机分配给某进程后, 就一直让它运行下去, 决不会因为时钟中断或任何其他原因取抢占当前正在运行进程的处理机, 直至该进程完成, 或发生某事件而被阻塞时, 才把处理机分配给其他进程.
抢占方式
系统允许调度程序根据某种原则, 取暂停某个正在执行的进程, 将已分配个该进程的处理机重新分配给另一进程.
"抢占"时应遵循一定的原则:

优先权原则
短进程优先原则
时间片原则

典型的调度算法

先来先服务调度算法(first-come first-served):

即FCFS调度算法, 既可用于作业调度, 也可用于进程调度. 系统按照作业到达的先后次序(优先考虑在就绪队列中等待时间最长的作业)进行调度.
缺点:未考虑作业的紧迫程度, 只能顺序运行

短作业(进程)优先的调度算法(short job first):

为短作业而设立, 因为操作系统中大多为短作业.系统在作业运行时, 选出运行时间最短的作业将其调入内存.

SJF(不可抢占):算法以作业的长短(作业需要运行的时间)来计算优先级, 作业越短, 其优先级越高.
SPF(可抢占):同上, 但是当有作业优先级较高时, 便可以抢占资源优先执行.

缺点:

必须预知作业的运行时间
对作业程不利
无法实现人机交互
没有考虑到作业的紧迫程度

优先级调度算法(priority-scheduling algorithm):

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

高响应闭优先调度算法(highest request ratio next):

HRRN算法即考虑了作业的等待时间, 又考虑了作业运行时间. 为没有作业引入一个动态优先级:

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

可缩写为:

R = 响应时间 / 要求服务时间

特点:

作业等待时间相同, 则要求服务时间越短, 优先权越高越, 类似于SJF算法, 有利于短作业
作业要求服务时间相同时, 则作业等待时间约长, 优先权越高, 类似于FCFS算法, 有利于长作业
对于长作业(要求服务时间长), 随着等待的时间足够长, 也可获得较高的优先级. 不会一直等下去.

时间片轮转调度算法(RR)

原理: 系统根据FCFS策略将所有的就绪进程排成一个就绪队列, 并设置每隔一段时间产生依次中断, 激活系统中的进程调度程序, 完成依次调度, 将cpu分配给新的队首进程(或新到达的紧迫进程).

进程切换

若一个时间片尚未用完, 正在运行的进程便已完成, 则立即激活调度程序, 将其从执行队列中删除, 在调度就绪队列的队首进程运行, 并启动一个新的时间片.
在一个时间片用完时, 计时中断处理程序被激活, 如果进程尚未运行完毕, 则调度程序将它送往就绪队列末尾, 并调度就绪队列的队首进程运行, 并启动新时间片.

注意:时间片选取过小, 则将频繁的执行进程调度和进程长下文切换, 增加系统开销; 时间片选取过长, 则RR算法退化为FCFS算法, 无法满足短作业和交互式用户需求. 时间片应选取略大于依次典型的交互所需要的时间, 是大多数进程在一个时间片内完成.

多级反馈队列调度算法(multileved feedback queue):

设置多个就绪队列, 并为每个队列赋予不同的优先级, 优先级越高的队列其时间片越小.优先级最高的队列最先进入待调度的队列
队列之间采用FCFS调度算法.只有高优先级队列中的全部进程完成时才调度下一队列
队列内的进程按照轮转算法调度.新进程进入内存后首先进入优先级最高的队列
在低优先级队列运行时, 若有新进程到达, 那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。

实时系统中的进程调度算法

实时系统是指系统能及时响应外部事件的请求并及时处理这些请求.基于这一特性, 实时系统在工业(武器)控制, 多媒体等系统中常见.
实时系统中通分为存在一个截止时间, 硬实时任务(HRT)要求在开始截止时间前必须执行, 在结束截止时间前必须结束. 软实时任务同上, 但并不严格.
在实时系统中有两类算法值得注意:最早截止时间优先算法(Earliest Deadline First)和最低松弛度优先算法(Least Laxity First).两类算法都可用抢占式和非抢占式调度, 但后者常用于抢占式调度.
在m个周期性的实时调度中, 每个实时任务的处理时间$C_i$, 周期时间$P_i$, 在但处理机的情况下, 需满足条件:$\sum_{i=1}^m\frac{C_i}{P_i} $小于1; 多处理机条件下, 须满足条件$\sum_{i=1}^m\frac{C_i}{P_i} $小于N, N为处理机数量.