在之前的 Project 2 中，我们让 Pintos 跑起了多个用户程序，但那时所有的程序大小都受限于物理内存。现在，我们要打破这个限制！

Project 3 Virtual Memory 是整个项目中相对具有挑战性的部分。你需要实现虚拟内存管理、延迟加载、栈增长以及页交换机制。

开始之前，请下载设计文档模板。由于 Project 3 建立在 Project 2 之上，请务必先修复 Project 2 的所有 Bug！（笔者这里有一个调试了半个礼拜也没搞定的bug，然后回头一看是 Project 2 留下的祸根）

文件介绍

vm 目录（新文件）

在这个项目中，你需要在 src/vm 目录下创建新文件：

frame.c / frame.h
- 帧表 (Frame Table)：记录每个物理页框的使用情况，用于实现页面置换算法（如 Clock 算法）。
page.c / page.h
- 补充页表 (Supplemental Page Table)：记录每个虚拟页的详细信息（在磁盘、在 Swap 还是在内存），这是处理 Page Fault 的核心。
swap.c / swap.h
- 交换表 (Swap Table)：管理 Swap 分区的空间分配，跟踪哪些 Swap Slot 是空闲的。

需要修改的现有文件

userprog/process.c
- 需要修改 load_segment 以支持延迟加载 (懒加载 Lazy Loading)。
userprog/exception.c
- 修改 page_fault()，这是实现按需分页的核心入口。
userprog/syscall.c
- 实现 mmap 和 munmap 系统调用。
devices/block.c / block.h
- 用于访问块设备以实现 Swap 功能。

任务要求与核心概念

核心数据结构

你需要设计并实现以下四个核心结构：

Supplemental Page Table (SPT)：补充页表。当发生 Page Fault 时，内核通过它查找该地址的数据应该从哪读取（文件、Swap 或全零页）。
Frame Table：帧表。全局唯一，用于物理内存分配。当内存满时，通过它选择一个帧进行置换 (Eviction)。
Swap Table：交换表。管理 Swap 磁盘空间。
Mmap Table：文件映射表。追踪哪些文件映射到了哪些虚拟地址。

关键功能

延迟加载 (Lazy Loading)：程序启动时不立即把所有代码读入内存，只有当 CPU 访问到相应页面触发 Page Fault 时，才从磁盘加载。
栈增长 (Stack Growth)：原本栈只有一个页（4KB）。现在需要根据访问情况动态增加页，限制通常为 8MB。
页面置换 (Page Replacement)：当物理内存耗尽时，必须选出一个页挤出去。要求实现类 LRU (最近最少使用) 算法，至少达到 Clock (时钟) 算法的效果。
内存映射文件 (Memory Mapped Files)：通过 mmap 系统调用将文件直接映射到内存空间。

执行建议与步骤

第一阶段：帧表与基础 SPT

实现基础的 frame_alloc（封装 palloc_get_page(PAL_USER)）。
实现补充页表（SPT），建议使用哈希表。
修改 process.c，在加载程序时不再直接读入内容，而是先在 SPT 中“挂号”。

第二阶段：Page Fault 处理器

修改 page_fault()，当缺页发生时，根据 SPT 的信息分配 Frame，并从文件系统读取数据。
完成后，你的 Pintos 应该能通过 Project 2 的测试，但此时是延迟加载的。

第三阶段：栈增长 (Stack Growth)

在 page_fault 中判断地址是否在栈附近（参考 esp 指针）。
如果是，则分配新页并扩大栈。

第四阶段：Memory Mapped Files

实现 mmap 和 munmap。
注意：映射的文件必须作为 backing store（置换时写回文件而不是 Swap）。

第五阶段：置换 Eviction 与 Swap

实现页面置换算法（建议用 accessed 和 dirty 位）。
实现 Swap 分区的读写逻辑。
处理最头疼的同步问题：防止一个页正在被写回磁盘时又被另一个线程访问。

代码量参考值

这是官方参考实现的 diffstat 结果，可以看到官方实现的 Project 3 的工作量接近 1500 行，比 Proj 2 翻了一倍。

Makefile.build       |    4
devices/timer.c      |   42 ++
threads/init.c       |    5
threads/interrupt.c  |    2
threads/thread.c     |   31 +
threads/thread.h     |   37 +-
userprog/exception.c |   12
userprog/pagedir.c   |   10
userprog/process.c   |  319 +++++++++++++-----
userprog/syscall.c   |  545 ++++++++++++++++++++++++++++++-
userprog/syscall.h   |    1
vm/frame.c           |  162 +++++++++
vm/frame.h           |   23 +
vm/page.c            |  297 ++++++++++++++++
vm/page.h            |   50 ++
vm/swap.c            |   85 ++++
vm/swap.h            |   11
17 files changed, 1532 insertions(+), 104 deletions(-)

回到目录

aaaaa online

CS130 操作系统I Project 3 Virtual Memory | 虚拟内存