虚拟内存机制实习报告范本.docx

资源描述

虚拟内存机制实习报告范本.docx

《虚拟内存机制实习报告范本.docx》由会员分享，可在线阅读，更多相关《虚拟内存机制实习报告范本.docx（20页珍藏版）》请在冰点文库上搜索。

虚拟内存机制实习报告范本.docx

虚拟内存机制实习报告范本

虚拟内存机制实习报告

一：

总体概述

通过认真仔细阅读Nachos系统虚拟内存部分的源代码，理解虚拟内存的管理和应用机制，用户程序的运行逻辑，并修改源代码，达到“实现虚拟存储系统”的目标。

二：

任务完成情况

任务完成列表（Y/N）

Exercise1

Exercise2

Exercise3

Exercise4

Exercise5

Exercise6

Exercise7

Challenge

yes

具体Exercise的完成情况

Exercise1:

源代码阅读

Part1:

阅读code/userprog/progtest.cc，着重理解nachos执行用户程序的过程，以及该过程中与内存管理相关的要点。

阅读情况：

用户程序执行过程：

步骤

相关内容

简单解释

TranslationEntry类（translate.h），包括：

virtualPage,physicalPage,

以及一些标志位：

valid,readonly等。

标识了用户空间的第i个虚拟页应该映射到主存的第j个物理页，并且这个物理页目前所处的状态。

（valid?

readOnly?

等）

TLB初始化（machine.cc构造函数）：

生成指定数量的TranslationEntry构成的数组，并且设置均为Invalid.

TLB本身就类似于Pagetable的子集，有若干的的映射对。

TLB的使用（translate.cctranslate函数）：

1.遍历TLB数组，查找是否有对应映射

2.如果有，TLB命中，直接进行物理地址转换；否则，TLBMISS，进入Exception处理。

（目前还没有对应的处理函数）

无

地址转换机制：

在translate.cctranslate函数中进行。

1.通过virtualaddr，计算出vpn和offset；

2.通过TLB或是直接通过Pagetable，获得vpn对应的ppn；（否则抛出异常，在异常处理函数中做处理，但目前这部分没有实现）

3.通过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:

步骤

简单解释

1.从machine的BadVAddrReg寄存器中取出发生异常的虚拟地址，并算出vpn；

在RaiseException函数中，将发生异常的虚拟地址放入该寄存器的。

2.扫描pagetable，寻找该vpn对应的项。

目前情况，是一定可以找到的。

由于目前用户程序运行的机理是：

将所有segment全部写入主存中，并且全部做好了虚实映射，放在自己的PageTable中。

当mechine需要加载这个用户程序时，会获得这个pagetable。

于是相当于是，mechine通过这个pagetable，可以得到用户空间所有虚地址对应的实地址。

因此当TLBMISS时，查找pagetable，是一定不会Miss的。

3.接下来是寻找放入TLB的位置：

1）先考虑TLB中invalid的项，如果存在，写入该项；

2）如果不存在invalid项，那么就涉及TLB置换算法，这在Exercise3中介绍。

总之最后一定可以找到一个放置新的entry项的位置。

无

Exercise3:

置换算法

任务：

为TLB机制实现至少两种置换算法，通过比较不同算法的置换次数可比较算法的优劣。

完成情况：

FIFO替换算法

LRU替换算法

1.如果替换的是Invalid项，那么不涉及算法。

2.否则，将数组第一个项丢弃，其他项向前移动一位。

新添加的项放在数组最后

3.为每个entry设立一个lru数值。

当TLBHIT时，HIT项的lru左移加一，其余项的lru左移；当TLBMISS时，进入异常处理函数

4.异常处理函数中，如果替换的是Invalid项，则将所有valid项（包括当前替换项）的lru值清零

5.否则，扫描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我是一起完成的。

分析：

1.缺页中断如何发生？

（Exercise6）

对于目前的虚拟内存系统来说，缺页中断是不会发生的。

因为无论是单线程还是多线程，在用户程序运行之前，就已经将所有内容拷贝到了主存当中，pagetable也做好了全部映射。

因此缺页中断要想发生，就不能在一开始就将全部内容拷贝到主存当中。

而这恰恰是Exercise7要做的。

2.缺页中断发生时，需要做什么？

（Exercise7）

核心任务是将发生缺页中断的虚拟地址所在的虚拟页拷贝到某一张物理页当中。

因此，需要：

1）找到该虚拟页；2）确定合适拷贝的物理页（必要时候需要考虑脏页写出的问题）。

3.缺页中断如何支持多线程用户程序的交替运行？

（Challenge2）

虽说每个用户空间都维护一张pagetable也是可行的，但如果是多线程用户程序运行，使用倒排页表显然更加节约空间。

在倒排页表中，记录了第i个物理页对应的虚拟页以及进程id，于是缺页中断（问题2）发生时，只需通过倒排页表找到对应线程进行页表内容的写入、写出即可。

改动：

改动

简单解释

增改变量

1.取消用户空间的pagetable，维护machine类中的物理页大小的倒排页表数组

倒排页表的每一项包括：

虚拟页号，进程id，一些标志位（如dirty位）

