实验三：虚拟内存管理
- 专业班级：
- 学号：
- 姓名：
- 上课老师：
一、实验目的
1.了解虚拟内存的Page Fault异常处理实现
2.了解页替换算法在操作系统中的实现
二、实验内容
本次实验是在实验二的基础上，借助于页表机制和实验一中涉及的中断异常处理机制，完成Page Fault异常处理和FIFO页替换算法的实现，结合磁盘提供的缓存空间，从而能够支持虚存管理，提供一个比实际物理内存空间“更大”的虚拟内存空间给系统使用。这个实验与实际操作系统中的实现比较起来要简单，不过需要了解实验一和实验二的具体实现。实际操作系统系统中的虚拟内存管理设计与实现是相当复杂的，涉及到与进程管理系统、文件系统等的交叉访问。如果大家有余力，可以尝试完成扩展练习，实现extended clock页替换法。
三、实验步骤
练习0：填写已有实验
练习1：给末被映射的地址映射上物理页（需要编程）
完成do_pgfault（mm/vmm.c）函数，给未被映射的地址映射上物理页。设置访问权限的时候需要参考页面所在 VMA 的权限，同时需要注意映射物理页时需要操作内存控制结构所指定的页表，而不是内核的页表。注意：在LAB2 EXERCISE 1处填写代码。执行
make qemu
后，如果通过check_pgfault函数的测试后，会有“check_pgfault() succeeded!”的输出，表示练习1基本正确。
请在实验报告中简要说明你的设计实现过程。请回答如下问题：
- 请描述页目录项（Pag Director Entry）和页表（Page Table Entry）中组成部分对ucore实现页替换算法的潜在用处。
- 如果ucore的缺页服务例程在执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？
解析
lab3的总体执行流程如下:
- 首先是初始化过程。参考ucore总控函数init的代码，可以看到在调用完成虚拟内存初始化的
vmm_init函数之前，需要首先调用pmm_init函数完成物理内存的管理，这也是我们lab2已经完成的内容。 - 接着是执行中断和异常相关的初始化工作，即调用
pic_init函数和idt_init函数等，这些工作与lab1的中断异常初始化工作的内容是相同的。 - 在调用完
idt_init函数之后，将进一步调用三个lab3中才有的新函数vmm_init、ide_init和swap_init。这三个函数设计了本次实验中的两个练习。第一个函数vmm_init是检查我们的练习1是否正确实现了。为了表述不在物理内存中的“合法”虚拟页，需要有数据结构来描述这样的页，为此ucore建立了mm_struct和vma_struct数据结构（接下来的小节中有进一步详细描述），假定我们已经描述好了这样的“合法”虚拟页，当ucore访问这些“合法”虚拟页时，会由于没有虚实地址映射而产生页访问异常。
do_pgfault函数会申请一个空闲物理页，并建立好虚实映射关系，从而使得这样的“合法”虚拟页有实际的物理页帧对应。
但page_fault函数不知道哪些是“合法”的虚拟页，原因是ucore还缺少一定的数据结构来描述这种不在物理内存中的“合法”虚拟页。为此ucore通过建立mm_struct和vma_struct数据结构，描述了ucore模拟应用程序运行所需的合法内存空间。
vma_struct的定义如下：
struct vma_struct{
struct mm_struct *vm_mm; // the set of vma using the same PDT
uintptr_t vm_start; // start addr of vma
uintptr_t vm_end; // end addr of vma
uint32_t vm_flags; // flags of vma
list_entry_t list_link; // linear list link which sorted by start addr of vma
};
-
vm_mm是一个指针，指向一个比vma_struct更高的抽象层次的数据结构mm_struct -
vm_start和vm_end描述的是一个合理的地址空间范围（即严格确保 vm_start < vm_end的关系）； -
list_link是一个双向链表，按照从小到大的顺序把一系列用vma_struct表示的虚拟内存空间链接起来，并且还要求这些链起来的vma_struct应该是不相交的，即vma之间的地址空间无交集； -
vm_flags表示了这个虚拟内存空间的属性，目前的属性包括
#define VM_READ 0x00000001 //只读
#define VM_WRITE 0x00000002 //可读写
#define VM_EXEC 0x00000004 //可执行
mm_struct的定义如下：
struct mm_struct{
list_entry_t mmap_list; // linear list link which sorted by start addr of vma
struct vma_struct *mmap_cache; // current accessed vma, used for speed purpose
pde_t *pgdir; // the PDT of these vma
int map_count; // the count of these vma
void *sm_priv; // the private data for swap manager
};
-
mmap_list是双向链表头，链接了所有属于同一页目录表的虚拟内存空间， -
mmap_cache是指向当前正在使用的虚拟内存空间，由于操作系统执行的“局部性”原理，当前正在用到的虚拟内存空间在接下来的操作中可能还会用到，这时就不需要查链表，而是直接使用此指针就可找到下一次要用到的虚拟内存空间。由于mmap_cache的引入，可使得mm_struct数据结构的查询加速 30% 以上。 -
pgdir所指向的就是mm_struct数据结构所维护的页表。通过访问pgdir可以查找某虚拟地址对应的页表项是否存在以及页表项的属性等。
-
map_count记录mmap_list里面链接的vma_struct的个数。 -
sm_priv指向用来链接记录页访问情况的链表头，这建立了mm_struct和后续要讲到的swap_manager之间的联系。
当启动分页机制以后，如果一条指令或数据的虚拟地址所对应的物理页框不在内存中或者访问的类型有错误（比如写一个只读页或用户态程序访问内核态的数据等），就会发生页错误异常。产生页面异常的原因主要有:
- 目标页面不存在（页表项全为0，即该线性地址与物理地址尚未建立映射或者已经撤销）;
- 相应的物理页面不在内存中（页表项非空，但Present标志位=0，比如在swap分区或磁盘文件上）
- 访问权限不符合（此时页表项P标志=1，比如企图写只读页面）.
当出现上面情况之一,那么就会产生页面page fault(#PF)异常。
产生页访问异常后，CPU把引起页访问异常的线性地址装到寄存器CR2中，并给出了出错码errorCode，说明了页访问异常的类型。ucore OS会把这个值保存在struct trapframe 中tf_err成员变量中。而中断服务例程会调用页访问异常处理函数do_pgfault进行具体处理。这里的页访问异常处理是实现按需分页、页换入换出机制的关键之处。
ucore中do_pgfault函数是完成页访问异常处理的主要函数，它根据从CPU的控制寄存器CR2中获取的页访问异常的物理地址以及根据errorCode的错误类型来查找此地址是否在某个VMA的地址范围内以及是否满足正确的读写权限，如果在此范围内并且权限也正确，这认为这是一次合法访问，但没有建立虚实对应关系。所以需要
分配一个空闲的内存页，并修改页表完成虚地址到物理地址的映射，刷新TLB，然后调用iret中断，返回到产生页访问异常的指令处重新执行此指令。
如果该虚地址不在某VMA范围内，则认为是一次非法访问。
do_pgfault部分具体实现如下：
// try to find a pte, if pte's PT(Page Table) isn't existed, then create a PT.
if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
cprintf("get_pte in do_pgfault failed\n");//如果找不到入口，是非法访问，退出
goto failed;
}
// if the phy addr isn't exist, then alloc a page & map the phy addr with logical addr
if (*ptep == 0) {
if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
cprintf("pgdir_alloc_page in do_pgfault failed\n");
//尝试申请一个页，如果申请失败，就是内存不足了，退出
goto failed;
}
}
练习2：补充完成基于FIFO的页面置换算法（需要编程）
完成vmm.c中的do_pgfault函数，并且在实现FIFO算法的swap_fifo.c中完成map_swappable swap_out_vistim函数。通过对swap的测试。注意：在LAB2 EXERCISE 2处填写代码。执行
make qemu
后，如果通过check_swap函数的测试后，会有“check_swap() succeeded!”的输出，表示练习2基本正确。
请在实验报告中简要说明你的设计实现过程。
请在实验报告中回答如下问题：
- 如果要在ucore上实现"extended clock页替换算法"请给你的设计方案，现有的swap_manager框架是否足以支持在ucore中实现此算法？如果是，请给你的设计方案。如果不是，请给出你的新的扩展和基此扩展的设计方案。并需要回答如下问题:
- 需要被换出的页的特征是什么？
- 在ucore中如何判断具有这样特征的页？
- 何时进行换入和换出操作？
解析
当应用程序访问它认为应该在内存中的的数据或代码时，如果这些数据或代码不在内存中，则根据上一小节的介绍，会产生页访问异常。这时，操作系统必须能够应对这种页访问异常，即尽快把应用程序当前需要的数据或代码放到内存中来，然后重新执行应用程序产生异常的访存指令。(换入）
如果在把硬盘中对应的数据或代码调入内存前，操作系统发现物理内存已经没有空闲空间了，这时操作系统必须把它认为“不常用”的页换出到磁盘上去，以腾出内存空闲空间给应用程序所需的数据或代码。（换出）
页面替换主要分为两个方面，页面换出和页面换入。
页面换入主要在vmm.c中的do_pgfault()函数实现；页面换出主要在swap_fifo.c中的swap_out_vistim()函数实现。
- 在换入时，需要先检查产生访问异常的地址是否属于某个vma表示的合法虚拟地址，并且保存在硬盘的swap文件中（对应的PTE的高24位不为0）。如果满足以上两点，则执行
swap_in()函数换入页面。 - 换出则相对简单，当申请空闲页面时，
alloc_pages()函数不能获得空闲页，则需要调用swap_out()函数换出不常用的页面。
换入
else {//页表项非空，可以尝试换入页面
if(swap_init_ok) {
struct Page *page=NULL;
//根据mm结构和addr地址，尝试将硬盘中的内容换入至page中
if ((ret = swap_in(mm, addr, &page)) != 0) {
cprintf("swap_in in do_pgfault failed\n");
goto failed;
}
page_insert(mm->pgdir, page, addr, perm);//建立虚拟地址和物理地址之间的对应关系
swap_map_swappable(mm, addr, page, 1);//将此页面设置为可交换的
page->pra_vaddr = addr;
}
else {
cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
goto failed;
}
}
换出
FIFO替换算法会维护一个队列，队列按照页面调用的次序排列，越早被加载到内存的页面会越早被换出。
具体实现的函数如下：
首先是_fifo_map_swappable()，它的主要作用是将最近被用到的页面添加到算法所维护的次序队列。
static int _fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in) {
list_entry_t *head=(list_entry_t*) mm->sm_priv;
list_entry_t *entry=&(page->pra_page_link);
assert(entry != NULL && head != NULL);
list_add(head, entry); //将最近用到的页面添加到次序队尾
return 0;
}
然后是_fifo_swap_out_victim()函数是用来查询哪个页面需要被换出，它的主要作用是用来查询哪个页面需要被换出。
static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick) {
list_entry_t *head=(list_entry_t*) mm->sm_priv;
assert(head != NULL);
assert(in_tick==0);
list_entry_t *le = head->prev; //用le指示需要被换出的页
assert(head!=le);
struct Page *p = le2page(le, pra_page_link);//le2page宏可以根据链表元素获得对应的Page指针p
list_del(le); //将进来最早的页面从队列中删除
assert(p !=NULL);
*ptr_page = p; //将这一页的地址存储在ptr_page中
return 0;
}
实验结果
扩展练习
实验总结
经过本次试验，明白了页面置换。
可以说非常有用了。
