06 调度 | 《操作系统》笔记

这一系列是操作系统 (清华大学向勇、陈渝)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

背景

• 上下文切换
  • 切换 CPU 的当前任务，从一个进程/线程到另一个
  • 保存当前进程/线程在 PCB/TCP 中的执行上下文（CPU 状态）
  • 读取下一个进程/线程的上下文
• CPU 调度
  • 从就绪队列中挑选一个进程/线程作为 CPU 将要运行的下一个进程/线程
  • 调度程序：挑选进程/线程的內核函数（通过一些调度策略）
• 内核运行调度程序的条件（满足一条即可）
  • 一个进程从运行状态切换到等待状态
  • 一个进程被终结了
• 不可抢占（内核态、用户态）
  • 调度程序必须等待事件结束
• 可以抢占（内核态、用户态）
  • 调度程序在中断被响应后执行
  • 当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪
  • 当前运行的进程可以被换出
• 内核态和用户态的抢占和不可抢占是操作系统的设计模式
  • 见“计算机基础”笔记本

调度原则

• 程序执行模型
  • 执行模型：程序在 CPU 突发和 I/0 突发中交替
    • 每个调度决定都是关于在下一个 CPU 突发时将哪个工作交给 CPU
    • 在时间分片机制下，线程可能在结束当前 CPU 突发前被迫放弃 CPU
• 比较调度算法的准则
  • CPU 使用率：CPU 处于忙状态所占时间的百分比
  • 吞吐量：在单位时间内完成的进程数量
  • 周转时间：个进程从初始化到结束,包括所有等待时间所花费的时间
  • 等待时间：进程在就绪队列中的总时间
  • 响应时间：从一个请求被提交到产生第一次相应所花费的总时间
• 吞吐量与延迟
  • 人们通常都需要“更快”的服务
    • 什么是更快？
      • 传输文件时的高带宽
      • 玩游戏时的低延迟
      • 这两个因素是独立的
    • 和水管类比
      • 低延迟：喝水的时候想要一打开水龙头水就流出来
      • 高带宽：给游泳池充水时希望从水龙头里同时流岀大量的水，并且不介意是否存在延迟
  • 解决方法
    • 减少响应时间
      • 及时处理用户的输出并且尽快将输出提供给用户
    • 减少平均响应时间的波动
      • 在交互系统中，可预测性比高差异低平均更重要
    • 增加吞吐量
      • 减少开销（操作系统开销、上下文切换）
      • 系统资源的高效利用（CPU、I/O 设备）
    • 减少等待时间
      • 减少每个进程的等待时间
  • 操作系统的吞吐量与带宽
    • 低延迟调度增加了交互式表现
      • 如果移动了鼠标，但是屏幕中的光标却没动，我可能会重启电脑
    • 但是操作系统需要保证吞吐量不受影响
      • 我想要结束长时间的编程，所以操作系统必须不时进行调度，即使存在许多交互任务
    • 吞吐量是操作系统的计算带宽
    • 响应时间是操作系统的计算延迟
• 公平的目标
  • 举例
    • 保证每个进程占用相同的 CPU 时间
    • 这公平么？如果一个用户比其他用户运行更多的进程怎么办
  • 举例
    • 保证每个进程都等待相同的时间
  • 公平通常会增加平均响应时间

调度算法

