PKU 操作系统 TacOS Lab1 踩坑记录

我能在完全不会 Rust 的情况下战胜 TacOS 吗？？！！

注：

  1. 由于本人目前正在修这门课，为了避免被抄袭，这里暂不给出大段代码。如果确有查看代码的需求，可以私下联系博主。
  2. 该 Lab 大量涉及并发编程，博主水平有限无法保证自己的代码的正确性，甚至不能保证最终的代码一定能够通过所有 testcase（我只能通过狂暴重复运行保证代码以高概率通过所有 testcase）。因此以下所有做法仅供参考，如果参考了做法中有问题的部分导致扣分博主概不负责。

0. Lab0

这个其实没啥坑，照着手册的 Option A 直接配就好了。只要你有一个好用的 73\frac 73 根木棍就不是问题。

同学用 CLab 好像出了神秘问题，不建议使用 CLab。

从 Lab1 开始坑就比较多，以下按我踩到的顺序依次写。

1. tool/ 下面的工具怎么用？

答案是……我也不知道。我首先尝试了直接 cd 进去然后 cargo tt -b lab1，但是按照 Option A 安装时自带的 rust 版本是 1.70，编译时有一些 package 需要更新的版本，于是就倒闭了。具体错误信息如下：

1
2
3
4
error: package `quote v1.0.45` cannot be built because it requires rustc 1.71 or newer, while the currently active rustc version is 1.70.0
Either upgrade to rustc 1.71 or newer, or use
cargo update -p quote@1.0.45 --precise ver
where `ver` is the latest version of `quote` supporting rustc 1.70.0

当然这是难不倒我的 它已经给出了一个升级提示，于是我按照该方式操作：先 rustup update stable 再 rustup default stable。

这样我成功获得了一个 1.94 版本的 rustc，然后 cargo h 就可以用了，但是 cargo tt -b lab1 仍然用不了，报错似乎是 src/fs/disk.rs 里面的一个 const u8 和 const i8 的类型不匹配问题。

于是我又尝试了在根目录下面 override 使用 rustc 1.70 并在 tool/ 下面使用 rustc 1.94，但是这样似乎仍然无法通过编译，报错与使用 1.94 版本编译 OS 是相同的。问 AI 说的是要增加一些文件，但是这样我不知道会不会导致本地通过然后提交上去少文件过不了，所以也没这么干。

最后也没有解决，所以就压根没用上这个 tool，采用的 workaround 是 cargo tt -b lab1 --dry 可以显示测试各个 test case 的命令，在根目录下面一条一条的跑就行了。

例如在 tool 下面运行 cargo tt -b lab1 --dry 的输出为：

1
2
3
4
5
6
7
8
9
10
11
Command for donation-three:
cargo run -r -q -F test-schedule -- -append donation-three
Command for priority-alarm:
cargo run -r -q -F test-schedule -- -append priority-alarm
Command for alarm-zero:
cargo run -r -q -F test-schedule -- -append alarm-zero

...

Command for alarm-multiple:
cargo run -r -q -F test-schedule -- -append alarm-multiple

在根目录下面运行 cargo run -r -q -F test-schedule -- -append alarm-zero，即可单独测试对应的 test case。这个 case 应该是直接可以通过的（因为 sleep 提供的是一个 working example）。看到如下输出说明测试正常。

1
2
3
4
[21 ms] Hello, World!
[42 ms] [PASS]
[42 ms] Leaving test...
[57 ms] Goodbye, World!

2. Alarm clock

我们观察到 src/thread.rs 下面有需要修改的 sleep 函数，而 src/sbi/timer.rs 下面有一个更改计时器的 tick 函数，从而我们需要做的就是：

  • 调用 sleep(time) 的时候，我们直接把当前线程 block 住，然后搞一个全局数据结构记录下来我们需要在当前 tick + time 时间唤醒这个进程。
  • 调用 tick() 的时候，我们从这个全局数据结构里面弹出唤醒时间在当前时间之前的线程，把这些线程唤醒。

理论上这个功能我们可以搞一个优先队列，但是由于 TacOS 里面似乎把 std 给 ban 了，并且也没有给我们提供 std::cmp::Ordering 的等价物，从而我们只能使用 BTreeMap 维护 (time, thread) 对。但是这个东西比较麻烦的地方在于它不支持两个相同的 key，从而我们需要维护 (time, Vec<thread>) 将唤醒时间相同的进程存到一起。

由于我们需要保证 sleep 是并发安全的，所以我们需要 Mutex 锁。但是这个东西还有一个不是 const function 的神秘问题，所以我们还需要一个叫 Lazy 的东西。至于这玩意是啥我也不知道（我完全不会 Rust），反正直接用就好了。最终这样声明全局数据结构 ALARM：

