一、CPU调度的相关概念

1.1 cpu调度 其任务是控制、协调进程对cpu的竞争，即按一定的调度算法从就绪队列中选择一个进程，把cpu的使用权交给被选中的进程。如果没有就绪进程，系统会安排一个系统空闲进程或idle进程进入cpu运行。

1.2 系统场景 * N个进程就绪、等待上cpu运行 * M个cpu， M>=1 * 需要决策：给哪个进程分配哪一个cpu？

1.3 cpu调度要解决的三个问题

• 1、按什么原则选择下一个要执行的进程：调度算法
• 2、何时进行选择：调度时机
• 3、如何让被选中的进程上cpu中运行：调度过程（进程的上下文切换）

1.3.1 调度的时机

cpu在运行时会发生很多事件：

• 创建、唤醒、推出等进程控制操作
• 进程等待I/O、I/O中断
• 时钟中断，如：时间片用完、计时器到时
• 进程执行过程中出现abort异常 这些事件发生后-->当前运行的进程暂停执行-->硬件机制响应后-->进入操作系统，处理相应的事件-->结束处理后：某些进程的状态会发生变化，也可能又创建了一些新的进程-->就绪队列改变了-->需要进程调度根据预设的调度算法从就绪队列选择一个进程
  进程调度的时机有四个：
• 进程正常终止或由于某种错误终止
• 新进程创建或一个等待进程变成就绪
• 当一个进程从运行态进入阻塞态
• 当一个进程从运行态变为就绪态 总的来说调度的时机一般就是内核对中断、异常、系统调用处理后返回到用户态时。

1.3.2 调度过程（进程切换）

• 进程调度程序从就绪队列选择了要运行的进程：这个进程可以是刚刚被暂停执行的进程，也可能是另一个新的进程。
• 进程切换：是指一个进程让出处理器，由另一个进程占用处理器的过程 进程切换一般有两部分工作： * 切换全局页目录以加载一个新的地址空间 * 切换内核栈和硬件上下文，其中硬件上下文包括了内核执行新进程需要的全部信息，如cpu相关寄存器。 总的来说，切换进程包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复。 上下文切换具体步骤： 场景：进程A下cpu，进程B上cpu。 * 保存进程A的上下文环境（程序计数器、程序状态字、其他寄存器......） * 用新状态和其他相关信息更新进程A的PCB * 把进程A移至合适的队列（就绪、阻塞......） * 将进程B的状态设置为运行态 * 从进程B的PCB中恢复上下文（程序计数器、程序状态字、其他寄存器......） 上下文切换的开销： * 直接开销：内核完成切换所用的cpu时间 * 保存和恢复寄存器.... * 切换地址空间（相关指令开销较大） * 间接开销 * 高速缓存（Cache）、缓冲区缓存（Buffer Cache）和TLB（Translation Lookup Buffer）失效。

1.3.3 cpu调度算法的设计

什么情况下需要仔细斟酌调度算法？

• 批处理系统-->多道程序设计系统-->批处理与分时的混合系统-->个人计算机-->网路服务器。 从用户角度和系统角度对调度算法的要求是不一样的：
  
  
  
  调度算法的衡量指标
• 吞吐量：每单位时间完成的进程数目 * 周转时间：每个进程提出请求到运行完成的时间
• 响应时间：从提出请求到第一次回应的时间
• 其他
  • cpu利用率：cpu做有效工作的时间比例
  • 等待时间：每个进程在就绪队列中等待的时间 #

二、设计调度算法前的要点

• 进程控制块中需要记录哪些与cpu调度有关的信息
• 进程优先级就绪队列的组织
• 抢占式调度与非抢占式调度
• I/O密集型与cpu密集型进程
• 时间片

2.1 进程优先级（数）

优先级和优先数是不同的，优先级表现了进程的重要性和紧迫性，优先数实际上是一个数值，反映了某个优先级。

• 静态优先级 进程创建时指定，运行过程中不再改变
• 动态优先级 进程创建时指定了一个优先级，运行过程中可以动态变化。如：等待时间较长的进程可提升其优先级。

2.2 进程就绪队列组织

• 按优先级排队方式

  
  
  

