rust-sched-sim

速成之后缺的那一次完整练习：用约 1000 行 Rust 写一个调度器，顺手把操作系统第一章学了。

零第三方依赖 · 只用标准库 · cargo run 立刻出结果 · 每个 Rust 知识点都在代码里标了出来

---

一、这个故事是写给谁的

我把 Rust 速成了一遍，然后发现自己卡在一个很尴尬的位置：语法都认识，但不知道该写什么。

回顾一下那条曲线，你大概也走过：

• 第 1 天：let、match、struct、enum —— 就这？好像也不难
• 第 2 天：所有权、借用、生命周期 —— 编译器开始逐行骂你
• 第 3 天：Rc、RefCell、trait、泛型、闭包、? —— 每个词单独都懂，连起来不知道在解决什么问题

然后你想找个项目练手，打开一个真实仓库：两万行、二十个依赖、满屏 async、宏和 unsafe。你安静地关掉了它。

教程里的例子也不救场：猜数字、写链表、实现一个 todo。它们都能跑，但都不像"一个真正的程序"——你学的那一堆概念在里面根本没有出场机会。

这个仓库就是中间那段空白。

它不教你语法（速成班已经教过了，我也不打算再讲一遍）。它给你的是一次完整的、能跑出结果的、规模刚好读得完的练习：991 行、零第三方依赖、只用标准库。而题目，正好是操作系统课的第一章——调度。

我是先速成了 Rust，再想学操作系统，然后发现「调度器」这个题目几乎是为这两件事的交集量身定做的。这个仓库就是我当时想找却没找到的那份练习。

---

二、它是什么

一个 CPU / GPU 任务调度器模拟器：

• 有 11 个任务排队，各有优先级和预估工作量
• 有两台"设备"（CPU 和 GPU），各有固定的名额（capacity）
• 每一轮，调度器按优先级挑出能放下的任务，各推进一个时间片（slice = 5 单位）
• 记录每一轮的吞吐、每个任务的完成顺序、每台设备上的日志
• 全部跑完后打印统计，并把设备日志写成 sched-log-CPU.txt / sched-log-GPU.txt

$ cargo run

== 调度器起步 ==
时间片 = 5 单位，CPU 名额 = 4，GPU 名额 = 4
排队任务 = 11 个
  [排队] vision-detect CPU  prio=80  0/9 state=Ready
  [排队] kernel-matmul GPU  prio=95  0/9 state=Ready
  ...

== 逐轮执行 ==
轮  1 推进 5 条：T6(kernel-matmul,5)=5 T1(vision-detect,5)=5 T2(sensor-fuse,5)=5 ...
轮  2 推进 5 条：T6(kernel-matmul,4)=4 T1(vision-detect,4)=4 T2(sensor-fuse,1)=1 ...
轮  3 推进 3 条：T3(path-plan,5)=5 T7(kernel-attn,5)=5 T8(kernel-norm,5)=5
轮  4 推进 3 条：T3(path-plan,4)=4 T7(kernel-attn,1)=1 T8(kernel-norm,1)=1
轮  5 推进 1 条：T11(kv-copy,3)=3
累计推进 60 个时间片单位

== 轮次统计 ==
轮     本轮完成      CPU 时间片     GPU 时间片
1     2         13          8
2     5         8           7
...

完成顺序：kernel-softmax → log-rotate → kernel-matmul → vision-detect → ...

调度器状态 = 任务 11 个，完成 11 个，记录 11 条
CPU  名额 1/4 日志 0 条 搬走 1 条日志，累计 1 条
  日志写入 sched-log-CPU.txt

跑一次不到一秒。输出是可见的，这一点对初学者比什么都重要——你能立刻看到"我改的那个数"造成了什么后果。

---

三、为什么是"调度器"这个题目

因为它同时满足了初学者练手最难凑齐的三个条件：

1. 它本质上只是"数据结构 + 规则"。 没有网络，没有异步，没有 unsafe，没有生命周期地狱级别的高阶技巧。你可以把整个程序在脑子里跑一遍。这正是"第一次完整练习"需要的规模。

2. 但它天然逼你用上 Rust 最难的那几块。 任务表归谁所有？调度计划借用了谁、借多久？为什么这里非得标 <'a> 不可？为什么 Rc 和 RefCell 会出现在这两个地方？——这些问题不是"为了练语法硬造的"，而是问题本身要求你回答。这是这个项目最值钱的地方。

3. 它正好是操作系统这门课的第一个正经话题。 调度是操作系统做的第一件真事。你在这里遇到的每一个概念——时间片、优先级、准入控制、饥饿、吞吐——在 OSTEP 或者任何一本操作系统教材的第一章里都会原样再出现一次。先用手写一遍，再去看教材，感受完全不同。

---

四、你会在这里用到哪些 Rust 知识

速成班讲过的概念，几乎每个都在这个项目里有非它不可的出场理由：

