Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 8: 调度（Scheduling）

目录 · ← l6 · l8 →

Lecture 8: 调度（Scheduling）

概述

调度器（dispatcher）是”怎么切换”的机制，调度策略（scheduler）是”切换给谁”的政策。本讲从最简单的 FIFO 出发，引入时间片与抢占（round robin），讨论响应时间最优的 SRPT 及其”用过去预测未来”的近似实现（优先级队列、4.4BSD 调度器），最后讨论多核调度与调度在现代系统中的角色。

核心概念与系统机制图解

基本术语与目标

  • 调度问题：给定一个可切换线程的调度器、一组就绪线程和若干核，哪个线程在哪个核上跑多久？
  • 调度指标（Goals）：
    • 最小化响应时间（让用户保持忙碌）；
    • 高效利用资源（核与磁盘都忙；上下文切换开销低）；
    • 公平性（均衡分配 CPU，避免饥饿）。

FIFO（先来先服务，非抢占）

  • 就绪队列尾部入队，队首线程跑到退出或阻塞为止。
  • 问题：饥饿（长任务堵死短任务）、响应时间长。

Round Robin（时间片轮转，抢占）

  • 每线程运行一个时间片（time slice）后被定时器中断强制切换，回到队尾。
  • 实现：定时器硬件周期性中断。
  • 时间片长短权衡：太长→退化成 FIFO；太短→切换开销过大。
  • 例子（Lecture 8 场景）：A 100ms、B 1ms、C 2ms 三个作业：
    • FIFO 平均完成时间 ≈ 101.3ms；RR（1ms 时间片）≈ 36.7ms → RR 对短作业友好得多；
    • 三个 10ms 作业：FIFO 平均 20ms；RR ≈ 29ms → 公平但不总是最优。

SRPT（最短剩余处理时间优先）

  • 定义：总是运行”剩余时间最少”的线程，运行到完成（不中断）。
  • 优点：理论上响应时间最优（可证明）；偏好 I/O 密集线程，保持磁盘/网络忙碌。
  • 缺点：需要知道未来（无法实现）；可能饥饿。
  • 近似：用过去预测未来——”一个线程若已长时间不阻塞，很可能继续不阻塞”。I/O 密集型线程刚被唤醒（用 CPU 少）→ 高优先级。

优先级调度与多级队列

          ┌────┐
优先级高  P0 │    │◄── 交互型/I/O密集线程 (用CPU少) 停留在此
          ├────┤
          P1 │    │
          ├────┤
          ...│    │
          ├────┤
优先级低  Pn │    │◄── CPU密集线程 (用满时间片) 逐级下降
          └────┘
规则: 调度器总运行最高优先级队列中的线程; 同优先级内 round robin;
     线程用满时间片未阻塞 → 降到下一级队列; 阻塞后回到高优先级队列
  • 4.4BSD 调度器（1990s Unix）：记录每线程近期 CPU 使用量；用 CPU 最少的线程优先级最高。CPU 密集线程积累 CPU 时间 → 优先级下降；等待运行 → 优先级回升（不会永久饥饿）；系统过载时退化为最高优先级队列内的 round robin。
  • 用户干预：Unix nice 值——nice -n 19 cmd（低优先级，最”客气”）、nice -n -20 cmd（最高优先级）。

多核调度

  • 简单方案：共享就绪队列 + 每核私有调度器/定时器；运行优先级最高的 k 个线程；新线程优先级高于当前最低者时用 IPI（核间中断） 抢占。
  • 问题与改进：
    • 就绪队列锁竞争 → 每核独立队列 + 工作窃取（work stealing）平衡负载；
    • 线程在核上积累缓存状态 → 核亲和（core affinity）尽量不迁移线程；
    • 工作守恒（work-conserving）：有可运行工作就绝不闲置核（理想属性，实现困难）。

调度器何时运行？

  • 调度器不是线程，而是事件驱动的代码：线程解除阻塞时、定时器中断时、收到其它核 IPI 时。

