《虚拟内存机制实习报告范本.docx》由会员分享，可在线阅读，更多相关《虚拟内存机制实习报告范本.docx（31页珍藏版）》请在课桌文档上搜索。
1、虚拟内存机制实习报告目录一：总体概述3二：任务完成情况3任务完成列表(Y/N)3具体EXerCiSe的完成情况3三：遇到的困难以及解决方法29四：收获及感想29五：对课程的意见和建议30六：参考文献30一总体概述通过认真仔细阅读Nachos系统虚拟内存部分的源代码，理解虚拟内存的管理和应用机制，用户程序的运行逻辑，并修改源代码，达到“实现虚拟存储系统”的目标。二：任务完成情况任务完成列表（Y/N）Exercise1Exercise2Exercise3Exercise4Exercise5Exercise6Eyesyesyesyesyesyes具体Exercise的完成情况Exercise1:源代
2、码阅读Partl:阅读code/userprog/progtest.cc,着重理解nachos执行用户程序的过程，以及该过程中与内存管理相关的要点O阅读情况：用户程序执行过程：步骤相关解释在main函数中，如果检测到传入的参数和“执行用户程序”相关，那么执行StartProcess函数(progtest,cc)在StartProcess函数中装载并运行一个用户程序StartProcess函数中:1.用OpenFiIe类打开文件OpenFiIe类在文件系统中定义，包括各种对文件的基本操作，如read,writeo实质上是包装了操作系统的底层函数。2.用AddrSpace类创建一个用户空间，并将打
3、开的文件装载进去创建用户空间包括：1 .获取文件头，并将大小端做适宜转换；2 .通过文件头计算出文件所需空间，包括代码段，初始化数据段，未初始化数据段，栈空间4个部分3 .通过文件所需空间计算出文件所需的虚拟页数量4 .创建用户空间的PagDtabIa,指示了第i个虚拟页（将）对应第i个物理页5 .由于目前是最基本的【直接映射+单用户程序无切换】模式，因此此时要将所有的虚拟页中的内容写到物理页（主存）当中。3.（AddrSpace:InitRegistersO）初始化用户空间中的各种寄存器，包括PC设为0,栈指针移到空间底部为执行用户程序做准备！4.（AddrSpace:RestoreStat
4、e（）将用户的部分状态（如pagetabIe）装载到machine类中，准备执行事实上，仅仅是将用户空间的PagetabIe（在第二步创建的）装载到machine的指针中,相当于是用户程序在machine上运行时，是通过machine的pagetabIe映射找到对应内容运行的5.调用machine-Run,运行用户程序Machine-run是在mipssim.cc中定义的。其工作原理为：1.通过OneInstruction(instr)模拟mips,将一条指令进行分割，并软件模拟执行。其中，在Onelnstruction函数中，通过machine-ReadMem,读取主存中当前PC值指向的地址
5、里的指令。在ReadMem函数中,通过TransIate函数对传入的虚地址做转换。在TransIate函数中，如果虚地址没有找到对应的实地址转换，就会抛出异常（返回异常值）。返回的异常值在ReadMem中判断，并传入RaiSeException函数中RaiSeException函数会调用ExceptionHandIer函数对不同的异常做相应的处理。（以上是异常处理机制。在这里就顺便说了。）2.调用OnetiCk让时间前进3.重复1,2Part2:阅读code/machine目录下的machine,h(cc),transIate.h(cc)文件和code/userprog目录下的exceptio
6、n.h(cc),理解当前Nachos系统所采用的TLB机制和她址转换机制。TLB机制和地址转换机制:相关内容简单解释TransIationEntry类(transIate.h),包括：VirtuaIPage,physicalPage,以及一些标志位：vaIid,readonIy等。标识了用户空间的第i个虚拟页应该映射到主存的第j个物理页，并且这个物理页目前所处的状态。（valid?readnly?等）TLB初始化（machine.cc构造函数）:生成指定数量的TransIationEntry构成的数组，并且设置均为InvaIid.TLB本身就类似于PagetabIe的子集，有若干的的映射对。T
7、LB的使用（transIate.cctransIate函数）:1.遍历TLB数组，查找是否有无对应映射2.如果有，TLB命中，直接进行物理地址转换；否则，TLBMISS,进入Exception处理。（目前还没有对应的处理函数）地址转换机制：在transIate.cctransIate函数中进行。1 .通过VirtUaladdr,计算出vpn和offset;2 .通过TLB或是直接通过PagetabIe,获得vpn对应的ppn;（否则抛出异常，在异常处理函数中做处理，但目前这部分没有实现）3 .通过ppn和offset得到物理地址，将物理地址返回。无TLBmiss或是pagefau11处理（ex
8、ception.cc）:在上一个表格中已经对异常处理是如何进入的做了介绍。无但这里要补充一点：在处理完TLBmiss或是Pagefault之后，不需要将PC+4,因为异常处理函数结束后，返回的最终位置会是OneInstruction函数的取指阶段。取指失败后，OneInstruction函数会退出,然后再用同样的PC取一次指令。而这次就能够TLBhit或者Pagetablehit了。Exercise2:TLBMISS异常处理任务：修改code/userprog目录下exception.cc中的ExceptionHandIer函数，使得Nachos系统可以对TLB异常进行处理（TLB异常时，Na
9、chos系统会抛出PageFauItException,详见code/machine/machine.cc）o完成情况：关于异常处理的机理已经在EXerCiSel中说明了。因此能够对TLB异常进行处理，我们只要在判断传入的参数为TLBMlSS的异常，并对其进行处理即可。事实上，我在实际操作的时候，TLBMISS和PAGEFAULT,抛出的异常都是PageFauItException,此后再判断machine-tIb是否为空。如果为空，则执行PagefauItFunc;否则，执行TLBmiSsFuncoTLBmissFunc:步骤简单解释1.从machine的BadVAddrReg寄存器中取出发
10、生异常的虚拟地址，并算出vpn;在RaiSeException函数中,将发生异常的虚拟地址放入该寄存器的。2.扫描pagetabIe,寻找该vpn对应的项。目前情况，是一定可以找到的。由于目前用户程序运行的机理是：将所有segment全部写入主存中，并且全部做好了虚实映射，放在自己的PageTabIe中。当mechine需要加载这个用户程序时，会获得这个pagetableo于是相当于是,mechine通过这个pagetabIe,可以得到用户空间所有虚地址对应的实地址。因此当TLBMISS时，查找pagetabIe,是不会Miss的。3.接下来是寻找放入TLB的位置：1) 先考虑TLB中inva
11、Iid的项，如果存在，写入该项；2) 如果不存在invalid项，那么就涉及TLB置换算法，这在Exercise3中介绍。总之最后一定可以找到一个放置新的entry项的位置。无Exercise3:置换算法任务：为TLB机制实现至少两种置换算法，通过比较不同算法的置换次数可比较算法的优劣。完成情况：FIFO替换算法LRU替换算法1 .如果替换的是Invalid项,那么不涉及算法。2 .否则，将数组第一个项丢3.为每个entry设立一个IrU数值。当TLBHIT时，HIT项的IrIl左移加一，其余项弃，其他项向前移动一位。的IrU左移；当TLBMISS新添加的项放在数组最后时，进入异常处理函数4
12、.异常处理函数中，如果替换的是Invalid项，则将所有valid项（包括当前替换项）的Iru值清零5 .否则，扫描TLB数组，找到Lru值最小的一项进行替换，并将所有项的IrU值清零测试的用户程序将数组大小改成5的矩阵相乘：matmuIto将会分配18个物理页，TLB访问次数为15000左右。（visittime不同，是因为每次miss异常处理之后，还会再次访问该地址，因此MiSS次数不同，造成ViSittime次数也会不同。）测试结果FIFO:TLBvisittimeis15534,hittimets14475,httrateis.9318271.RU:TLBvisittimeis1532
13、7,htttimeis14429,hitrateis0.941411结论：LRU算法略优于FIFO。Exercise4:内存全局管理数据结构任务：设计并实现一个全局性的数据结构（如空闲链表、位图等）来进行内存的分配和回收，并记录当前内存的使用状态。完成情况:增改情况简单解释创建Machine类中,新增一个bitmap的数据结构memoryMNG,大小设置为物理页大小memoryMNG的母个bit对应一个物理页的分配状况内存分配Addrspace.cc构造函数中,在构建用户空间的pagetabIe时，通过bitmap的成员函数find返回第一个为0的位，将其作为空闲物理页分配。Find函数返回第
14、一个为0的位，并将该位置1。这非常符合我们的要求。如果不存在为0的位，返回7。因此我会用Assert来保证能够正确分配物理页。内存回收Exception.cchandIer函数中，关于在哪回收内存，这是个比较麻烦的问题。因为用户程序运行完毕之后，是不会离开对于exit系统调用的处理函数中，通过bitmap的成员函数CIear,将pagetabIe中的所有物理页释放，并设置该项为invaIidmachine-run的for循环的，并且在调用machine-run之后的语句也不会被执行。因此，只能在exit系统调用中回收比较可行。补充：关于exit系统调用的异常处理函数其实有点麻烦，因为用户程序可
15、以显式调用Exit,而用户程序结束之后，也会自动执行一个exit。所以，有可能会有2个exit被执行。考虑到这个情况，需要做如下处理：1)如果bitmap已经被回收过了，就break出来。2)exit处理函数之后，PC要+4。测试结果截图:phys page0 for mainisallocated.phys page1 for maintsallocated.phys page2 for mainISallocated.phys page3 for mainisallocated.phys page4 for maintsallocated.phys page5 for mainisallo
16、cated.phys page6 for maintsallocated.phys page7 for mainisallocated.phys page8 for maintsallocated.phys page9 for mainisallocated.starts running.thread main thread main分配页开始执行用户程序Phys Phys Phys Phys Phys Phys PhyS Phys PhyS Physpage page Page page page Page Pge0123456page 7page 8page 9exited. for ma
17、in for main for main for main for main for main for main for main for main for mainclear, clear, clear, clear, clear, clear, clear, clear, clear, clear.用户程序结束释放页Exercise5:多线程支持任务：目前NaChoS系统的内存中同时只能存在一个线程,我们希望打破这种限制，使得Nachos系统支持多个线程同时存在于内存中。完成情况：考虑：目前用户程序对mainMemory的操作是：在初始化用户空间的时候，会将mainMemory清零，并写入
18、自己的内容。因此，每次运行用户程序，只能有一个在主存中。（主存里仅容许一个用户程序存放）如下截图：/zeroouttheentireaddressspace,tozerotheunitializeddatasegment/andthestacksegmentbzero（machtne-maiMemory,size）;此外，目前mainMemory并没有真正实现分页，所有的segment都是直接且一次性全部写入的，如下图：主存一个用户程序因此，我们希望实现的目标是，将主存分页（物理页）,也将用户程序分页（虚拟页）这样不同的用户程序的某些虚拟页就可以映射到某些物理页上，也就可以“共存”了，原理如下
19、图：T 代码段十数据段T切分成代码段数据段PageSiZe 大A 瑾）若干份每一份对应了一个 ,mi 址页号就是从OH始 往后Sl写,物理碱 页号前面已经分配 好.数螃K（通过每个字节的虚拟地址找 度与节 入到对应的物理地址即可）标注的位BL放入 mainmemory 当一中（困示随便西 的.不连犊.事实 上要按照实际情 * 在真正实现的时候，是按照字节写入的，先写代码段，再写数据段。if(noffH.code.size)DEBUC(,a,Initializingcodesegment,atx%x,size%dn,noffH.code.virtualAddr,noffH.code.size);
20、/positionofcodetobewrittenintomainmemorytntcode_pos=noffH.code.InFtleAddr;for(tntj=0;jReadAt(8(machine-mainMemorypaddr)Jl,code_pos+);/InFileAddrmeansthepositioninthefile)if(noffH.InttData.size)DEBUG(a,Initializingdatasegment,atx%x,size%dn*,noffH.initData.VirtualAddr,noffH.InitData.size);/positionofc
21、odetobewrittenintomainmemorytntdata_pos=noffH.InitData.inFtleAddr;for(tntj=;jReadAt(S(machine-mainMenorypaddr),1,data_pos+);/iFileAddrmeansthepositioninthefilepritf(%dn,paddr);测试的时候，在startprocess函数体中，再新创建一个线程，并让这个线程装载一个用户程序，且抢占式执行。因此我们会看到：主函数的用户程序分配完页表后，还没开始执行，另一个线程的用户程序就分配页表，并执行了。当这个线程执行完毕之后，才轮到主函数
22、的用户程序执行。这就说明了，可以多线程同时存在于主存当中。此外，还有一个需要说明的点：线程切换是如何影响用户程序切换的？在scheduIer-run函数的ifdefuser_program的宏定义语句中，包括以下两个函数：函数简单解释Switch之前currentThread-SaveUserState()将所有用户程序的寄存器，从machine的寄存器数组拷贝到装载线程的寄存器数组中，包括PC寄存器等。currentThread-space-SaveState()目前函数体为空。改写：将machine的TLB数组全部设置为invaIido（因为线程切换后，TLB中的内容全部失效）Switch
23、之后currentThread-RestorellserState()与对应，将所有用户程序的寄存器，从装载线程的寄存器数组拷贝到machine的寄存器数组中，相当于恢复上下文环境。currentThread-space-RestoreState()与对应，将用户空间的Pagetable装载到machine上。总结：通过寄存器数组以及PagetabIe的转换，实现了不同用户程序的切换。测试截图：（测试函数：主线程和第二个线程均运行一个只有空函数体的用户程序。）wwubuntu:OSachos-3.4/code/userprog$./nachos-x./test/haltttd=,prtortt
24、y=lmainthreadtscreatedphysPhySphysPhySPhySPhySPhySIphysPhySphysPhySPhySPhySPhySPhySPhySphysPhySPhySphyspagePage1page2page3page4pageSpage6page7page8page9pagepagepagepagePagepagePagepagepagepage1416171819forIforIforIforIforIforIforIforIforIforIfor.for:forIforIforiforiforforforformaintsallocated,maints
25、allocated,mainisallocated,nattsallocated,maintsallocated,maintsallocated,natntsallocated,mainisallocated,maintsallocated,natntsallocated.secondsecondsecondsecondsecondsecondsecondsecondsecondsecondthreadISthreadisthreadtsthreadtsthreadtsthreadtsthreadtsthreadtsthreadtsthreadts主线程中的用户程序分配页threadsecon
26、dthreadstartsrunning.threadsecondthreadexited.allocated,allocated,allocated,allocated,allocated,allocated,allocated,allocated,allocated,allocated.第二个线程中的用户程序分配页第二个线程中的用户程序开始运行PhySPhySPhySPhySPhySPhySphysohvsPagepagePagepagePagepagePagel1112141516forforforforforforforsecondsecondsecondsecondsecondsec
27、ondsecondforSeCOndthreadthreadtsclear,threadtsclear,threadtsclear,threadtsclear,threadtsclear,threadtsclear,threadisclear.Clear.第二个线程中的用户程序结束运行第二个线程中的用户程序释放页physpage17forsecondphyspage18forsecondphyspage19forsecondtid=lhasfinished.nowinthreadmainthreadisclear.threadisclear.threadisclear.threadmainst
28、artsrunning.threadmainexited.physpageOPhySPhySPhySPhySPhySPhySPhysPhySPhySpage1page2page3page4page5page6page7page8page9forforforforforforforforforformainmainmainmainnatnmainmainmainmainmainclear,clear,clear,clear,clear,clear,clear,clear,clear,clear.线程切换主线程中的用户程序开始运行主线程中的用户程序结束运行主线程中的用户程序释放页TLBvisitt
29、imeis58,hittimeisMachinehalting!51,hitrateis.87931Ticks:total76,idle,system3,user46DiskI/O:reads,writesConsoleI/O:readsO,writesPaging:faultsNetworkI/O:packetsreceived,sentCleaningup.ww0ubuntu:-/OS/nachos-3.4/code/userprog$Exercise6:缺页中断处理任务：基于TLB机制的异常处理和页面替换算法的实践，实现缺页中断处理(注意！TLB机制的异常处理是将内存中已有的页面调入TL
30、B,而此处的缺页中断处理则是从磁盘中调入新的页面到内存)、页面替换算法等。Exercise7:Lazy-1oading任务：我们已经知道，Nachos系统为用户程序分配内存必须在用户程序载入内存时一次性完成，故此，系统能够运行的用户程序的大小被严格限制在4KB以下。请实现Lazy-Ioading的内存分配算法，使得当且仅当程序运行过程中缺页中断发生时，才会将所需的页面从磁盘调入内存。ChalIenge2:倒排页表任务：多级页表的缺陷在于页表的大小与虚拟地址空间的大小成正比，为了节省物理内存在页表存储上的消耗，请在Nachos系统中实现倒排页表。完成情况：Exercise6,Exercise7和
31、ChaIIenge2我是一起完成的。分析：1 .缺页中断如何发生？(EXerCiSe6)对于目前的虚拟内存系统来说，缺页中断是不会发生的。因为无论是单线程还是多线程，在用户程序运行之前，就已经将所有内容拷贝到了主存当中，pagetable也做好了全部映射。因此缺页中断要想发生，就不能在一开始就将全部内容拷贝到主存当中。而这恰恰是Exercise7要做的。2 .缺页中断发生时，需要做什么？（EXerCiSe7）核心任务是将发生缺页中断的虚拟地址所在的虚拟页拷贝到某一张物理页当中。因此，需要：1）找到该虚拟页；2）确定合适拷贝的物理页（必要时候需要考虑脏页写出的问题）。3 .缺页中断如何支持多线程
32、用户程序的交替运行？（ChalIenge2）虽说每个用户空间都维护一张pagetabIe也是可行的,但如果是多线程用户程序运行，使用倒排页表显然更加节约空间。在倒排页表中，记录了第i个物理页对应的虚拟页以及进程id,于是缺页中断（问题2）发生时，只需通过倒排页表找到对应线程进行页表内容的写入、写出即可。改动：改动简单解释增改变量1.取消用户空间的pagetabIe,维护machine类中的物理页大小的倒排页表数组倒排页表的每一项包括：虚拟页号，进程id,一些标志位（如dirty位）第i项表示第i个物理页的情况。2.Thread类中新增char*变量，用于记录用户程序文件的文件名。在Progte
33、st,co中,初始化用户程序空间的地方，赋值。3.Thread类中新增int变量，用于记录用户程序文件的codesegment的起始位置。在addrspace.cc中,addrspace构造函数的是偶，赋值。线程运行流程中虚实地址转换（translate,cc）（取消了TLB!）1 .将虚拟地址算出所在的虚拟页vpn2 .对比倒排页表中，是否有某项满足:Valid;虚拟页号=vpn;线程Id二当前线程Ido事实上，TLB可以使用，但太麻烦了O3 .如果有，表示pagehit,可以计算出物理地址从而访问主存4 .如果没有,抛出Pagefault异常。Pagefau11处理函数(exception
34、.cc)1.使用Exercise4中写的内存管理器，调用bitmap的find函数，寻找是否有空闲的物理页面由于bitmap和倒排页表此时是一一对应的，即：如果bitmap某位为0,那么证明该物理页未分配，那么倒排页表中该项就一定没有内容。2.如果有，1）修改该物理页面对应的倒排页表项，填写“虚拟页号”和“线程ID”项2）设置标志位3）通过当前线程指针找到用户程序文件,把虚拟页面写入主存Thread类中新增了用户程序文件的名称以及codeSegment的偏移量。可以正确拷贝一张虚拟页的内容进入主存3.如果没有，根据页面替换算法,选择倒排页表中的一项进行替换：这里有两个问题：1）脏页写回：事实上
35、应该采用交换空间，暂时存放换1）判断dirty位，如果是脏页，通过该项找到对应的线程，从而获得用户程序文件，将对应的页面写回2）执行步骤2.出主存的页面的；但由于维护起来过于麻烦，贪图方便，就将脏页直接写回文件了。2）通过倒排页表中的线程id找到对应线程：在LABl中实现了一个存放所有线程的线程池，池内的线程Id和在池内的下标是一一对应的。线程切换Addrspace.cc中,restorestate（）函数中，载入用户程序的pagetabIe的两条语句需要注释掉不再需要维护用户空间的pagetabIe线程结束(exception,cc)Exit系统调用中，需要将原来对Pagetable的操作转
36、移到对倒排页表的操作。将占用的物理页归还（bitmap对应位置清0）,将倒排页表对应项清空无页面替换算法LRU替换算法：1. Translate, cc 中，倒排页 表命中一次，将命中项的 Lru左移加一，其余项的 Lru左移2. Pagefault处理函数中，对 新添表项处理完毕之后，都 需要将所有的倒排页表的IrIl 清 OLrU是一个IrTt型数值，在页 面替换的时候，选取最小的一 项进行替换。并且每次 pagefault发生时，需要将所 有项的LrU从O开始计算，防 止某个页面反复被替换。于是，到目前为止，我们已经可以在NaChOS系统中多线程同时（交替上下cpu）运行用户程序了！并且
37、是支持Iazy-1oading的、（&）/测试截图：（主线程和第二个线程均运行Matmult,该程序自身需要的物理页就已经趣出了主存。因此不仅仅是线程切换会造成pagefault,同个线程本身也会需要pagefau11来更替内容）nowinthreadmainthreadmainpagefault:happenedat768nowtnthreadsecondthreadnowtnthreadmainthreadmainpagefault:happenedat64nowtnthreadsecondthreadthreadsecondthreadpagefaulthappenedat588nowi
38、nthreadmainthreadmainpagefault:happenedat892nowinthreadsecondthreadthreadsecondthreadpagefaulthappenedat896nowinthreadmainnowtnthreadsecondthreadthreadsecondthreadpagefaulthappenedat768nowtnthreadmainthreadmainpagefault:happenedat876nowtnthreadsecondthreadthreadsecondthreadpagefaulthappenedat768thre
39、adsecondthreadpagefaulthappenedat64threadsecondthreadpagefaulthappenedat768nowtnthreadmainnowinthreadsecondthreadnowtnthreadmainnowinthreadsecondthread这里看起来似乎发生了替换页颠簸。测试截图：程序执行完毕退出的时候，需要交还分配的物理页。这里看起来两个线程各拿了一半。threadsecondthreadexited.PhysPge2forsecondthreadisclear.PhySpage3forsecondthreadisclear.Ph
40、ySPage6forsecondthreadIsclear.physpage9forsecondthreadisclear.PhySpage10forsecondthreadisclear.PhySpage16forsecondthreadisclear.PhySpage18forsecondthreadisclear.PhySpage19forsecondthreadisclear.PhySPage21forsecondthreadisclear.Physpage23forsecondthreadISclear.PhySpage24forsecondthreadisclear.PhySPag
41、e25forsecondthreadisclear.PhySpage27forsecondthreadisclear.PhySPage3forsecondthreadisclear.PhySpage31forsecondthreadisclear.tid=lhasfinished.nowtnthreadmainthreadmainexited.PhySPageformainisclear.PhySPage1formainisclear.physpage4formainisCleay,PhySpage7forIainIs1clear.PhySpage8forIainIs1clear.PhySpage11formainisclear.PhySpage12formainisclear.Physpage13formainisclear.PhySPage14formainisclear.PhySpage15formainisclear.PhySPage17formainisclear.PhySpage2formainisclear.PhySpage22formainisclear.Physpage26formainisclear.Physpage28formainisclear.PhySpage29formainisclear.threadmain
