前置知识

在 Tacos 中关于 lab2 的文档实在是少得可怜，对于实现细节以及需要的背景知识的介绍都不甚清楚，再加上运行过程中各种各样奇奇怪怪的报错，使得这个 lab 要比 lab1 难上很多。因此，在这篇文章内我想先总结一下可能需要的背景知识以及在实现过程中我遇到的报错。

一点碎碎念

操作系统的 lab 相比于 ics 的 lab 难度明显上了一个档次，里面可能踩的坑实在是太多了！！而且对于新编写出的 rust 版本的操作系统，没有前人的足迹可以追寻，在写的时候也可能出现各种各样莫名其妙的问题。这篇文章权当一个小小的指北吧。我只会列出每个任务的设计思路。

首先我想列出在写这个 lab 之前，我们应该达成的几点“共识”（要不然这 lab 没法写了）

• 多线程中常用 Mutex<> 来确保对关键数据访问的独一性。它有一个优点是不需要 Mutex 本身可变就可以修改里面的数据，同时可以很安全地被多个线程访问。

• std 是没法用的，但是 rust 很贴心地帮我们在 alloc 里面实现了很多有用的工具，比如 Vec, BinaryHeap, BTreeMap 等等。需要注意的是 rust 中没有与 multiset 类似的数据结构。

• 在这个 lab 中，我们只需要考虑单核 cpu 的情况。虽然整个系统看上去很多很多部分都是并行的，但实际上这些代码在某个时刻只会有一行正在被执行。

• 这个 lab 的核心是维护不同线程的切换，线程的切换涉及以下几种情况：

  1. 主动调用了 schedule 函数：将当前线程放回 ready 线程列表中，切换上下文，将执行权交给下一个线程。
  2. 一个线程被唤醒了，且它比当前正在运行的线程具有更高的优先级。
  3. 程序主动更改了一个线程的优先级（注意：这个线程一定是当前正在运行的线程！这个 lab 里面不需要实现更改其它线程的优先级），并且使得处于 ready 列表的线程中，存在一个线程的优先级更高。
  4. 一个线程请求了一个未被释放的锁。
  5. time interrupt。在内核中有一个计时器与一个切换阈值，如果距离上次切换的时间长于这个阈值，那么操作系统会触发一次 time interrupt 陷阱。如果不关闭 time interrupt，这个陷阱内会执行一次 schedule。因此如果要从系统层面上确保当前操作是原子的，需要关闭 time interrupt（关上这个之后甚至连 tick 都不会调用）。每个线程都有自己独立的 time interrupt 状态。在多核 cpu 上频繁地关 interrupt 不是一个好习惯，因为所有 cpu 都会停下，效率很低。不过我们只需要考虑单核的情况，因此该关还是关吧。

• 关于 CondVar：在使用互斥锁的场景下，如果我们手持一个锁，但同时又想要等待另外一个锁被释放，此时有两种想法：

  • 不释放当前手持的锁，等待被释放的锁。好处是不会产生数据竞争，但是此时任何其他需要第一个锁的线程都会被阻塞，这样效率不高。
  • 释放当前手持的锁，等待被释放的锁。这样做有一定风险：等待此线程持有的锁的那些线程有可能会在中间插入，从而导致数据竞争。

  CondVar 就是专门针对这样的场景设计的工具，核心部分由三个函数组成：

  1. wait(cond, guard) 这里 cond 是条件变量，guard 是锁，且必须处于持有状态。这个函数可以理解为“释放锁 guard，等待条件变量 cond 被触发，再重新获取锁 guard” 的原子过程，尽管其内部实现并不是原子的。
  2. notify_one(cond) 通知一个等待这个条件变量触发的线程。如果没有线程在等待，那么这次触发将会被丢失。
  3. notify_all(cond) 通知所有正在等待这个变量触发的线程。