OS-SWAP 实验报告

前言

个人感觉SWAP相比Shell来说要不友好一些，因为很难有循序渐进的正反馈，做题的大部分时间都在对着各种报错痛苦地干瞪眼。本次任务我分了两段时间做，一次是考军理之前，花了两天整的时间企图给他速通掉，结果最后被一个顽固的bug击败，选择先复习。然后是24号考完马原之后又做了一天半，最后才完成。

题目要求基于自己的lab6进行迭代，实现一套页面置换（SWAP）机制。该实现采用Linux风格的LRU（Least Recently Used）算法，通过维护active_list和inactive_list两个双向链表来管理物理页面的访问频率，并在物理内存不足时将页面换出到磁盘，在访问时自动换入。

题目分解

工作内容

LRU算法实现：正确维护active_list和inactive_list双向链表，跟踪页面访问模式
SWAP操作：为内核创建访问磁盘的接口，实现swap_out和swap_in操作，管理磁盘存储
COW兼容性：确保SWAP机制与Copy-On-Write机制正确协作
性能优化：避免频繁的TLB刷新，优化磁盘访问

一些注意事项

MIPS R4K没有硬件访问位，需要通过软件TLB重填模拟。记得考虑奇偶页的问题。
页表项需要同时支持COW、SWAP等多种状态
注意换出页面的状态保存和恢复
确保系统稳定性，避免页表等关键页面被换出

具体实现

数据结构扩展

为了支持功能，我对核心数据结构进行了扩展。

首先，扩展了Page结构体。这部分基本按照题目来就好，例如新增页面标志位（pp_flags），其中我使用的有PG_REFERENCED用于标记页面近期是否被访问，PG_PINNED用于“钉住”关键页面防止被换出，以及后期做性能优化的时候我临时追加了PG_ACTIVE和PG_INACTIVE用于标识页面当前所在的LRU链表，避免每次都遍历。

同时，为了在换出页面时能找到所有指向它的页表项（PTE），每个Page结构体维护一个Pte_list链表，链表中的每个节点PteNode都包含一个指向PTE的指针、该PTE对应的虚拟地址以及地址空间ID（ASID）。这样，当一个物理页需要被换出时，可以遍历这个链表，修改所有相关的PTE。

此外，当一个页面被换出到磁盘后，其在Page结构体中保存的状态（如引用计数pp_ref和页表项链表pp_pte_list）需要被保留。为此，我也是用了题目推荐的状态管理结构PageState，并创建了一个全局数组page_state_set。该数组以磁盘块号为索引，用于存放换出页面的PageState信息，确保页面换入时能够正确恢复状态。

LRU算法实现

LRU算法的核心在于追踪页面访问模式和定期老化页面。

页面访问追踪通过page_touch函数实现。当一个页面被访问时，该函数会被调用。它首先检查页面是否被钉住，如果是则不参与LRU管理。否则，它会设置页面的PG_REFERENCED标志位。如果页面原先在inactive_list中，page_touch会将其移动到active_list的末尾，表示它最近被频繁使用。如果页面是新分配的，则会被加入inactive_list的末尾。

页面老化机制由shrink_active_list函数负责，该函数会定期执行（例如在调度器中）。它遍历active_list中的所有页面：

如果页面的PG_REFERENCED标志位被设置，说明它在上一轮老化周期中被访问过。此时，函数会清除该标志位，给予它“第二次机会”，让它留在active_list中。
如果标志位未被设置，则说明该页面近期“不活跃”，函数会将其从active_list移动到inactive_list的头部，使其成为优先被换出的候选者。

SWAP磁盘管理

使用磁盘的次IDE控制器作为SWAP分区，以避免与主文件系统冲突。访存操作对着lab5里的内容模仿即可。

磁盘空间分配采用位图（bitmap）来管理。为了提高分配效率，我引入了一个next_free_hint变量作为优化。分配函数swap_block_alloc会从next_free_hint指示的位置开始搜索空闲块，而不是每次都从头开始。找到空闲块后，更新next_free_hint，这大大减少了平均搜索时间。

页面换出实现

页面换出是内存紧张时的核心操作，由置换算法和具体的换出逻辑组成。

置换算法（algo_swap）负责挑选一个“受害者”页面。它的策略如下：

优先在inactive_list中寻找。
遍历inactive_list，如果一个页面未被钉住（这也算是重复检查了）且其PG_REFERENCED标志位为0，则它就是理想的受害者，算法直接返回该页面。
如果页面的PG_REFERENCED标志位为1，则清除该标志位，给予其最后一次机会，然后继续查找下一个。
如果遍历完inactive_list仍未找到合适的页面（或列表为空），则调用shrink_active_list将active_list中的不活跃页面老化到inactive_list中，然后重试查找。

