北大操作系统nachos实习报告——第三部分内存系统实习.docx

操作系统实习三（虚拟内存管理）马亮 1001210767目录内容一：总体概述3内容二：任务完成情况3任务完成列表（Y/N）3具体Exercise的完成情况3内容三：遇到的困难以及解决方法13内容四：收获及感想13内容五：对课程的意见和建议13内容六：参考文献14内容一：总体概述通过本次实习，搞清了Nachos中虚拟内存部分的实现原理，通过实现TLB和页表的页面置换算法，修改系统为多线程驻留内存并实现lazy loading，进一步理解了操作系统实现虚拟内存的原理。并且本次实习过程中遇到大量错误，在解决错误的过程中进一步学习巩固了C+。内容二：任务完成情况任务完成列表（Y/N）Exercise1Exercise2Exercise3Exercise4Exercise5Exercise6第一周YYY第二周YYY第三周Y第四周YNN具体Exercise的完成情况第一周Exercise1 源代码阅读machine.h和machine.cc阅读这两个程序实现了执行用户程序的虚拟机，machine.h中将内存页大小定义为和磁盘扇区大小相同的128B，总共有32个页，通过一个char数组来模拟内存，内存总大小为32*128字节，通过一个40个长度的int数组来模拟40个寄存器。声明了TranslationEntry类型的tlb和pageTable作为快表和页表。Machine.cc中在构造函数中对寄存器和内存做了清零，RaiseException用来发出异常，包括系统调用、page fault等异常，调用exception.cc的ExceptionHandler方法来处理，还有一些读写寄存器、打印寄存器状态等方法。translate.h和translate.cc阅读translate.h中定义了快表项和页表项的结构TranslationEntry类translate.cc中ReadMem (int addr, int size, int *value)方法调用translate方法，将用户虚拟地址addr转换为物理地址，读出 size 个字节，存放在 value 所指向的空间中。WriteMem (int addr, int size, int *value) 方法调用translate方法，将用户虚拟地址addr转换为物理地址，然后将 value 表示的数值根据 size 大小转换成相应的机器类型存放在此物理地址中。Translate (int virtAddr, int *physAddr, int size, bool writing) 方法将用户的逻辑地址转换成实际的物理地址，同时需要检查对齐。 首先，判断用户逻辑地址是否对齐，没有对齐则返回 AddressErrorException。接着计算出虚拟地址所在的页号 vpn 及其在页面中的偏移量，根据采用不同的转换方法作不同的处理。如果采用的是线性转换表，当 vpn=pageTableSize 时， 即虚拟页数过大，返回 AddressErrorException。当页表中显示该页为无效时，返回 PageFaultException，一切正常则得到相应的页表表项。如果采用的是 TLB 转换表，查找 TLB 表，如果查找到，得到相应的页表项；如果没有查找到，返回 PageFaultException。如果得到的页表项是只读，设置writing 标志，返回 ReadOnlyException，如果表项中相应的物理地址大于实际的内存物理地址，返回 BusErrorException，都正常则返回NoException。Exercise2 修改exception.cc使得 Nachos 系统可以对 TLB 异常进行处理首先在machine.h中ExceptionType中增加一种异常TlbFaultException：然后在exception.cc中加入这种异常的处理方法：具体的TlbSwap页面置换算法见下一个exercise的说明Exercise3 为TLB机制实现一种合适的页面替换算法基本思想是利用系统中的totalTicks作为时间戳，每次使用到tlb中的一页时更新此页的时间戳为当前的totalTicks，需要淘汰一页的时候选取时间戳最早的那页，即LRU算法。由于nachos中原有的页表实现方法为线性页表，如果define了USE_TLB，则在machine类构造函数中初始化了tlb，故首先启用tlb。在translate.cc的ReadMem和WriteMem方法中，调用了translate方法来将虚拟地址转换为物理地址，而translate方法中如果定义了TLB，则会在TLB中寻找此页，如果找不到则发出PageFaultException异常。首先在TranslationEntry类中加入最后使用时间的属性，用以记录访问此页时的totalTicks：为了区分tlb缺页和页表缺页，利用上个exercise中声明的TlbFaultException来标识tlb缺页异常，修改translate方法中tlb寻页的相关代码如下：如果tlb中找到此页，则更新时间戳为当前的totalTicks。如果tlb中没找到，则发出TlbFaultException异常。Exception.cc中当接收到TlbFaultException异常时，调用machine类的一个TlbSwap方法，来将缺少的页从页表中装入tlb中。TlbSwap方法如下，首先根据转换出错的地址算出此地址所在虚存页的编号，然后循环tlb，找到未被使用的页或者上次使用时间最早的页A，将此虚存页从页表复制到tlb页A中，并且将页表和tlb中此页的最后使用时间都更新为当前totalTicks：Translate.cc的ReadMem和WriteMem方法中，调用修改后的translate方法，如果返回的是TlbFaultException，则说明tlb缺页，由于在上面的TlbSwap方法中已经将缺少的内存页从页表复制到了tlb中，但并没有将此虚存地址的内容写入物理内存，则还需再次调用translate方法，在tlb中找到此页，将内容写入此页的物理地址中：写一个用户程序测试tlb缺页置换的效果，编译为noff格式文件后运行此程序，运行：可看到tlb缺页成功的按照LRU算法进行了页面替换。第二周Exercise1 设计并实现一个全局性的数据结构（如空闲链表、位图等）来进行内存的分配和回收，并记录当前内存的使用状态。可以利用系统已经提供的bitmap功能来记录内存的分配。在system.h中加入全局位图memoryMap；同时在system.cc中声明memoryMap。修改addrspace类的构造函数，使得初始化物理页时从memoryMap获取：同时析构时相应位置0，回收物理页：Exercise2 目前Nachos系统的内存中同时只能存在一个线程，我们希望打破这种限制，使得Nachos系统支持多个线程同时存在于内存中。要实现多个线程同时运行在内存中，首先要修改nachos原有的内存分配方式，nachos原来的方式在给程序分配地址空间时，每次都先清空物理内存，然后从头开始依次写入code段和initData段。为了支持多个线程同时存在，在上一个exercise根据位图获取可用物理页的基础上，根据虚拟地址算出物理地址所在的页和页内偏移，然后逐位写入code段和initData段的数据，由于这时每个物理页都是从全局位图获得的，可保证写入的物理页不重复，并且是离散的分布于物理内存中的：还需将bzero(machine-mainMemory, size);这一句注释掉，以免每次都清空物理内存。Nachos在线程切换的时候，已经实现了页表的切换，machine-PageTable始终应当指向当前线程的页表。线程时用户程序寄存器也实现了保存和恢复。但是线程创建时并没有对线程的寄存器进行初始化，而是在AddrSpace中的InitRegister()初始化了虚拟机machine中的寄存器，改为多线程后，需要给每个线程在创建的时候对自己的用户寄存器进行初始化。为此，在thread类中增加InitUserRegisters方法，对线程的用户寄存器进行初始化。在progtest.cc中加入另一个测试线程，并发执行命令行传入的用户程序和halt用户程序，如下：运行测试，同时执行上一次实习做的createTest和halt这两个用户程序，可看到他们都在内存空间中同时运行了：Exercise3 基于TLB 机制的异常处理和页面替换算法的实践，实现缺页中断处理前面的TLB页面替换算法采用了LRU算法，利用系统的totalTicks记录使用每个页面的时间戳，每次找时间戳最小的一个替换出去。对于PageFaultException，也可采用相同的方法。TLB缺页时需要将内存中的对应页装入TLB，而PageFaultException时，则需要将磁盘中对应的页装入内存。为此，需要首先建立虚拟内存文件。为方便起见，可为每个线程分配一个虚拟内存文件，由于系统中只允许存在128个线程，故虚拟内存文件最多不超过128个。声明一个全局的长度为128的数组来记录文件名分配情况，在addrspace的构造方法中循环遍历此数组，找到未分配的虚拟内存文件名，并创建此文件。而后将用户程序的code段和initData段顺序写入此文件中。由于nachos在addrspace的构造方法中已将程序的code段和initData段全部装入了内存。故虚拟内存文件其实并没有作用，如果想实现内存中只装入运行程序所需的一部分内容，而产生PageFault后再从虚拟内存文件中加载对应页，则需要先实现lazy-loading。故更详细的说明见下一个exercise。第三周 Lazy-loading上一个exercise在addrspace构造函数中加入了建立虚拟内存文件并将内存内容写入的功能，实现lazy loading，需要限制每个线程能使用的实际内存页的大小，比如限制每个线程只能用到8个页帧，则addrspace初始化时将程序的code段和initData段全部装入虚拟内存文件，并且将前8个页帧大小的内容写入内存中。当PageFaultException发生时，调用一个PageSwap方法，从虚拟内存文件中加载对应的页帧到内存中，并替换掉内存中8个页帧中最长时间未使用的页。替换算法和之前实现的TLB页面替换算法相同，利用系统的totalTicks记录每个页帧的最后使用时间，每次找totalTicks最小的页面替换出内存，将虚拟内存文件中对应的页帧装入这个位置。第四周Exercise1 在已完成的文件系统和内存管理功能的基础之上，实现线程在“SUSPENDED”，“READY”和“BLOCKED”状态之间的切换。要实现线程的SUSPENED，需要实现线程的用户空间持久化到硬盘和从硬盘恢复到内存中的功能。之前的exercise已经实现了虚拟内存文件的功能。用户程序的地址空间已经完整的写入到了虚拟内存文件中，为了能够恢复用户程序的执行，还需要将用户寄存器的内容也写入此文件中进行保存。首先增加虚存文件的大小，在原本size上再增加40个int大小，用于记录用户寄存器的值。其次，在AddrSpace中加入一个Suspend方法，将本线程的所有内存中的页面写回虚拟内存文件，以便将来恢复。而且要放弃所有已经占有的物理页面。最后，在Thread类中增加Suspend方法，调用AddrSpace中的Suspend方法，并将自己所有寄存器的值写入到虚拟内存文件中的内存映像最后的40个int中。内容三：遇到的困难以及解决方法困难1这次作业在修改多线程同时存在于内存中的exercise时遇到了很多段错误，属于思路不清晰从而导致的逻辑错误，不过使用eclipse