代码示例与系统调用解说

示例：时间片轮转调度器的核心循环（Assign3 的用户级线程调度器骨架）

#include <list>

struct Thread {
    bool blocked = false;
    // ... 保存的寄存器现场、栈指针等 ...
};

class Scheduler {
public:
    void addReady(Thread* t) { readyQueue.push_back(t); }

    // 定时器中断处理器: 把当前线程放回队尾, 换下一个线程运行
    void onTimerInterrupt(Thread* current) {
        readyQueue.push_back(current);   // 1. 当前线程回队尾
        Thread* next = readyQueue.front();
        readyQueue.pop_front();          // 2. 取队首
        if (next && next != current) {
            contextSwitch(current, next); // 3. 保存 current 现场, 恢复 next 现场
        }
    }

private:
    std::list<Thread*> readyQueue;
};

【代码做了什么？】 定时器中断到来时，调度器把当前线程放回就绪队列尾部，取出队首线程并上下文切换——这就是 round robin。

【系统机制透视】

  • 定时器中断打断用户线程，CPU 陷入内核（/调度器代码），此时当前线程的寄存器现场保存在它的 TCB 中；恢复下一个线程时从它的 TCB 装载寄存器——这与你看到的内核级上下文切换是同一机制。
  • 时间片过短 → 切换开销占比高（保存/恢复寄存器 + 缓存/TLB 冷启动）；时间片过长 → 交互响应差。Linux 常见时间片约 4ms。
  • Assign3 的”虚拟化”视角：一个系统线程被虚拟化成许多用户级线程，调度器就运行在这个系统线程里——这正是内核在多核之间调度系统线程的缩影。

关键要点

  1. 调度是政策：FIFO（简单但会饥饿）→ RR（公平、抢占）→ SRPT（最优但需预知未来）。
  2. 用过去预测未来：I/O 密集/交互线程用 CPU 少 → 保持高优先级；CPU 密集线程降级 → 近似 SRPT。
  3. 优先级调度 + 老化（等待时优先级回升）避免饥饿。
  4. 多核调度的核心难题：共享队列的锁竞争、缓存/核亲和、工作守恒。
  5. 调度算法不应改变系统结果，只影响效率与响应时间；最好的调度器是自适应的。

常见陷阱与注意事项

  • 把调度器当成线程：它是事件驱动代码，运行在中断/陷阱上下文里。
  • 时间片设置不当：过长退化为 FIFO（短作业饥饿），过短则切换开销爆炸。
  • 纯优先级调度导致饥饿：必须配合优先级老化或时间片补偿。
  • 忽略核亲和：频繁迁移线程会因缓存/TLB 冷启动而显著变慢。
  • 过度追求公平：公平不等于最小平均响应时间（RR 对等长作业并不优于 FIFO）。

思考题

  1. 问题：为什么 SRPT 能同时改善响应时间和资源利用率？它有什么致命缺陷？
    • 答案：SRPT 优先运行最短作业，短作业迅速完成（响应时间最优）；偏好 I/O 密集线程意味着磁盘/网络保持忙碌（利用率高）。缺陷是需要知道每个作业的剩余时间（未来），实际无法实现，且长作业可能饥饿。
  2. 问题：4.4BSD 调度器如何保证 CPU 密集线程不被交互线程饿死？
    • 答案：优先级基于”近期 CPU 使用量”——CPU 密集线程等待运行时它的 CPU 用量在衰减、优先级逐渐回升，最终会成为最高优先级；因此只会”延迟”而不会”永久饿死”。
  3. 问题：多核系统为什么需要每核独立就绪队列和工作窃取？
    • 答案：单一共享就绪队列会成为锁竞争瓶颈（所有核抢同一把锁）；每核独立队列消除竞争，但负载可能不均，因此用工作窃取：空闲核从繁忙核”偷”线程来执行。