第8章：处理机调度

操作系统

• 处理机调度概念
  
  • 处理机调度
  • 处理机调度时机
• 调度准则
  
  • 调度策略
  • 比较调度算法的准则

• 调度算法

  • 先进先服务算法（FCFS：First Come, First Served）
  • 短进程优先算法
    
    • SPN: Shortest Process Next
    • SJF: Shortest Job First（短作业优先算法）
    • SRT: Shortest Remaining Time（短剩余时间优先算法）
  • 最高响应比优先算法（HRRN: Highest Response Ratio Next）
  • 时间片轮转算法（RR: Round Robin）
  • 多级队列调度算法（MQ: Multilevel Queues）
  • 多级反馈队列算法（MFQ: Multilevel Feedback Queues）
  • 公平共享调度算法（FSS: Fair Share Scheduling）

• 实时调度

  • 实时操作系统
  • 可调度性
  • 实时调度算法
    
    • 速度单调调度算法（RM，Rate Monotonic)
    • 最早截止时间优先算法（EPF，Earlist Deadline First）
• 多处理器调度
• 优先级反转

8.1 处理机调度

CPU资源的时分复用

• 进程切换：CPU资源的当前占用者切换

  • 保存当前进程在PCB中的执行上下文（CPU状态）
  • 恢复下一个进程的执行上下文

• 处理机调度

  • 从就绪队列中挑选下一个占用CPU运行的进程
  • 从多个可用CPU中挑选就绪进程可使用的CPU
• 调度程序：挑选就绪进程的内核函数
  
  • 调度策略
  • 调度时机

调度时机

• 内核运行调度程序的条件
  
  • 进程从运行状态切换到等待状态
  • 进程被终结了
• 非抢占系统
  
  • 当前进程主动放弃CPU时
• 可抢占系统
  
  • 中断请求被服务例程响应完成时
  • 当前进程被抢占
    
    • 进程时间片用完
    • 进程从等待切换到就绪

8.2 调度准则

（一）调度策略

• 调度策略
  
  • 确定如何从就绪队列中选择下一个执行进程

• 调度策略要解决的问题

  • 挑选就绪队列中的哪一个进程？
  • 通过什么样的准则来选择？

• 调度算法

  • 在调度程序中实现的调度策略

• 比较调度算法的准则

  • 哪一个策略/算法较好？

调度算法的考核指标

• 处理机资源的使用模式
  
  • 进程在CPU计算和I/O操作间交替
  • 在时间片机制下，进程可能在结束当前计算前被迫放弃CPU

（二）比较调度算法的准则

• 系统利用效率角度：
  
  • CPU使用率
    
    • CPU处于忙状态的时间百分比
  • 吞吐量
    
    • 单位时间内完成的进程数量
• 用户角度：
  
  • 周转时间
    
    • 进程从初始化到结束（包括等待）的总时间
  • 等待时间
    
    • 进程在就绪队列的总时间
• 交互性应用角度：
  
  • 响应时间
    
    • 从提交请求到产生响应所花费的总时间

吞吐量与延迟

• 调度算法的要求
  
  • 希望“更快”的服务
• 什么是更快？
  
  • 传输文件时的高带宽，调度算法的吞吐量
  • 玩游戏时的低延迟，调度算法的低响应延迟
  • 这两个因素是独立的

处理机调度策略的响应时间目标

• 减少响应时间
  
  • 及时处理用户的输入请求，尽快将输出反馈给用户
• 减少平均响应时间的波动
  
  • 在交互系统中，可预测性比高差异低平均更重要
• 低延迟调度改善了用户的交互体验
• 响应时间是操作系统的计算延迟

处理机调度策略的吞吐量目标

• 增加吞吐量
  
  • 减少开销（操作系统开销，上下文切换）
  • 系统资源的高效利用（CPU，I/O设备）

• 减少等待时间

  • 减少每个进程的等待时间

• 操作系统需要保证吞吐量不受用户交互的影响

  • 操作系统必须不时进行调度，即使存在许多交互任务