第i项表示第i个物理页的情况。

2.Thread类中新增char*变量，用于记录用户程序文件的文件名。

在Progtest.cc中，初始化用户程序空间的地方，赋值。

3.Thread类中新增int变量，用于记录用户程序文件的codesegment的起始位置。

在addrspace.cc中，addrspace构造函数的是偶，赋值。

线程运行流程中

虚实地址转换（translate.cc）

（取消了TLB！

！

）

1.将虚拟地址算出所在的虚拟页vpn

2.对比倒排页表中，是否有某项满足：

valid;虚拟页号=vpn;线程Id=当前线程Id。

3.如果有，表示pagehit，可以计算出物理地址从而访问主存

4.如果没有，抛出Pagefault异常。

事实上，TLB可以使用，但太麻烦了。

Pagefault处理函数（exception.cc）

1.使用Exercise4中写的内存管理器，调用bitmap的find函数，寻找是否有空闲的物理页面

由于bitmap和倒排页表此时是一一对应的，即：

如果bitmap某位为0，那么证明该物理页未分配，那么倒排页表中该项就一定没有内容。

2.如果有，

1）修改该物理页面对应的倒排页表项，填写“虚拟页号”和“线程ID”项

2）设置标志位

3）通过当前线程指针找到用户程序文件，把虚拟页面写入主存

Thread类中新增了用户程序文件的名称以及codesegment的偏移量。

可以正确拷贝一张虚拟页的内容进入主存

3.如果没有，根据页面替换算法，选择倒排页表中的一项进行替换：

1）判断dirty位，如果是脏页，通过该项找到对应的线程，从而获得用户程序文件，将对应的页面写回

2）执行步骤2.

这里有两个问题：

1）脏页写回：

事实上应该采用交换空间，暂时存放换出主存的页面的；但由于维护起来过于麻烦，贪图方便，就将脏页直接写回文件了。

2）通过倒排页表中的线程id找到对应线程：

在LAB1中实现了一个存放所有线程的线程池，池内的线程Id和在池内的下标是一一对应的。

线程切换

Addrspace.cc中，restorestate（）函数中，载入用户程序的pagetable的两条语句需要注释掉

不再需要维护用户空间的pagetable

线程结束（exception.cc）

Exit系统调用中，需要将原来对Pagetable的操作转移到对倒排页表的操作。

将占用的物理页归还（bitmap对应位置清0），将倒排页表对应项清空

无

页面替换算法

LRU替换算法：

1.Translate.cc中，倒排页表命中一次，将命中项的Lru左移加一，其余项的Lru左移

2.Pagefault处理函数中，对新添表项处理完毕之后，都需要将所有的倒排页表的lru清0

Lru是一个Int型数值，在页面替换的时候，选取最小的一项进行替换。

并且每次pagefault发生时，需要将所有项的Lru从0开始计算，防止某个页面反复被替换。

于是，到目前为止，我们已经可以在Nachos系统中多线程同时（交替上下cpu）运行用户程序了！

并且是支持lazy-loading的\（≧▽≦）/

测试截图：

（主线程和第二个线程均运行Matmult，该程序自身需要的物理页就已经超出了主存。

因此不仅仅是线程切换会造成pagefault，同个线程本身也会需要pagefault来更替内容）

测试截图：

程序执行完毕退出的时候，需要交还分配的物理页。

这里看起来两个线程各拿了一半。

三：

遇到的困难以及解决方法

困难1：

在一开始做LAB的时候，无法让TLB生效

即使在makefile里使用了DUSE_TLB也不管用，为了使用TLB，只能对machine初始化函数中做了一些注释，让machine一定使用TLB。

困难2：

用户程序的运行过程，包括线程切换等

这是为了做lab必须了解清楚的。

因此只能很认真地研究了不少时间。

困难3：

换出的脏页往哪放？

交换空间是个正确选择，但是实现起来有些麻烦……因此最后采取“直接写回文件”。

但应该是不正确的。

四：

收获及感想

这次lab的完成时间是三周，事实上我也确实断断续续写了快三周才写完。

首先研究清楚机制就花了不少时间，其次要将Nachos系统的虚拟内存和真实系统的虚拟内存做比较，搞清楚二者之间的相同和相异的点，才能找到折中又不失优雅的方式完成每一个Exercise。

但话说回来，感觉收获还是很大的。

这套系统有很多设计巧妙的小细节，一旦注意到了就会觉得是一个值得学习的点，对于将来一定是有着潜在益处的。

这次Lab我和我们组的组员陈震鹏探讨了不少时间，感觉讨论的力量还是强大的。

两个臭皮匠发挥了半个诸葛亮的作用~

五：

对课程的意见和建议

感觉实验要求里什么有用的信息都没有，全部都靠自己摸索完成的lab。

希望下次布置lab（尤其是这种比较繁琐的）能够给予更多的一些基本提示。

（当然事实上这些提示也只是加快我们完成lab的速度，靠自己摸索也是能够实现的:

）所以仅仅是从一个学生角度的建议啦~）

六：

参考文献

1组员陈震鹏的一起讨论

大神王维梓的请教

展开阅读全文