一、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调度算法的设计

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

• 批处理系统-->多道程序设计系统-->批处理与分时的混合系统-->个人计算机-->网路服务器。
  从用户角度和系统角度对调度算法的要求是不一样的：

  
  1

调度算法的衡量指标

• 吞吐量：每单位时间完成的进程数目
• 周转时间：每个进程提出请求到运行完成的时间
• 响应时间：从提出请求到第一次回应的时间
• 其他
  • cpu利用率：cpu做有效工作的时间比例
  • 等待时间：每个进程在就绪队列中等待的时间

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

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

2.1 进程优先级（数）

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

• 静态优先级
  进程创建时指定，运行过程中不再改变

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

2.2 进程就绪队列组织

• 按优先级排队方式
  

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

• 另一种排队方式
  

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

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能力
• 进程的行为

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

• 先来先服务（FCFS-First Come First Serve）
• 最短作业优先（SJF-Shortest Job First）
• 最短剩余时间优先（FRTN-Shortest Remaining Time Next）
• 最高响应比优先（HRRN-Highest Response Ratio Next）

在批处理系统中调度算法主要考虑的是吞吐量、周转时间、cpu、公平/平衡。

3.1 先来先服务算法

• 按照进程就绪的先后顺序使用cpu
• 非抢占式
• 优点
  • 公平
  • 实现简单
• 缺点
  长进程后面的短进程需要等很长时间，不利于用户体验

4

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

5

3.2 短作业优先SJF和最短剩余时间优先

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

如果我们将短作业优先进行改进，改进为抢占式，这就是最短剩余时间优先算法了，即一个新就绪的进程比当前运行进程具有更短的完成时间，系统抢占当前进程，选择新就绪的进程执行。例如：

6

优缺点：

• 最短的平均周转时间
  在所有进程同时可运行时，采用SJF调度算法可以得到最短的平均周转时间。
• 不公平
  源源不断的短任务到来，可能使长的任务长时间得不到运行，导致产生“饥饿”现象。

3.3 最高响应比优先

• 是一个综合的算法
• 调度时，首先计算每个进程的响应比R（一个参数）；之后，总是选择R最高的进程执行。
• 响应比 = 周转时间/处理时间 = （处理时间+等待时间）/处理时间 = 1+（等待时间/处理时间）

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

• 轮转调度（RR-Round Robin）
• 最高优先级调度（HPF-Highest Priority First）
• 多级反馈队列（Multiple feedback queue）
• 最短进程优先（Shortest Process Next）

4.1 时间片轮转调度算法

7
说明：首先当前进程是B，当B的时间片用完后就被放在队列的尾部，此时当前进程就是F。

• 目标
  为短任务改善平均响应时间
• 解决问题的思路
  • 周期性的切换
  • 每个进程分配一个时间片
  • 时钟中断-->轮转

如何选择合适的时间片？

• 太长：大于典型的交互时间

  
  8
  

  就是进程所需时间小于时间片，那么就会剩余一段时间。如果大部分进程都像这样，那么此算法就退化成了先来先服务算法。同时会延长段进程的响应时间。

• 太短：小于典型的交互时间

  
  9
  

  这种情况下进程的响应时间也会延长。同时不断的切换也会浪费时间。

优缺点：

• 公平
• 有利于交互式计算，响应时间快
• 由于进程切换，时间片轮转算法要花费较高的开销

• 对不同大小的进程是有利的，但是对相同大小的进程呢？例子如下：

  
  10

小结：此算法往往不区分是I/O密集型还是cpu密集型，所以会给I/O```密集型进程带来一下不公平，下面看虚拟轮转算法。

虚拟轮转法：

11
说明：按照之前的时间片算法，对于I/O型进程时是不公平的，因为它总是用不完时间片，但是调度之后都要重新进入就绪队列进行排队，这样显然不公平。于是就设计了上图的调度算法。为I/O型进程专门设计了一个辅助队列，当一个I/O进程运行完之后不进入就绪队列，而是进入辅助队列，同时cpu也优先去调度辅助队列中的进程，知道辅助队列中为空，才去就绪队列中选择进程。

4.2 最高优先级调度算法

• 选择优先级最高的进程投入运行
• 通常：系统进程优先级高于用户进程；前台进程优先级高于后台进程；操作系统更偏好I/O型进程。
• 优先级可以是静态的，也可以动态调整，优先数可以决定优先级
• 就绪队列可以按照优先级组织
• 实现简单，但是不公平

优先级反转问题：
主要出现在基于优先级的抢占式调度算法中。表现为，一个低优先级进程持有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行。例如：

12

• 影响
  是一个系统错误；高优先级进程停滞不前，导致系统性能降低。

• 解决方案
  设置优先级上限：凡是进入临界区的进程的优先级都是最高的
  优先级继承：低优先级继承高优先级进程的优先级
  使用中断禁止：凡是进入临界区的进程都不再响应中断，直到出了临界区