相关信息

本文为我在完成 ShanghaiTech CS130 project (Stanford CS140 project) 时的学习与思考。

注意

为遵守 ShanghaiTech 学生学术诚信规范，各 project 的代码相关部分将在本 project 提交 ddl 结束后上传。

关于 project

Stanford CS140 Project

简单来说，本 project 提供了一个基本的 PintOS 系统，你需要根据题目对本系统进行修改、优化等，并通过每个子 project 的测试点。

我将其提供的 PintOS 系统进行了 docker 打包，运行在一个 Ubuntu 系统中，以使协作更顺利：链接

project 1: Threads

doc

在这个项目中，提供了一个功能及其基础的线程系统，我们需要扩展它的功能。

Alarm Clock

• 问题：系统现有的 timer_sleep() 函数（在 devices/timer.c）下使用的是 busy waiting，即不断循环直至 sleep 结束。

那么我们为了解决这个问题，可以考虑在线程进入睡眠时添加到一个 waiting_list 队列中（这个队列按照 wakeup 顺序排序），并将此线程 thread_block() 掉，由 interrupt 在每个时钟周期检测列表头是否应该苏醒，并逐个 thread_unblock() 直至列表头不再需要唤醒。

思路很简单，剩下的就是代码细节的问题：

1. 我们需要注意普通线程和 interrupt 线程的并发冲突问题，由于 waiting_list 需要在 timer_sleep() 函数（由普通线程调用）和 timer_interrupt() 函数（由 interrupt 线程调用）中同时被使用，我们需要在 timer_sleep() 操作该队列之前禁用 interrupt。
2. 你会发现完成后始终有一个 alarm-priority 测试点 fail 掉，阅读测试点 c 代码可发现其需要优先级调度（本 project part2，我至今不理解为什么要把这个 part 排在 Priority Scheduling 前面），其对本 part 代码的影响就是在 interrupt 线程中只要唤醒了线程，就需要进行 intr_yield_on_return()（即将正在进行的线程扔回 ready_list，并按照优先级重新取出）

另外，你会发现在不对提供的 PintOS 做任何修改的情况下，仍可以通过 part1 的所有测试点...

Priority Scheduling

1. Standard：实现严格的优先级调度机制。
   • 当一个具有更高优先级的线程加入到 ready_list 中时，正在运行的低优先级线程需要 thread_yield() 让出 CPU 资源。
   • 当多个线程在等待锁（lock）、信号量（semaphore）或条件变量（condition variable）时，一旦资源释放，优先级最高的等待线程应当被优先唤醒。

这个 part 比上一个复杂了一些，主要在于提出了很多模糊的术语，我们需要理解 lock, semaphore 和 condition variable 都是什么。

总体来说，我们可以将这三个名词从底层到高层排序，分别是 semaphore -> lock -> condition variable。

下面我们简单介绍一下这三个东西。

semaphore

核心是计数器+阻塞队列。

struct semaphore {
    unsigned value;
    struct list waiters;
}

它可以管理有限数量的资源。

我们可以使用 sema_down(s) 和 sema_up(s) 函数对资源进行获取、释放，若获取时无对应资源则阻塞直到提供资源给该线程。

lock

本质上是一种 semaphore(1)。

例如我们分配一片共享内存，多个线程可以操作这片内存，就必须对此内存进行 lock 以避免 race condition。

condition variable

多个线程等待某个条件成立后被唤醒。

好了，现在对这三个名词有了基本理解后思考一种情况：如果某个 lock 被一个低优先级线程拥有，又有一个高优先级线程进入了 ready_list，且希望拥有这个 lock，受 semaphore 的限制，它需要等待低优先级线程运行完释放 lock 才能被唤醒，若此时有一堆不需要该锁的中优先级线程加入，则一直不会运行原本就应该先运行的高优先级线程，这是我们不想看到的。

于是引出了该 part 的第二个任务：

2. Priority Donation
   • 线程拥有锁后，其优先级应为持有锁的优先级（定义锁的优先级为该锁等待队列线程和持有线程的优先级最大值）。
   • 另外，我们不难发现会出现会出现递归现象，那么整条需求链路上的线程优先级都应该被调整。
   • 当锁被释放后，原本持有该锁的线程优先级应被更新，其可能会被 thread_yield()。

代码实现起来并不算难，难点在于理解上述概念（不知道我的表述是否足够清晰了）。

Advanced Scheduler

• 实现一个类似于 4.4 BSD 操作系统的多级反馈队列调度器 (Multilevel Feedback Queue Scheduler, MLFQS)，以降低系统的平均响应时间。

什么是 BSD？

BSD 调度器的目标是在没有外部优先级信息的情况下，自动实现公平调度和良好的交互性响应。

关键在于：

1. 动态优先级

   不像简单的优先级调度器需要手动设置优先级，BSD 调度器会根据线程的行为自动调整优先级：

   • CPU 密集型任务（计算多）→ 优先级降低
   • I/O 密集型任务（交互多）→ 优先级提高

2. 指标

   • recent_cpu（最近 CPU 使用量）
   • nice 值：用户可设置（-20~20），nice 值越高 = 越"友好" = 优先级越低
   • load_avg （系统负载，影响 recent_cpu 衰减速度）

具体实现 doc

更新日志

2026/3/16 14:23

查看所有更新日志

• e78db-docs: add cs130 note于 2026/3/16

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

编辑此页