知识点	在代码里	为什么这里绕不开
所有权与移动	Scheduler::add	任务一旦交给调度器，调用方就不再拥有它
切片与借用	Scheduler::tasks() -> &[Task]	返回 &[Task] 而不是 &Vec<Task>：只承诺"能挨个读"，不承诺底层容器
生命周期标注	fn heavier<'a>(a: &'a Task, b: &'a Task) -> &'a Task	返回值借自 a 或 b，编译器无法自己判断，不写标注直接编译不过
借用边界	Scheduler::advance_round	调度计划借用了调度器，所以必须"先把编号抄出来、再 drop 计划"，之后才允许修改它
Rc<str>	Task.name、Completion.name	任务名被任务表和完成记录同时持有；克隆只让计数 +1，字符串不复制第二份
RefCell	Device.log	只拿到 &self 也要能往日志里追加——内部可变性，借用规则改到运行期检查
Box	Device.sink	把整块日志放堆上，Device 自身大小与日志条数无关
trait 与默认方法	Describable	Task 和 Device 各自给出一行摘要，labeled 用默认实现复用；&dyn Describable 是运行期分派
泛型方法	advance_round<Summary>、total_by<Key>	"每条计划要留下什么信息"由调用方决定，调度器本身不关心
闭包与 FnMut	run_simulation 里的 note、total_by 的 by	调用方需要一个能顺手改自己捕获变量的闭包来记账
自定义错误 + ?	SchedulerError、main 里的 Box<dyn Error>	一个函数只该有一种错误类型；装箱让 io::Error 和 SchedulerError 能共存
带数据的枚举	TaskKind::Cpu(u8)、SchedulerError::CapacityFull { .. }	同一概念的不同形态各自带数据，match 时编译器保证你不漏分支
derive 的取舍	各类型的 #[derive(...)]	Copy / Hash / Eq / Ord 各自解决什么问题，为什么有些能派生有些不能
迭代器与 collect	任务清单构造、Scheduler::views	enumerate + map + collect 是 Rust 的日常句式，不是炫技
内部可变性 vs 可变借用	Device 的 &self / &mut self 方法划分	哪些操作真的需要独占，哪些只是"看起来需要"

速成班通常把知识点讲成一份清单。这个项目想干的事，是把清单上的每一项接回一个具体的问题上。

---

五、你会顺手学到哪些操作系统概念

操作系统的概念	在这个项目里
时间片 time slice	slice = 5，每轮每个被选中的任务推进的固定单位
资源名额与准入控制 admission control	Device::admit 放不下就拒绝，并在错误里告诉你 occupied/capacity
优先级调度	Scheduler::plan 按 (priority, id) 降序排，数值大的先上
轮次推进	advance_round：排一轮 → 跑一轮 → 记一轮，循环到排不出计划为止
设备抽象	CPU 与 GPU 是两台独立的名义设备，各有自己的容量和日志
完成记账	Completion 同时记住"第几个完成"和"这次跑了多久"
饥饿 starvation	静态优先级的固有毛病——低优先级任务永远排在后面
装箱/顺序问题	plan 按加入顺序走一遍、不回头，可能留下填不满的空隙

---

六、快速开始

git clone [email protected]:Caden-1224/rust-sched-sim.git
cd rust-sched-sim
cargo run

没有依赖要装，没有配置文件要改。想换参数就直接改 src/main.rs 开头那几个数：

let slice = 5u32;          // 时间片长度
let cpu_capacity = 4usize; // CPU 上能同时容纳的份额总数
let gpu_capacity = 4usize; // GPU 同理

先只改这三个数，跑几遍，看输出怎么变。 这一步的收获比读代码大。

代码地图

文件	行数	负责什么
src/main.rs	357	程序入口：造任务、造设备、逐轮推进、打印报告
src/scheduler.rs	418	调度器本体与 Device：计划、执行、记账、日志、写文件
src/task.rs	156	Task / TaskKind / TaskState / TaskId 与 Describable trait
src/error.rs	60	SchedulerError：把"调度器可能失败的方式"写成一个类型

991 行里有 306 行是纯注释，所以真正要读的代码比你想象得少。

---

七、四条练习路线

这不是一个"看完就结束"的仓库。下面每一层都有明确的"做到什么样算过关"。

Level 0 · 跑起来，改参数（约 30 分钟）

• 把 slice 从 5 改成 1，看轮数怎么变。再改成 20，看"时间片"是怎么影响响应速度的
• 把 cpu_capacity 从 4 改成 2，看哪些任务被挤到后面去
• 把 ("kernel-matmul", TaskKind::Gpu(3), 95, 9) 里的 95 改成 1，看它什么时候才完成
• 把 TaskKind::Gpu(3) 的 3 改成 4，看 GPU 上同时能跑的任务数变少

过关标准：你能不看代码，说出"我改的这个数"是通过哪条路径影响输出的。

Level 1 · 改（约 1–2 小时）