• 吞吐量是操作系统的计算带宽

处理机调度策略的公平性目标

• 公平的定义

  • 保证每个进程占用相同的CPU时间
  • 保证每个进程的等待时间相同

• 公平通常会增加平均响应时间

8.3 调度算法

（一）先进先服务算法（FCFS：First Come, First Served）

• 依据进程进入就绪状态的先后顺序排列
  
  • 进程进入与等待或结束状态时，就绪队列中的下一个进程占用CPU

先进先服务算法的周转时间

例

• 3个进程，计算时间分别为12，3，3

• 任务到达顺序：P1，P2，P3

  • 执行时间：| 0 | P1 | 12 | P2 | 15 | P3 | 18|
  • 周转时间：（12+15+18）/3 = 15

• 任务到达顺序：P2，P3，P1

  • 执行时间：| 0 | P2 | 3 | P3 | 6 | P1 | 18|
  • 周转时间：（3+6+18）/3 = 9

先进先服务算法特征

• 优点

  • 简单

• 缺点

  • 平均等待时间波动较大

    • 短进程可能排在长进程后面

  • I/O资源CPU资源的利用率较低

    • CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待

（二）短进程优先算法（SPN: Shortest Process Next）

• 选择就绪队列中执行时间最短进程占用CPU进入运行状态
  
  • 就绪队列按预期的执行时间来排序

短进程优先算法特征

• 优点

  • 具有最优的平均周转时间

• 缺点

  • 可能导致饥饿

    • 连续的短进程流会使长进程无法获得CPU资源

  • 需要预知未来

    • 如何预知下一个CPU计算的持续时间？
    • 简单的解决办法：询问用户
      
      • 用户欺骗就杀死相应进程
      • 用户不知道怎么办？

短进程优先算法执行时间预估

• 用历史的执行时间来预估未来的执行时间

• τn+1 = αtn + (1-α)τn，其中 0 <= α <= 1

  • tn：第n次的CPU计算时间
  • τn+1：第n+1次的CPU计算时间预估

短剩余时间优先算法（SRT: Shortest Remaining Time）

• 短进程优先算法的可抢占改进

（三）最高响应比优先算法（HRRN: Highest Response Ratio Next）

• 选择就绪队列中响应比的R值最高的进程

• R = （w+s)/s

  • w：等待时间（waiting time）

  • s：执行时间（Service time）

  • 在短进程优先算法的基础上改进

  • 不可抢占
  • 关注进程的等待时间
  • 防止无限期推迟

（四）时间片轮转算法（RR：Round Robin）

• 时间片

  • 分配处理机资源的基本时间单元

• 算法思路

  • 时间片结束时，按先进先服务算法切换到下一个就绪进程
  • 每隔（n-1）个时间片进程执行一个时间片q

例

• 时间片为20的时间片轮转算法示例
• 4个进程的执行时间如下：
  
  • P1：53，P2：8，P3：68，P4：24
• 甘特图如下：

• 等待时间：

  • P1：（68-20）+（112-88） = 72
  • P2：（20-0）= 20
  • P3：（28-0）+（88-48）+（125-108）= 85
  • P4：（48-0）+（108-68）=88

• 平均等待时间：（72+20+85+88）/4 = 66.25

时间片长度

• 时间片轮转算法开销：

  • 额外的上下文切换（靠时钟中断强行把正在执行的进程结束掉）

• 时间片太大（进程响应时间）

  • 等待时间过长
  • 极限情况退化成先进先服务算法

• 时间片太小（系统开销）

  • 反应迅速，但产生大量的上下文切换
  • 大量上下文切换开销影响到系统吞吐量

• 时间片长度选择目标

  • 选择一个合适的时间片长度
  • 经验规则：维持上下文切换开销在1%以内

（五）多级队列调度算法（MQ: Multilevel Queues）

• 就绪队列被划分成多个独立的子队列

  • 如：前台（交互）、后台（批处理）

