CPU调度

CPU调度是指多任务操作系统的基础，目的是使得CPU尽可能用于执行指令，从而提高CPU效率。

CPU调度可分为三种，长程调度、中程调度、短程调度。

有些进程状态的改变需要CPU的干预，因为进程间存在竞争，需要操作系统选择一个进程来进行这种转换。

长程调度

“道”（有的也叫“度”）：允许在内存运行的最多进程数。
并不是每个用户创建的进程都能马上被装入内存去运行。每个用户创建进程的初始状态是“新建”，处于新建状态的进程一般首先被放到外存的进程池中，操作系统的调度程序才从新建状态选择一个进入内存并转换为就绪状态。这种从“新建”转换到“就绪”状态的操作就是长程调度，又称为作业调度或高级调度。

短程调度

又称为CPU调度或低级调度。在就绪队列中可能存在不止一个进程，当CPU空闲时，操作系统需要从就绪队列中挑选一个进程让它运行。

长程调度 VS 断层调度

相比物	切换频率角度	切换开销角度	操作系统中
短程调度	频率高、速度快	开销小（毫秒级，切换快）	必需
长程调度	频率低、速度慢	开销大（秒/分级，切换慢）	可选

中程调度（交换）

即一个进程在内存和外存间的换进换出，最大的目的是节省内存。

从本质上讲，中程调度不属于进程管理的内容，而应该属于内存管理。

当一个进程在内存中长期不运行时，会造成内存浪费。把这些进程从内存换到外存，从而腾出内存空间供运行进程使用。反之，当一个外存的进程接下来需要运行时，操作系统则执行换入操作，把这个进程从外存换入内存。

为了方便进行CPU调度，操作系统需要对不同状态的进程进行组织和管理。为此，为某些特定的状态设立了一个或多个进程队列，用于管理这些进程。

进程调度队列

就绪队列：在主内存中处于就绪状态并等待执行的所有进程集合；
设备队列：等待某一I/O设备的进程队列

进程的执行过程实际上就是进程在各种队列之间的迁移。

就绪队列和各种I/O设备队列如下图：

CPU调度过程

1. 调度程序（Scheduler）
   根据某种策略选择一个就绪进程。一个CPU同时只能运行一个进程。
2. 分派程序（Dispatcher）
   负责把CPU的控制权转交CPU调度程序；切换上下文；切换到用户态；跳转到用户程序的适当位置并重新运行之。

具体过程如下：
① 利用定时器把CPU的控制权转交给CPU调度程序，让调度程序选择一个需要运行的进程；
② 进行进程的上下文切换，把该进程从就绪状态转换到运行状态；
③ 系统切换到用户态，跳转到用户程序的适当位置并重新运行之。

分派延迟——分派程序终止一个进程的运行并启动另一个进程运行所花的时间。

调度方式

（1）非抢占调度

• 一旦把CPU分配给某进程后，系统不可以抢占已分配的CPU并分配给其他进程；
• 只有进程自愿释放CPU，才可把CPU分配给其他进程；
• 优点：易实现，调度开销小，适合批处理系统；
• 缺点：响应时间长，不适合交互式系统。

（2）抢占调度

• 调度程序可根据某种原则暂停某个正在执行的进程，将已分配给它的CPU重新分配给另一进程。
• 可防止单一进程长时间独占CPU；
• 系统开销大；

两种调度方式的区别在于运行进程是否是自愿放弃CPU。

CPU调度时机

CPU调度可能发生在当一个进程：

1. 从运行转到等待（非抢占式）
2. 从运行转到就绪（抢占式）
3. 从等待转到就绪（抢占式）
4. 终止运行（非抢占式）

CPU调度准则——基本指标

• CPU利用率——固定时间内CPU运行时间的比例
• 吞吐量——单位时间内运行完的进程数
• 周转时间——进程从提交到运行结束的全部时间
• 等待时间——进程等待调度（不运行）的时间片总和
• 响应时间——从进程提交到首次运行（不是输出结果）的时间段，也就是第一段的等待时间。

周转时间=等待时间+运行时间
响应时间<=等待时间

调度准则——优化方法

• 最大的CPU利用率
• 最大的吞吐量
• 最短的周转时间
• 最短的等待时间
• 最短的响应时间

解决方法：

• 调度算法：就绪队列中哪个进程被选中运行。

调度算法

先来先服务调度算法（FCFS）

调度策略

按进程请求CPU的先后顺序使用CPU。

所谓甘特图主要用于项目管理，将活动与时间联系起来，在此，是将进程的运行与时间联系起来，可直观显示进程运行情况。

周转时间：进程从提交到运行结束的时间；
等待时间=周转时间-运行时间；
响应时间：从进程提交到首次运行的时间段。

P₁、P₂、P₃都是在0提交，所以
周转时间：P₁=24; P₂=27; P₃=30     平均周转时间：（24+27+30）/3=27
等待时间：P₁=0; P₂=24; P₃=27     平均等待时间：（0+24+27）/3=17
响应时间：P₁=0; P₂=24; P₃=27     平均响应时间：（0+24+27）/3=17