1
2
static ALARM: Lazy<Mutex<BTreeMap<i64, Vec<Arc<Thread>>>>> =
    Lazy::new(|| Mutex::new(BTreeMap::new()));

需要的所有东西的位置：

1
2
3
4
5
use crate::sync::{Lazy, Mutex};
use crate::thread::Thread;
use alloc::collections::BTreeMap;
use alloc::sync::Arc;
use alloc::vec::Vec;

使用 ALARM.lock() 访问内部受保护的 BTreeMap。

剩下的代码写起来都比较符合直觉，就不多说了。如果遇到奇怪的类型不匹配问题（例如多引用 / 不变量 vs 变量这种），基本上把代码和错误信息粘给 LLM 都能直接帮你调出来。

如果测试的时候爆了，可以通过 cargo run -r -q -F test-schedule,debug -- -append <test-case> 查看单个 test case 的详细运行过程。

如果出现类似 panicked on no thread is ready 的错误信息，并且 debug 发现 Idle 线程或者别的线程莫名其妙被 block 了，可以检查一下是不是死锁了。如果你的循环 / if 条件里面写的是 if let Some(v) = ALARM.lock().get_mut(&time) 然后循环 / if 里面还有 ALARM.lock() 就会死锁。这个时候需要在循环 / if 外面声明一个 let guard = ALARM.lock(); 然后在 if 条件和内部都只用 guard 访问。

理论上到这里你应该通过了以 alarm 开头的五个 case。不过写完后面的优先级调度可能就又挂了，至于为什么我们下回分解。

3. Priority scheduling

虽然我写完 alarm 已经燃尽了但是其实这一部分才是 lab1 的主菜。

请教 OpenClaw 发现优先级调度大概可以拆成三个部分：

  • 实现 scheduler；
  • 针对 Mutex、Semaphore 和 Condvar 实现基于优先级的调度；
  • 实现 donation。

以下依次拆解。

3.1 实现 scheduler

首先的一个问题是代码在哪写。

我们观察到 src/thread.rs 下面的 schedule() 函数使用的是 src/thread/manager.rs 里面的 Manager 类，而 Manager 内部使用了一个叫 Scheduler 的东西，从而这个就是我们要的。打开 src/thread/scheduler.rs 看到如下代码：

1
2
3
4
5
#[cfg(feature = "thread-scheduler-priority")]
// (Lab1) Your task: priority scheduling
pub type Scheduler = self::fcfs::Fcfs;
#[cfg(not(feature = "thread-scheduler-priority"))]
pub type Scheduler = self::fcfs::Fcfs;

同时我们发现 src/thread/scheduler/fcfs.rs 下面有个叫 Fcfs 的东西，里面写的是个基于 deque 的 FIFO 调度，从而我们就是要把这个东西换成优先级调度。我们在 fcfs.rs 中新建一个结构体 Priority 并将以上代码中 // (Lab1) ... 下面一行的 Fcfs 替换为 Priority。Priority 结构体整体对着 Fcfs 照猫画虎。相信有自信在不会 Rust 的情况下选 TacOS 的大家都是有充分强的照猫画虎能力的。

那么自然的想法就是我们直接拿一个 BTreeMap 来按优先级顺序存储所有的线程。不过这里要求我们对同优先级的进程仍然按照 FIFO 的顺序调度，所以我们还需要在里面额外使用一个时间戳变量作为排序的第二关键字。

在修改线程的优先级时，我们为了修改按优先级顺序存储线程的 BTreeMap 需要知道该线程对应的时间戳，由于该信息没有被保存在线程内部，我们需要再额外使用一个 map 来存储线程对应的优先级和时间戳。这里索引可以直接使用线程的 ID，该信息可以通过 thread.id() 获取。

register 和 schedule 的实现是直接的。注意点：

  • 为了避免中断引发的问题，我们在两个函数开始时关闭中断（即 crate::sbi::interrupt()::set(false)，将该函数返回值（即原本中断是否打开）记录于变量中。在函数返回时恢复状态。
  • schedule 中，需要判断当前线程优先级是否最高。如果当前线程处于 Running 状态并且优先级高于队列中其他线程，则应继续运行当前线程（即返回 None）。

实现 Priority 结构体后回到 src/thread.rs 下面，修改 set_priority 函数和 get_priority 函数。这一部分的实现整体不会遇到太多问题。需要注意现在 set_priority 以及 wake_up 在将当前线程加入 scheduler 之后都要判断是否需要重新 schedule。

