操作系统之处理机的调度

处理机调度的层次和调度算法的目标

在多道程序环境下，进程数目往往多于处理机数目。

这就要求系统能够按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行

分配处理机的任务是由处理机调度程序完成的

处理机调度的层次

高级调度：

用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程排在就绪队列上，准备执行

又称长程调度或作业调度。它的调度对象为作业，只适用于多道批处理系统中，不适合实时和分时系统。

低级调度：

用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。为最基本的一种调度

又称进程调度或短程调度。它的调度对象为进程或内核级线程，适用于所有类型的操作系统。

中级调度：

又称内存调度。主要目的是为了提高内存利用率和系统吞吐量。

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

进程调度可采用下述两种调度方式：

非抢占方式（Non-preemptive Mode）

一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才把处理机分配给其他进程
抢占方式（Preemptive Mode）

允许调度程序根据某种原则，去暂停某个正在执行的进程，将处理机重新分配给另一进程。

队列调度模型

仅有进程调度的调度队列模型

在分时系统中，通常仅设置进程调度。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表，形式取决于OS类型和所采用的调度算法。

具有高级和低级调度的调度队列模型

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

当在OS中引入中级调度后，可以把进程的就绪状态分为内存就绪和外存就绪。也可以把阻塞状态分为内存阻塞和外存阻塞两种状态。

处理机调度算法的目标

共同目标：

资源利用率
公平性

公平性是指应使诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。公平性是相对的。
平衡性

应尽可能保持系统资源使用的平衡性。
策略强制执行

包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

批处理系统的目标：

平均周转时间短：所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔

带权周转时间：作业的周转时间 T 与系统为它提供服务的时间 Ts 之比

系统吞吐量高：吞吐量是指在单位时间内系统所完成的作业数。如果单纯是为了获得高的系统吞吐量，就应尽量多地选择短作业运行。

处理机利用率高：如果单纯是为使处理机利用率高，应尽量多地选择计算量大的作业运行

分时系统的目标：

响应时间快。所谓响应时间，是从用户通过键盘提交一个请求开始，直至屏幕上显示出处理结果为止的一段时间间隔。

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

实时系统的目标

截止时间的保证。是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。

可预测性。例如在多媒体系统中，可实现第 i 帧的播放和第 i+1 帧的读取并行处理，进而提高其实时性。

作业和作业调度

作业控制块 JCB

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

每当一个作业进入系统时，便由“作业注册”程序为该作业建立一个 JCB，再根据作业类型将它插入相应的作业后备队列中等待调度。

在每次执行作业调度时，都须作出两个决定：

接纳多少作业
接纳哪些作业

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

收容阶段。

把作业输入到硬盘上，再为作业建立 JCB 并把它放入作业后备队列中。此时作业状态为“后备状态”。
运行阶段。

此时作业状态为“运行状态”。
完成阶段。

此时作业状态为“完成状态”。系统中的“终止作业”程序将会回收已分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。

作业调度算法

先来先服务调度算法 FCFS。

当在作业调度中采用FCFS算法时，每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业

优先考虑在系统中最先进入（等待时间最长）的作业。

比较有利于长作业（进程），而不利于短作业（进程）。有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业（进程）

短作业（进程）优先调度算法 SJF

SJF算法是以作业的长短来计算优先级的，作业的长短是以作业所要求的运行时间来衡量的。

从后备队列中选择一个或若干个估计运行时间最短的作业

优点是有效降低作业的平均等待时间，提高系统吞吐量。

缺点是可能使长作业等待时间过长，出现饥饿现象。

高优先权优先调度算法：

优先权调度算法的类型

为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法

分为：

非抢占式优先权算法
抢占式优先权调度算法

静态优先权：在创建进程时确定的，在进程的整个运行期间保持不变

动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变。

高相应比优先调度算法

高响应比优先调度算法是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长。

为每个作业引入一个动态优先级，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加

于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比 RP。

例子：

进程调度

进程调度的任务：

保存处理机的现场信息。
按某种算法选取进程。
把处理器分配给进程。

进程调度可采用下述两种调度方式：

非抢占式
抢占式

抢占的原则：
- 优先权原则：优先权高的可以抢占优先级低的进程的处理机。
- 短作业（进程）优先原则：短作业（进程）可以抢占长作业（进程）的处理机。
- 时间片原则：各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度。

轮转调度算法：RR

系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。

进程切换时机：

若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，并为新进程启动一个新的时间片。
在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

例题：

过程：

(q = 1) 时的调度过程
- 0 时刻：进程 A 到达，进入就绪队列，此时就绪队列只有 A，A 开始运行。运行 1 个时间片后（到 1 时刻），A 还需服务时间 (4 - 1=3) ，A 被暂停，放入就绪队列队尾。
- 1 时刻：进程 B 到达，加入就绪队列，此时队首是 B，B 开始运行 1 个时间片，B 还需服务时间 (3 - 1 = 2) ，B 被暂停，放入队尾。然后队首是 A，A 运行 1 个时间片，如此循环。
- 随着时间推进，不断按照每个进程运行 1 个时间片后放入队尾的规则调度，直到所有进程完成。比如 D 进程在 3 时刻到达，加入队尾，按序调度运行。
- 计算周转时间：周转时间 = 完成时间 - 到达时间，例如 A 的周转时间 (= 12 - 0 = 12) 。
- 计算带权周转时间：带权周转时间 = 周转时间 / 服务时间，A 的带权周转时间 (=12 / 4 = 3) 。
(q = 4) 时的调度过程
- 原理类似，但时间片变长。0 时刻 A 到达运行，运行 4 个时间片到 4 时刻，A 服务时间 4 刚好完成，离开就绪队列。
- 之后按序调度其他进程，每个进程运行 4 个时间片，若未完成则放入队尾等待下次调度。例如 B 进程 1 时刻到达，在 A 完成后开始运行，运行 4 个时间片到 7 时刻，B 还需 (3 - 4=-1) （已完成）。
- 同样计算周转时间和带权周转时间，如 A 的周转时间 (= 4 - 0 = 4) ，带权周转时间 (= 4 / 4 = 1) 。

优先级调度算法

类型：

非抢占式优先级调度算法。
抢占式优先级调度算法，实时性高

多级反馈队列调度算法：

调度机制：
- 设置多个就绪队列：
  
  每个队列赋予不同的优先级，第一个最高，依次逐渐降低；时间片设置也不同，优先级越高，时间片越小。
- 每个队列都采用FCFS算法：
  
  当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度，依次
- 按队列优先级调度：
  
  调度程序首先调度最高优先级队列中的诸进程运行，仅当第 1～(i-1) 所有队列均空时，才会调度第 i 队列中的进程运行。
  
  如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程