换出操作（swap_out）是具体的执行者：

调用algo_swap获取一个受害者页面。
调用swap_block_alloc在磁盘上申请一个空闲块。
将受害者页面的状态（引用计数、PTE链表）保存到与磁盘块号对应的page_state_set条目中。
通过IDE接口，将受害者页面的物理内存内容写入到分配好的磁盘块中。
遍历该页面的PTE链表，对每一个PTE进行修改：将其有效位（PTE_V）清零，设置一个自定义的PTE_SWAP标志位，并将物理地址部分替换为磁盘块号。同时，精确地使该PTE对应的TLB条目失效。
最后，清空受害者Page结构体的状态，使其成为一个干净的空闲页，可以被系统重新分配。

页面换入实现

当程序访问一个已被换出的页面时，会触发缺页异常，最终调用swap_in函数。

swap_in的逻辑与swap_out相反：

从触发异常的PTE中，解析出PTE_SWAP标志位和存储在地址部分的磁盘块号。
调用page_alloc分配一个新的物理页面。如果此时内存不足，page_alloc内部可能会递归地触发一次swap_out。
通过IDE接口，从磁盘的指定块号中将页面内容读入新分配的物理页。
从page_state_set数组中取出该页面之前保存的状态，并恢复到新的Page结构体中（包括引用计数和PTE链表）。
遍历恢复的PTE链表，将每个PTE重新指向新的物理页地址，并设置PTE_V、清除PTE_SWAP标志。
释放磁盘上的SWAP块，并清理page_state_set中对应的条目。
最后，调用page_touch将这个新换入的页面加入LRU管理体系。

TLB重填优化

为了将SWAP机制集成，我修改了TLB重填处理函数_do_tlb_refill。当发生TLB未命中时，内核会查找对应的PTE。

如果PTE中设置了PTE_SWAP标志，处理函数会立即调用swap_in，将页面从磁盘换回内存，并自动处理PTE的更新。
在页面被确认在内存中后（无论是原本就在还是刚刚换入），调用page_touch来更新其在LRU链表中的位置。
考虑MIPS处理器的奇偶页TLB项设计，确保成对的PTE被正确加载。

这种设计实现了按需换入，并且将LRU状态更新与页面访问紧密结合。

COW机制兼容性

为了让SWAP与写时复制（COW）协同工作，我调整了fork中的页面复制逻辑，并在SWAP相关代码考虑COW的存在。例如，fork操作在复制一个父进程的地址空间时：

如果一个页表项指向的页面是只读、COW页面，或者是已换出的页面（即PTE带有PTE_SWAP标志），那么子进程只复制这个页表项，而不分配新的物理页面。
对于已换出的页面，父子进程将共享同一个指向磁盘块的PTE。当其中任何一个进程首次访问该页面时，才会触发swap_in，并将页面加载到内存。此时，再结合COW逻辑，将其设置为只读。

性能优化要点

我最后的修复是解决TLE。我在本地发现三个样例都过之后兴冲冲的去交，然后惨遭重拳，评测结果全空。

经助教认证，这是典型的TLE症状。我去测了一下，我的项目此时跑完fork样例要花三分多，确实是太慢了。于是我开始做下面的优化。

1. TLB刷新优化

移除schedule中的全局TLB刷新
仅在页面状态变化时进行精确刷新

2. 磁盘访问优化

使用hint机制加速空闲块分配

3. 内存管理优化

使用页面标志位快速判断状态
优化链表操作减少遍历开销

大模型使用

不建议在搭建过程中依赖大模型。大模型是强大的工具，但是前提是自己得看过并能看懂他的代码，不然省下的精力会在debug阶段通通还回去。时刻保证自己对架构有掌控力是很重要的。

但是gemini还是很适合提出建议和找bug的，除了直接扔文件以外，让他帮着用命令行体验也很不错，成功帮我这个从没用过gdb的人靠看栈找到了一个关键bug。

感想

随着实验报告的完成，操作系统这门课程也正式告一段落。从lab0 extra的挫败到后面的习以为常，再到被SWAP折磨的这几个夜晚，这一切都要成为过往了。

操作系统的任务全部完成之后，大二的学习内容就基本全部结束。马上就要成为一年前觉得遥不可及的大三老登了，时间过得真快。