Lec 11 处理器调度

License

本内容版权归上海交通大学并行与分布式系统研究所所有
使用者可以将全部或部分本内容免费用于非商业用途
使用者在使用全部或部分本内容时请注明来源
资料来自上海交通大学并行与分布式系统研究所+材料名字
对于不遵守此声明或者其他违法使用本内容者，将依法保留追究权
本内容的发布采用 Creative Commons Attribution 4.0 License
完整文本

1 处理器调度

• 系统中的任务（线程，单线程进程）多于处理器数目
• 对象：CPU执行的最小单元，可以是进程或线程，统一用“任务”描述。

• 决策：

  1. 下一个执行的任务
  2. 执行该任务的CPU
  3. 执行的时长

• 时机：

  1. 执行时间用尽
  2. 等待I/O请求
  3. 睡眠
  4. 中断

1.1 什么是调度？

• 协调请求对于资源的使用。
• 不同场景下具有不同的调度指标。
  • 批处理系统：高吞吐量。
  • 交互式系统：低响应时间。
  • 网络服务器：可扩展性。
  • 移动设备：低能耗。
  • 实时系统：实时性
• 共有的目标：高资源利用率，多任务公*性，低调度开销。

1.2 常用调度指标

• 降低周转时间：任务第一次进入系统到执行结束的时间
• 降低响应时间：任务第一次进入系统到第一次给用户输出的时间
• 实时性：在任务的截止时间内完成任务
• 公*性：每个任务都应该有机会执行，不能饿死
• 开销低：调度器是为了优化系统，而非制造性能BUG
• 可扩展：随着任务数量增加，仍能正常工作

1.3 调度面临挑战

• 缺少信息（没有先知）
  • 工作场景动态变化
• 任务间的复杂交互
• 调度目标多样性
  • 不同的系统可能关注不一样的调度指标
• 许多方面存在取舍
  • 调度开销 V.S. 调度效果
  • 优先级 V.S. 公*
  • 能耗 V.S. 性能

1.4 Linux中的调度策略

• 为了满足不同需求提供多种调度策略
• 以Linux两种调度器为例，每种对应多个调度策略
  • 完全公*调度器(CFS, Complete Fair)
    • SCHED_OTHER
    • SCHED_BATCH
    • SCHED_IDLE
  • 实时调度器(RT, Real Time)
    • SCHED_FIFO
    • SCHED_RR

2 经典调度

2.1 先到先得

• 简单，直观。
• *均周转，响应时间过长。

2.2 短任务优先

• *均周转时间短
• 不公*，任务饿死。*均响应时间过长。

2.3 抢占式调度(Preemptive Scheduling)

• 每次任务执行
  • 一定时间后被切换到下一任务
  • 并非执行到终止
• 通过定时触发的时钟中断实现

2.4 Round Robin(时间片轮转)

• 轮询：公*，*均响应时间短
• 牺牲了周转时间。

• 当每个任务执行时间差不多时，周转时间问题会很明显。
• 时间片过长，退化成“先到先得”。
• 时间片过短，调度时间开销会变大。

3 优先级调度

3.1 调度优先级

• 操作系统中任务是不同的。例如系统/用户，前台/后台。
• 不加以区分有可能导致关键任务无法及时处理，导致缓慢或错误
• 确保重要的任务优先调度

3.2 多级队列(Multi-Level Queue, MLQ)

