Status
Done
实验目的
实验内容：
- 在未实现虚拟内存管理之前，Nachos在运行一个用户进程的时候，需要将程序运行所需全部内存空间一次性分配。虚拟内存实现将突破物理内存限制。本实验核心任务为根据理论学习中涉及的对换（Swapping）技术，在Lab6的基础上，设计并实现用户空间的虚拟内存管理。
- 用户进程的帧数采用固定分配(建议5帧)，局部置换。
- 实现“纯按需调页”(pure demand paging)。
- 对class Statistics进行调用及修改，以便在程序结束时打出页故障次数及将牺牲页写入交换空间的次数。
- 页置换算法可以采用LRU、增强型二次机会、二次机会、FIFO等算法之一，或自己认为合适的其他算法(不包括随机置换)。
- 使用lab7目录中的示例程序n7(若lab7额外实现了多种算法，可用自己的lab7)，测试用户程序用同样ARRAYSIZE参数值的sort，但不同的页置换算法(详见code/lab7/n7readme.txt)多次运行n7。不同页置换算法运行结束时显示的user ticks数是否一样？解释这是为什么？
- 最优页置换算法(OPT)有最低的页故障率，但需要未来的页面引用信息，因此不能用于实际环境，主要用于评估其他页置换算法的性能。在前述1-5实现的基础上，给出在Nachos中获得最优页置换算法页故障次数的具体实现方法(不要求实现可运行的代码。在实验报告中用文字描述即可，必要时可在文字中结合进关键代码片段、数据结构、对象等说明)。
参阅：
操作系统课程设计 指导教程 -张鸿烈 2012.pdf，pp.60-63
操作系统概念 第7版或第9版 第9章相关部分
code/lab7/n7
code/lab7/n7readme.txt
code/lab7/n7screen.txt
注1：要求用耗费用户内存比较多的code/test/sort.c作为虚拟内存的用户测试程序。可根据需要适当修改ARRAYSIZE值的大小，但不要修改除此之外的其他sort.c代码。
注2：可以让Nachos直接运行用户程序sort。也可以先运行一个Nachos用户程序，然后第一个Nachos用户程序用Exec()系统调用来运行sort。二者在演示验收时只需演示一个即可。
实验步骤与内容
基础知识
虚拟内存
用户进程需要整个地址空间都进入物理内存后才能开始运行，这种进程全部进入内存后再运行的策略是很受限制和浪费内存空间的。
实际上多数程序的工作方式是符合”局部性原理”的，即当前要执行的程序的和当前要访问的数据往往是集中在某些内存页面上，而当前执行不到程序和访问不到的数据完全可以先放在第二存储器中，等到用到时再从第二存储器中装入物理内存。
虚拟内存技术就是解决程序部分装入物理内存也能执行的技术。由于允许进程部分驻留物理内存，所以一个进程的逻辑空间可以远远大于分配给进程工作的物理空间。
请求式分页技术
虚拟内存技术可以在带有分页式内存管理的系统中，通过采用请求式分页存储管理技术实现。请求式分页内存管理技术的意思是，装入物理内存的内存逻辑页仅在访问到它时才被分配到物理内存帧。其关键的技术是，当请求的页不在物理内存时使用缺页异常或自陷进入内核，由内核缺页异常处理程序从外存将该页装入一空闲内存帧中，如果无空闲帧，将选择已在物理内存中的一页将其置换。在这一异常被处理完成之后，发出对该内存访问的同一条指令将再次被执行。
Nachos 提供了实现虚拟内存技术的基本机制，其中缺页异常是由MIPS机模拟函数translate产生的。这个函数是由函数ReadMem和WriteMem调用的。
页置换
页置换是解决当物理内存已满且有一新页需要装入时怎样选择被淘汰页的问题。
Nachos 对于页置换的硬件模拟的支持反映在machine/translate.h文件中定义的页表结构TranslationEntry 中。
变量valid和readonly对应valid和read-only位，是用于内存管理和保护的。
变量use和dirty对应硬件的use位和dirty位，是用于虚拟内存页置换的。
帧的分配
在Nachos的MIPS模拟器中的物理内存是通过一个字节型的数组模拟的。在文件machine/machine.cc 中定义的 Machine 类的构造函数初始化了这个基本内存
1.设计并实现用户空间的虚拟内存管理。
在未实现虚拟内存管理之前，Nachos在运行一个用户进程的时候，需要将程序运行所需全部内存空间一次性分配。虚拟内存实现将突破物理内存限制。本实验核心任务为根据理论学习中涉及的对换（Swapping）技术，在Lab6的基础上，设计并实现用户空间的虚拟内存管理。
虚拟内存管理的核心是实现地址空间映射，Nachos 使用页表 (
TranslationEntry) 来记录虚拟地址与物理地址之间的映射关系，将用户进程的虚拟地址转换为物理地址，并通过对换（Swapping）技术突破物理内存限制，即当物理内存已满时，选择一个页将其从内存中写回磁盘，并腾出空间供新页加载。在实验六中，我们已经实现了虚拟地址到物理地址的基本转换，但尚未支持缺页处理和页置换。
因此我们需要扩展的功能涉及以下几个方面
- 缺页异常处理。
- 页表扩展以支持有效性检查。
- 对换空间的设计。
涉及的文件为
translate.cc和addrspace.cc 1.修改AddrSpace类的构造函数和析构函数
初始实验中，我们定义了LoadSections函数，实现对执行文件的加载，每次判断出所需页不在内存中时，便从可执行文件中重新调页。
但是为了解决每次重新加载可执行文件带来的复杂性，我们发现可以将页面在首次加载时存储到
swapfile 中，后续访问只需要从 swapfile 中调页，从而简化文件操作，最终实现的版本如下：构造函数：
析构函数：
2.用户进程的帧数采用固定分配(建议5帧)，局部置换
固定分配：每个用户进程分配一个固定数量的物理页帧（此处为 5 帧），不随运行时其他进程的需求动态调整，这种方式易于管理，但如果分配的帧不足，可能导致频繁的缺页中断。
局部中断：进程只能在自己的分配帧范围内执行页置换操作，有助于隔离进程间的内存使用，避免某个进程过度占用内存资源。
在system.h中添加
在system.cc中添加
在addrspace类中修改或添加以下内容：
3.实现“纯按需调页”(pure demand paging)
按需调页（demand paging），在需要时才调入相应的页。
常为虚拟内存系统所采用。
对于按需调页虚拟内存，只有程序执行时需要才载入页，那些从未访问的页不会调入到物理内存。
一种极端的情况是所有的页都不在内存中，就开始执行进程。当操作系统将指令指针指向进程的第一条指令时，由于其所在的页并不在内存中，进程立即出现页错误。当页调入内存时，进程继续执行，并不断地出现页错误直到所有所需的页均在内存中。这时，进程可以继续执行且不出现页错误。这种方案称为纯按需调页(pure demand paging)：只有在需要时才将页调入内存。
在exception.cc中添加
PageFault方法在interrupt.h中定义并在interrupt.cc中具体实现：
修改AddrSpace构造函数：
当
valid = TRUE时，表示该虚拟页当前有对应的物理页，且映射关系是有效的。当
valid = FALSE时，表示该虚拟页当前没有映射到物理内存，访问这些页会导致缺页异常。使用按需调页策略，也就是说，只有当进程实际访问某个虚拟页时，才会将该页调入内存。在程序初始化时，所有虚拟页都还未被使用，因此这些页的
valid值被设置为FALSE。4.class Statistics调用修改
对class Statistics进行调用及修改，以便在程序结束时打出页故障次数及将牺牲页写入交换空间的次数。
在stats.h中定义新的变量numPageWrites
并在stats.cc中完成对该变量的初始化和print输出
5.页置换算法
页置换算法可以采用LRU、增强型二次机会、二次机会、FIFO等算法之一，或自己认为合适的其他算法(不包括随机置换)。
在实现虚拟内存管理时，页置换算法是关键环节。当内存空间不足时，操作系统需要选择一页替换出内存，以腾出空间给新的页面。Nachos实验中提供多种可选的页置换算法，此处选择FIFO算法，主要实现逻辑是：首先读取需要执行的文件到主存中，然后进行执行，每当内存的页满的时候，对出现缺页错误，按照FIFO将部分页面写入磁盘，然后空闲的页进行读入，依次进行，直到程序执行完毕，具体实现如下：
在addrspace.h中定义以下数据结构和函数
在
addrspace.cc中实现：在AddrSpace类构造函数中初始化FIFO相关结构
页置换逻辑
接下来我们测试一下我们完成的页置换算法：./nachos -x ,,test/sort.noff
由于获得的输出太长，我们将输出结果保存到output1.txt文件中
分析结果：
例如，此处第 0 页是第一个按需加载的页面。当 5 个页面填满内存后，如果需要加载新的第 7 页，则会将第 0 页替换出去，分析其他地方，结果符合预期。
完整运行结果可以见附件output1.txt
6.测试sort
使用lab7目录中的示例程序n7(若lab7额外实现了多种算法，可用自己的lab7)，测试用户程序用同样ARRAYSIZE参数值的sort，但不同的页置换算法(详见code/lab7/n7readme.txt)多次运行n7。不同页置换算法运行结束时显示的user ticks数是否一样？解释这是为什么？
由readme可知pra选项用来选择页置换算法：
pra 0 最优页置换(需要相应的二进制引用串文件才能执行)
pra 1 FIFO页置换
pra 2 二次机会(时钟)页置换
pra 3 增强型二次机会页置换
pra 4 LRU(栈)页置换，默认算法
pra 5 a值为>=5的整数时，为随机页置换(仅用于比较前述算法的优劣)，这时a值也作为伪随机数的种子
使用./n7 -pra -0 -x ../test/sort.noff > test_output_0 等命令测试sort，并将结果保存下来
接下来分析一下获得的结果（ARRAYSIZE参数值设置为100）
具体结果见附件
test_output_0
test_output_1
test_output_2
test_output_3
test_output_4
test_output_5
执行用户态指令，时钟前进是显而易见的。我们认为， Nachos 执行每条指令所需时间是固定的，为一个Tick时钟前进一个单位。
user tick之间会有差异是因为缺页调度算法不同，缺页之后使用调度算法将该页调入内存，修改页表项，重新执行该指令读取该页，即发生的缺页中断越多，额外的user tick越多。
为了更清晰的看出差距，绘制折线图如下：
通过该图表，可以明显地看出相比随机的页置换，使用页置换算法可以较大程度上提高效率。最优算法代表着缺页次数的下限；FIFO调页时仅考虑了初次访问，效果最差，LRU考虑最后的访问时间，效果最优，RU的两个近似算法效果次优，但增强二次机会算法的效果与LRU非常接近，且复杂度比LRU低，比较适合做调页算法。
7.获得最优页置换算法页故障次数
最优页置换算法(OPT)有最低的页故障率，但需要未来的页面引用信息，因此不能用于实际环境，主要用于评估其他页置换算法的性能。在前述1-5实现的基础上，给出在Nachos中获得最优页置换算法页故障次数的具体实现方法(不要求实现可运行的代码。在实验报告中用文字描述即可，必要时可在文字中结合进关键代码片段、数据结构、对象等说明)。
最佳页面置换算法在每次换页时换出最晚使用或不再使用的页。具体实现方法如下：
1.在 Nachos 的虚拟内存管理模块中，增加对页面引用序列的记录。
可以在缺页处理函数中记录被访问的虚拟页号，保存到一个队列或数组中：
2.通过读取记录的页面引用序列，模拟程序的页面访问行为。
3.实现 OPT 算法逻辑，在模拟中，当一个页面需要调入主存时，如果内存尚未满，将页面加入主存；如果内存已满，计算当前内存中的每个页面何时会被再次使用，替换距离未来使用时间最远的页面。
结论分析和体会
通过这次实验，我深入理解了虚拟内存管理的核心概念和实际实现过程。虚拟内存技术使得程序在物理内存不足时仍然能够运行，这突破了物理内存的限制，提升了系统的资源利用率。在实现过程中，我体会到了缺页异常和页置换算法的重要性，尤其是在处理按需调页和实现对换技术时，如何有效管理内存和处理页错误是一个复杂且关键的过程。
在虚拟内存管理的设计中，页表起到了至关重要的作用，它负责虚拟地址到物理地址的映射。而实现对换空间和局部置换的过程中，也让我更加了解了如何管理内存中的物理页，确保进程之间的内存隔离与资源优化。
通过对不同页置换算法的比较和测试，我发现不同算法在性能上有显著差异，例如LRU和FIFO等算法对于内存管理的效率有直接影响，而最优页置换算法则提供了理论上的最低页故障率，尽管在实际中无法实现。这使我对内存管理算法的选择有了更深刻的认识。
总体来说，实验让我更加熟悉了操作系统中内存管理的细节，理解了如何利用虚拟内存技术提升系统的效率和稳定性，并掌握了如何设计和实现虚拟内存的关键机制。