第三部分 CPU调度

一、相关基本概念

• 引入多程序设计，目的是提高计算机资源利用率，尤其是CPU利用率（CPU utilization）。（前面所讲的多程序和多任务的目的就是让多个进程竞争使用资源，从而使CPU利用率提高。）
• CPU密集 — I/O密集的循环
• 进程的执行，呈现出CPU运行和I/O等待的交替循环。

注意前面的知识：

• CPU中有READY信号,当收到I/O送来的信号后才会进行读写操作。
• I/O操作不消耗CPU，而是让CPU闲置了，浪费CPU，因为I/O设备相对于CPU来说速度很慢,CPU要花大部分时间来等待I/O处理数据。

二、CPU调度器

CPU调度器的使命

• 从内存中一堆准备就绪的进程中（就绪队列中的就绪进程），选取一个进程；
• 将CPU分配给该进程。
• 后者也可以由dispatcher完成。

CPU调度器的操作对象.png

由上图我们可以看见，通过CPU 调度器，计算机进程（PCB）有四个去向：
1）留在就绪队列
2）进入CPU
3）等待队列
4）I/O操作

CPU调度器的操作时机

调用CPU调度器的时机，通常发生在：
1）某一进程从执行状态转为等待状态
2）某一进程从执行状态转为就绪状态（图上应为双向箭头）
如果有一个进程进入就绪队列，且进程优先级高，则有可能该优先级高的进程把原先执行队列里的进程抢过来。
3）某一进程从等待状态转为就绪状态
如I/O操作完成以后，转回ready queue。
4）某一进程终止
进程上下文切换。
等等，不限于以上四种，只是举了四个例子（引发调度的时机可能有十几种）。
1,4属于“非抢占式（nonpreemptive）调度”，2,3属于“抢占式（preemptive）调度”。

非抢占式：

进程自愿交出CPU，引起新一轮的调度。

抢占式：

进程被迫交出CPU，引起新一轮的调度。

解释一下第三种情形：
本身等待到就绪状态是不需要CPU调度的，由图可知，做完I/O操作，进入ready queue即可。但现在如果有重要或紧迫的进程到达，那么当前进程必须为就绪状态。则强行将CPU调度从等待状态转为就绪状态，并且强行放弃处理现在的运行进程，将CPU立即分配给新到达的进程。故它是一种抢占式调度。

CPU调度器追求目标

• CPU利用率（CPU utilization）。CPU的利用率就是非空闲进程占用时间的比例，即CPU执行非空闲进程的时间/ CPU总的执行时间。
• 吞吐率（Throughput） — 单位时间内完成执行的进程数
• 周转时间（Turnaround time） — 执行某一进程所耗用的CPU累积时间（进程进入就绪队列开始到拿到CPU执行结束为止的累积时间，其间有可能存在时间片到了或者高优先级抢占CPU的情况）
• 等待时间（Waiting time） — 某一进程等待在就绪队列里面的累积时间（不包括CPU执行时间）
• 响应时间（Response time） — 某一进程从发出调度请求，到其开始得到CPU调度器响应，其间所经历的时间。

优异的指标，当然是

• Maximize CPU utilization
• Maximize throughput
• Minimize turnaround time
• Minimize waiting time
• Minimize response time

三、CPU分配器（Dispatcher）

CPU调度器决定了将CPU分配给谁。后续操作就是，CPU分配器将CPU控制权移交给该进程。
操作内容通常包括：

• 上下文切换（switching context）
• 从内核态（kernel mode）转移至用户态（user mode）
• 跳转至用户程序中PC寄存器所指示的位置

注意，分配器的工作是有延迟的，这种属于“无用功”，也就是处理时的额外开销。

四、FCFS调度算法（First-Come,First-Served Scheduling）

• 这种实现比较简单，先进入就绪队列的进程最先处理。处理方式自然是将这些进程构成一个链表，先处理先进入就绪队列的进程，然后根据next指针一步步往后。
• Burst time，即中央处理器突发时间。是指CPU从接到命令到开始处理命令所需时间。

FCFS调度算法处理进程.png

• 如图可见，假设只有单核CPU的情况下，同时在0时刻进入P1，P2，P3三个进程。但同时只能有一个进程进行CPU处理（由具体的CPU调度算法控制）。
  甘特图：下方的数字表示时间，表示横向时间轴。上面表示进程的使用过程P1，P2，P3。
• 周转时间：
  P1：0-24，24
  P2：0-27，27
  P3：0-30，30
• 等待时间：
  P1：0，P2：24，P3：27，平均等待时间为（0+24+27）/3 = 17。