算法特点

1. 实现简单，可使用FIFO队列实现
2. 非抢占式调度（进程一旦获得CPU，就始终占有CPU，直到该进程运行完一个时间片）
3. FCFS调度算法是公平的
4. 适用于长程调度，后台批处理系统的短程调度。
5. FCFS对长CPU脉冲的进程有利，对短CPU脉冲不利。意思是当一个长进程后面的多个短进程，让长进程先执行，会让后面的短进程等待较长时间，从而导致CPU和设备利用率降低（护航效果）。

等待时间：P1=6; P2=0; P3=3     平均等待时间：（6+0+3）/3=3
周转时间：P1=30; P2=3; P3=6     平均周转时间：（30+3+6）/3=13

比前例好得多，前例结果（护航效果）的产生是由于长进程先于短进程到达。

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

关联到每个进程下次运行的CPU区间长度，调度最短的进程

两种模式：

• 非抢占式调度——一旦进程拥有CPU，它的使用权限只能在该CPU区间结束后让出；
• 抢占式调度——发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度，简写为SRTF。

SJF是最优的——对一组指定的进程而言，它给出了最短的平均等待时间。但是存在饥饿问题。例如，一个长进程很早就加入就绪队列，但是不断地有短进程加入就绪队列，长进程可能一直得不到运行。

非抢占式短作业优先(SJF)例子：

平均等待时间：（0+6+3+7）/4=4
平均周转时间：（7+10+4+11）/4=8

抢占式短作业优先（SJF）例子：

平均等待时间：（9+1+0+2）/4=3
平均周转时间：（16+5+1+6）/4=7
平均响应时间：（0+0+0+2）/4=0.5

抢占式比非抢占式有更短的等待时间，开销更大。

SJF算法在进程中实现的困难是如何知道进程下一个CPU区间的长度？
SJF通常用于长程（作业）调度；
指数估算法：假设下一个区间长度与以前的相似，通过先前的CPU区间长度及其指数平均进行预测。

公式中，t_n为第n个区间长度的实际值，τ_n+1为下一次区间长度的预测值，参数a大于等于0小于等于1.

FCFS和SJF主要适用于长程调度。

---

优先级调度算法（PR）

调度策略：
为每个进程分配一个优先数，该数值为整数。然后按照进程的优先数来分配使用CPU。
是数字大先运行还是数字小先运行，由各个系统默认确定。

在本书中，优先数越小，优先级越高，也就是说，具有最小优先数的进程具有最高优先级。
就绪队列的排队策略是优先级高在前。优先级低在后。

调度模式

• 抢占式调度
  当一个比正在运行选程的优先级高的选程加入就绪队列后，该进程将抢占正在运行进程的CPU。
• 非抢占式调度
  例子：

平均等待时间：（6+0+16+18+1）/5=8.2

优先调度算法最重要的一点是优先级的设置。
可以参考不同的因素来设置。如时间极限、内存要求、进程重要性等；同时该值可以静态不变，也可以动态调整。
优先级可分为两类：

• 静态优先级
  进程创建时确定，在运行期间不变；
  简单易行，系统开销小；
  不够精确，可能会出现饥饿问题。

• 动态优先级
  进程创建时的优先级随进程推进或等待时间增加而改变，以便获得更好的调度性能。

高响应比优先调度算法

既考虑进程的等待时间，又考虑进程的运行时间等待时间
优先数=响应比R_p=等待时间/运行时间

• 如等待时间相同，运行时间越短，优先级越高，类似于SJF
• 如运行时间相同，优先级取决于其等待时间，类似于FCFS
• 长进程的优先级可随等待时间的增加而提高，最终可得到服务

缺点：每次调度之前，都需要计算响应比，增加系统开销。
优点：实现简单；考虑了选程的紧迫程度；灵活；可模拟其它算法
存在问题：饥饿-低优先级的进程可能永远得不到运行。
解决方法：老化一延长进程等待时间以提高其优先数。

时间片轮转调度算法（RR）

原理

把一段时间分割成若干个小碎片，每个需要运行的进程获得一个碎片运行。也就是在这段时间内，每个进程都得到运行。
分时系统同时有多个用户在使用计算机，时间片轮转算法可以满足用户对响应时间的要求。

时间片：小单位的CPU时间，通常为10-100毫秒。

调度：
为每个进程分配不超过一个时间片的CPU。时间片用完后，该进程将被插入就绪队列末尾。
假如就绪队列中有n个选程、时间片为q。则但何一个选程的等待时间不会超过（n-1）*q。

极端情况：
时间片非常大，那么RR算法等同于FCFS算法。
时间片很小，如1ms。那么该算法相当于共享处理器，会增加进程的上下文切换时间，也就是系统的开销会变大。

---

多级队列调度（MLQ）

不同类型的进程需要不同的策略，交互进程需要短的响应时间，批处理进程需要短的等待时间。

多级队列调度：系统中存在多个就绪队列，每个队列有自己的调度算法

