实验三 Nachos虚存
一、概述本实验牵涉到Nachos虚存子系统的部分实现，也是第一次用到Nachos的虚拟机。测试代码是一组覆盖了绝大部分虚存空间的数组操作，该虚存空间被映射到20个物理页中。
地址转换和页表结构已给出。本实验的目的是要实现缺页处理程序，这需要在适当的时候将某些页面替换出/入。为了减少缺页和将页面从内存淘汰到磁盘的次数，要求你实现二种页面替换算法：最少使用算法（LFU）、最近最少使用算法（LRU）。
二、准备注意：
本实验比较长，需要较多的时间才能完成，最好提前准备。
由于本实验比较复杂，所以略去了许多描述细节。
素材：
本实验的源代码是本压缩文件中的mp3.tar.gz文件。解包后，你要在userprog子目录下工作，当然也需阅读文件filesys/filesys.h，filesys/openfile.h，machine/translate.h，machine/timer.h，和bin/noff.h。本实验你只需修改文件memmanager.h和memmanager.cc。
下面是一些相关的细节问题。
结构：
大家都知道，每个地址空间都有相应的页表，页表中的每一项称为页表条目。在本实验中，我们会牵涉到其中的三个主要字段：USE、DIRTY和VALID，它们在machine/translate.h中有详细描述。
AddrSpace结构包含了Nachos进程地址空间的所有信息：页表、页表长度等，以及操作地址空间的函数。当创建了一个新的进程时，该结构也就随之产生并初始化。所提供的代码已实现了页面调度机制，在该机制中，仅在一个执行进程访问页面时，才将它从可执行的源文件中读入物理内存。所以，在进程刚创建时，页表中的所有条目都是初始化为无效的（所有页表条目的有效位都置为false）。然而，访问这样的页面（不属于任何程序段）一般来说是不合法的。当初始化一个页表时，要生成一个报告，该报告说明哪些页面的访问是合法的，而哪些页面的访问是不合法的（Legal字段）。每个可执行程序都以一个头开始，它指定程序中所有程序段的虚存范围。
若想得到更多信息，请阅读AddrSpace::AddrSpace()和noff.h中的相关描述。
开始：
调用AddrSpace::ReadSourcePage()函数来从可执行文件中读一个页面到物理内存。注意，该函数仅在进程第一次访问虚页时调用。至于后续的访问，如果页面不在物理内存中，则搜索替换文件而不是源文件。替换文件由类似与MainMemory的内存帧组成，只不过它们存储在磁盘上。一组称为“SwapOwners”的TranslationEntry指针用来跟踪指向替换文件中页面的页表条目，一个类似的结构“CoreOwner”则用来跟踪指向内存中页面的页表条目。
若想得到更多信息，请阅读AddrSpace::ReadSourcePage()和Memmanager::PageIn()。
执行：
在执行阶段，仿真程序将在TranslationEntrys中设置适当的位，如：当出现写操作时置DIRTY=TRUE、当出现写或读操作时置USE=TRUE。如果仿真器处理了这样一个TranslationEntry中的存储器请求：LEGAL=TRUE但VALID=FALSE，它将自陷到MemManager::faultIn()中去，这就是你要实现的地方：给定缺页的TranslationEntry，用SwapIn()、SwapOut()以及你要实现的将适当的缓冲页面调入物理页的方法，更新TranslationEntry并将控制权返回给虚拟机。
阅读代码MemManager::PageFaultExceptionHandler()，它由ExceptionHandler()在接收到一个缺页异常时调用。关于如何实现MemManager::faultIn()的一些细节和几点提示都以注释的方式在MemManager::PageFaultExceptionHandler()中给出。注意：在此函数中，程序计数器的值不应加一。在处理完异常且控制权返回给缺页进程后，引起缺页的那条指令将重新执行。
剖析：
“faultIn”是“handler”，而其它各种方法则聚合成了重要的功能：
PageOut负责将页面写到备份存储中，它只处理脏页，因为其它的页面已在备份存储中或是与原始状态相比没有变化，所以其它的页面可以覆盖它；
PageIn负责将页面读入指定的物理页，若该页不在备份存储中，则从原始文件中装载；
MakeFreeFrame负责在没有空闲页时用适当的页面替换算法来选择一个牺牲页；
RecordHistory是一个定时中断处理程序(在memmanager.cc文件中)，它修改translationEntries中适当的位来更新历史信息。
三、阅读指南阅读本文档；
阅读exception.cc、addrspace.h、addrspace.cc、memmanager.h和memmanager.cc；
在translate.h中看看TranslationEntry的声明；
阅读bitmap.h、bitmap.cc;
阅读MemManager:,pageOut 和MemManager:,pageIn ；
在编写代码之前，做好纸面设计。
四、问题：各种页面替换算法先决条件：RecordHistory
实现中断服务例程(ISR,Interrupt Service Routine)，以记录每个“in core”物理页的TranslationEntry中USE位的状态，用作历史信息。
4.1 N位历史信息的LFU算法利用RecordHistory()记录的历史信息，用最少使用算法选择出一个物理页面；
历史信息的位数可以随命令行参数而改变；
注意历史信息和USE位的当前状态；
若有多个物理页面的情况相同，则选择遇到的第一个物理页；
后续请求应直接从所选页面后的物理页开始查找（例如，从MakeFreeFrame返回）；
不要忘记在适当的地方复位历史信息。（提示：在其它函数中）
4.2 N位历史信息的LRU算法
五、增加页缓冲扩充faultIn，以实现页缓冲。该函数由MemManager::pageFaultExceptionHandler()调用。在实现时，可以利用前面介绍的pageIn 和pageOut函数。
页缓冲包含了一组物理页。注意，缓冲中的物理页不需连续，它们随机地分布在主存中。缓冲中的页数可随命令行参数而变化，且构造器可用，请将该值赋予变量<buffersize>。分配物理页给缓冲时，从存储器底端开始。（例如，Buffer[0]是最后一页，Buffer[1]是倒数第二页，…）而考虑缓冲中的条目时，则从前往后扫描。这有助于解决不一致性问题。
算法：
在下面的讨论中，主存代表不在缓冲中的物理页。当缺页时，首先检查主存中是否有空闲的物理页面（条件A），然后检查所缺页面是否在缓冲中（条件B）。有四种可能情况：
A=true，B=false：所缺页面读入主存中的空闲页并交缺页进程，缓冲无变化；
A=true，B=true：缓冲中的页面读入并交缺页进程，将内存中的空闲页加入缓冲；
A=false，B=true：从主存中选一页面作为牺牲页，将缓冲中的页面读入并交缺页进程，然后将主存中的牺牲页加入缓冲；
A=false，B=false：从主存中选一页面作为牺牲页。如果缓冲中有空闲页（无任何内容），则在读入所缺页面后交缺页进程，主存中的的牺牲页加入缓冲。如果缓冲中没有空闲页，则查找“修改位”为0的页面：若找到，则在读入所缺页面后交缺页进程；若没有找到，则说明缓冲中所有页面都是修改过的，将所有页面换出到交换文件中，任选一页读入所缺页面后交缺页进程，然后将主存中的牺牲页加入缓冲。
六、编译测试为了编译代码，在userprog目录中键入：
gmake depend
gmake
有三个测试程序：tc1、dump和tc2，但只有一个（tc2）充分测试了上述算法。在userprog目录中键入：
nachos –M <num_pages> <num_bits> -x,./test/<testcase>
其中，<num_pages>是页缓冲中的页数；<num_bits>在LRU算法中大于0，LFU算法中小于0；如果让<num_pages>为0，则关闭页缓冲。
测试程序使用了一个新的系统调用“test case”（代码见testcase.cc）来进行测试和显示。
建议按如下方法测试：
nachos –M 0 2 -x,./test/tc2
nachos –M 0 0 -x,./test/tc2
nachos –M 0 -2 -x,./test/tc2
nachos –M 5 2 -x,./test/tc2
nachos –M 5 0 -x,./test/tc2
nachos –M 5 -2 -x,./test/tc2
一、概述本实验牵涉到Nachos虚存子系统的部分实现，也是第一次用到Nachos的虚拟机。测试代码是一组覆盖了绝大部分虚存空间的数组操作，该虚存空间被映射到20个物理页中。
地址转换和页表结构已给出。本实验的目的是要实现缺页处理程序，这需要在适当的时候将某些页面替换出/入。为了减少缺页和将页面从内存淘汰到磁盘的次数，要求你实现二种页面替换算法：最少使用算法（LFU）、最近最少使用算法（LRU）。
二、准备注意：
本实验比较长，需要较多的时间才能完成，最好提前准备。
由于本实验比较复杂，所以略去了许多描述细节。
素材：
本实验的源代码是本压缩文件中的mp3.tar.gz文件。解包后，你要在userprog子目录下工作，当然也需阅读文件filesys/filesys.h，filesys/openfile.h，machine/translate.h，machine/timer.h，和bin/noff.h。本实验你只需修改文件memmanager.h和memmanager.cc。
下面是一些相关的细节问题。
结构：
大家都知道，每个地址空间都有相应的页表，页表中的每一项称为页表条目。在本实验中，我们会牵涉到其中的三个主要字段：USE、DIRTY和VALID，它们在machine/translate.h中有详细描述。
AddrSpace结构包含了Nachos进程地址空间的所有信息：页表、页表长度等，以及操作地址空间的函数。当创建了一个新的进程时，该结构也就随之产生并初始化。所提供的代码已实现了页面调度机制，在该机制中，仅在一个执行进程访问页面时，才将它从可执行的源文件中读入物理内存。所以，在进程刚创建时，页表中的所有条目都是初始化为无效的（所有页表条目的有效位都置为false）。然而，访问这样的页面（不属于任何程序段）一般来说是不合法的。当初始化一个页表时，要生成一个报告，该报告说明哪些页面的访问是合法的，而哪些页面的访问是不合法的（Legal字段）。每个可执行程序都以一个头开始，它指定程序中所有程序段的虚存范围。
若想得到更多信息，请阅读AddrSpace::AddrSpace()和noff.h中的相关描述。
开始：
调用AddrSpace::ReadSourcePage()函数来从可执行文件中读一个页面到物理内存。注意，该函数仅在进程第一次访问虚页时调用。至于后续的访问，如果页面不在物理内存中，则搜索替换文件而不是源文件。替换文件由类似与MainMemory的内存帧组成，只不过它们存储在磁盘上。一组称为“SwapOwners”的TranslationEntry指针用来跟踪指向替换文件中页面的页表条目，一个类似的结构“CoreOwner”则用来跟踪指向内存中页面的页表条目。
若想得到更多信息，请阅读AddrSpace::ReadSourcePage()和Memmanager::PageIn()。
执行：
在执行阶段，仿真程序将在TranslationEntrys中设置适当的位，如：当出现写操作时置DIRTY=TRUE、当出现写或读操作时置USE=TRUE。如果仿真器处理了这样一个TranslationEntry中的存储器请求：LEGAL=TRUE但VALID=FALSE，它将自陷到MemManager::faultIn()中去，这就是你要实现的地方：给定缺页的TranslationEntry，用SwapIn()、SwapOut()以及你要实现的将适当的缓冲页面调入物理页的方法，更新TranslationEntry并将控制权返回给虚拟机。
阅读代码MemManager::PageFaultExceptionHandler()，它由ExceptionHandler()在接收到一个缺页异常时调用。关于如何实现MemManager::faultIn()的一些细节和几点提示都以注释的方式在MemManager::PageFaultExceptionHandler()中给出。注意：在此函数中，程序计数器的值不应加一。在处理完异常且控制权返回给缺页进程后，引起缺页的那条指令将重新执行。
剖析：
“faultIn”是“handler”，而其它各种方法则聚合成了重要的功能：
PageOut负责将页面写到备份存储中，它只处理脏页，因为其它的页面已在备份存储中或是与原始状态相比没有变化，所以其它的页面可以覆盖它；
PageIn负责将页面读入指定的物理页，若该页不在备份存储中，则从原始文件中装载；
MakeFreeFrame负责在没有空闲页时用适当的页面替换算法来选择一个牺牲页；
RecordHistory是一个定时中断处理程序(在memmanager.cc文件中)，它修改translationEntries中适当的位来更新历史信息。
三、阅读指南阅读本文档；
阅读exception.cc、addrspace.h、addrspace.cc、memmanager.h和memmanager.cc；
在translate.h中看看TranslationEntry的声明；
阅读bitmap.h、bitmap.cc;
阅读MemManager:,pageOut 和MemManager:,pageIn ；
在编写代码之前，做好纸面设计。
四、问题：各种页面替换算法先决条件：RecordHistory
实现中断服务例程(ISR,Interrupt Service Routine)，以记录每个“in core”物理页的TranslationEntry中USE位的状态，用作历史信息。
4.1 N位历史信息的LFU算法利用RecordHistory()记录的历史信息，用最少使用算法选择出一个物理页面；
历史信息的位数可以随命令行参数而改变；
注意历史信息和USE位的当前状态；
若有多个物理页面的情况相同，则选择遇到的第一个物理页；
后续请求应直接从所选页面后的物理页开始查找（例如，从MakeFreeFrame返回）；
不要忘记在适当的地方复位历史信息。（提示：在其它函数中）
4.2 N位历史信息的LRU算法
五、增加页缓冲扩充faultIn，以实现页缓冲。该函数由MemManager::pageFaultExceptionHandler()调用。在实现时，可以利用前面介绍的pageIn 和pageOut函数。
页缓冲包含了一组物理页。注意，缓冲中的物理页不需连续，它们随机地分布在主存中。缓冲中的页数可随命令行参数而变化，且构造器可用，请将该值赋予变量<buffersize>。分配物理页给缓冲时，从存储器底端开始。（例如，Buffer[0]是最后一页，Buffer[1]是倒数第二页，…）而考虑缓冲中的条目时，则从前往后扫描。这有助于解决不一致性问题。
算法：
在下面的讨论中，主存代表不在缓冲中的物理页。当缺页时，首先检查主存中是否有空闲的物理页面（条件A），然后检查所缺页面是否在缓冲中（条件B）。有四种可能情况：
A=true，B=false：所缺页面读入主存中的空闲页并交缺页进程，缓冲无变化；
A=true，B=true：缓冲中的页面读入并交缺页进程，将内存中的空闲页加入缓冲；
A=false，B=true：从主存中选一页面作为牺牲页，将缓冲中的页面读入并交缺页进程，然后将主存中的牺牲页加入缓冲；
A=false，B=false：从主存中选一页面作为牺牲页。如果缓冲中有空闲页（无任何内容），则在读入所缺页面后交缺页进程，主存中的的牺牲页加入缓冲。如果缓冲中没有空闲页，则查找“修改位”为0的页面：若找到，则在读入所缺页面后交缺页进程；若没有找到，则说明缓冲中所有页面都是修改过的，将所有页面换出到交换文件中，任选一页读入所缺页面后交缺页进程，然后将主存中的牺牲页加入缓冲。
六、编译测试为了编译代码，在userprog目录中键入：
gmake depend
gmake
有三个测试程序：tc1、dump和tc2，但只有一个（tc2）充分测试了上述算法。在userprog目录中键入：
nachos –M <num_pages> <num_bits> -x,./test/<testcase>
其中，<num_pages>是页缓冲中的页数；<num_bits>在LRU算法中大于0，LFU算法中小于0；如果让<num_pages>为0，则关闭页缓冲。
测试程序使用了一个新的系统调用“test case”（代码见testcase.cc）来进行测试和显示。
建议按如下方法测试：
nachos –M 0 2 -x,./test/tc2
nachos –M 0 0 -x,./test/tc2
nachos –M 0 -2 -x,./test/tc2
nachos –M 5 2 -x,./test/tc2
nachos –M 5 0 -x,./test/tc2
nachos –M 5 -2 -x,./test/tc2