说明：创建多个进程后按照不同的优先级进行排列，cpu调度优先级较高的进程进行执行。

• 另一种排队方式

  
  
  

说明：所有进程创建之后都进入到第一级就绪队列，随着进程的运行，可能会降低某些进程的优先级，如某些进程的时间片用完了，那么就会将其降级。

2.3 占用cpu的方式 通常有两种方式，即抢占式和非抢占式。

• 抢占式（可剥夺式）
  当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的cpu，提供给具有更高优先级的进程使用。
• 不可抢占式
  某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。

2.4 I/O密集型与cpu密集型进程 按进程执行过程中的行为划分：

• I/O密集型或I/O型（I/O-bound） 频繁的进程I/O，通常会花费很多时间等待I/O操作的完成。
• cpu密集型或cpu型或计算密集型（cpu-bound） 需要大量的cpu时间进行计算

2.5 时间片（Time slice或quantum）

一个时间段，分配给调度上cpu的进程，确定了允许该进程运行的时间长度。那么如何选择时间片？有一下需要考虑的因素：

• 进程切换的开销
• 对响应时间的要求
• 就绪进程个数
• cpu能力
• 进程的行为

三、批处理系统中常用的调度算法

引起低级调度的原因
有四种情况都会发生CPU调度
当一个进程从运行态切换成等待态时
当一个进程从运行态切换成就绪态时
当一个进程从等待态切换成就绪态时
当一个进程中止时。也就是说当一个进程由运行状态变为非运行状态
或者一个进程变为就绪状态时都会引起低级调度
.

• 先来先服务（FCFS-First Come First Serve） (作业调度,进程调度)
• 最短作业优先（SJF-Shortest Job First） (作业调度,进程调度)
• 最短剩余时间优先（FRTN-Shortest Remaining Time Next）
• 最高响应比优先（HRRN-Highest Response Ratio Next）
  在批处理系统中调度算法主要考虑的是吞吐量、周转时间、cpu、公平/平衡。

3.1 先来先服务算法

• 按照进程就绪的先后顺序使用cpu
• 非抢占式
  • 优点
    • 公平
    • 实现简单

  • 缺点
    长进程后面的短进程需要等很长时间，不利于用户体验

    
    
    
    
    

    那能否改变调度顺序来提供效率呢？

    
    
    

3.2 短作业优先SJF和最短剩余时间优先(作业调度,进程调度)

• 具有最短完成时间的进程优先执行

• 非抢占式
  如果我们将短作业优先进行改进，改进为抢占式，这就是最短剩余时间优先算法,例如
  

  
  
  优缺点：

• 最短的平均周转时间
  在所有进程同时可运行时，采用SJF调度算法可以得到最短的平均周转时间

• 不公平
  源源不断的短任务到来，可能使长的任务长时间得不到运行，导致产生“饥饿”现象

3.3 最高响应比优先 (重点)

• 一个综合的算法
  调度时，首先计算每个进程的响应比R
  之后，总是选择R最高的进程执行。

• 响应比 = 周转时间/处理时间 = （处理时间+等待时间）/处理时间 = 1+（等待时间/处理时间）

四、交互式系统的调度算法

• 轮转调度（RR-Round Robin）

• 最高优先级调度（HPF-Highest Priority First）

• 多级反馈队列（Multiple feedback queue）

