文件介绍

threads目录下的文件

接下来pintos/src/threads路径下的24个代码文件（除去.gitignore Makefile Make.vars等仓库和作业配置文件）会大致按照代码的调用顺序一一介绍：

loader.S loader.h
- 这是一个只有512字节的内核加载器程序，由BIOS加载，负责在磁盘上定位操作系统内核，然后把这个内核加载到内存里，并跳转执行内核start.S中的start()函数。
- 不用看懂，不要修改。
kernel.Ids.S
- 连接内核的链接程序。
- 设置了内核的加载地址，安排start.S在内核镜像最前端附近。
- 不用看懂，不要修改。
start.S
- 为32位操作系统的运行提供基础环境。
- 这不属于加载器，而是内核的一部分。
- 不用看懂，不要修改。
init.c init.h
- 内核初始化程序，其中main()函数（或pintos_init()函数）是整个内核的主函数。
- 需要至少理解初始化过程每一步初始化了什么，可能需要增加自定义的初始化代码。
thread.c thread.h
- 线程相关的主要代码文件。
- thread.h文件中关于struct thread的定义很有可能在四个Project中都会修改。
- 需要理解绝大多数代码含义，需要大量增添或修改代码。
switch.S switch.h
- 用汇编语言直接控制CPU实现的线程切换。
- 这是线程底层实现，不涉及控制何时切换线程。
- 不用看懂，不要修改。
palloc.c palloc.h
- 这是页分配器(Page ALLOCator)，负责以页（每页是4kB）为单位向系统分配内存（只能是整数页）。
- 需要理解代码目的，不用修改。
malloc.c malloc.h
- 这是内核代码中malloc()函数和free()函数的简单实现。
- 需要理解代码目的，不用修改。
interrupt.c interrupt.h
- CPU中断的基础处理代码。
- 管理中断与分发相关底层内容，不涉及调度策略。
- 需要理解代码目的，不用修改。
intr-stubs.S intr-stubs.h
- 处理中断的底层汇编代码。
- 不用看懂，不要修改。
synch.c synch.h
- 定义了基本同步原语（primitive, 指从当前考虑的操作系统层面上看，不可继续细分的单元结构）：
  - semaphore | 信号量
  - lock | 线程锁
  - condition variable | 条件变量
  - optimization barrier | 优化屏障
- 在四个Project中均会用到。
- 需要看懂，需要修改。
io.h
- 输入输出I/O端口连接相关函数。
- 不用看懂，不要修改。
vaddr.h pte.h
- 处理虚拟地址和页表项的相关函数和宏定义。
- 在Project 3之前不需要看懂和修改。
flags.h
- 标志寄存器的一些标志的宏定义。
- 不用看懂，不要修改。

devices目录下的文件

接下来介绍pintos/src/devices目录下的24个代码文件：

timer.c timer.h
- 系统计时器，默认每秒100次中断
- 需要看懂，需要修改。
vga.c vga.h
- 控制终端的输出，printf()会调用这里的内容。
- 不用看懂，不要修改。
serial.c serial.h
- 串口驱动，与输入输出相关。
- 不用看懂，不要修改。
block.c block.h
- 块设备抽象层。
- 将磁盘抽象为块（定长数组）。
- 在Project 2之前不需要看懂和修改。
ide.c ide.h
- 支持IDE硬盘扇区的直接读写。
- 不用看懂，不要修改。
partition.c partition.h
- 硬盘分区相关代码。
- 不用看懂，不要修改。
kbd.c kbd.h
- 键盘驱动，控制键盘的输入。
- 不用看懂，不要修改。
input.c input.h
- 输入层，控制输入队列。
- 不用看懂，不要修改。
intq.c intq.h
- 中断队列，管理线程和中断都能安全访问的循环队列。
- 不用看懂，不要修改。
rtc.c rtc.h
- 读取当前日期和时间。
- 默认仅供pintos/src/threads/init.c中随机数生成器的初始种子使用。
- 不用看懂，不要修改。
speaker.c speaker.h
- 蜂鸣器驱动。
- 不用看懂，不要修改。
pit.c pit.h
- 8254可编程定时器的代码。
- 仅由timer.c和speaker.c调用的底层代码。
- 不用看懂，不要修改。

lib目录下的文件

lib和lib/kernel包含了许多C语言的库函数，以供编程时调用；而lib/user中包含了用户程序可能用到的内容，在Project 2中才会用到。

具体文件不再一一列举，不过有以下内容需要了解：

<string.h>和<stdio.h>下的部分字符串相关函数由于其安全性问题，被踢出了这次lib的C标准库。详情见此处。
kernel/list.c kernel/list.h 可能会在Project 1中使用到。

更详细的内容请参阅：Background | Pintos

任务要求与执行建议

任务要求

在devices/timer.c中重构timer_sleep()的实现代码，避免使用忙等待。
1. 实现线程的优先级调度
2. 实现线程的优先级捐赠和嵌套优先级捐赠
3. 实现（补全）线程检查和修改自己优先级的函数
实现类似4.4BSD调度器的分级反馈队列调度器(mlfqs)，以优化作业平均响应时间

详细要求请参考：Your Tasks | Pintos

执行建议

执行顺序

先跑测试，结果应该是 fail 20/27。
完成任务1；
- 涉及修改的文件：devices/timer.c
- 测试结果仍然是 fail 20/27，但是速度会变快。
完成任务2；
- 涉及修改的文件：threads/synch.c threads/thread.c threads/thread.h
- 测试结果为 fail 7/27，前18个测试点都通过。
完成任务3MLFQS所需的定点实数运算例程；
- 涉及修改的文件：threads/thread.c threads/thread.h
- 不用跑测试，结果不会有变化，编译通过即可。
完成任务3。
- 涉及修改的文件：threads/thread.c threads/thread.h
- 测试结果为 All 27 tests passed.

代码量参考值

这是官方给出的参考值，单位是行。由于代码不同，这显然不能代表唯一正确答案。

devices/timer.c       |   42 +++++-
threads/synch.c       |   88 ++++++++++++-
threads/thread.c      |  196 ++++++++++++++++++++++++++----
threads/thread.h      |   23 +++
4 files changed, 320 insertions(+), 29 deletions(-)

如果你也想测试一下，可以在pintos容器内（或Windows的pintos目录下）依次按照以下执行：

安装diffstat：

1
2
3

apt update
apt install diffstat
diffstat --version

版本比较：
1
2
cd ~/pintos
git diff | diffstat

笔者写的代码比官方的标准版本修改多很多，说明笔者代码效率不高。

需要注意的内容

耐心调试，有看不懂的~~不想看的~~可以问AI，这个项目代码应该大部分主流LLM都熟悉。
保证全程参与~~，或者全程不参与~~：Project 1相对独立，代码内部逻辑联系紧密，所以建议合作时时刻保持跟进代码进度~~，或者干脆抱队友大腿~~。
Project 1 几乎无法一次性完成，所以需要时间分段。一个合理的时间分段方式是按照任务分开，一次性完成一个任务的代码编写和设计文档撰写。
完成任务3时，会涉及部分修改任务2的代码；请确保不要删除任务2的代码，而是使用关键指示变量thread_mlfqs作为开关控制。
Project 1 中代码完成的所有内容都不在后面的Project中重复利用。这意味着Project 2是从白板PintOS开始的。

回到目录

aaaaa online

CS130 操作系统I Project 1 Threads | 线程