nachosLab4实习报告剖析.docx
《nachosLab4实习报告剖析.docx》由会员分享，可在线阅读，更多相关《nachosLab4实习报告剖析.docx（29页珍藏版）》请在冰点文库上搜索。
nachosLab4实习报告剖析
虚拟内存实习报告
内容一：
总体概述
实习的主要内容是了解和改进nachos存储管理相关实现，主要分为三个部分。
第一部分的主要内容是实现TLB相关异常处理和置换算法，第二部分的主要内容是实现全局内存管理机制，使得nachos内存可以同时存在复数线程，第三部分的主要内容是实现程序运行时载入所需页面。
扩展部分主要是增加线程挂起状态以及实现倒排页表。
内容二：
任务完成情况
任务完成列表（Y/N）
Exercise1
Exercise2
Exercise3
Exercise4
Exercise5
Exercise6
Exercise7
Y
Y
Y
Y
Y
Y
Y
Challenge1
Challenge2
Y
Y
具体Exercise的完成情况
1、TLB异常处理
目前，Nachos系统对于内存的管理是基于软件模拟的TLB机制。
其工作原理、异常处理、替换算法等方面，与分页式内存管理非常相像。
Exercise1源代码阅读
阅读code/userprog/progtest.cc，着重理解nachos执行用户程序的过程，以及该过程中与内存管理相关的要点。
阅读code/machine目录下的machine.h（cc）,translate.h（cc）文件和code/userprog目录下的exception.h（cc），理解当前Nachos系统所采用的TLB机制和地址转换机制
（1）用户程序执行过程
userprog/progtest.cc定义函数StartProcess主要功能是实现用户程序启动，如果我们希望执行test中的用户程序，那么我们进入userprog，执行./nachos-x../test/（用户程序），通过识别-x参数，nachos调用StartProcess执行用户程序（具体实现在threads/main.cc）
StartProcess的基本流程是，通过文件系统定义的OpenFile打开相关文件，通过AddrSpace的构造函数建立用户空间，装载文件，通过AddrSpace的InitRegisters函数初始化用户寄存器，通过AddrSpace的RestoreState函数装载页表，通过machine的Run函数运行用户程序
AddrSpace的构造函数实现在userprog/addrspace.cc，主要流程是，获取文件头，大小端做适宜转换，通过文件头计算文件所需空间，包括代码段，初始化数据段，未初始化数据段，栈空间4个部分，通过文件所需空间计算出文件所需的虚拟页面数量，创建用户空间页表，指示了第i个虚拟页对应第i个物理页，将用户程序的正文段和相关数据依次调入内存
AddrSpace的InitRegisters函数实现在userprog/addrspace.cc，主要流程是初始化普通寄存器（初始化为0），初始化当前指令指针（PC，初始化为0），初始化下一条指令指针（初始化为4），初始化栈指针（地址空间尾部适当前移）
AddrSpace的RestoreState函数实现在userprog/addrspace.cc，主要流程是将页表装载到machine类中，准备执行用户程序
machine的Run函数实现在machine/mipssim.cc，基本流程是通过OneInstruction函数完成指令译码和执行，通过interrupt的OneTick函数使得时钟前进
machine的Run函数通过machine的ReadMem函数读内存数据，通过machine的WriteMem函数写内存数据，两个函数的实现在machine/translate.cc，核心是translate函数，translate函数实现在machine/translate.cc，主要功能是实现虚拟地址到物理地址的转换，translate函数可能返回相应的错误，在这样的情况下，ReadMem函数/WriteMem函数调用RaiseException函数进行处理，RaiseException函数定义在machine/machine.cc，基本流程是将错误信息存储在特定位置，调用ExceptionHandler函数处理不同的错误，ExceptionHandler函数实现在userprog/exception.cc，主要流程是根据错误信息处理不同错误。
目前支持的错误
NoException,//正常
SyscallException,//系统调用
PageFaultException,//缺页（页表/快表）
ReadOnlyException,//访问只读页面
BusErrorException,//总线错误
AddressErrorException,//访问地址对齐错误/超出范围
OverflowException,//算数溢出
IllegalInstrException,//非法指令
NumExceptionTypes
寄存器支持
（2）TLB机制和地址转换机制
表项维护的位置是machine/translate.h中TranslationEntry数据结构
classTranslationEntry{
public:
intvirtualPage;//虚拟页号
intphysicalPage;//物理页号
bootvalid;//该Entry是否使用，TRUE表示使用
boolreadOnly;//对应页的访问属性，TRUE示只读，否则为读写
booluse;//该Entry是否被使用过，每次访问后置为TRUE
booldirty;//对应的物理页使用情况，TRUE表示被写过
}
相关参数
以下参数定义在filesys/disk.h
#defineSectorSize128
以下参数定义在machine/machine.h
#definePageSizeSectorSize
#defineNumPhysPages32
#defineMemorySize（NumPhysPages*PageSize）
#defineTLBSize4
TLB初始化的位置是machine/machine.cc中machine的构造函数
TLB的使用的位置是machine/translate.cc中的translate函数，基本流程是遍历TLB数组，查找是否有对应映射，如果有，那么TLB命中，直接进行物理地址转换，否则，TLB没有命中，标志PageFaultException，进入Exception处理。
（目前还没有对应的处理函数）
地址转换机制的位置是machine/translate.cc中的translate函数，基本流程是，通过虚拟地址得到vpn和offset，通过TLB或是Pagetable得到
vpn对应的ppn，（否则抛出异常，在异常处理函数中做处理，但目前这部分没有实现），通过ppn和offset得到物理地址，返回物理地址。
需要说明的是，在处理完TLBmiss或者Pagefault之后，不需要将PC+4，因为异常处理函数结束后，返回的最终位置会是OneInstruction函数的取指阶段。
取指失败后，OneInstruction函数会退出，然后再用相同的PC取指。
而这次就能够TLBhit或者pagetablehit了。
machine/machine.cc的Machine类模拟内存，重要函数包括
Run运行用户程序
ReadRegister/WriteRegister读/写寄存器
OneInstruction执行一条指令
ReadMem/WriteMem读/写内存
Translate地址转换（虚拟地址->物理地址）
RaiseException抛出异常
userprog/addrspace.cc的AddrSpace类模拟用户程序内存，重要函数包括
InitRegisters初始化相关寄存器
SaveState保存机器状态
RestoreState恢复机器状态
Exercise2TLBMISS异常处理
修改code/userprog目录下exception.cc中的ExceptionHandler函数，使得Nachos系统可以对TLB异常进行处理（TLB异常时，Nachos系统会抛出PageFaultException，详见code/machine/machine.cc）
基本思路：
（1）我们需要使用TLB，但是根据nachos的默认设置，TLB没有开启，需要修改userprog/Makefile，开启USE_TLB（后面困难部分详细说明#ifdef）
DEFINES=......-DUSE_TLB
（2）PageFaultException分为两种情况，一种情况是页表失效，一种情况是快表失效，需要分别进行处理，通过machine->tlb进行判断
elseif（which==PageFaultException）{
if（machine->tlb!
=NULL）{
处理快表失效
else{
处理页表失效
}
}
（3）目前的情况下，因为物理页面全部进入内存，所以不会发生页表失效的问题，处理页表失效时直接使用ASSERT（FALSE）
（4）处理快表失效的主要流程是首先从machine的BadVAddrReg寄存器中取出
发生异常的虚拟地址，并算出vpn（在RaiseException函数中，将发生异常的虚拟地址放入该寄存器），然后确定快表替换的表项，如果快表存在空的表项，那么直接使用空的表项，否则根据特定的规则确定替换的表项，这里实现的是直接替换首个表项，最后实现表项的替换，需要设置表项的相关信息
测试结果：
结合Exercise3进行测试
Exercise3置换算法
为TLB机制实现至少两种置换算法，通过比较不同算法的置换次数可比较算法的优劣
基本思路：
（1）FIFO算法
FIFO算法淘汰的是最先进入内存的页面，具体实现时，每次移除快表数组的首项，并将后面的项依次前移，新的表项进入快表数组的尾项
（2）LRU算法
LRU算法淘汰的是最久没有使用的页面，具体实现时，设置数组LRU_queue，数组各项数值分别是1,2，...，TLBSize，数值越大表示越久没有使用，每次替换的表项是LRU_queue为TLBSize的对应的表项，需要注意的是，数组数值在TLB命中和不命中的时候都需要进行相应的修改，总的修改思路是当前表项数值为1，小于当前表项的数值加1
表项选择：
表项维护（TLB命中）：
表项维护（TLB没有命中）：
测试结果：
使用nachos提供的排序程序sort进行快表置换算法的相关测试，因为原来的程序超出内存限制，所以将原来的数组大小适当缩小（我选择缩小为100），另外，因为我们目前没有实现Exit系统调用，所以将程序最后的Exit语句注释，改为已经实现的Halt系统调用，修改Hait系统调用，输出快表相关信息
使用FIFO算法
使用LRU算法
可以发现，LRU算法的快表命中率有一定提升，符合实际
另外，我们可以编写自己的测试程序进行测试，例如我们建立test文件，基本功能是实现数组的按列赋值，这样的实现相当于数组的按列遍历
因为我们添加文件，所以需要修改相应的MakeFile
重复上面的测试
使用FIFO算法
使用LRU算法
可以发现，LRU算法的快表命中率有一定提升，符合实际
2、分页式内存管理
目前Nachos系统中，类ClassThread的成员变量AddrSpace*space中使用TranslationEntry*pageTable来管理内存，应用程序的启动过程中，对其进行初始化，而在线程的切换过程中，亦会对该变量进行保存和恢复的操作（使得类ClassMachine中定义的ClassMachine:
:
TranslationEntry*pageTable始终指向当前正在运行的线程的页表）。
Exercise4内存全局管理数据结构
设计并实现一个全局性的数据结构（如空间链表，位图等）来进行内存的分配和回收，并记录当前内存的使用状态
基本思路：
我选择使用位图维护内存空间，在machine类增加成员变量bitmap，变量类型为整型数组，相应位置为1表示相应内存已经被使用，相应位置为0表示相应内存没有被使用，初始化时所有位置为0。
另外，需要实现两个函数find和clear，find函数的主要功能是分配内存空间，主要流程是返回空闲的内存，并且将位图对应位置设置为1，如果没有空闲的内存，那么返回-1，clear函数的主要功能是回收内存空间，主要流程是将当前页表对应的所有位图位置设置为0
分配内存空间的find函数主要在内存空间初始化时调用，需要修改userprog/addrspace.cc中的构造函数
回收内存空间的clear函数主要在程序退出时调用，需要实现相关的系统调用Exit，具体定义参见syscall.h，这个系统调用需要增加PC数值
实际上,也可以利用已经实现的BitMap类来记录物理内存使用情况
测试结果：
运行空的程序，结果如下（为了方便，直接使用halt.c）
可以发现，实现了对内存的分配和回收
Exercise5多线程支持
目前Nachos系统的内存中同时只能存在一个线程，我们希望打破这种限制，使得Nachos系统支持多个线程同时存在于内存中
基本思路：
核心是修改userprog/addrspace.cc将用户程序的正文段和相关数据依次调入内存的过程，修改前调入内存的位置根据虚拟地址确定，因为系统的内存中同时只能存在一个线程，并且规定这个线程的虚拟地址和物理地址相同，修改后调入内存的位置根据物理地址确定，因为我们希望系统支持多个线程同时存在于内存中，基于Exercise4实现的相关机制，我们需要首先获得虚拟地址对应的物理地址，然后写入相关的数据，为了方便，这里选择逐个字节写入
另外，线程切换时，快表会失效，需要考虑这样的情况
voidAddrSpace:
:
SaveState（）
{
for（inti=0;imachine->tlb[i].valid=FALSE;
}
测试结果：
我选择修改userprog/progtest.cc定义的函数StartProcess，前面已经叙述，函数StartProcess主要功能是实现用户程序启动，测试的时候，在StartProcess函数中，再创建一个线程，并让这个线程装载一个用户程序（为了方便起见，两个线程装载相同的用户程序，我使用的用户程序是空的函数，即前面提到的修改后的halt.c），且抢占式执行（通过currentThread->Yield（）实现）。
因此我们会看到，主函数的用户程序分配相关空间后，还没有开始执行，新的线程的用户程序就分配相关空间并且执行。
当这个线程执行完毕并且释放相关空间之后，主函数的用户程序执行并且释放相关空间。
这就说明了，可以多线程同时存在于内存中。
需要说明是，因为涉及线程切换，所以在已经实现的Exit系统调用的基础上增加currentThread->Finish（）结束当前线程
新线程运行函数
主线程运行函数
运行结果（空间分配部分）
运行结果（空间释放部分）
可以发现，首先，用户程序1分配空间，用户程序2分配空间，然后，用户程序2开始执行，完成执行，释放空间，最后，用户程序1开始执行，完成执行，释放空间，基本符合实际。
Exercise6缺页中断处理
基于TLB机制的异常处理和页面替换算法的实践，实现缺页中断处理（注意，TLB机制的异常处理是将内存中已有的页面调入TLB，而此处的缺页中断处理则是从磁盘中调入新的页面到内存）、页面替换算法等。
基本思路：
缺页中断处理的核心是将发生缺页中断的虚拟页面拷贝到适当的物理页面
前面已经叙述，PageFaultException分为两种情况，一种情况是页表失效，一种情况是快表失效，需要分别进行处理
elseif（which==PageFaultException）{
if（machine->tlb!
=NULL）{
处理快表失效（已经实现）
else{
处理页表失效（需要实现）
}
}
假设虚拟内存通过文件virtual_memory模拟（后面按照这样的思路实现），我们需要通过文件系统的相关操作获得文件的内容
根据前面的方法，我们可以得到发生中断的虚拟页面，同时，根据前面实现的全局内存管理数据结构，我们可以尝试获得空闲的物理内存
如果存在空间的物理内存，那么不需要考虑页面的替换，如果不存在空闲的物理内存，那么需要考虑页面的替换，这里实现的是朴素的替换算法，即替换首个物理页面，需要说明的是，替换的过程中需要检查脏位，如果脏位设置，说明页面已经被修改，需要将当前页面写回磁盘模拟虚拟内存的文件
确定使用的物理页面后，将虚拟页面的内容拷贝到物理页面，页表的相关信息需要进行设置，最后关闭模拟虚拟内存的文件
测试结果：
结合Exercise7进行测试
3、Lazy-loading
Exercise7
我们已经知道，Nachos系统为用户程序分配内存必须在用户程序载入内存时一次性完成，故此，系统能够运行的用户程序的大小被严格限制在4KB以下。
请实现Lazy-loading的内存分配算法，使得当且仅当程序运行过程中缺页中断发生时，才会将所需的页面从磁盘调入内存
基本思路：
前面已经实现缺页中断的处理，这里只需要修改Addspace的构造函数中将用户程序的正文段和相关数据依次调入内存的部分，修改前是将相关数据调入内存，修改后是将相关内容写入文件。
首先建立模拟虚拟内存的文件，然后写入代码段和初始化数据段，最后关闭相关文件。
需要说明的是，这里我选择不向内存写入任何内容，也可以先向内存写入一定数量的内容
同时，解除页面限制ASSERT（numPages<=NumPhysPages），页表初始化时所有表项设置为无效，即pageTable[i].valid=FALSE。
需要说明的是，因为目前的文件系统限制文件的最大长度，所以这里实际上没有解除用户程序的大小限制，如果需要实现这样的目的，需要修改文件系统。
测试结果：
重新运行前面提到的修改后的halt程序（空函数）
可以发现，在缺页中断时，根据前面实现的全局内存管理数据结构进行物理内存的分配，将虚拟页面调入相应的位置，基本符合实际。
Challenge1为线程增加挂起SUSPENDED状态，并在已完成的文件系统和内存管理功能的基础之上，实现线程在“SUSPENDED”,”READY”和“BLOCKED”状态之间的转换
基本思路：
这里假设我们已经完成Challenge2倒排页表，在这样的情况下，所有线程共用相同的页表，注意到我们已经完成Exercise7的Lazy-loading，在这样的情况下，线程运行前不向内存写入任何内容，只有在需要时才通过缺页中断载入特定的页面。
所以，我们需要实现的SUSPEND状态实际上就是READY状态，需要实现的核心状态转换是从RUNNING状态到SUSPEND状态的转换，注意到已经实现的Yield函数实现线程从RUNNING状态到RUNNIG状态的转换，我们需要实现的SUSPEND函数实际上就是在此基础上增加将相关页面写入磁盘的过程，这里由于不理解makefile的相关机制，所以我选择分别实现Suspend_prepare函数和Suspend函数，前者实现在machine/machine.cc，后者实现在thread/thread.cc
定义函数Suspend_prepare实现将相关页面写入磁盘的过程，需要说明的是，需要写回的页面需要满足是当前线程的页面并且脏位已经设置
定义函数Suspend实现线程的挂起，该函数和Yield函数的实现完全相同,主要流程是将当前线程添加到就绪队列尾部，并且通过线程上下文转换从就绪队列中选择线程运行。
如果就绪队列为空，Yield函数不执行任何操作，当前线程继续运行。
测试结果：
仿照Exercise5的测试思路，修改userprog/progtest.cc定义的函数StartProcess，前面已经叙述，函数StartProcess主要功能是实现用户程序启动，测试的时候，在StartProcess函数中，创建一个线程，输出当前内存信息。
主函数的用户程序分配相关空间后，输出内存信息，然后进入suspend状态，此时，新建的线程开始运行，输出内存信息，两次输出结果对比可以说明SUSPENDED状态的相关属性。
需要说明的是，因为前面已经实现Lazy-loading，执行时进行内存分配，调入相关页面，所以这里选择在线程退出时执行Suspend_prepare函数和Suspend函数。
新线程输出内存信息
主线程运行用户程序
主线程输出内存信息并suspend
主线程suspend前内存信息
主线程suspend后内存信息
可以发现，SUSPENDED状态的实质是将当前线程的页面从内存调入磁盘
Challenge2多级页表的缺陷在于页表的大小与虚拟地址空间的大小成正比，为了节省物理内存在页表存储上的消耗，请在Nachos系统中实现倒排页表
基本思路：
倒排页表的基本思路是从物理地址出发建立页表，而不是从虚拟地址出发建立页表。
需要修改的部分主要包括userprog/addrspace.cc构造函数页表初始化的部分和userprog/exception.cc异常处理缺页中断部分。
经典页表的规模由虚拟内存决定
pageTable=newTranslationEntry[numPages];
倒排页表的规模由物理内存决定
pageTable=newTranslationEntry[NumPhysPages];
倒排页表基于物理内存进行索引
for（i=0;ipageTable[i].virtualPage=i;
pageTable[i].physicalPage=i;//核心部分
pageTable[i].valid=FALSE;
pageTable[i].use=FALSE;
pageTable[i].dirty=FALSE;
pageTable[i].readOnly=FALSE;
}
异常处理缺页中断部分前面已经叙述，确定使用的物理页面后，将虚拟页面的内容拷贝到物理页面，页表的相关信息需要进行设置，设置需要适当修改machine->pageTable[pos].valid=TRUE;
machine->pageTable[pos].virtualPage=vpn;//核心修改
//machine->pageTable[vpn].physicalPage=pos;//对比可见区别
machine->pageTable[pos].use=FALSE;
machine->pageTable[pos].dirty=FALSE
升级会员 