• 加一个任务：在 specs 里加一行。加之前先回答：TaskKind::Cpu(2) 里的 2 是什么？它和二元的 capacity 是什么关系？
• 加一台设备：main.rs 里已经有一台 NPU 的现成例子（它先接纳成功、第二次被拒绝）。把它接进真正的调度循环里
• 换排序规则：把 plan() 里的 (priority, id) 换成 SJF（最短作业优先，用 remaining() 当键），对比完成顺序和平均等待时间
• 加一个统计指标：平均周转时间、平均等待时间，或者 CPU 利用率

Level 2 · 写（约半天）

• 实现多种策略：FCFS、轮转 Round-Robin、多级反馈队列 MLFQ。用一个 enum SchedulePolicy 选策略，让 plan() 按策略分派
• 给任务加到达时间：加一个 arrived_at: u32 字段，让任务在不同轮次才出现（改 plan() 的过滤条件即可）
• 让优先级老化：effective_priority = priority + 等待轮数。做完这个，再想想为什么真实系统要这么做

Level 3 · 挑战

• 依赖关系：给 Task 加 deps: Vec<TaskId>，只有依赖全部完成的任务才能进入计划。这就从"调度"走到"DAG 调度"了
• 饥饿检测：某个任务连续 N 轮没被选中就打印警告
• 跨设备任务：一个任务需要先跑 CPU、再跑 GPU。状态机该怎么设计？TaskState 够用吗？
• 抢占式调度：允许一个更高优先级的任务中途打断正在跑的任务。想想这会破坏现在的哪条借用假设

---

八、我故意留在这里的坑

这个调度器是**故意写成"天真版本"**的。它现在能正确跑完 11 个任务，但下面每一条都是真实调度器必须解决的问题——我把它们留成了思考题，而不是悄悄修掉：

1. plan() 只按加入顺序走一遍，不回头填坑。 前面的大任务把名额吃掉之后，后面的小任务即使放得下也进不来。对比输出里 轮 1（推进 5 条）和 轮 3（推进 3 条）的差别——那就是容量碎片。

2. 优先级是静态的，不会老化。 注意一个容易误判的点：当前这份工作负载里，饥饿其实不会发生。因为任务集合是有限的、没有新任务持续到来，低优先级的 prefetch（prio=10）和 kv-copy（prio=15）最后都完成了，只是等得久。 但只要你做了 Level 2 的"到达时间"，或者把负载换成一个持续到来的流，饥饿立刻就会出现。那时候优先级老化就从"优化"变成了"必须"。

3. 没有抢占。 一个任务一旦被排进这一轮，就必须跑完这个时间片。

4. 份额是固定的。 任务占多少资源在创建时就定死了，没有动态调整，也没有"任务跑得越久份额越高"这类启发式。

5. 没有优先级反转的概念。 因为没有锁，也就没有持锁的低优先级任务。但当你加上并发（Level 3 之后），这是下一个必然会撞上的问题。

---

九、关于代码里那些 【知识点：xxx】 注释

打开任何一个 .rs 文件，你会看到大量这种注释：

// 【知识点：生命周期】返回的引用来自 a 或 b 之一，编译器无法自己判断它该跟谁同生，
// 所以要显式写出 <'a> 并标注两个入参与返回值用的是同一个 'a；
// 少了这个标注，编译直接报「缺少生命周期说明符」
fn heavier<'a>(a: &'a Task, b: &'a Task) -> &'a Task {

它们刻意不解释"这行在干什么"（那个你看代码就知道了），而是解释三件事：

1. 为什么这里非得用这个语言特性——不用行不行？不行，因为编译器会拦住你
2. 编译器会怎么拦你——那条报错信息长什么样
3. 这个概念在这个问题里的角色——它解决的是哪个具体的麻烦

你完全可以删掉所有注释，代码照样跑。它们存在的唯一目的是让你在第一次读到一个陌生语法时，就知道它为什么在这里。

---

十、这个仓库不是什么

写清楚这一点，比写十条优点更有用：

• 不是一个真正的操作系统内核，也不会真的调度你机器上的进程。它是一个模型
• 不是生产级调度器：单线程、没有并发、没有锁、没有抢占
• 不是 Rust 语法教程：语法不解释，只解释取舍。看不懂 let 的话，请先回去补速成班
• 不是一份"标准答案"：第八节列的那些坑就是明证。它是一份起点

它的大小是刻意的：小到一个下午能读完，大到能装下操作系统调度那一章的主要概念。

如果你读完、跑通、并且至少做完 Level 1，那你已经比"速成完不知道写什么"的时候往前走了一大步——你手里有一个自己改过的、能跑的程序了。

---

环境

• Rust 1.85+（项目使用 edition 2024），实测 1.98.1
• 无第三方依赖（Cargo.toml 的 [dependencies] 是空的）
• 运行后会在项目根目录写出 sched-log-CPU.txt / sched-log-GPU.txt（已在 .gitignore 中忽略）

许可

MIT，见 LICENSE。随意 fork、改写、拿去当教学材料。

最后

如果这个仓库帮你跨过了"速成完不知道写什么"那一步，那它的目的就达到了。有更好的练习题目，欢迎开 issue 聊聊。