假设进程到达就绪队列的顺序：P2，P3，P1，则FCFS调度算法的调度结果有显著变化，如甘特图：

P2，P3，P1顺序的等待时间甘特图.png

• 等待时间（某一进程在就绪队列里面的等待时间） P1=6，P2=0，P3=3。平均等待时间（6+0+3）/3 = 3，改善非常多。

启示：短进程先于长进程，减少等待时间。
问题：时间波动很大，不稳定。

五、Shortest-Job-First（SJF）调度算法（最短作业优先算法）

算法要求：

• 进入就绪队列的进程预告需要多长CPU时间才能完成本次执行

算法思想：

• 选取就绪队列中，“需要CPU时间”最短的进程。

举例：非抢占式SJF

非抢占式SJF.png

• 首先P1于0时刻进入就绪队列，因此先交于CPU处理。处理时间为7秒。
• 之后P2于2时刻进入就绪队列，由于我们研究的是非抢占式队列，因此它先在就绪队列里待着，不进入CPU。
• P3，P4在4，5时刻进入，同样的，由于P1并没有到Burst time，因此P2，P3，P4都在就绪队列没有进入CPU处理。
• 7秒时，P1结束处理。此时先处理P3因为其时间最短。1秒后，交出CPU重新调度。此时剩下P2和P4。
• 由于P2和P4时间一样，假设使用FCFS算法。先处理P2，再处理P4。整个甘特图如图所示。

平均等待时间为：
（0+（7-4）+（8-2）+（12-5））/4 = 4
（上面我们都假设CPU利用率为100%）

结论：由等待时间可知，SJF优于FCFS。

举例：抢占式SJF算法：

抢占式SJF算法.png

• 基本理论为：更短时间的进程抢占更长时间的进程。
• 首先，P1于0时刻进入CPU，执行2秒。
• 紧接着，P2时间更短，进入CPU，抢占P1的CPU，又执行2秒。
• P3于4时刻进入就绪队列，Burst time更短，抢占P2的CPU，执行一秒结束。
• P4于5时刻进入CPU，Burst time为4，由于P2已经执行了2秒，因此它的Burst time更短，所以先执行P2，P2执行完毕，交出CPU。
• 由于P1还剩下5秒执行时间，因此先执行P4，最后执行P1。
• 周转时间（16+5+5+11）=37

平均等待时间 = （9+1+0+2）/4 = 3。
平均等待时间算法可以由（周转时间-Burst time）得出。
具体写下来就是：
（（16-7）+（5-4）+（1-1）+（6-4））=3，即（周转时间-Burst time）。

SJF算法的缺点

• CPU Burst time必须很准确，才能确定这种算法。然而实际情况下基本不可能预估准确时间。（预先通报是不可能做到的，这是一个致命问题，导致SJF算法无法实现）。

六、优先权法（Priority Scheduling）

具体要求：

• 每个进程都有一个优先数（priority number），通常是个整型数。
• 选取就绪队列（双向链表）中，优先权最高的进程。
• （最小优先数 = 最高优先权）
  1）Preemptive
  2）Nonpreemptive
• 当优先权定义为进程“需要的CPU时间”时，SJF算法就是优先权法。

优先权算法的一个缺陷：

• Issue — 进程饥饿（Starvation）
  优先权较低的就绪进程可能永远得不到CPU
• Solution — Aging思想
  就绪进程等在就绪队列里的时间，折算叠加到进程优先权。因此，等待在就绪队列里的进程，其优先权单调递增。
• 同时如果就绪队列进程过多，那么优先权低的进程也很难得到处理。

七、轮转法（Round Robin，RR）

轮转法是交互式操作系统必要的条件。（先了解相关名词）

具体步骤：

• 每个就绪进程获得一小段CPU时间（时间片，time quantum），通常10ms - 100ms
• 时间片用毕，这个进程被迫交出CPU，重新挂回到就绪队列
• 当然，进程在时间片用毕之前其Burst Cycle结束，也（主动）交出CPU
• 假设n个就绪进程，时间片q，每个就绪进程得到1/n的CPU时间。任何就绪进程最多等待（n-1）q单位时间。

举例：RR算法，时间片设定为20个单位

RR算法实例.png

• 由图可见，时间片一到，只要不是在时间片内处理完进程，那么就将交出时间片。然后回到了链表的末尾。
• 分配给同一个进程（只有一个进程）和分配给不同进程的情况有一个细微的区别：不需要做上下文切换（进程保存与转移），也就是说不需要额外开销。

轮转法的问题：
当时间片到了以后，一个进程要交出CPU。如果交给其他进程，则要做一次进程上下文切换。