要素：队列数、每一队列的调度算法、决定新进程将进入哪个队列的方法。

典型例子：
就绪队列分为：

• 前台（交互式）
• 后台（批处理）

每个队列有自己的调度算法

• 前台——RR
• 后台——FCFS

问题：先解决哪个队列中的进程呢？
解决方法：

• 固定优先级：前台运行完后再运行后台，有可能产生饥饿
• 给定时间片：每个队列得到一定比例的CPU时间，进程在给定时间内执行；如：80%时间执行前台RR，20%时间执行后台FCFS

多级反馈队列调度（MLFQ）

是多级队列的延伸。

不同：

• 多级队列：进程不能在不同队列间移动（即多级队列调度算法中一旦一个进程进入了某个队列，那么它在运行过程中不能加入其它队列）
• 多级反馈队列：进程能在不同队列间移动

多级反馈队列调度需要考虑以下问题：

• 队列数
• 每一队列的调度算法
• 决定进程升级（低级队列到高级队列）的方法
• 决定进程降级（高级队列到低级队列）的方法
• 决定新进程将进入哪个队列的方法

MLFQ很好地解决了CPU调度问题。Unix，Solaris，Windows的调度算法一定程度上都是MLFQ的变种。

多级反馈队列调度例子

三个队列：
Q₀——时间片为8毫秒
Q₁——时间片为16毫秒
Q₂——FCFS

调度策略：

• 新进程进入Q₀队列，得到CPU时间片8毫秒，如果不能在该时间片内完成，将被移动到队列Q₁；Q₀内的进程采用FCFS算法；
• 进程在Q₁队列得到CPU时间片16毫秒，如果还不能完成，将被移至队列Q₂；Q₁内的进程采用FCFS算法；
• 进入Q₂的进程将采用FCFS算法一次运行完

MLFQ需要考虑的5个问题

1. 该算法由3个队列；
2. 每个队列均采用FCFS算法；
3. 新进程均进入Q₀；
4. 降级的方法是每个队列只运行每一次；
5. 没有升级方法。

从图中可以发现，如果一个选程的CPU脉冲时间小于等于8ms，则该进程在进入Q₀后就可以一次运行完；
如果一个选程CPU脉冲时间大于8ms小于等于24ms，则选入Q₀运行一次后降级到Q₁。并在Q₁中一次运行完；
如果一个进程CPU脉冲时间大于24ms，则进入Q₀运行一次后降级到Q₁，并在Q₁中运行一次后降级到Q₂，并在Q₂中一次运行完。

以上讨论的都是单核单处理器系统的调度方法。

多处理器调度方法

从调度算法而言，多处理器调度方法沿用单处理器的调度方法。

多处理器架构有两种：

对称多处理器（SMP），非对称多处理器（ASMP）。

SMP是目前的主流多处理器架构，每个处理器决定自己的调度方案。
ASMP中，一般仅一个处理器能处理系统数据结构，减轻对数锯的共享需求。

负载平衡：将任务平均分配给各个处理器。

亲和性：

进程在某个给定的CPU上尽量长时间地运行而不被迁移到其他处理器的倾向性。

为了让CPU运行更快，CPU中存在高速缓存Cache，它的容量比主存小，但是存取速度快，所以每次CPU获取指令或数据时，都先从Cache中读，读不到再从主存中加载到Cache。
根据Cache的时间局部性和空间局部性，每次加载将要执行的指令附近的数据，以及将数据保存到Cache中，就能让CPU Cache保存的命中率高，从而加速CPU的运行。

多核处理器可能存在Cache一致性的问题。

亲和性的解决方法：

• 软亲和性：进程通常不会在处理器之间频繁迁移
• 硬亲和性：进程不会在处理器之间迁移
• 例子：Linux的task_struct
  与亲和性相关的是cpus_allowed位掩码；
  该位掩码由n位组成，与系统中n个逻辑处理器一一对应，1表示进程可在对应处理器上运行

单队列调度方法（SQMP）

单队列多核调度方法（single-Queue MuliProcessor Scheduling）

• 系统有一个就绪队列
• 当任意一个CPU空闲时，就从就绪队列中选择一个进程到该CPU上运行

优点：

• 容易从单核调度算法推广到多核/多处理器
• 实现简单，负载均衡

缺点：

• 不具有亲和性，一个进程可能在不同时候被调度到不同的CPU；
• 多核同时访问一个队列，会有加锁问题，从而严重影响调度的性能。

多队列调度方法（MQMP）

多队列调度方法（wMulti-Queue MultiProcessor Scheduing）

• 系统有多个就绪队列，每个CPU一个
• 每个就绪队列有自己的调度算法，并且调度相对独立

优点：亲和性好，不需要加锁；
缺点：负载不均衡。

解决策略：“偷”进程。负载较低的CPU会定时偷看一下其他CPU的就绪队列，如果是，会选择性的偷几个过来，这样使得计算机负载相对均衡。

一章没有啦，感觉就像一个莫得感情的搬运机器T^T