• 最短进程优先（Shortest Process Next） ## 4.1 时间片轮转调度算法
  

  
  
  说明：首先当前进程是B，当B的时间片用完后就被放在队列的尾部，此时当前进程就是F。 * 目标 为短任务改善平均响应时间 * 解决问题的思路 * 周期性的切换 * 每个进程分配一个时间片 * 时钟中断-->轮转 如何选择合适的时间片？ * 太长：大于典型的交互时间
  
  
  
  就是进程所需时间小于时间片，那么就会剩余一段时间。如果大部分进程都像这样，那么此算法就退化成了先来先服务算法。同时会延长段进程的响应时间。 * 太短：小于典型的交互时间
  
  
  
  这种情况下进程的响应时间也会延长。同时不断的切换也会浪费时间。 优缺点： * 公平 * 有利于交互式计算，响应时间快 * 由于进程切换，时间片轮转算法要花费较高的开销 * 对不同大小的进程是有利的，但是对相同大小的进程呢？例子如下：
  
  
  
  小结：此算法往往不区分是I/O密集型还是cpu密集型，所以会给I/O```密集型进程带来一下不公平，下面看虚拟轮转算法。 虚拟轮转法：
  
  
  
  说明：按照之前的时间片算法，对于I/O型进程时是不公平的，因为它总是用不完时间片，但是调度之后都要重新进入就绪队列进行排队，这样显然不公平。于是就设计了上图的调度算法。为I/O型进程专门设计了一个辅助队列，当一个I/O进程运行完之后不进入就绪队列，而是进入辅助队列，同时cpu也优先去调度辅助队列中的进程，知道辅助队列中为空，才去就绪队列中选择进程。 ## 4.2 最高优先级调度算法 * 选择优先级最高的进程投入运行 * 通常：系统进程优先级高于用户进程；前台进程优先级高于后台进程；操作系统更偏好I/O型进程。 * 优先级可以是静态的，也可以动态调整，优先数可以决定优先级 * 就绪队列可以按照优先级组织 * 实现简单，但是不公平 优先级反转问题： 主要出现在基于优先级的抢占式调度算法中。表现为，一个低优先级进程持有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行。例如：
  
  

• 影响 是一个系统错误；高优先级进程停滞不前，导致系统性能降低。 * 解决方案 设置优先级上限：凡是进入临界区的进程的优先级都是最高的 优先级继承：低优先级继承高优先级进程的优先级 使用中断禁止：凡是进入临界区的进程都不再响应中断，直到出了临界区

五、多级反馈队列调度算法(重点)

• UNIX的一个分支BSD5.3版所采用的调度算法
• 一个综合调度算法（折中权衡）
• 设置多个就绪队列，第一级队列优先级最高
• 给不同就绪队列的进程分配长度不同的时间片，第一级队列时间片最小；随着队列优先级别的降低，时间片增大。
• 当第一级队列为空时，就在第二级队列调度，以此类推
• 各级队列按照时间片轮转方式进行调度
• 当一个新创建进程就绪后，进入第一级队列
• 进程用完时间片而放弃cpu，进入下一级就绪队列
• 由于阻塞而放弃cpu的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列

以上所说都是属于非抢占式的，如果允许抢占，则当有一个优先级更高的进程就绪时，可以抢占cpu，被抢占的进程回到原来一级就绪队列的末尾。

各种调度算法的比较

七、多处理器调度算法设计

• 不仅要决定选择哪一个进程执行，还需要决定在哪一个cpu上执行
• 要考虑进程在多个cpu之间迁移时的开销
  1、高速缓存失效、TLB失效
  2、尽可能使进程总是在同一个cpu上执行
  • 如果每个进程可以调度到所有cpu上，假如进程上次在cpu1上执行，本次被调度到cpu2，则会增加高速缓存失效、TLB失效；如果每个进程尽量调度到指定的cpu上，各种失效就会减少。
• 考虑负载均衡问题

7.1 典型系统所采用的调度算法

• UNIX： 动态优先数法
• BSD5.3：多级反馈队列法
• Linux：抢占式调度
• Windows：基于优先级的抢占式多任务调度
• Solaris：综合调度算法

7.2 Windows线程调度

• 调度单位是线程
• 采用基于动态优先级的、抢占式调度，结合时间配额的调整

基本思想：

• 就绪线程按优先级进入相应的队列
• 系统总是选择优先级最高的就绪线程运行
• 同一优先级的各线程按时间片轮转进行调度
• 多cpu系统中允许多个线程并行运行

引发线程调度的条件：
之前我们提到了四个条件：

• 线程正常终止或由于某种错误而终止
• 新线程创建或一个等待的线程变成就绪
• 当一个线程从运行态进入阻塞态
• 当一个线程从运行态变为就绪态

这里还有两个条件：

• 一个线程的优先级改变
• 一个线程改变了它的亲和（Affinity）处理机集合（比如允许一个线程在多个处理机上执行，但是如果其他的处理机空闲，则此线程也不能在其上进行执行）

Windows线程优先级：

• 分成了三类：

  <div class="image-package">

  <div class="image-caption">3</div>

  </div>

线程的时间配额：

• 时间配额不是一个时间长度值，而一个称为配额单位的整数
• 一个线程用完了自己的时间配额时，如果没有其他相同优先级的线程，Windows将重新给该线程分配一个新的时间配额，让它继续执行。实质就是不会一定让一个线程一直运行直到其结束，首先给其分配一个时间配额，运行完之后再次检查，如果没有运行完则再次分配时间配额，让其运行，这个过程不是连续的，是有间断的。

时间配额的一种特殊作用：

• 假设用户首先启动了一个运行时间很长的电子表格计算程序，然后切换到一个游戏程序（需要复杂图形计算并显示，是CPU型）
• 如果前台的游戏进程提高它的优先级，则后台的电子表格计算进程就几乎得不到CPU时间了
• 但增加游戏进程的时间配额，则不会停止执行电子表格计算，只是给游戏进程的CPU时间多一些而已。

调度策略：

• 主动切换
  某个线程可能在运行过程中需要输入输出，此时进入阻塞态，此时cpu会选择新的线程进行执行。
• 抢占
  如果上面所说的阻塞线程被唤醒，同时其优先级又更高，那么就会去抢占执行。当线程被抢占时，它被放回相应优先级的就绪队列的队首
  • 处于实时优先级的线程在被抢占时，时间配额被重置为一个完整的时间配额
  • 处于可变优先级的线程在被抢占时，时间配额不变，重新得到cpu后将运行剩余的时间配额
    这里的实时优先级和可变优先级有什么区别？？？？难道实时优先级就是按创建顺序产生的优先级，而可变优先级就是优先级可变的？
• 时间配额用完
  假设线程A的时间配额用完
  • A的优先级没有降低
    1、如果队列中有其他就绪线程，选择下一个线程执行，A回到原来的就绪队列末尾
    2、如果队列中没有其他就绪线程，系统会给A重新分配时间配额，让其继续执行
  • A的优先级降低，此时Windows将选择一个更高优先级的线程执行

线程优先级提升与时间配额调整：
为什么一个线程的时间配额用完后其优先级会被降低，这是因为之前此线程的优先级被提升过。

• Windows的调度策略
  • 如果体现对某类线程具有倾向性？
  • 如何解决由于调度策略中潜在的不公平性而带来的饥饿现象？
  • 如何改善系统吞吐量、响应时间等整体特征？
• 解决方案
  • 提升线程的优先级
    下列五种情况，Windows会提升线程的当前优先级：
    1、I/O操作完成
    2、信号量或事件等待结束
    3、前台进程中的线程完成了一个等待操作
    4、由于窗口活动而唤醒窗口线程
    5、线程处于就绪态超过了一定的时间还没有运行（即“饥饿”现象）
    在Windows中线程优先级的提升只是针对可变优先级范围内（1-15）的线程优先级
  • 给线程分配一个很大的时间配额

几个线程优先级提升的例子：
1、I/O操作完成后的线程优先级提升

• 在完成I/O操作后，Windows将临时提升等待该操作线程的优先级，保证该线程能更快上CPU运行进行数据处理

• 优先级的提升值由设备驱动程序决定，提升建议值保存在系统文件“Wdm.h”或“Ntddk.h”中

• 优先级的提升幅度与对I/O请求的响应时间要求是一致的，响应时间要求越高，优先级提升幅度越大

• 设备驱动程序在完成I/O请求时通过内核函数IoCompleteRequest来指定优先级提升的幅度

• 为避免不公平，在I/O操作完成唤醒等待线程时会将该线程的时间配额减一

• 2、饥饿线程的优先级提升

• 系统线程“平衡集管理器”每秒钟扫描一次就绪队列，发现是否存在等待时间超过300个时钟中断间隔的线程

• 平衡集管理器将这些线程的优先级提升到15，并分配给它一个长度为正常值的4倍的时间配额

• 当被提升的线程用完它的时间配额后，立即衰减到原来的基本优先级

</div>