时间片与上下文切换时间的关系.png

由图进行性能分析：

• 如果q很大，那么就很像FIFO算法。
• 如果q很小，那么上下文切换频繁，则额外开销太大，q必须远远大于上下文切换时间。

周转时间受时间片的影响

周转时间受时间片的影响举例.png

• 复习：周转时间 — 执行某一进程所耗用的CPU累积时间（进程进入就绪队列开始到拿到CPU执行结束为止的累积时间，其间有可能存在时间片到了或者高优先级抢占CPU的情况）。
• 当时间片大于等于6时，平均周转时间稳定在10.5。因此建议用6或者6以上的时间片长度。

轮转法还有一个好处，就是他的响应时间一定优于前面的SJF。因为时间片的存在。

八、多层队列（Multilevel Queue）

前面我们将就绪队列看成一个队列。但是队列里进程诉求是不一样的，有的进程是大块进程运算，不要求马上响应，只需要做完即可。而有的Burst Cycle非常短，但需要响应后立马做完（例如按钮）。因此这些进程如果放入一个队列，将非常不合理。

例如：

• 要求交互的进程，在前台队列。
• 可以批处理的进程，在后台队列。
• 每个队列都有其自己的调度算法，例如：
  1）前台就绪队列 — RR
  2）后台就绪队列 — FCFS

多层队列调度实例：

多层队列调度实例.png

按优先级分别为：

• 系统进程队列，要实时响应。
• 交互进程队列（要求响应非常及时）—— RR
• 交互编辑队列（人输入键盘，移动鼠标等，响应时间可能半秒也可以，对操作系统来说已经很长了。交互要求不是很高）—— RR
• 批处理进程队列，不需要交互。—— FCFS

设计多层队列：

• 就绪进程进入就绪队列时，决定去哪儿？
  答：看上图，决定他是属于哪一层的队列。
• CPU怎么在队列间分配？
  1）固定优先权法。例如，先前台队列，再后台队列。
  2）时间片办法，例如，80%的CPU时间给前台队列，20%CPU时间给后台进程。

九、多层反馈队列（Multilevel Feedback Queue）
基本上类似于多层队列算法，另外考虑了进程可以在就绪队列之间迁移。

• 如上图，可能第二层交互时由文本编辑转换到程序编译(要几秒或几分钟），于是第二层第三层可以互换。

多层反馈队列实例

多层反馈队列实例.png

• 图上三层队列：
  1）Q0 — 用RR算法，时间片8ms
  2）Q1 — 用RR算法，时间片16ms
  3）Q2 — 用FCFS算法。
• 调度场景
  1）一个就绪进程进入Q0层，当它分配到CPU，可执行8ms。如果它8ms后没有执行完毕，则迁移至Q1层。否则，它离开就绪队列该干嘛干嘛。
  2）在Q1层，当它分配到CPU，可执行16ms。如果它16ms后没有执行完毕，则迁移至Q2层。否则，它离开就绪队列，该干嘛干嘛。
  （是否合理按具体需求来，此处只是一个假设）

设计多层反馈队列

• 队列个数
• 每层队列它自己的调度算法
• 一个算法，将就绪进程升级至高层次队列
• 一个算法，将就绪进程降级至低层次队列
• 一个算法，决定当一个就绪进程进入就绪队列时，去哪层

如果算法设计OK，那么整体队列效率高，overhead就会降低。

实时调度

分为两点：

• 硬实时系统 — 调度机制能够确保一个关键任务在给定时间点前完成（快到基本上实时完成，实时性按照具体需要来）。
• 软实时计算 — 调度机制尽量给予关键任务最高优先级，尽量在预定时间点前完成。

调度算法这两点表明：
1）硬实时要求在某一时间点前必须做完，要求比较苛刻。
2）软实时要求会把关键任务尽可能提前做，但做不做完无法保证。

调度算法评估

设定指标，指标完成好，则算法优秀。

• 确定模型法 — 采用事先设定的特定负荷，计算在给定负荷下每个算法的性能。（演示用可以，但特定负荷很难设置，因为具体进程很难设定）
• 排队模型（Queueing models）（模型如果设置不得当，模型如果不准，那么调度评估就很难实现）
• 编程实现该算法，观察其执行情况（效果较差，因为哪怕效果不好，你算法已经做好了）
• 仿真

仿真

仿真模型.png

• 思路：测试数据采集可以来自于实际情况，而算法是放在一个假的系统里，让实际数据馈送到假的操作系统中去。

那么综上，CPU调度的内容就差不多结束了，接下来将要学习的会是线程的知识了。