完成这部分之后，你应该可以额外通过 priority-alarm、priority-change、priority-fifo 和 priority-preempt。

3.2 实现控制原语的优先级调度

我们需要保证当若干线程被同一个 Mutex 锁 / Semaphore 信号量 / Condvar 条件变量卡住时，如果有一个解锁 / 信号量增加等操作使得我们可以唤醒一个线程继续，我们需要选择优先级最高的线程。

我们首先注意到代码中 Mutex 基于 Sleep 而 Sleep 基于 Semaphore，从而我们直接不用管 Mutex。而 Condvar 虽然看起来基于 Semaphore 但是它的等待队列其实是自己实现的，所以我们还需要分开实现。

由于后续优先级可能通过 donation 改变，所以这里我们最好不用 BTreeMap，而是直接拿个 Vec 存然后暴力找最大值。可以通过从前往后遍历并在后面 push 实现 FIFO。

实际上好像测试数据没卡这个， BTreeMap 也能过。

这块整体无难点。完成后，可以通过 priority 开头的所有测试点。

3.3 优先级捐赠

本 lab 最大难点。如果不熟悉 Rust 可能会导致选择一些难以实现的设计方案，写出来之后卡在一个编译错误上面，然后拼尽全力无法战胜（这里的主要问题是 Thread 里面的东西要求其可以安全地在线程之间共享，因此很多东西无法直接放进去）。由于尝试过并且倒闭的方案太多了就不详细写心路历程了，以下直接给出我经过很多尝试得到的最终方案。

由于说明了不需要对 Semaphore 实现，我们只需要调整 Sleep 和 Thread。我们要实现的是：

  • 如果一个线程 H 尝试获得一把锁，但是这把锁在 M 手里，那么 M 通过这把锁获取到 H 的优先级。
  • 如果此时 M 正在等待 L 手里的一把锁，则 L 也要递归地通过其正在持有的锁获得 H 的优先级。
  • 当一个线程释放一把锁时，其失去通过这把锁获得的所有优先级。

对于 Sleep，我们使用一个静态变量（类似 TICKS）对每一个该类型的锁分配一个唯一的 id。为了方便后续与不持有锁做区分，我们令这个 id 从 1 开始。

对于 Thread，我们额外记录以下信息：

  • 其正在等待获取的锁被哪个线程持有：类型为 Mutex<Option<Arc<Thread>>>。如果当前没有被锁卡住，则值为 None。
  • 其正在等待获取的锁的 id：类型为 AtomicUsize。
  • 其接受的捐赠：使用两个 Mutex<BTreeMap> 保存；
    • 第一个按优先级顺序保存每一个优先级受到了几个捐赠（BTreeMap<u32, i64>），用于获取有效优先级；
    • 第二个保存每一把锁受到了哪些捐赠（BTreeMap<usize, Vec<u32>>），用于在释放锁时撤回通过这把锁获得的捐赠。

每个 Thread 向外暴露两个优先级捐赠相关的方法：

  • donate：传入捐赠的优先级和锁 id，加入两个 BTreeMap，检查当前进程是否被锁卡住，如果卡住则递归捐赠。由于进程一定被锁卡住所以一定不在 Ready 状态，故递归捐赠中不需要动 scheduler，只需要在最外层检查是否需要更新 scheduler 即可。
  • recall：传入锁 id，删除与该锁相关的所有捐赠，更新 scheduler。

Sleep 中，acquire 时如果当前锁有 holder 则向其捐赠优先级；release 时对当前线程撤回捐赠。这部分实现直接，不多讲。

正确实现该部分后，理论上可以通过所有测试点。如果挂了，可以先调 donation-one、donation-two、donation-three，这三个不涉及递归捐赠；如果这三个过了，再调 donation-nest，这个是比较简单的递归捐赠；最后再调 donation-chain。

这部分写起来其实不难，主要难点在于不会 Rust 需要试很久才能得到一个合适的解决方案。

如果你通过了所有 donation 开头的 case，不要急着开香槟，记得把之前的 case 再测一遍。如果都通过了，那么你可以开香槟了。如果没有，可以继续往下看。

4. 我怎么 alarm 又爆了啊？

由于我们改了 Mutex 的实现，而 alarm clock 里面又用了 Mutex 又用了 sleep，所以爆了其实也是正常现象。

这里我试了试似乎主要问题是 sleep 过程中被 interrupt 会导致一个 blocked 的线程获取锁，然后线程就会虚空变成 ready。把第一部分的 sleep 的 interrupt 关掉就能解决所有问题。