Nachos虚拟内存机制实习报告

虚拟内存机制实习汇报善良的大姐姐.4.18

目录一：总体概述 3二：任务完毕状况 3任务完毕列表（Y/N） 3详细Exercise的完毕状况 3三：碰到的困难以及处理措施 15四：收获及感想 15五：对课程的意见和提议 15六：参照文献 15一：总体概述 通过认真仔细阅读Nachos系统虚拟内存部分的源代码，理解虚拟内存的管理和应用机制，顾客程序的运行逻辑，并修改源代码，到达“实现虚拟存储系统”的目的。二：任务完毕状况任务完毕列表（Y/N）Exercise1Exercise2Exercise3Exercise4Exercise5Exercise6Exercise7Challengeyesyesyesyesyesyesyesyes详细Exercise的完毕状况Exercise1:源代码阅读 Part1:阅读code/userprog/progtest.cc，着重理解nachos执行顾客程序的过程，以及该过程中与内存管理有关的要点。 阅读状况：顾客程序执行过程：环节有关解释在main函数中，假如检测到传入的参数和“执行顾客程序”有关，那么执行StartProcess函数（progtest.cc）在StartProcess函数中装载并运行一种顾客程序StartProcess函数中：用OpenFile类打开文献OpenFile类在文献系统中定义，包括多种对文献的基本操作，如read,write。实质上是包装了操作系统的底层函数。用AddrSpace类创立一种顾客空间，并将打开的文献装载进去创立顾客空间包括：获取文献头，并将大小端做合适转换；通过文献头计算出文献所需空间，包括代码段，初始化数据段，未初始化数据段，栈空间4个部分通过文献所需空间计算出文献所需的虚拟页数量创立顾客空间的pagetable，指示了第i个虚拟页（将）对应第i个物理页由于目前是最基本的【直接映射+单顾客程序无切换】模式，因此此时要将所有的虚拟页中的内容写到物理页（主存）当中。3.（AddrSpace::InitRegisters()）初始化顾客空间中的多种寄存器，包括PC设为0，栈指针移到空间底部为执行顾客程序做准备！（AddrSpace::RestoreState()）将顾客的部分状态（如pagetable）装载到machine类中，准备执行实际上，仅仅是将顾客空间的Pagetable（在第二步创立的）装载到machine的指针中，相称于是顾客程序在machine上运行时，是通过machine的pagetable映射找到对应内容运行的调用machine->Run，运行顾客程序Machine->run是在mipssim.cc中定义的。其工作原理为：通过OneInstruction(instr)模拟mips，将一条指令进行分割，并软件模拟执行。其中，在OneInstruction函数中，通过machine->ReadMem，读取主存中目前PC值指向的地址里的指令。在ReadMem函数中，通过Translate函数对传入的虚地址做转换。在Translate函数中，假如虚地址没有找到对应的实地址转换，就会抛出异常（返回异常值）。返回的异常值在ReadMem中判断，并传入RaiseException函数中RaiseException函数会调用ExceptionHandler函数对不一样的异常做对应的处理。（以上是异常处理机制。在这里就顺便说了。）调用onetick让时间前进反复1,2 Part2:阅读code/machine目录下的machine.h(cc)，translate.h(cc)文献和code/userprog目录下的exception.h(cc)，理解目前Nachos系统所采用的TLB机制和地址转换机制。TLB机制和地址转换机制：有关内容简朴解释TranslationEntry类（translate.h），包括：virtualPage,physicalPage,以及某些标志位：valid,readonly等。标识了顾客空间的第i个虚拟页应当映射到主存的第j个物理页，并且这个物理页目前所处的状态。（valid?readOnly?等）TLB初始化（machine.cc构造函数）：生成指定数量的TranslationEntry构成的数组，并且设置均为Invalid.TLB自身就类似于Pagetable的子集，有若干的<vpn,ppn>的映射对。TLB的使用（translate.cctranslate函数）：遍历TLB数组，查找与否有对应映射假如有，TLB命中，直接进行物理地址转换；否则，TLBMISS，进入Exception处理。（目前还没有对应的处理函数）无地址转换机制：在translate.cctranslate函数中进行。通过virtualaddr，计算出vpn和offset；通过TLB或是直接通过Pagetable，获得vpn对应的ppn；（否则抛出异常，在异常处理函数中做处理，但目前这部分没有实现）通过ppn和offset得到物理地址，将物理地址返回。无TLBmiss或是pagefault处理（exception.cc）：在上一种表格中已经对异常处理是怎样进入的做了简介。但这里要补充一点：在处理完TLBmiss或是Pagefault之后，不需要将PC+4，由于异常处理函数结束后，返回的最终位置会是OneInstruction函数的取指阶段。取指失败后，OneInstruction函数会退出，然后再用同样的PC取一次指令。而这次就可以TLBhit或者pagetablehit了。无Exercise2:TLBMISS异常处理 任务：修改code/userprog目录下exception.cc中的ExceptionHandler函数，使得Nachos系统可以对TLB异常进行处理（TLB异常时，Nachos系统会抛出PageFaultException，详见code/machine/machine.cc）。 完毕状况：有关异常处理的机理已经在Exercise1中阐明了。因此可以对TLB异常进行处理，我们只要在判断传入的参数为TLBMISS的异常，并对其进行处理即可。实际上，我在实际操作的时候，TLBMISS和PAGEFAULT，抛出的异常都是PageFaultException，此后再判断machine->tlb与否为空。假如为空，则执行PagefaultFunc；否则，执行TLBmissFunc。TLBmissFunc:环节简朴解释从machine的BadVAddrReg寄存器中取出发生异常的虚拟地址，并算出vpn；在RaiseException函数中，将发生异常的虚拟地址放入该寄存器的。扫描pagetable，寻找该vpn对应的项。目前状况，是一定可以找到的。由于目前顾客程序运行的机理是：将所有segment所有写入主存中，并且所有做好了虚实映射，放在自己的PageTable中。当mechine需要加载这个顾客程序时，会获得这个pagetable。于是相称于是，mechine通过这个pagetable，可以得到顾客空间所有虚地址对应的实地址。因此当TLBMISS时，查找pagetable，是一定不会Miss的。接下来是寻找放入TLB的位置：先考虑TLB中invalid的项，假如存在，写入该项；假如不存在invalid项，那么就波及TLB置换算法，这在Exercise3中简介。总之最终一定可以找到一种放置新的entry项的位置。无Exercise3:置换算法 任务：为TLB机制实现至少两种置换算法，通过比较不一样算法的置换次数可比较算法的优劣。 完毕状况：FIFO替代算法LRU替代算法假如替代的是Invalid项，那么不波及算法。否则，将数组第一种项丢弃，其他项向前移动一位。新添加的项放在数组最终为每个entry设置一种lru数值。当TLBHIT时，HIT项的lru左移加一，其他项的lru左移；当TLBMISS时，进入异常处理函数异常处理函数中，假如替代的是Invalid项，则将所有valid项（包括目前替代项）的lru值清零否则，扫描TLB数组，找到Lru值最小的一项进行替代，并将所有项的lru值清零测试的顾客程序将数组大小改成5的矩阵相乘：matmult。将会分派18个物理页，TLB访问次数为15000左右。（visittime不一样，是由于每次miss异常处理之后，还会再次访问该地址，因此Miss次数不一样，导致visittime次数也会不一样。）测试成果FIFO：LRU：结论：LRU算法略优于FIFO。Exercise4:内存全局管理数据构造 任务：设计并实现一种全局性的数据构造（如空闲链表、位图等）来进行内存的分派和回收，并记录目前内存的使用状态。 完毕状况：增改状况简朴解释创立Machine类中，新增一种bitmap的数据构造memoryMNG，大小设置为物理页大小memoryMNG的每一种bit对应一种物理页的分派状况内存分派Addrspace.cc构造函数中，在构建顾客空间的pagetable时，通过bitmap的组员函数find返回第一种为0的位，将其作为空闲物理页分派。Find函数返回第一种为0的位，并将该位置1。这非常符合我们的规定。假如不存在为0的位，返回-1。因此我会用Assert来保证可以对的分派物理页。内存回收Exception.cchandler函数中，对于exit系统调用的处理函数中，通过bitmap的组员函数clear，将pagetable中的所有物理页释放，并设置该项为invalid有关在哪回收内存，这是个比较麻烦的问题。由于顾客程序运行完毕之后，是不会离开machine->run的for循环的，并且在调用machine->run之后的语句也不会被执行。因此，只能在exit系统调用中回收比较可行。补充：有关exit系统调用的异常处理函数其实有点麻烦，由于顾客程序可以显式调用Exit，而顾客程序结束之后，也会自动执行一种exit。因此，有也许会有2个exit被执行。考虑到这个状况，需要做如下处理：1）假如bitmap已经被回收过了，就break出来。2）exit处理函数之后，PC要+4。测试成果截图：释放页顾客程序结束开始执行顾客程序分派页释放页顾客程序结束开始执行顾客程序分派页Exercise5:多线程支持 任务：目前Nachos系统的内存中同步只能存在一种线程，我们但愿打破这种限制，使得Nachos系统支持多种线程同步存在于内存中。 完毕状况： 考虑：目前顾客程序对mainMemory的操作是：在初始化顾客空间的时候，会将mainMemory清零，并写入自己的内容。因此，每次运行顾客程序，只能有一种在主存中。（主存里仅容许一种顾客程序寄存）如下截图： 此外，目前mainMemory并没有真正实现分页，所有的segment都是直接且一次性所有写入的，如下图： 因此，我们但愿实现的目的是，将主存分页（物理页），也将顾客程序分页（虚拟页）这样不一样的顾客程序的某些虚拟页就可以映射到某些物理页上，也就可以“共存”了，原理如下图： 在真正实现的时候，是按照字节写入的，先写代码段，再写数据段。 测试的时候，在startprocess函数体中，再新创立一种线程，并让这个线程装载一种顾客程序，且抢占式执行。因此我们会看到：主函数的顾客程序分派完页表后，还没开始执行，另一种线程的顾客程序就分派页表，并执行了。当这个线程执行完毕之后，才轮到主函数的顾客程序执行。这就阐明了，可以多线程同步存在于主存当中。 此外，尚有一种需要阐明的点：线程切换是怎样影响顾客程序切换的？ 在scheduler->run函数的ifdefuser_program的宏定义语句中，包括如下两个函数：函数简朴解释Switch之前①currentThread->SaveUserState()将所有顾客程序的寄存器，从machine的寄存器数组拷贝到装载线程的寄存器数组中，包括PC寄存器等。②currentThread->space->SaveState()目前函数体为空。改写：将machine的TLB数组所有设置为invalid。（由于线程切换后，TLB中的内容所有失效）Switch之后③currentThread->RestoreUserState()与①对应，将所有顾客程序的寄存器，从装载线程的寄存器数组拷贝到machine的寄存器数组中，相称于恢复上下文环境。④currentThread->space->RestoreState()与②对应，将顾客空间的Pagetable装载到machine上。总结：通过寄存器数组以及pagetable的转换，实现了不一样顾客程序的切换。 测试截图：（测试函数：主线程和第二个线程均运行一种只有空函数体的顾客程序。）第二个线程中的顾客程序分派页第二个线程中的顾客程序释放页第二个线程中的顾客程序结束运行第二个线程中的顾客程序开始运行主线程中的顾客程序分派页第二个线程中的顾客程序分派页第二个线程中的顾客程序释放页第二个线程中的顾客程序结束运行第二个线程中的顾客程序开始运行主线程中的顾客程序分派页主线程中的顾客程序释放页主线程中的顾客程序结束运行主线程中的顾客程序开始运行线程切换主线程中的顾客程序释放页主线程中的顾客程序结束运行主线程中的顾客程序开始运行线程切换Exercise6:缺页中断处理 任务：基于TLB机制的异常处理和页面替代算法的实践，实现缺页中断处理（注意！TLB机制的异常处理是将内存中已经有的页面调入TLB，而此处的缺页中断处理则是从磁盘中调入新的页面到内存）、页面替代算法等。Exercise7:Lazy-loading 任务：我们已经懂得，Nachos系统为顾客程序分派内存必须在顾客程序载入内存时一次性完毕，故此，系统可以运行的顾客程序的大小被严格限制在4KB如下。请实现Lazy-loading的内存分派算法，使得当且仅当程序运行过程中缺页中断发生时，才会将所需的页面从磁盘调入内存。Challenge2:倒排页表 任务：多级页表的缺陷在于页表的大小与虚拟地址空间的大小成正比，为了节省物理内存在页表存储上的消耗，请在Nachos系统中实现倒排页表。 完毕状况： Exercise6,Exercise7和Challenge2我是一起完毕的。 分析：缺页中断怎样发生？（Exercise6）对于目前的虚拟内存系统来说，缺页中断是不会发生的。由于无论是单线程还是多线程，在顾客程序运行之前，就已经将所有内容拷贝到了主存当中，pagetable也做好了所有映射。因此缺页中断要想发生，就不能在一开始就将所有内容拷贝到主存当中。而这恰恰是Exercise7要做的。缺页中断发生时，需要做什么？（Exercise7）关键任务是将发生缺页中断的虚拟地址所在的虚拟页拷贝到某一张物理页当中。因此，需要：1）找到该虚拟页；2）确定合适拷贝的物理页（必要时候需要考虑脏页写出的问题）。缺页中断怎样支持多线程顾客程序的交替运行？（Challenge2）虽说每个顾客空间都维护一张pagetable也是可行的，但假如是多线程顾客程序运行，使用倒排页表显然愈加节省空间。在倒排页表中，记录了第i个物理页对应的虚拟页以及进程id，于是缺页中断（问题2）发生时，只需通过倒排页表找到对应线程进行页表内容的写入、写出即可。 改动：改动简朴解释增变化量取消顾客空间的pagetable，维护machine类中的物理页大小的倒排页表数组倒排页表的每一项包括：虚拟页号，进程id，某些标志位（如dirty位）第i项表达第i个物理页的状况。Thread类中新增char*变量，用于记录顾客程序文献的文献名。在Progtest.cc中，初始化顾客程序空间的地方，赋值。Thread类中新增int变量，用于记录顾客程序文献的codesegment的起始位置。在addrspace.cc中，addrspace构造函数的是偶，赋值。线程运行流程中虚实地址转换（translate.cc）（取消了TLB！！）将虚拟地址算出所在的虚拟页vpn对比倒排页表中，与否有某项满足：valid;虚拟页号=vpn;线程Id=目前线程Id。假如有，表达pagehit，可以计算出物理地址从而访问主存假如没有，抛出Pagefault异常。实际上，TLB可以使用，但太麻烦了。Pagefault处理函数（exception.cc）使用Exercise4中写的内存管理器，调用bitmap的find函数，寻找与否有空闲的物理页面由于bitmap和倒排页表此时是一一对应的，即：假如bitmap某位为0，那么证明该物理页未分派，那么倒排页表中该项就一定没有内容。假如有，1）修改该物理页面对应的倒排页表项，填写“虚拟页号”和“线程ID”项2）设置标志位3）通过目前线程指针找到顾客程序文献，把虚拟页面写入主存Thread类中新增了顾客程序文献的名称以及codesegment的偏移量。可以对的拷贝一张虚拟页的内容进入主存假如没有，根据页面替代算法，选择倒排页表中的一项进行替代：1）判断dirty位，假如是脏页，通过该项找到对应的线程，从而获得顾客程序文献，将对应的页面写回2）执行环节2.这里有两个问题：脏页写回：实际上应当采用互换空间，临时寄存换出主存的页面的；但由于维护起来过于麻烦，贪图以便，就将脏页直接写回文献了。通过倒排页表中的线程id找到对应线程：在LAB1中实现了一种寄存所有线程的线程池，池内的线程Id和在池内的下标是一一对应的。线程切换Addrspace.cc中，restorestate()函数中，载入顾客程序的pagetable的两条语句需要注释掉不再需要维护顾客空间的pagetable线程结束（exception.cc）Exit系统调用中，需要将本来对Pagetable的操作转移到对倒排页表的操作。将占用的物理页偿还（bitmap对应位置清0），将倒排页表对应项清空无页面替代算法LRU替代算法：Translate.cc中，倒排页表命中一次，将命中项的Lru左移加一，其他项的Lru左移Pagefault处理函数中，对新添表项处理完毕之后，都需要将所有的倒排页表的lru清0Lru是一种Int型数值，在页面替代的时候，选用最小的一项进行替代。并且每次pagefault发生时，需要将所有项的Lru从0开始计算，防止某个页面反复被替代。 于是，到目前为止，我们已经可以在Nachos系统中多线程同步（交替上