Stanford-CS140 Operating System Project 随记
信息
本文为我在完成 ShanghaiTech CS130 project (Stanford CS140 project) 时的学习与思考。
关于 project
简单来说，本 project 提供了一个基本的 PintOS 系统，你需要根据题目对本系统进行修改、优化等，并通过每个子 project 的测试点。
我将其提供的 PintOS 系统进行了 docker 打包，运行在一个 Ubuntu 系统中，以使协作更顺利：链接
project 1: Threads
在这个项目中，提供了一个功能及其基础的线程系统，我们需要扩展它的功能。
Alarm Clock
- 问题：系统现有的
timer_sleep()函数（在devices/timer.c）下使用的是 busy waiting，即不断循环直至 sleep 结束。
那么我们为了解决这个问题，可以考虑在线程进入睡眠时添加到一个 waiting_list 队列中（这个队列按照 wakeup 顺序排序），并将此线程 thread_block() 掉，由 interrupt 在每个时钟周期检测列表头是否应该苏醒，并逐个 thread_unblock() 直至列表头不再需要唤醒。
思路很简单，剩下的就是代码细节的问题：
- 我们需要注意普通线程和 interrupt 线程的并发冲突问题，由于
waiting_list需要在timer_sleep()函数（由普通线程调用）和timer_interrupt()函数（由 interrupt 线程调用）中同时被使用，我们需要在timer_sleep()操作该队列之前禁用 interrupt。 - 你会发现完成后始终有一个
alarm-priority测试点 fail 掉，阅读测试点 c 代码可发现其需要优先级调度（本 project part2，我至今不理解为什么要把这个 part 排在 Priority Scheduling 前面），其对本 part 代码的影响就是在 interrupt 线程中只要唤醒了线程，就需要进行intr_yield_on_return()（即将正在进行的线程扔回ready_list，并按照优先级重新取出）
另外，你会发现在不对提供的 PintOS 做任何修改的情况下，仍可以通过 part1 的所有测试点...
Priority Scheduling
- 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 的第二个任务：
- Priority Donation
- 线程拥有锁后，其优先级应为持有锁的优先级（定义锁的优先级为该锁等待队列线程和持有线程的优先级最大值）。
- 另外，我们不难发现会出现会出现递归现象，那么整条需求链路上的线程优先级都应该被调整。
- 当锁被释放后，原本持有该锁的线程优先级应被更新，其可能会被
thread_yield()。
代码实现起来并不算难，难点在于理解上述概念（不知道我的表述是否足够清晰了）。
Advanced Scheduler
- 实现一个类似于 4.4 BSD 操作系统的多级反馈队列调度器 (Multilevel Feedback Queue Scheduler, MLFQS)，以降低系统的平均响应时间。
什么是 BSD？
BSD 调度器的目标是在没有外部优先级信息的情况下，自动实现公平调度和良好的交互性响应。
关键在于：
动态优先级
不像简单的优先级调度器需要手动设置优先级，BSD 调度器会根据线程的行为自动调整优先级：
- CPU 密集型任务（计算多）→ 优先级降低
- I/O 密集型任务（交互多）→ 优先级提高
指标
- recent_cpu（最近 CPU 使用量）
- nice 值：用户可设置（-20~20），nice 值越高 = 越"友好" = 优先级越低
- load_avg （系统负载，影响 recent_cpu 衰减速度）
具体实现 doc
Project 2: User Program
Project 2 需要能够让程序通过 System Call 与操作系统交互，让操作系统能够处理程序的错误。
完成 Project 2 的时候需要注意可能带来影响的 bug，因为未来 Project 3 和 Project 4 都将基于 Project 2 的代码实现。
Process Termination Messages
文档要求所有用户进程退出时都打印形如 name: exit(status) 的信息。这里的退出并不只包括显式调用 exit(status)，也包括用户程序触发非法访问、非法指令等异常后被内核杀死。
因此我们在线程结构中维护 exit_status：
- 正常调用
SYS_EXIT时，由sys_exit()写入用户传入的 status； - 用户指针非法、page fault 等异常退出时，统一通过
exit_process_with_error()将状态设为-1； process_exit()中如果当前线程确实运行过用户进程，就打印退出信息。
halt 是一个例外。它会直接关闭 PintOS，不应该额外打印某个进程的退出信息。
Argument Passing
用户程序最终会从 _start(int argc, char *argv[]) 开始执行，如果用户栈上没有正确放置 argc 和 argv，程序一启动就会因为访问错误栈内容而 page fault。
这里需要注意：传入 process_execute() 的 file_name 并不只是可执行文件名，而是完整命令行，例如 echo x y。因此我们需要先把命令行拆成两部分：
- 第一个 token 作为真正要加载的程序名，用于
thread_create()和load()； - 全部 token 作为参数列表，用来构造用户栈。
我们在 process_execute() 中先复制一份命令行，然后用 strtok_r() 取出第一个 token 作为线程名。真正构造栈的工作放在 start_process() 中完成：它会再次将完整命令行拆成 argv，调用 load(argv[0], ...) 加载可执行文件，加载成功后再开始向用户栈写入参数。
栈的构造顺序需要符合 x86 的函数调用约定。由于栈向低地址增长，所以实现时大致是反着压入：
最终用户程序看到的栈就像普通 C 函数调用一样，main(argc, argv) 可以直接读取参数。这里一个很容易犯错的地方是：不能把完整命令行传给 load()，否则系统会尝试打开名为 echo x y 的文件，而不是打开 echo。
System Calls
PintOS 中，用户程序发起 system call 时，会把系统调用号和参数放在用户栈上。进入内核后，syscall_handler() 可以通过 f->esp 找到这些参数。
因此，一个 system call 的处理流程大致是：
- 从用户栈中读取 syscall number；
- 根据 syscall number 判断是哪一个系统调用；
- 从用户栈继续读取对应参数；
- 验证所有用户传入的指针是否合法；
- 调用内核中的实际处理函数；
用户指针验证
这部分文档中提及了两个方法，我们采用的是第二种方法：依赖页错误（page fault）机制进行检查。文档中提供的get_user和put_user函数，会尝试从用户地址读取或写入一个字节。如果访问失败，就返回错误，并让当前用户进程以 -1 退出。
我们基于get_user封装了两个函数
user_read (void *kaddr, const void *uaddr, size_t size)从
uaddr读入size长度的内容到kaddr，成功读入则返回true，反之返回false。user_string (char *kaddr, const void *uaddr, size_t max_size)从
uaddr读入最多max_size长度的字符串到kaddr，成功读入则返回true，反之返回false。
借助这两个函数，大多数 syscall 在访问用户内存时，只需调用对应的辅助函数即可完成用户指针验证，而无需手动检查页表映射或地址合法性。
不过 SYS_READ 是一个特殊情况。由于该 syscall 需要向用户提供的 buffer 中写入数据，因此不仅要保证地址可读，还必须保证其可写。对此，我们使用 put_user 对 buffer 覆盖范围内的地址逐字节尝试写入 0。若写入过程中未发生异常，则说明该缓冲区可写，从而完成验证。
File Syscalls
这里比较重要的是文件描述符，也就是 fd。用户程序拿到的 fd 只是一个整数，而真正的文件对象是内核中的 struct file *。因此我们需要在每个进程中维护一个 fd table，用来把用户态的 fd 映射到内核态的文件对象。
另外，所有涉及文件系统的操作都需要注意同步问题。PintOS 提供的文件系统本身并不是完全线程安全的，如果多个进程同时读写文件，可能会出现 race condition。因此我们使用一个全局的 filesys_lock 来保护文件系统操作。
我们的实现中，struct thread 中维护了一个固定大小的 fd_table[128]：
fd = 0表示标准输入，read(0, ...)通过input_getc()从键盘读入；fd = 1表示标准输出，write(1, ...)通过putbuf()写到控制台；fd >= 2才对应真正打开的文件，open()会从2开始寻找空位。
这样做的好处是查找 fd 非常直接，用户传入的 fd 可以直接作为数组下标访问。不过它也带来了一个固定上限：每个进程最多维护 128 个 fd。对于本 project 来说这个限制足够使用。
文件相关 syscall 中还需要处理字符串指针。比如 create、remove、open 都会接收用户传入的文件名指针。我们不会直接把这个用户指针传入文件系统，而是先申请一页 kernel page，用 user_string() 把文件名复制到内核空间，再调用 filesys_create() / filesys_open() 等函数。这样即使用户传入了非法字符串，也只会终止当前用户进程，不会让文件系统拿到不可信地址。
进程退出时，还需要扫描自己的 fd table，将所有未关闭的文件逐个 file_close()。否则即使用户程序忘记调用 close()，内核也应该回收对应资源。
process_wait / process_execute
这两个函数在 process.c 中，syscall 会通过它们实现 exec 和 wait。
其中 exec 对应 process_execute()，作用是创建并启动一个新的用户进程；wait 对应 process_wait()，作用是让父进程等待某个子进程结束，并获得它的退出状态。
这部分的核心问题是：父进程和子进程之间需要共享一部分状态。
因为父进程调用 exec() 之后，只会得到一个子进程的 tid。但是仅有 tid 是不够的，后续还需要：
- 知道子进程是否成功加载
- 知道子进程是否已经退出
- 知道子进程的退出状态码
- 等待子进程退出 / 加载
所以我们需要额外维护一个 child_info 结构体，用来记录子进程的信息。我们创建了如下结构体
struct child_info {
tid_t tid; /* 子进程tid */
int exit_status; /* 子进程退出状态码 */
bool exited; /* 子进程是否已经退出 */
bool loaded; /* 子进程是否已经加载 */
struct list_elem elem;
struct semaphore wait_sema;
struct semaphore load_sema;
int count; /* 父/子进程有几个还在，初始值为2，count=0才会free */
struct lock lock;
};然后我们就可以基于这些信息实现 exec 和 wait 的功能。
process_executeprocess_execute()对应 syscall 中的exec。它的返回值不只表示子进程线程是否创建成功，还需要表示子进程是否成功加载了可执行文件。因此，父进程调用
thread_create()创建子进程后不能立即返回，而是需要通过load_sema等待子进程完成加载。子进程在load()结束后，会把加载结果记录到对应的child_info中，并通过sema_up(&child->load_sema)唤醒父进程。父进程从
sema_down(&child->load_sema)返回后，再检查child_info->loaded。如果子进程加载成功，则返回子进程的tid；如果加载失败，则返回-1。process_waitprocess_wait()对应 syscall 中的wait。它需要让父进程等待指定子进程退出，并获得该子进程的退出状态。父进程会先在自己的子进程列表中查找对应的
child_info。如果找不到，说明传入的tid不是当前进程的子进程，直接返回-1。如果找到了对应子进程，并且子进程尚未退出，父进程就通过wait_sema阻塞等待。子进程退出时，会把自己的退出状态写入
child_info->exit_status，并将child_info->exited设为true，然后通过sema_up(&child->wait_sema)唤醒可能正在等待它的父进程。父进程被唤醒后，就可以读取子进程的exit_status，并将其作为wait的返回值。
不过这里还需要考虑资源释放的问题。父进程和子进程的退出顺序是不确定的：可能父进程先退出，也可能子进程先退出。因此，child_info 不能简单地只由父进程或子进程单方面释放。
为了解决这个问题，我们使用 count 作为引用计数。父进程和子进程各自持有一份对 child_info 的引用。当其中一方不再需要这个结构体时，就调用 child_release() 将 count 减一。只有当父进程和子进程都不再需要它，也就是 count 变为 0 时，才真正释放这个 child_info 结构体。
Denying Writes to Executables
Project 2 还有一个容易忽略的要求：正在运行的可执行文件不能被写入。否则一个进程运行到一半，另一个进程把它的 executable 改掉，后续 Project 3 做 lazy loading 时会出现非常难判断的行为。
PintOS 已经提供了 file_deny_write() 和 file_allow_write()。关键在于：不能在 load() 结束后立刻关闭 executable 文件。因为一旦关闭，deny write 的效果也会随之消失。
因此我们的做法是在 load() 成功后：
- 将打开的 executable 文件保存在当前线程的
runing_file中； - 调用
file_deny_write()禁止其他写入； - 直到该进程退出时，再在
process_exit()中关闭这个文件。
这样 executable 在整个进程生命周期内都会保持打开和写保护状态。
警告
如果你看到这里，说不定你已经写完了你的代码，建议你执行make clean && make check 5-10 次，防止可能出现的随机性 FAIL。
Project 3: Virtual Memory
警告
Project 3 在 Project 2 的代码基础上实现，开工前尽量保证 Project 2 的正确性，否则在 Project 3 中改 Project 2 的 bug 会非常非常痛苦。
Project 3 需要在 Project 2 的基础上实现一系列和内存管理相关的功能。目前用户程序运行前都要加载所有需要的页面，也没有淘汰机制，能够同时运行的程序数量和程序大小都受到物理内存大小的限制。
Project 3 并没有初始的代码，所有新增的代码文件需要前往根目录下Makefile.build中注册。
Frame Table
警告
Project 3 需要处理很多地址，每次不验证addr != NULL都是对未来 debug 的自己不负责。
每次处理 Frame Table 时不加锁都是对未来 debug 的自己不负责。
每次发现NULL之后不 release 锁的更是对未来 debug 的自己不负责。
参考文档 4.2 一节，我们首先需要实现 Frame Table。
Frame Table 用来记录系统中已经分配出去的物理页。后续的swap、mmap 等功能都需要依赖它来查找和管理 frame，因此它是 Project 3 中虚拟内存系统的基础结构。
我们的实现中，Frame Table 使用 PintOS 提供的 list.h 维护。这一阶段的实现可以参考 palloc.c 的思路，对 frame 的获取和释放进行简单封装。需要注意的是，如果一次操作中需要获取多个 frame，而中途分配失败，就必须释放之前已经成功分配的 frame，避免产生内存泄漏。
此外，由于 Frame Table 是全局数据结构，可能被多个线程同时访问，因此对它的修改和遍历都需要使用 lock 保护，防止出现神奇又神秘的同步问题。
Hash Table
此处我们先介绍一下哈希表。
PintOS 在 lib/kernel/hash.h 和 lib/kernel/hash.c 中实现了一套通用的哈希表结构。它的作用和普通哈希表类似：通过一个 key 快速查找对应的元素，避免每次都在线性表中遍历查找。它只要求被存储的结构体中包含一个 struct hash_elem 字段。之后我们就可以通过这个 hash_elem，把自己的结构体挂到哈希表里。这和list.h是类似的。
使用哈希表时，需要提供两个函数：
hash：告诉哈希表如何根据某个字段计算哈希值；less：当两个元素需要比较时，告诉哈希表如何判断大小或是否相同。
在实现 Supplemental Page Table 中，我们需要知道一些相关函数
hash_insert()用来把一个新的元素插入哈希表中。对于 Supplemental Page Table 来说，当我们新建一个 SPT entry 后，就可以通过hash_insert()将它加入当前进程的 SPT 中。如果表中已经存在相同upage的元素，hash_insert()会返回原有元素，因此也可以用它来判断是否出现了重复页面。hash_find()用来在哈希表中查找元素。它并不是直接传入 key，而是传入一个临时构造的结构体元素。比如我们想通过upage查找对应的 SPT entry，就可以先创建一个只填好upage的临时 entry，再用hash_find()查找哈希表中是否存在相同页面。
Supplemental Page Table
Supplemental Page Table 用来记录用户虚拟页面的额外信息，使内核能在 page_fault 时判断该页面是非法访问，还是需要从文件、swap 或栈增长中按需加载。
我们第二个需要实现的就是 Supplemental Page Table。这部分我们使用哈希表实现，参考hash.h/hash.c，并使用upage来索引。
在初始步骤中，Supplemental Page Table 结构体只需要记录upage和hash_elem即可。后续步骤中，按照需要给结构体新增项即可。
Supplemental Page Table 会贯穿整个 Project 3，无论是 Memory Mapped Files，还是 Swap，亦或是 Stack Growth、Eviction 的部分，都需要或多或少在 Supplemental Page Table 中添加点东西。
Lazy Loading / Memory Mapped Files
警告
Project 3 同样需要处理很多文件，每次不给文件操作加锁，都是对未来 debug 的自己不负责。
每次给文件操作 acquire 或 release 同一个锁两遍以上的，更是对未来 debug 的自己不负责。
我们首先需要解释一下 Project 3 中和文件相关的页面加载到底要做什么。
在 Project 2 中，process.c 里的 load_segment() 会在程序启动时直接把可执行文件中的 segment 加载到内存里。这样显然很简单，但是非常浪费空间
Project 3 要解决的一个重要问题就是 lazy loading。具体来说，load_segment() 不再立刻把文件内容读入 frame，而是先为这些用户虚拟页创建 Supplemental Page Table 来记录这个页面应该如何被加载。
这样，程序启动时并不会马上占用大量物理内存。只有当用户程序真正访问某个尚未加载的页面时，才会触发 page_fault。此时 page fault handler 会检查 Supplemental Page Table，如果发现这个地址对应的页面是合法的、只是还没有被加载，就分配一个 frame，然后根据 SPT (Supplemental Page Table) 中记录的信息从文件中读取内容，并将这个 frame 安装到当前进程的 page table 中。
我们还需要实现mmap和munmap两个 System Call。每一次mmap都要对应一个单独的id，我们可以使用结构体mmap_entry来保存相关信息。同时，mmap的文件和thread绑定，我们可以把相关信息储存在thread中。
当用户程序调用 mmap 时，和 lazy loading 一样，操作系统不会立刻把整个文件读入内存，而是把这个文件映射到从 addr 开始的一段用户虚拟地址空间上。文件可能占据一个或多个 page，因此我们需要为这些 page 分别创建 Supplemental Page Table。
每个被映射的页面都会记录它对应的文件、文件偏移量、需要读取的字节数以及需要补零的字节数。之后当用户程序访问这些地址时，如果对应页面还没有加载，就会触发 page_fault，再由内核把对应的文件内容加载进 frame。
然后是munmap，若文件被修改，则需要写回文件系统，这里我们需要使用pagedir_is_dirty (thread_current ()->pagedir, upage)来判断文件是否被修改过。
提示
此处可以进行一次 check，确保 Memory Mapped Files 相关测试点通过。
Stack Growth
Project 2 中 PintOS 只给 Stack 分配了一页的 page，这显然不够用。我们要移除这个限制。
首先我们看文档，
Allocate additional pages only if they "appear" to be stack accesses.
这里我们看到了一个非常神秘的词appear，Project 3 需要你给 Stack 额外的页面仅当“看起来像”栈指针，我们自然对这个出现在这很神秘的词语有疑问。不过既然文档说只要看起来像，那我们可以针对page_fault的地址作出判断，依据文档，我们可以给出如下判断条件
bool if_stack_pointer = fault_addr >= stack_pointer - 32
&& fault_addr <= PHYS_BASE
&& fault_addr >= PHYS_BASE - 8 * 1024 * 1024;由于page_fault可能由 kernel 直接触发，也可能在 user 切换到 kernel 的时候触发，而在前者我们没有办法获取f->esp，所以我们需要在当前thread中记录其栈指针。记录的时机可以在前一次 Syscall 的时候，于是
void *stack_pointer = user ? f->esp : thread_current ()->esp;当发生page_fault且我们发现这是一个stack_pointer的时候，我们就可以分配一页 stack page。
提示
此处可以进行一次 check，确保 Stack Growth 相关测试点通过。
BitMap
此处我们再简单介绍一下 Bitmap。
PintOS 在 lib/kernel/bitmap.h 和 lib/kernel/bitmap.c 中实现了一套位图结构。Bitmap 可以理解为一组连续的 bit，每一个 bit 只有两种状态：true 或 false。因此它非常适合用来记录某些资源是否已经被占用。
在 Swap Table 中，我们可以把每一个 swap slot 看作一个编号：
- 第
0位表示第0个 swap slot 是否被占用； - 第
1位表示第1个 swap slot 是否被占用； - 以此类推。
如果某一位是 false，说明对应的 slot 还没有被使用；如果是 true，说明这个 slot 已经被分配出去了。
在实现 Swap Table 时，我们需要知道一些相关函数：
bitmap_create()用来创建一个指定大小的 bitmap。比如 swap 分区中一共有多少个 page-sized slot，就可以创建多少位的 bitmap。bitmap_scan_and_flip()用来查找一段连续的空闲 bit，并将其状态翻转。对于 swap 来说，我们通常只需要找一个空闲 slot，所以可以用它找到一个空闲位置，并立刻把这个位置标记为已经使用。bitmap_reset()用来把某一位重新设置为false。当一个页面从 swap 中读回内存后，对应的 swap slot 就可以被释放，此时需要用bitmap_reset()把这个 slot 标记为空闲。bitmap_test()用来检查某一位当前的状态。它可以判断某个 slot 是否正在被使用。
Swap
警告
在调用 Swap 的时候不检查是否成功的都是对未来 debug 的自己不负责。
在 Project 3 中，用户程序看到的是虚拟地址空间，但真正能放在内存里的页面数量受物理内存大小限制。当 frame 不够用时，操作系统就需要选择一个暂时不用的页面，将它从物理内存中换出。如果这个页面之后还可能被访问，就不能直接丢弃，而是需要把它保存到 swap 分区中。
因此，我们需要实现 Swap Table 来管理 swap 分区中哪些位置已经被使用，哪些位置仍然空闲。通常可以使用 bitmap 来记录 swap slot 的使用情况。
这里需要注意，Swap 的一个 slot 并非一个 page，一个 page 对应 8 个 slot。还需要注意的是 Swap 的初始化时机。我们需要在init.c里面初始化 Swap，我们通过block_get_role (BLOCK_SWAP)获得BLOCK_SWAP，但是太早初始化无法获得BLOCK_SWAP，太晚初始化会让系统跑起来了之后还没初始化 Swap，都会出事。
Eviction & Reclamation
这里我们需要实现一套页面淘汰和页面恢复的机制。
在 Project 3 中，用户程序使用的是虚拟地址空间，但真正的物理内存大小是有限的。当没有空闲 frame 可以分配时，操作系统就不能简单地失败，而是需要从当前已经使用的 frame 中选择一个暂时不用的页面，将它从物理内存中淘汰出去，这个过程就是 eviction。
但是，被淘汰的页面不能随便直接丢弃。不同来源的页面需要用不同的方式处理，否则之后用户程序再次访问这个页面时，就无法恢复出正确内容。
因此，我们首先需要在 Supplemental Page Table 中记录页面的类型，例如：
enum spt_type {
PAGE_MMAP,
PAGE_EXEC,
PAGE_STACK,
PAGE_OTHER
};这样在淘汰页面时，就可以根据页面类型决定它应该被如何保存。
对于通过 mmap 映射的文件页面，如果页面被修改过，也就是 dirty bit 被设置过，那么在淘汰时需要把页面内容写回原文件；如果页面没有被修改，则可以直接丢弃，因为之后还可以从原文件重新读入。
对于 exec 相关的页面，也就是从可执行文件中 lazy loading 得到的页面，如果页面没有被修改，同样可以直接丢弃，之后 page fault 时重新从可执行文件加载即可。但是如果这个页面被修改过，就不能再简单地从原文件恢复了，因为原文件中的内容已经不是当前页面的最新内容。这种情况下就需要把页面写入 swap。
对于 stack page，它没有对应的文件作为后备存储，因此一般不能直接丢弃。即使页面当前没有被标记为 dirty，为了保证程序之后仍然能看到正确的栈内容，比较稳妥的做法也是将其写入 swap。
所以整体来说，淘汰页面时可以按照下面的思路处理：
PAGE_MMAP：dirty 时写回文件，不 dirty 时可以直接丢弃；PAGE_EXEC：不 dirty 时可以从原文件恢复，dirty 时需要 swap；PAGE_STACK：通常需要 swap；PAGE_OTHER：如果没有可靠的文件后备，也应该 swap。
完成页面内容的保存后，还需要清除原来的 page table 映射，并更新 SPT entry 的状态。比如被换出到 swap 的页面，需要在 SPT 中记录对应的 swap slot；被直接丢弃的文件页面，则需要保留 file、offset、read bytes、zero bytes 等信息，方便之后重新加载。
接下来是如何选择要淘汰的 frame。
不是所有 frame 都适合被淘汰。例如，正在进行 I/O 的 frame 不能被淘汰，否则可能出现读写到一半页面被换走的问题。因此可以在 Frame Table 的表项中加入一个 busy 字段，只有当 busy == false 时，这个 frame 才能作为 eviction 的候选对象。比如在 syscall 读写用户 buffer、mmap 写回文件、swap in / swap out 等过程中，都可以临时将相关 frame 标记为 busy，避免它在关键操作中被淘汰。
在选择具体 victim frame 时，可以实现一个简化版的 clock algorithm，也就是 second-chance algorithm。
我们维护一个类似时钟指针的变量，在 Frame Table 中循环移动。每次检查当前 frame 时：
- 如果该 frame 是 busy，则跳过；
- 如果该 frame 的 accessed bit 为 true，说明它最近被访问过，就把 accessed bit 清成 false，然后跳过；
- 如果该 frame 的 accessed bit 为 false，说明它最近没有被访问，就选择它作为 victim frame。
这里用到的 accessed bit 可以通过 pagedir_is_accessed() 检查，并通过 pagedir_set_accessed() 清除。这个算法的直觉是：最近访问过的页面先给一次机会，只有连续一段时间没被访问的页面才会被淘汰。
页面被淘汰后，之后用户程序如果再次访问这个虚拟地址，就会触发 page_fault。这时 page fault handler 会去 Supplemental Page Table 中查找对应 entry，并根据 entry 中记录的信息恢复页面：
- 如果页面是 file-backed 且没有被 swap，就重新从文件加载；
- 如果页面在 swap 中，就分配新的 frame，并从对应 swap slot 读回；
- 如果页面是合法的 stack growth，就创建新的 stack page；
- 如果 SPT 中找不到对应页面，才说明这是非法访问，需要结束进程。
这些就是 Project 3 的大概的思路。到这，你可以尝试跑20次make clean && make check，确保一切正常。
Project4: File System
Buffer cache
目前，PintOS 访问文件系统时，总会直接从磁盘读写。
众所周知地，从磁盘访存是极慢的，我们迫切地需要一种缓存的机制提升读写效率，减少对磁盘的访问。
此部分，我们需要修改文件系统，使其保留文件块的缓存。当发起读取或写入某个块的请求时，先检查该块是否在缓存中；如果在，就直接使用缓存中的数据，而不访问磁盘。否则，就从磁盘把该块取入缓存，必要时驱逐一个较旧的缓存项。在此项目中，缓存大小不得超过 64 个扇区。
由于缓存大小有限，我们需要一个淘汰算法来决定当缓存满时将哪个缓存写入磁盘空出，其复杂度应类似于 时钟算法。
可以想到，我们需要评估一个缓存是否还 “活着”，也就是说，它最近是否有被读写过？于是，类似于 Project3 的 Eviction 过程我们就是可以实现这个算法。
同时我们需要一个 write_behind 机制——内容保留在缓存中，必要时再写入磁盘。这是很好实现的，但重点是我们需要考虑到缓存机制实际降低了安全性，若文件系统崩溃，缓存的加入只会加重损失。
于是我们需要一个线程，周期性地将缓存中的内容写入磁盘，同时，不要忘记再文件系统关闭时也要将所有内容写入。可以想象，若周期过短，缓存效果将下降，若周期过长，安全性会下降，这是这个工程上必然遇到的困境。
为了加速读取，我们还可以设计一个 read_ahead 机制——当某个线程请求读取磁盘中某个块时，它有很大概率会继续读取下一个块，我们 异步 地将下一个块的内容提前写入缓存便可以加速读取。
提示
设计完这些，并通过 Project2 的测试点，本部分就收工啦！