• 每个队列拥有自己的调度策略

  • 如：前台--RR，后台：FCFS

• 队列间的调度

  • 固定优先级

    • 先处理前台，然后处理后台
    • 可能导致饥饿

  • 时间片轮转

    • 每个队列都得到一个确定的能够调度其进程的CPU总时间
      
      • 如：80% CPU时间用于前台，20% CPU时间用于后台

（六）多级反馈队列算法（MFQ: Multilevel Feedback Queues）

• 进程可在不同队列间移动的多级队列算法
  
  • 时间片大小随优先级增加而减小
  • 如进程在当前时间片没有完成，则降到下一个优先级

多级反馈队列算法特征

• CPU密集型进程的优先级下降很快（时间片大）
• I/O密集型进程停留在高优先级（时间片小）

（七）公平共享调度算法（FSS: Fair Share Scheduling）

• 公平共享调度算法控制用户对系统资源的访问
  
  • 一些用户组比其他用户组更重要
  • 保证不重要的无法垄断资源
  • 未使用的资源按比例分配
  • 没有达到资源使用率目标的组获得更高的优先级（时间片减小）

8.4 实时调度

（一）实时操作系统

• defs：正确性依赖于其时间和功能两方面的操作系统

• 性能指标：

  • 时间约束的及时性（deadlines）
  • 速度和平均性能相对不重要

• 特征：

  • 时间约束的可预测性

实时任务

• 任务（工作单元）

  • 一次计算、一次文件读取、一次信息传递等等

• 任务属性

  • 完成任务所需要的资源
  • 定时参数

周期实时任务

• defs：一系列相似的任务

  • 任务有规律的重复
  • 周期 p = 任务请求时间间隔（ocp）
  • 执行时间 e = 最大执行时间（ocecp)
  • 使用率 U = e/p

• 硬时限（Hard deadline）

  • 错过任务时限会导致灾难性或非常严重的后果
  • 必须验证，在最坏情况下能够满足时限

• 软时限（Soft deadline）

  • 通常能满足任务时限

    • 如有时不能满足，则降低要求

  • 尽力保证满足任务时限

（二）可调度性

• defs：可调度表示一个实时操作系统能够满足任务时限要求
  
  • 需要确定实时任务的执行顺序
  • 静态优先级调度
  • 动态优先级调度

（三）实时调度算法

速度单调调度算法（RM，Rate Monotonic)

• 通过周期安排优先级
• 周期越短优先级越高
• 执行周期最短的任务

最早截止时间优先算法（EPF，Earlist Deadline First）

• 截止时间越早优先级越高
• 执行截止时间最早的任务

8.5 多处理器调度

多处理器调度特征

• 多个处理机组成一个多处理机系统
• 处理机间可负载共享

对称多处理器（SMP，Symmetric multiprocessing)调度

• 每个处理器运行自己的调度程序
• 调度程序对共享资源的访问需要进行同步

对称多处理器的进程分配

• 静态进程分配
  
  • 进程从开始到结束都被分配到一个固定的处理上执行
  • 每个处理机有自己的就绪队列
  • 调度开销小
  • 各处理机可能忙闲不均
• 动态进程分配
  
  • 进程在执行中可分配到任意空闲处理机上执行
  • 所有处理机共享一个公共的就绪队列
  • 调度开销大
  • 多处理机的负载是均衡的

8.6 优先级反置（Priority Inversion）

• 操作系统中出现高优先级进程长时间等待低优先级进程所应用资源的现象
• 基于优先级的可抢占调度算法存在优先级反置

优先级继承（Priority Inheritance）

• 占用资源的低优先级进程继承申请资源的高优先级进程的优先级
  
  • 只在占用资源的低优先级进程被阻塞时，才提高占用资源进程的优先级

优先级天花板协议（Priority ceiling protocol）

• 占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同
  
  • 不管是否发生等待，都提升占用资源进程的优先级
  • 优先级高于子系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会被阻塞