虚拟内存管理实习报告.doc

虚拟内存管理实习报告姓名 李炜 学号 1100012810日期 4月10日目录内容一：总体概述3内容二：任务完成情况3任务完成列表（Y/N）3具体Exercise的完成情况3内容三：遇到的困难以及解决方法4内容四：收获及感想5内容五：对课程的意见和建议5内容六：参考文献5内容一：总体概述这次实习主要是加入对tlb和虚拟内存的进一步支持，并且实验一下在原理课上学到过的各种替换策略，tlb是为了加速从虚拟地址到物理地址的翻译过程，而虚拟内存更是肩负着提供比实际物理内存更大的虚拟内存的重任，有了虚拟内存，才可以运行比实际内存更大的程序。内容二：任务完成情况任务完成列表（Y/N）Exercise1Exercise2Exercise3TLB异常处理YYY分页式内存管理YYYLazy-loadingY倒排页表Y具体Exercise的完成情况TLB异常处理部分：Exercise 1:Progtest.cc这个文件中和本次实习相关的主要是StartProcess这个函数，在这个函数中，首先打开一个文件，判断这个文件是否是可执行文件，如果是的话，为这个文件开辟一块地址空间来运行一个新线程，之后初始化和这个线程相关的寄存器，初始化完成之后运行这个程序。其中在开辟新的地址空间的时候，为这个地址空间中的page table的每一项进行了初始化。所以在后面对translationEntry增加内容的时候，最好还是在这个初始化过程中加入相应的初始化操作。在构造可执行文件的空间时，首先读入这个文件的开始部分，即noffH，这个部分包含了文件的magic number（表示是否是可执行文件），文件中代码，数据，栈等各部分的位置、大小等。之后根据这个大小，按照页大小分配内存页数量，初始化page table，将可执行文件的代码段和数据段按照虚存与内存一一对应的方式读入内存中。Machine.cc(h)在这个文件中，主要是针对虚拟机整体的操作，其中在构造函数中，首先初始化了寄存器和内存，这个部分和本次实习没有关系，下面初始化了tlb中的项。开始的时候，我认为对于每个地址空间都应该有自己的tlb，每次切换线（进）程的时候都要同时切换tlb内容，这个方案在nachos这样的虚拟机上实际上时可以实现的，而且tlb的miss可能会比只有一个tlb要少很多，但是这种情况不符合计算机系统的实际情况，因为对于实际的计算机体系结构来说，tlb是一个硬件不见，每个cpu的核心应该具备一个tlb，因为多超标量等优化机制的存在，线程切换十分频繁，如果每次都要同时按照线程切换tlb，那样代价太大了，tlb本身是用来利用局部性来减少对page table的访问的，如果频繁改变tlb内容开销上太大，得不偿失。在这个文件中，与本次实习相关的还有raiseexception这个函数，这个函数其实就是针对不同的异常调用相应的处理函数的地方，在处理异常之前要先使得系统进入系统模式运行（之前在用户模式下）。Translate.cc(h)这个文件在这次实习中具有十分重要的作用，readMem和writeMem分别是从内存中读和写的函数，它们都需要首先进行虚拟地址到物理地址的转换，如果转换成功则继续读写操作，否则会对因为转换产生的异常进行处理。在translate函数中，首先检查想要读取的内存地址是不是对齐的，之后根据虚拟地址算出相应的虚拟页号和页内偏移（需要转换的其实只是虚拟页号到物理页号，页内偏移在虚拟页中和在物理页中都是相同的）。因为nachos本身只支持tlb或者page table中的一个，所以如果是page table模式的话，那么就在page table中直接取出vpn对应的项，并且取出物理页号，当然其间也要进行有效性检查，如果所需要的物理页是无效的，就会引发page fault异常。如果使用的是tlb模式，则在tlb中遍历查找想要读取的vpn，如果找不到，同样会引发page fault异常。之后的操作就是读出这个物理页的具体地址以及一些其它的检查操作。Exception.cc对于这个文件来说，只有一个Exceptionhandler函数，用来判断异常的类型和相应的处理方式并且处理异常，对于本次实习来说，其实就是加一个else if判断pagefaultexception异常并处理这个tlb miss。Exercise 2:从ExceptionHandler中可以看到对于系统调用的处理方法，就是输出调试信息，并且停止用户进程，对于TLB miss来说，开始的时候我仍然使用了PageFaultException，因为在translate文件中如果出现tlb miss会返回PageFaultException，也就是说在handler中首先判断产生的是PageFaultException，判断完之后，我感到很茫然，因为除了需要知道是何种异常外，还必须知道引发这个寻址异常的具体地址是什么，这样才能从page table中调入这个页，去哪里得知这个信息呢？重新去看translate中的读写内存的两个函数，可以看到translate函数返回异常，那么就会调用RaiseException这个函数，而我们可以看到引发异常的那个地址也被当做参数传了进去，在这个函数中，和这个我们需要的地址有关的就是把这个地址写到了一个寄存器中，因为寄存器是machine中的属性，也就是说不管是用户进程还是系统进程都共享相同的寄存器，这样我们就知道可以在exception handler中通过读取寄存器信息来得到那个引发异常的地址了。那么是哪个寄存器呢？从raiseException中可以看到是BadVAddrReg，这个是一个宏，对应着39号寄存器。这样，在ExceptionHandler中，我首先通过machine的读取寄存器的方法读出BadVAddrReg寄存器中的内容，有了这个地址就可以开始具体的替换过程了，对于替换的方法，我首先实验了通过hit次数多少来决定去除哪一个entry的方法，因为其中许多操作都涉及machine中的信息，所以我把这个处理函数放在了machine中，这个函数接受地址作为参数，学习translate中的方法，首先通过address计算获得vpn和offset，其实后来发现offset用处不大，只是在输出哪个物理地址时有帮助，有了vpn也就知道了哪个页要被换进，问题就是要找到一个tlb项来换出，对于这个目标来说，也很简单，只要通过遍历tlb表项，找到hit最小的一项，如果有valid为false的项，那么可以直接把这个项作为应该被换出的项即可，之后把这个tlb项写回到page table中，并且把vpn号page table中的项调入这个应该被换出的项所在的位置。之后还需要做些tlb项的初始化工作，把这个项的hit置为1（如果置成0的话可能会造成震荡，这一点是我在调试程序的时候，发现的），valid置为TRUE，为了看哪个地址引发了异常，我还让它输出了对应的物理地址。当然还要维护这个hit值，也就是说，在translate中每次tlb项被找到，就使相应的hit值加一。但是再后来的测试阶段我发现matmult这个算矩阵乘法的程序会产生真正的pagefault（内存不足），这样就有必要区分tlb miss和page fault了，于是我在machine.h中定义了新的异常类型叫TLBMissException，并且在exceptionHandler中添加了对这种类型的处理。Exercise 3：已经有了上一个exercise的基础，其实这个exercise也就不难了，我首先选择了使用aging算法（因为体系大作业曾经实现过，觉得不难），我通过定义宏GROWOLD使得tlb项的age右移一位，通过REFEREDTO使得age右移一位并且首位或上1，每次tlb项被使用时，就对它REFEREDTO，而在Exceptionhandler中如果不是要找的项，就先对它GROWOLD，这样较近时间被使用的tlb项就不会很快被换出（找的时候直接找age最小的就可以）。说起来比较简单，但是实际编写的过程中，发现在sort这个程序的测试中出现了震荡现象，经过仔细检查发现是因为age在translationEntry中被我定义为了int，但是实际上必须被定义成unsigned int，在找age最小的时候也需要使用unsigned int类型。之后听同学说lru实现起来比较简单，只需要通过stats-totalTick就可以知道最近被访问的时间了，于是我在之前应该REFEREDTO的地方把lastUsedTime赋成stats-totalTick，比较的时候同样找lastUsedTime最小的项。由于实现起来差不多，所以就不多说了。测试的时候我主要跑了halt，sort，matmult三个程序，halt是用来验证pageTable中的项可以被换入的正确性的，对性能比较上基本没有意义。而在测试sort时，aging算法和lru竟然产生了相同的miss次数，在tlb最多为8的时候，内存为1024页的时候，都产生了8678次miss，改变一些参数仍然相同，于是我只好继续通过matmult来测试。但是matmult在测试时会产生很大的问题，tlb中竟然出现了多次相同的项且valid都是1，我查了很长时间程序都不知道哪里错了，后来看matmult程序本身，发现注释说这个程序会造成内存溢出，于是我明白了，因为开始的时候我没有区别tlb miss和page fault，所以其实是引发了真正的page fault，之后像之前说的，我首先扩大了内存页数从128变到1024，之后区别page fault和tlb miss，这样之后测试aging和lru的miss次数，结果令我大跌眼睛，aging miss发生了8647次，而lru却只发生了5722次，原本一位aging会更高级的，结果却是原理更加简单的lru的miss次数更少。分页式内存管理部分：Exercise 4：由于nachos本身提供了bitmap这个很好的数据结构，所以我就直接使用bitmap来指示内存页的使用情况了，因为一个机器只能有一个内存，所以我把bitmap直接放到了system.cc中作为全局的数据结构称为memoryBitMap，并且在原来的if user_program中加入创建bitmap的new 操作。这样之后，就需要维护这个位图，也就是在addrspace中的初始化pagetable的时候，把原本是一一对应的虚存与物理内存的映射关系，改变成每次到bitmap中寻找空闲的页（bitmap中提供了find操作，可以直接做到，而且找到以后就已经标记了）。也就是说，在原来physical page直接赋成i的地方改成memoryBitMap-find就可以了。对于要求的记录内存使用情况，我在bitmap中添加了一个属性usedBits来记录使用了多少内存页，在初始化时赋成0，在clear的时候减一，在find的时候加一。为了输出使用情况，加入一个函数打印usedBits除以numBits的结果。Exercise 5：要支持多线程操作比较复杂，我花费了比较长的时间，终于找到了实现的方法，首先在初始化内存空间的时候，内存不能每次都清空，这样就需要把bzero这个操作注释掉，转而在每次page table找到某个页的时候将这个页置成0，接着向下看，到了把可执行文件中的代码段和数据段内容写入内存的部分，原来的时候可以直接把两个部分的内容全部写入内存，但是加入了分页机制后，就不能直接一一对应地写了，而要按照页来写，于是我采用了逐字节写的方式，每次先根据虚拟地址算出vpn和页内偏移，并且计算出在文件中的位置，然后把这个字节写入内存中相应位置。这样之后我转去修改progtest，我定义了用于启动可执行文件的函数作为线程需要用到的包装函数，然后fork两个线程，分别启动相同的sort可执行文件，这样之后发现只有一个文件能够运行，到了切换线程之后马上就会出现unexpected exception，我想了半天，终于明白了是之前的tlb的问题，在切换线程的时候，必须要把tlb清空（全部置成invalid），否则tlb中存的地址还是上一个线程的对应关系，这样自然会出错，于是我在thread中的restoreuserstate中把tlb全部置成失效，这样修改之后终于可以正常运行了。Exercise 6，Exercise7:首先，需要像之前的tlb miss一样先在exception里面加入对pageFaultException的处理，由于之前图省事，我在开始的时候把tlb miss也作为了page fault来处理，但是到了这里自然不能还这样处理了（之前的时候实际上根本不会出现page fault，如果出现的话那就是程序有错误，而我确实出现过，但是已经改正了，也就是之前所说的tlb清除操作），于是我先重新在machine里面定义了tlbMissException，之后在translate里面把需要使用tlb miss处理的都改成return tlbMissException，最后把exception里的改名，这样原来的tlb miss就彻底和page fault的处理分离开了。按照和之前tlb miss类似的步骤，加入page fault的处理，也就是在exception中加入pageFaultHandler在machine里面加入pageFaultSwap，handler和之前几乎完全一样，这里就不说了，重点当然在于pageFaultSwap，其实如果没有lazy-loading的策略，那么就不会产生page fault，所以我就一起实现了。还是先说这个swap函数，要在什么条件下触发page fault呢？这个看似简单的问题困扰了我很久，如果只有一个线程的话就十分简单了，当然就是page table里面的项valid是False的时候，但是对于有两个甚至多个线程的时候，就不是那么简单了，因为目前只有从page table到内存的指向关系，而没有倒过来从内存指向page table的，这样，如果线程1的某个页被线程2选择替代，那么并没有很有效的机制来使得线程1的page table及时修改其中指向相应页的项为valid，于是我决定修改bitmap，使得这个位图不仅能指示哪些页可用，而且需要它充当类似后面的challenge要求的倒排页表的功能，当然现在还没有那么高级，而只是需要有和内存中的页一一对应的，能够标记这个物理页对应的线程和这个线程中vpn，以及为了替换策略而实现的lastUsedTime，因为lazy-loading中还涉及将修改过的“脏页”写回的操作，所以我在这里还加入了dirty属性，于是我把这四个属性包装成bitmap文件中的一个小类称为MemoryEntry，在bitmap中添加一个MemoryEntry的数组，数组元素的数量和NumBits一样多，这样就可以起到一一对应的标记作用。经过这样的修改，就需要在找空页的时候加入lastUsedTime的因素，也就是说需要找lastUsedTime最小的页（还是首先找空页，在没有空页的情况下才使用lastUsedTime最小的页，也就是说我使用了lru的策略，找最近使用时间最长的）。而因为是lazy-loading，所以在addrspace里的构造函数中就不能把page table中的每个页和物理内存对应起来，这样，在这里我就不给physicalPage赋值，并且把valid设置为False，这样就可以在用到这个地址的时候调用pageFaultException了。现在就可以写出在translate中判断是否产生page fault的条件了，首先要判断page table中的这一项是否为valid的，其次要从bitmap里判断这个页是不是被当前线程拥有，并且物理页指向的vpn和现在的vpn是不是一致，只有这三个条件都满足，才认为没有page fault，否则就会return page fault exception。再回到swap函数中，swap的首要任务就是找到一个可用的物理页，把可执行文件中需要的页写入到这个物理页中，这个任务也是听上去不难，只要算出这个异常的地址并且把文件中的相应页写入就可以了，可是实际调试的过程中总是说指令不正确（6号异常），为什么呢？我看了好久代码才明白，在这个可执行文件的结构中，首先是noffH这个记录文件信息的文件头，而实际上文件中定义的虚拟地址并不包括这个文件头，比如我在调试的时候打印出code的虚拟地址是0,而inFileAddr是40，也就是说可能在这个文件中noffH占40字节的大小。于是我参照之前的没有lazy-loading时的做法，在addrspace中加入一个交换空间swapMemory，在初始化一个地址空间的时候，首先像之前一样把文件的code部分和initData部分写入这个交换空间中（不写入noffH），这样需要的地址就和文件中的虚拟地址是一致的了，对于这个交换空间来说，就是在addrspace中的一个类似于内存的大char数组，大小我赋给了它在addrspace中计算出来的需要的大小size，这样做的结果就是同时解决了脏页的问题，如果发生了writeMem操作，那么就把这个页在bitmap的memoryEntry中设置为dirty，而如果swap函数中挑选到的需要被替换的页是dirty的，那么就需要先从物理内存中将这个页写回到这个交换空间中，具体需要做的就是在挑选到一个页后，首先查询出这个物理页对应的线程的tid和vpn，然后通过以前的threadList找到对应的线程的指针，这样就可以得到这个线程的space（地址空间），之后就可以写回脏页了。写回脏页之后，就可以放心地使用这个页了，首先当然还是要先清空这个物理页，然后从交换空间中把计算出来的这个页写入到物理内存中，在bitmap中标记这个页（tid，vpn，lastUsedTime）。为了lazy-loading的缘故，还需要在addrspace中注释掉把文件写入到内存的部分，转而把文件写入到相应的交换空间中，为了方便，写入的时候我采用了实际上是虚拟页和交换空间中的物理页一一对应的方式（这样就可以在从交换空间中load这个页的时候直接用虚拟地址找到了）。经过这么多的努力，本来以为可以成功运行了，而且单线程页确实可以成功运行了，但是加入多线程后，还是崩溃了，于是又开始长时间的调试，发现在最后出错的时候，通过page fault找到可用的物理页后，没有进入tlb miss的处理函数中（发生page fault就一定会接着发生tlb miss），于是我在page fault swap这个函数的末尾加入了tlb miss swap来直接处理这各tlb miss，这样之后终于使得两个线程能够同时运行了。Challenge 2 倒排页表：从前面一个exercise可以看到，我已经实现了一个对于倒排页表来说十分关键的数据结构，就是bitmap的增强版，有了这个增强版，给出物理页号之后，我就可以查询到相应的线程号和虚拟页号等信息，为了完成倒排页表，下一步就是彻底抛弃每个线程内部的地址空间的页表以及machine中的页表，最简单的办法可以每次引用某个页时都去bitmap的memoryEntries中去遍历查找，但是这样的效率实在太低了，于是我决定在每个地址空间中增加一个链表来存放这个地址空间中占有的页，这样的话就不需要遍历整个物理内存中的页，而只需要遍历一个地址空间中的页。这个任务也是听起来容易，做起来费事的活。首先，要让list这个链表支持插入，删除，查询三个基本操作，也就是说给定vpn，必须能够在这个链表中插入一个项，删除具有这个vpn的项，查询是否有具有vpn的这一项并且返回这个项（实际上我只返回了物理页号）。于是我在list里添加了这三个相应的函数，把所有能想到的用到了page table的地方全部注释掉（其实只要把machine和addrspace头文件里面的注释掉，再用gcc帮着找错就可以了），找错的过程中，发现在析构函数中还需要将bitmap中所有属于这个地址空间的项清空，于是又添加了一个clear操作，以清空bitmap中相应的项。这样之后，原来用到page table和vpn的地方就直接去用这个vpn从pageList（我在addrspace中定义用来替代page table的数据结构）中查找就可以了，另外在找到可用的页后需要把这一项加入到地址空间中，感觉这样就基本可以了，于是就去试着跑了一下，果然可以运行了，很高兴啊。可是发现两个线程只用了39个页，而实际上我给分配了256个页，也就是说根本不会使用页的替换策略，因为总是会有空页的。于是我直接把内存大小调成了20页，这样就肯定需要替换了，刚一改，马上就错了，甚至是第一次page fault就直接段错误了，去查代码，发现之前在找到一个物理页后，没有去查这个页以前是不是真的被占用了，就去进行写回脏页操作，这样当然有问题了，于是先用bitmap自带的Test函数test一下，发现完全没变化，这不科学啊，接着查，发现find那步的时候我就直接把bitmap中找到的这个页给mark了，也就是说之后去查就一定是1了，无论之前到底是不是真的被使用了，好吧，只好去掉这里的mark，改为去MarkMemoryEntry（标记vpn，物理页号，使用时间的函数）里面去mark这个页，这样应该能跑了吧！确实能跑了，不过到了感觉快跑完的时候还是出了问题，在一次想替换一个页时却没找到，于是输出各种调试信息，包括输出地址空间中占有的链表中所有页的信息，发现好像要删掉的项在链表中不存在，于是我加了一条ASSERT，断