• 维护多个队列并设置对应优先级。
• 队列间采取优先级调度。高优先级先行。
• 队列内采取round robin或其他公*/*似公*调度策略。

优先级如何选取

• 什么样的任务应该有高优先级？
  • I/O密集型任务
    • 为了更高的资源利用率
  • 用户主动设置的重要任务
  • 时延要求极高（必须在短时间内完成）的任务

本质上，先到先得和最短任务优先都是优先级调度策略。时间片轮转是优先级全部相同的优先级策略。

3.3 Linux 实时调度器

• Linux Real-Time Scheduler，使用Multi-level Queue优先级调度
• 每个任务有自己的优先级、具体策略
• 具体策略可根据任务需求针对性选择
  • SCHED_RR：任务执行一定时间片后挂起
  • SCHED_FIFO：任务执行至结束
  • SCHED_OTHER为完全公*调度。

3.4 优先级动态调整

• 操作系统中的工作场景是动态变化的

• 静态设置的优先级可能导致

• 资源利用率低

  • 一个CPU密集型动态转变为I/O密集型任务

• 优先级反转

• 某些场景下，任务的优先级需要动态调整

饥饿（低优先级）

• 目前存在的调度策略限制：
• 周转时间、响应时间过长
  • 先到先得
• 依赖对于任务的先验知识
  • 预知任务执行时间：最短任务优先
  • 预知任务是否为I/O密集型任务：多级队列（设置优先级）
• 假设调度没有开销
  • RR（将时间片设置过短会导致调度开销过大）

3.5 解决：多级反馈队列（MLFQ）

• 一个无需先验知识的通用调度策略

  • 周转时间低、响应时间低
  • 调度开销低

• 通过动态分析任务运行历史，总结任务特征

  • 类似思想的体现：分支预测、缓存
  • 需要注意：如果工作场景变化频繁，效果会很差

基本算法

• 规则 1:

  • 优先级高的任务会抢占优先级低的任务

• 规则 2:

  • 每个任务会被分配时间片，优先级相同的两个任务使用时间片轮转

• 规则 3:

  • 任务被创建时，假设该任务是短任务，为它分配最高优先级

• 规则 4a:

  • 一个任务时间片耗尽后，它的优先级会被降低一级

• 规则 4b:

  • 如果一个任务在时间片耗尽前放弃CPU，那么它的优先级不变
  • 任务重新执行时，会被分配新的时间片

• 更改规则4a，规则4b。规则4:

  • 一个任务时间片耗尽后（无论它期间放弃了多次CPU，它的时间片不会被重置），它的优先级会被降低一级

• MLFQ在该规则下:

  • 记录每个任务在当前优先级使用的时间片
  • 当累计一个完整时间片被用完后，降低其优先级

• 规则 5

  • 在某个时间段S后，将系统中所有任务优先级升为最高

• 针对混合工作场景

  • 执行时间短的任务
    • 交互式任务
    • I/O密集型任务

• 执行时间长的任务

  • CPU密集型计算任务

基本算法（规则1-规则4b）存在问题一

• 长任务饥饿

  • 过多的短任务、I/O密集型任务可能占用所有CPU时间

• 任务特征可能动态变化

  • CPU密集型任务变成了交互式任务等

• 规则 5:

  • 在某个时间段S后，将系统中所有任务优先级升为最高

• 避免长任务饿死

  • 所有任务的优先级会定时地提升最高
  • 最高级队列采用RR，长任务一定会被调度到

• 针对任务特征动态变化的场景

  • MLFQ会定时地重新审视每个任务

基本算法（规则1-5）存在问题二

• 无法应对抢占CPU时间的攻击
  • 恶意任务在时间片用完前发起I/O请求
  • 避免MLFQ将该任务的优先级降低，并且每次重新执行时间片会被重置
    • 几乎独占CPU！

更改规则4如下:

• 更改规则4a，规则4b。规则4:
  • 一个任务时间片耗尽后（无论它期间放弃了多次CPU，它的时间片不会被重置），它的优先级会被降低一级
• MLFQ在该规则下:
  • 记录每个任务在当前优先级使用的时间片
  • 当累计一个完整时间片被用完后，降低其优先级

参数调试

• 如何确定MLFQ的各种参数？

  • 优先级队列的数量
  • 不同队列的时间片长短
  • 定时优先级提升的时间间隔

• 每个参数都体现了MLFQ的权衡

  • 对于不同的工作场景，不同的参数会导致不一样的表现

• 为不同队列选择不同的时间片

  • 高优先级队列时间片较短，针对短任务
    • 提升响应时间
  • 低优先级队列时间片较长，针对长任务
    • 降低调度开销

小结

• Multi-Level Feedback Queue 多级反馈队列
  • 通过观察任务的历史执行，动态确定任务优先级
    • 无需任务的先验知识
  • 同时达到了周转时间和响应时间两方面的要求
    • 对于短任务，周转时间指标*似于最短工作时间优先。
    • 对于交互式任务，响应时间指标*似于时间片轮转。
  • 可以避免长任务的饿死
• 许多著名系统的调度器是基于多级反馈队列实现的
  • BSD, Solaris, Windows NT 和后续Windows操作系统

3.6 高响应比优先：短任务优先执行，防止长任务饥饿

响应比（Response Ratio）是一个任务的响应时间与运行时间的比值。

结合了先到先得和最短工作时间优先的策略，避免了后者的公*性问题。

4 公*共享调度

4.1 公*共享

• 每个用户占用的资源是成比例的

  • 而非被任务的数量决定

• 每个用户占用的资源是可以被计算的

  • 设定“份额"以确定相对比例（绝对值不重要）
  • 例：份额为4的用户使用资源，是份额为2的用户的2倍

4.2 彩票调度(Lottery Scheduling)

• 每次调度时生成随机数 \(R\in[0,T)\).
• 根据生成的随机数找到对应的任务。
• 原理就是调度T次时，每个任务被调度次数的期望==该任务的份额

彩票转让

• 场景：
  • 在通信过程中，客户端需要等到服务端返回才能继续执行
• 客户端将自己所有的ticket转让给服务端
  • 确保服务端可以尽可能使用更多资源，迅速处理
• 同样适用于其他需要同步的场景

• 份额影响任务对CPU的占用比例

  • 不会有任务饿死

• 优先级影响任务对CPU的使用顺序

  • 可能产生饿死

• 随机的好处是？

  • 简单

• 随机带来的问题是？

  • 不精确——伪随机非真随机
  • 各个任务对CPU时间的占比会有误差

4.3 步幅调度(stride scheduling)

• 确定性版本的Lottery Scheduling
  • 可以沿用tickets的概念

Stride——步幅，任务一次执行增加的虚拟时间.

• \(\text{步幅}=\dfrac{\text{最大步幅}}{\text{份额}}\)