• FCFS(先来先服务, First Come First Served）
  • 
  • 优点
    • 简单
  • 缺点
    • 平均等待时间波动较大
    • 花费时间少的任务可能排在花费时间长的任务后面
    • 可能导致 I/0 和 CPU 之间的重叠处理
      • CPU 密集型进程会导致 I/O 设备闲置时，I/O 密集型进程也在等待
• SPN/SJF/SRT(短进程优先/短作业优先/短剩余时间优先, Shortest Process Next/Shortest Job First/Shortest Remaining Time)
  • 选择下一个最短的进程（短任务优先），按照预测的完成时间来将任务入队
  • 
  • 可以是可抢占的或者不可抢占的
    • 不可抢占的是 SPN/SJF
    • 可抢占的是 SRT
  • 优点
    • 最优平均等待时间（考虑一组进程的 SPN 执行）
  • 缺点
    • 可能导致饥饿
      • 连续的短任务流会使长任务饥饿
      • 短任务可用时的任何长任务的 CPU 时间都会增加平均等待时间
    • 需要预知未来
      • 怎么预估下一个 CPU 突发的持续时间
      • 简单的解决办法：询问用户
      • 如果用户欺骗就杀死进程
      • 如果用户不知道怎么办
• HRRN(最高响应比优先, Highest Response Ratio Next)
  • 在 SPN 调度的基础上改进
  • 不可抢占
  • 关注进程等待了多长时间
  • 防止无限期推迟
  • 
• Round Robin(轮循，使用时间切片和抢占来轮流执行任务)
  • 方法
    • 在叫作量子（或时间切片）的离散单元中分配处理器
    • 时间片结束时，切换到下一个准备好的进程
    • 
    • 
  • 时间量子设置
    • 花销
      • 额外的上下文切换
    • 时间量子太大
      • 等待时间过长
      • 极限情况退化成 FCFS
    • 时间量子太小
      • 反应迅速，但是吞吐量由于大量的上下文切换开销受到影响
    • 目标
      • 选择一个合适的时间量子
    • 经验规则
      • 维持上下文切换开销处于 1% 以内
• Multilevel Feedback Queues(多级反馈队列，优先级队列中的轮循)
  • 多级队列
    • 就绪队列被划分成独立的队列，如：前台（交互），后台（批处理）
    • 每个队列拥有自己的调度策略，如：前台-RR，后台-FCFS
    • 调度必须在队列间进行
      • 固定优先级
        • 先处理前台，然后处理后台
        • 可能导致饥饿
      • 时间切片
        • 每个队列都得到一个确定的能够调度其进程的 CPU 总时间
        • 如：80% 给使用 RR 的前台，20% 给使用 FCFS 的后台
  • 一个进程可以在不同的队列中移动
  • 例如：n 级优先级——优先级调度在所有级别中，RR 在每个级别中：
    • 时间量子大小随优先级级别增加而增加
    • 如果任务在当前的时间量子中没有完成,则降到下一个优先级
  • 
  • 优点
    • CPU 密集型任务的优先级下降很快
    • I/O 密集型任务停留在高优先级
• Fair Share Scheduling(公平共享调度)
  • 一些用户组比其他用户组更重要
  • 保证不重要的组无法垄断资源
  • 未使用的资源按照每个组所分配的资源的比例来分配
  • 没有达到资源使用率目标的组获得更高的优先级

实时调度

• 实时系统
  • 定义
    • 正确性依赖于其时间和功能两方面的一种操作系统
  • 性能指标
    • 时间约束的及时性(deadlines)
    • 速度和平均性能相对不重要
  • 主要特性
    • 时间约束的可预测性
  • 强实时系统
    • 需要在保证的时间內完成重要的任务，必须完成
  • 弱实时系统
    • 要求重要的进程的优先级更高，尽量完成，并非必须
  • 硬时限
    • 如果错过了最后期限，可能会发生灾难性或非常严重的后果
    • 必须验证：在最坏的情况下也能够满足时限吗？
    • 保证确定性
  • 软时限
    • 理想情况下，时限应该被最大满足
    • 如果有时限没有被满足，那么就相应地降低要求
    • 尽最大努力去保证
• RM(Rate Monotonic)速率单调调度
  • 最佳静态优先级调度
  • 通过周期安排优先级
  • 周期越短优先级越高
  • 执行周期最短的任务
• EDF(Earliest Deadline First)最早期限调度
  • 最佳的动态优先级调度
  • Deadline 越早优先级越高
  • 执行 Deadline 最早的任务

多处理器调度

• 多处理器的 CPU 调度更加复杂
  • 多个相同的单处理器组成一个多处理器
  • 优点：负载共享
• 对称多处理器(SMP)
  • 每个处理器运行自己的调度程序
  • 需要在调度程序中同步

优先级反转

• 可以发生在任何基于优先级的可抢占的调度机制中
• 当系统内的环境强制使高优先级仼务等待低优先级任务时发生
• 优先级天花板：“资源”的优先级和“所有可以锁定该资源的任务中优先级最高的那个任务”的优先级相同
• 除非优先级高于系统中所有被锁定的资源的优先级上限，否则任务尝试执行临界区的时候会被阻塞
• 持有最高优先级上限信号量锁的任务，会继承被该锁所阻塞的任务的优先级