实验题目

ucore lab3 虚拟内存管理

实验目的

做完实验二后，大家可以了解并掌握物理内存管理中的连续空间分配算法的具体实现以及如何建立二级页表。本次实验是在实验二的基础上，借助于页表机制和实验一中涉及的中断异常处理机制，完成Page Fault异常处理和FIFO页替换算法的实现。实验原理最大的区别是在设计了如何在磁盘上缓存内存页，从而能够支持虚存管理，提供一个比实际物理内存空间“更大”的虚拟内存空间给系统使用。

了解虚拟内存的Page Fault异常处理实现
了解页替换算法在操作系统中的实现

实验内容

本次实验是在实验二的基础上，借助于页表机制和实验一中涉及的中断异常处理机制，完成 Page Fault 异常处理和 FIFO 页替换算法的实现，结合磁盘提供的缓存空间，从而能够支持虚存管理，提供一个比实际物理内存空间“更大”的虚拟内存空间给系统使用。这个实验与实际操作系统中的实现比较起来要简单，不过需要了解实验一和实验二的具体实现。实际操作系统系统中的虚拟内存管理设计与实现是相当复杂的，涉及到与进程管理系统、文件系统等的交叉访问。如果大家有余力，可以尝试完成扩展练习，实现extended　clock页替换算法。

完成 Page Fault 异常处理和 FIFO 页替换算法的实现
结合磁盘提供的缓存空间，从而能够支持虚存管理，提供一个比实际物理内存空间”更大“的虚拟内存空间给系统使用

练习0：填写已有实验

本实验依赖实验1/2。请把你做的实验1/2的代码填入本实验中代码中有“LAB1”,“LAB2”的注释相应部分。

根据前面做的 lab1 和 lab2（包括扩展练习），我们可以知道总共有五个文件需要修改和填写：

kdebug.c
init.c
default_pmm.c
pmm.c
trap.c

在终端输入 meld ，使用 meld 用之前的文件来对 lab3 中的文件进行修改和填写（当然也可以直接手动修改，但是不是很推荐，因为可能会漏掉一些地方）

这里以 default_pmm.c 为例进行演示

在终端执行以下命令：

meld

选择 lab2 中的 default_pmm.c 和 lab3 中的default_pmm.c 进行比较

点击左边文件的箭头，并且删除右边文件中右箭头的代码块，使 lab3 中的 default_pmm.c 和 lab2 中的 default_pmm.c 一致

最后出现如下效果：

最后再保存即可，其他四个文件也按照如此步骤进行即可（不是一定要完全一样，只要在 lab1 和 lab2 写过的地方一样即可）

练习1：给未被映射的地址映射上物理页

完成do_pgfault（mm/vmm.c）函数，给未被映射的地址映射上物理页。设置访问权限的时候需要参考页面所在 VMA 的权限，同时需要注意映射物理页时需要操作内存控制结构所指定的页表，而不是内核的页表。注意：在LAB3 EXERCISE 1处填写代码。执行

make　qemu

后，如果通过check_pgfault函数的测试后，会有“check_pgfault() succeeded!”的输出，表示练习1基本正确。

请在实验报告中简要说明你的设计实现过程。请回答如下问题：

请描述页目录项（Page Directory Entry）和页表项（Page Table Entry）中组成部分对ucore实现页替换算法的潜在用处。
如果ucore的缺页服务例程在执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

基本原理概述

什么是虚拟内存？简单地说是指程序员或CPU“看到”的内存。但有几点需要注意：

虚拟内存单元不一定有实际的物理内存单元对应，即实际的物理内存单元可能不存在；
如果虚拟内存单元对应有实际的物理内存单元，那二者的地址一般是不相等的；
通过操作系统实现的某种内存映射可建立虚拟内存与物理内存的对应关系，使得程序员或CPU访问的虚拟内存地址会自动转换为一个物理内存地址。

那么这个“虚拟”的作用或意义在哪里体现呢？在操作系统中，虚拟内存其实包含多个虚拟层次，在不同的层次体现了不同的作用。首先，在有了分页机制后，程序员或CPU“看到”的地址已经不是实际的物理地址了，这已经有一层虚拟化，我们可简称为内存地址虚拟化。有了内存地址虚拟化，我们就可以通过设置页表项来限定软件运行时的访问空间，确保软件运行不越界，完成内存访问保护的功能。

通过内存地址虚拟化，可以使得软件在没有访问某虚拟内存地址时不分配具体的物理内存，而只有在实际访问某虚拟内存地址时，操作系统再动态地分配物理内存，建立虚拟内存到物理内存的页映射关系，这种技术称为按需分页（demand paging）。把不经常访问的数据所占的内存空间临时写到硬盘上，这样可以腾出更多的空闲内存空间给经常访问的数据；当CPU访问到不经常访问的数据时，再把这些数据从硬盘读入到内存中，这种技术称为页换入换出（page　swap in/out）。这种内存管理技术给了程序员更大的内存“空间”，从而可以让更多的程序在内存中并发运行。

关键数据结构和相关函数分析

对于第一个问题的出现，在于实验二中有关内存的数据结构和相关操作都是直接针对实际存在的资源–物理内存空间的管理，没有从一般应用程序对内存的“需求”考虑，即需要有相关的数据结构和操作来体现一般应用程序对虚拟内存的“需求”。一般应用程序的对虚拟内存的“需求”与物理内存空间的“供给”没有直接的对应关系，ucore是通过page fault异常处理来间接完成这二者之间的衔接。

page_fault函数不知道哪些是“合法”的虚拟页，原因是ucore还缺少一定的数据结构来描述这种不在物理内存中的“合法”虚拟页。为此ucore通过建立mm_struct和vma_struct数据结构，描述了ucore模拟应用程序运行所需的合法内存空间。当访问内存产生page fault异常时，可获得访问的内存的方式（读或写）以及具体的虚拟内存地址，这样ucore就可以查询此地址，看是否属于vma_struct数据结构中描述的合法地址范围中，如果在，则可根据具体情况进行请求调页/页换入换出处理（这就是练习2涉及的部分）；如果不在，则报错。mm_struct和vma_struct数据结构结合页表表示虚拟地址空间和物理地址空间的示意图如下所示：

图虚拟地址空间和物理地址空间的示意图

在ucore中描述应用程序对虚拟内存“需求”的数据结构是vma_struct（定义在vmm.h中），以及针对vma_struct的函数操作。这里把一个vma_struct结构的变量简称为vma变量。vma_struct的定义如下：

struct vma_struct {
    // the set of vma using the same PDT
    struct mm_struct *vm_mm;
    uintptr_t vm_start; // start addr of vma
    uintptr_t vm_end; // end addr of vma
    uint32_t vm_flags; // flags of vma
    //linear list link which sorted by start addr of vma
    list_entry_t list_link;
};

vm_start和vm_end描述了一个连续地址的虚拟内存空间的起始位置和结束位置，这两个值都应该是PGSIZE 对齐的，而且描述的是一个合理的地址空间范围（即严格确保 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 //可执行

vm_mm是一个指针，指向一个比vma_struct更高的抽象层次的数据结构mm_struct，这里把一个mm_struct结构的变量简称为mm变量。这个数据结构表示了包含所有虚拟内存空间的共同属性，具体定义如下

struct mm_struct {
    // linear list link which sorted by start addr of vma
    list_entry_t mmap_list;
    // current accessed vma, used for speed purpose
    struct vma_struct *mmap_cache;
    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之间的联系。

涉及vma_struct的操作函数也比较简单，主要包括三个：

vma_create–创建vma
insert_vma_struct–插入一个vma
find_vma–查询vma。

vma_create函数根据输入参数vm_start、vm_end、vm_flags来创建并初始化描述一个虚拟内存空间的vma_struct结构变量。insert_vma_struct函数完成把一个vma变量按照其空间位置[vma->vm_start,vma->vm_end]从小到大的顺序插入到所属的mm变量中的mmap_list双向链表中。find_vma根据输入参数addr和mm变量，查找在mm变量中的mmap_list双向链表中某个vma包含此addr，即vma->vm_start<=addr end。这三个函数与后续讲到的page fault异常处理有紧密联系。

涉及mm_struct的操作函数比较简单，只有mm_create和mm_destroy两个函数，从字面意思就可以看出是是完成mm_struct结构的变量创建和删除。在mm_create中用kmalloc分配了一块空间，所以在mm_destroy中也要对应进行释放。在ucore运行过程中，会产生描述虚拟内存空间的vma_struct结构，所以在mm_destroy中也要进对这些mmap_list中的vma进行释放。

Page Fault异常处理

实现虚存管理的一个关键是page fault异常处理，其过程中主要涉及到函数 – do_pgfault的具体实现。比如，在程序的执行过程中由于某种原因（页框不存在/写只读页等）而使 CPU 无法最终访问到相应的物理内存单元，即无法完成从虚拟地址到物理地址映射时，CPU 会产生一次页访问异常，从而需要进行相应的页访问异常的中断服务例程。这个页访问异常处理的时机被操作系统充分利用来完成虚存管理，即实现“按需调页”/“页换入换出”处理的执行时机。当相关处理完成后，页访问异常服务例程会返回到产生异常的指令处重新执行，使得应用软件可以继续正常运行下去。

具体而言，当启动分页机制以后，如果一条指令或数据的虚拟地址所对应的物理页框不在内存中或者访问的类型有错误（比如写一个只读页或用户态程序访问内核态的数据等），就会发生页访问异常。产生页访问异常的原因主要有：

目标页帧不存在（页表项全为0，即该线性地址与物理地址尚未建立映射或者已经撤销)；
相应的物理页帧不在内存中（页表项非空，但Present标志位=0，比如在swap分区或磁盘文件上)，这在本次实验中会出现，我们将在下面介绍换页机制实现时进一步讲解如何处理；
不满足访问权限(此时页表项P标志=1，但低权限的程序试图访问高权限的地址空间，或者有程序试图写只读页面).

当出现上面情况之一，那么就会产生页面page fault（#PF）异常。CPU会把产生异常的线性地址存储在CR2中，并且把表示页访问异常类型的值（简称页访问异常错误码，errorCode）保存在中断栈中。

[提示]页访问异常错误码有32位。位0为１表示对应物理页不存在；位１为１表示写异常（比如写了只读页；位２为１表示访问权限异常（比如用户态程序访问内核空间的数据）

[提示]　CR2是页故障线性地址寄存器，保存最后一次出现页故障的全32位线性地址。CR2用于发生页异常时报告出错信息。当发生页异常时，处理器把引起页异常的线性地址保存在CR2中。操作系统中对应的中断服务例程可以检查CR2的内容，从而查出线性地址空间中的哪个页引起本次异常。

产生页访问异常后，CPU硬件和软件都会做一些事情来应对此事。首先页访问异常也是一种异常，所以针对一般异常的硬件处理操作是必须要做的，即CPU在当前内核栈保存当前被打断的程序现场，即依次压入当前被打断程序使用的EFLAGS，CS，EIP，errorCode；由于页访问异常的中断号是0xE，CPU把异常中断号0xE对应的中断服务例程的地址（vectors.S中的标号vector14处）加载到CS和EIP寄存器中，开始执行中断服务例程。这时ucore开始处理异常中断，首先需要保存硬件没有保存的寄存器。在vectors.S中的标号vector14处先把中断号压入内核栈，然后再在trapentry.S中的标号__alltraps处把DS、ES和其他通用寄存器都压栈。自此，被打断的程序执行现场（context）被保存在内核栈中。接下来，在trap.c的trap函数开始了中断服务例程的处理流程，大致调用关系为：

trap–> trap_dispatch–>pgfault_handler–>do_pgfault

下面需要具体分析一下do_pgfault函数。do_pgfault的调用关系如下图所示：

图 do_pgfault的调用关系图

产生页访问异常后，CPU把引起页访问异常的线性地址装到寄存器CR2中，并给出了出错码errorCode，说明了页访问异常的类型。ucore OS会把这个值保存在struct trapframe 中tf_err成员变量中。而中断服务例程会调用页访问异常处理函数do_pgfault进行具体处理。这里的页访问异常处理是实现按需分页、页换入换出机制的关键之处。

ucore中do_pgfault函数是完成页访问异常处理的主要函数，它根据从CPU的控制寄存器CR2中获取的页访问异常的物理地址以及根据errorCode的错误类型来查找此地址是否在某个VMA的地址范围内以及是否满足正确的读写权限，如果在此范围内并且权限也正确，这认为这是一次合法访问，但没有建立虚实对应关系。所以需要分配一个空闲的内存页，并修改页表完成虚地址到物理地址的映射，刷新TLB，然后调用iret中断，返回到产生页访问异常的指令处重新执行此指令。如果该虚地址不在某VMA范围内，则认为是一次非法访问。

do_pgfault函数分析

函数参数:

第一个是一个mm_struct变量，其中保存了所使用的PDT，合法的虚拟地址空间（使用链表组织），以及与后文的swap机制相关的数据；

第二个参数是产生pagefault的时候硬件产生的error code，可以用于帮助判断发生page fault的原因

最后一个参数则是出现page fault的线性地址（保存在cr2寄存器中的线性地址）

int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr);

在函数中，首先查询mm_struct中的合法的虚拟地址(事实上是线性地址，但是由于在ucore中弱化了段机制，段仅仅起到对等映射的作用，因此虚拟地址等于线性地址)链表，用于确定当前出现page fault的线性地址是否合法，如果合法则继续执行调出物理页，否则直接返回；

//返回状态参数
int ret = -E_INVAL;                         
//try to find a vma which include addr
//查询mm_struct中的合法的虚拟地址
struct vma_struct *vma = find_vma(mm, addr);

pgfault_num++;
//If the addr is in the range of a mm's vma?
//如果地址合法执行调出物理页,否则返回失败
if (vma == NULL || vma->vm_start > addr) {
    cprintf("not valid addr %x, and  can not find it in vma\n", addr);c
    goto failed;
}

接下来使用error code, 其指示这次内存访问是否为读/写，对应的物理页是否存在.

对查找到的该线性地址的内存页是否允许读写来判断是否出现了读/写不允许读/写的页这种情况

如果出现了上述情况，则应该直接返回，否则继续执行page fault的处理流程；

( W/R=1, P=1): error code的后2位, 内存访问是否为读/写，对应的物理页是否存在

//check the error_code
//检查pagefault时,硬件产生的error code错误码, 后两位
switch (error_code & 3) {
default:
        /* error code flag : default is 3 ( W/R=1, P=1): write, present */
case 2: /* error code flag : (W/R=1, P=0): write, not present */
//(W/R=1, P=0) 允许写, 不存在, 如果地址不允许写goto failed
    if (!(vma->vm_flags & VM_WRITE)) {
        cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
        goto failed;
    }
    break;
case 1: /* error code flag : (W/R=0, P=1): read, present */
//(W/R=0, P=1) 允许读, 存在, 直接返回
    cprintf("do_pgfault failed: error code flag = read AND present\n");
    goto failed;
case 0: /* error code flag : (W/R=0, P=0): read, not present */
//(W/R=0, P=0)  允许读, 不存在,  如果地址不允许读或执行,goto fail
if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
        cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
        goto failed;
    }c
}

接下来根据合法虚拟地址（mm_struct中保存的合法虚拟地址链表中可查询到）的标志，来生成对应产生的物理页的权限；

uint32_t perm = PTE_U;
if (vma->vm_flags & VM_WRITE) {c
    perm |= PTE_W;
}
addr = ROUNDDOWN(addr, PGSIZE);     //四舍五入, 获取addr规范处理后的地址

ret = -E_NO_MEM;                    //由于内存不足，请求失败 

填写 do_pgfault 函数

接下来的部分则是在本练习中需要完成代码补全的部分，首先使用在lab2中实现的函数get_pte来获取出错的线性地址对应的虚拟页起始地址对应到的页表项，在ucore中同时使用页表项来保存物理地址（在Present位为1的时候）以及被换出的物理页在swap外存中的位置（以页为单位，每页大小刚好为8个扇区，此时P位为0），并且规定swap中的第0个页空出来不用于交换，因此如果查询到的PTE不为0，则表示对应的物理页可能在内存中或者在外存中（根据P位决定），否则则表示对应的物理页尚未被分配，此时则需要调用在lab2中实现的内存分配功能来获取对应的物理页，并且将其与当前的虚拟页设置上映射关系，这个部分在lab3中被封装成了pgdir_alloc_page函数；根据上述分析练习1中需要编写的代码实现如下：

// 查找当前虚拟地址所对应的页表项
if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
    cprintf("get_pte in do_pgfault failed\n");
    goto failed;
}
// 如果这个页表项所对应的物理页不存在，则
if (*ptep == 0) {
    // 分配一块物理页，并设置页表项
	if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
        cprintf("pgdir_alloc_page in do_pgfault failed\n");
        goto failed;
    }
}

问题回答

1. 请描述页目录项（Page Directory Entry）和页表项（Page Table Entry）中组成部分对ucore实现页替换算法的潜在用处。

这个问题和 lab2 中的练习 2 中十分类似，只要搞清楚页目录项和页表项的每一位具体功能即可

页目录项是指向储存页表的页面的，所以本质上与页表项相同，结构也应该相同。每个页表项的高 20 位，就是该页表项指向的物理页面的首地址的高 20 位(当然物理页面首地址的低 12 位全为零)，而每个页表项的低 12 位，则是一些功能位，可以通过在 mmu.h 中的一组宏定义发现。对于实现页替换算法来说，页目录项（pgdir）作为一个双向链表存储了目前所有的页的物理地址和逻辑地址的对应，即在实内存中的所有页，替换算法中被换出的页从 pgdir 中选出。

接下来描述页目录项的每个组成部分，PDE（页目录项）的具体组成如下图所示；描述每一个组成部分的含义如下：

前 20 位表示 4K 对齐的该 PDE 对应的页表起始位置（物理地址，该物理地址的高 20 位即 PDE 中的高 20 位，低 12 位为 0）；
第 9-11 位未被CPU使用，可保留给 OS 使用；
接下来的第 8 位可忽略；
第 7 位用于设置 Page 大小，0 表示 4KB；
第 6 位恒为 0；
第 5 位用于表示该页是否被使用过；
第 4 位设置为 1 则表示不对该页进行缓存；
第 3 位设置是否使用 write through 缓存写策略；
第 2 位表示该页的访问需要的特权级；
第 1 位表示是否允许读写；
第 0 位为该PDE的存在位；

页表项（PTE）则存储了替换算法中被换入的页的信息，替换后会将其映射到一物理地址。

接下来描述页表项（PTE）中的每个组成部分的含义，具体组成如下图所示：

高 20 位与 PDE 相似的，用于表示该 PTE 指向的物理页的物理地址；
第 9-11 位保留给 OS 使用；
第 7-8 位恒为 0；
第 6 位表示该页是否为 dirty，即是否需要在 swap out 的时候写回外存；
第 5 位表示是否被访问；
第 3-4 位恒为 0；
第 0-2 位分别表示存在位、是否允许读写、访问该页需要的特权级；

对ucore实现页替换算法的潜在用处：

通过上述分析可以发现，无论是页目录项还是页表项，表项中均保留了3位供操作系统进行使用，可以为实现一些页替换算法的时候提供支持，并且事实上在PTE的Present位为0的时候，CPU将不会使用PTE上的内容，这就使得当P位为0的时候，可以使用PTE上的其他位用于保存操作系统需要的信息，事实上ucore也正是利用这些位来保存页替换算法里被换出的物理页的在交换分区中的位置
此外PTE中还有dirty位，用于表示当前的页是否经过修改，这就使得OS可以使用这个位来判断是否可以省去某些已经在外存中存在着，内存中的数据与外存相一致的物理页面换出到外存这种多余的操作
而PTE和PDE中均有表示是否被访问过的位，这就使得OS可以粗略地得知当前的页面是否具有着较大的被访问概率，使得OS可以利用程序的局部性原理来对替换算法进行优化（时钟替换算法中使用）

2. 如果ucore的缺页服务例程在执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

其实和普通进程遇到缺页时要做的一样，调用一个新的缺页中断程序就可以了，具体的过程如下：

将发生错误的线性地址（虚拟地址）保存至CR2寄存器中。
压入EFLAGS，CS, EIP，错误码和中断号至当前内核栈中。
保存上下文。
执行新的缺页中断程序。
恢复上下文。
继续执行上一级的缺页服务例程。

检验

填写完代码后在终端输入 make qemu ，得到如下结果：

可以看到标红处：

check_pgfault( ) succeeded!

说明检验成功，练习 1 实现正确

练习2：补充完成基于FIFO的页面替换算法

完成vmm.c中的do_pgfault函数，并且在实现FIFO算法的swap_fifo.c中完成map_swappable和swap_out_victim函数。通过对swap的测试。注意：在LAB3 EXERCISE 2处填写代码。执行

make　qemu

后，如果通过check_swap函数的测试后，会有“check_swap() succeeded!”的输出，表示练习2基本正确。

请在实验报告中简要说明你的设计实现过程。

请在实验报告中回答如下问题：

如果要在ucore上实现”extended clock页替换算法”请给你的设计方案，现有的swap_manager框架是否足以支持在ucore中实现此算法？如果是，请给你的设计方案。如果不是，请给出你的新的扩展和基此扩展的设计方案。并需要回答如下问题
- 需要被换出的页的特征是什么？
- 在ucore中如何判断具有这样特征的页？
- 何时进行换入和换出操作？

页替换算法

操作系统为何要进行页面置换呢？这是由于操作系统给用户态的应用程序提供了一个虚拟的“大容量”内存空间，而实际的物理内存空间又没有那么大。所以操作系统就就“瞒着”应用程序，只把应用程序中“常用”的数据和代码放在物理内存中，而不常用的数据和代码放在了硬盘这样的存储介质上。如果应用程序访问的是“常用”的数据和代码，那么操作系统已经放置在内存中了，不会出现什么问题。但当应用程序访问它认为应该在内存中的的数据或代码时，如果这些数据或代码不在内存中，则根据上一小节的介绍，会产生页访问异常。这时，操作系统必须能够应对这种页访问异常，即尽快把应用程序当前需要的数据或代码放到内存中来，然后重新执行应用程序产生异常的访存指令。如果在把硬盘中对应的数据或代码调入内存前，操作系统发现物理内存已经没有空闲空间了，这时操作系统必须把它认为“不常用”的页换出到磁盘上去，以腾出内存空闲空间给应用程序所需的数据或代码。

操作系统迟早会碰到没有内存空闲空间而必须要置换出内存中某个“不常用”的页的情况。如何判断内存中哪些是“常用”的页，哪些是“不常用”的页，把“常用”的页保持在内存中，在物理内存空闲空间不够的情况下，把“不常用”的页置换到硬盘上就是页替换算法着重考虑的问题。容易理解，一个好的页替换算法会导致页访问异常次数少，也就意味着访问硬盘的次数也少，从而使得应用程序执行的效率就高。本次实验涉及的页替换算法（包括扩展练习）：

先进先出(First In First Out, FIFO)页替换算法：该算法总是淘汰最先进入内存的页，即选择在内存中驻留时间最久的页予以淘汰。只需把一个应用程序在执行过程中已调入内存的页按先后次序链接成一个队列，队列头指向内存中驻留时间最久的页，队列尾指向最近被调入内存的页。这样需要淘汰页时，从队列头很容易查找到需要淘汰的页。FIFO算法只是在应用程序按线性顺序访问地址空间时效果才好，否则效率不高。因为那些常被访问的页，往往在内存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO算法的另一个缺点是，它有一种异常现象（Belady现象），即在增加放置页的页帧的情况下，反而使页访问异常次数增多。
时钟（Clock）页替换算法：是LRU算法的一种近似实现。时钟页替换算法把各个页面组织成环形链表的形式，类似于一个钟的表面。然后把一个指针（简称当前指针）指向最老的那个页面，即最先进来的那个页面。另外，时钟算法需要在页表项（PTE）中设置了一位访问位来表示此页表项对应的页当前是否被访问过。当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当操作系统需要淘汰页时，对当前指针指向的页所对应的页表项进行查询，如果访问位为“0”，则淘汰该页，如果该页被写过，则还要把它换出到硬盘上；如果访问位为“1”，则将该页表项的此位置“0”，继续访问下一个页。该算法近似地体现了LRU的思想，且易于实现，开销少，需要硬件支持来设置访问位。时钟页替换算法在本质上与FIFO算法是类似的，不同之处是在时钟页替换算法中跳过了访问位为1的页。
改进的时钟（Enhanced Clock）页替换算法：在时钟置换算法中，淘汰一个页面时只考虑了页面是否被访问过，但在实际情况中，还应考虑被淘汰的页面是否被修改过。因为淘汰修改过的页面还需要写回硬盘，使得其置换代价大于未修改过的页面，所以优先淘汰没有修改的页，减少磁盘操作次数。改进的时钟置换算法除了考虑页面的访问情况，还需考虑页面的修改情况。即该算法不但希望淘汰的页面是最近未使用的页，而且还希望被淘汰的页是在主存驻留期间其页面内容未被修改过的。这需要为每一页的对应页表项内容中增加一位引用位和一位修改位。当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当该页被“写”时，CPU中的MMU硬件将把修改位置“1”。这样这两位就存在四种可能的组合情况：（0，0）表示最近未被引用也未被修改，首先选择此页淘汰；（0，1）最近未被使用，但被修改，其次选择；（1，0）最近使用而未修改，再次选择；（1，1）最近使用且修改，最后选择。该算法与时钟算法相比，可进一步减少磁盘的I/O操作次数，但为了查找到一个尽可能适合淘汰的页面，可能需要经过多次扫描，增加了算法本身的执行开销。

页面置换机制

如果要实现页面置换机制，只考虑页替换算法的设计与实现是远远不够的，还需考虑其他问题：

哪些页可以被换出？
一个虚拟的页如何与硬盘上的扇区建立对应关系？
何时进行换入和换出操作？
如何设计数据结构以支持页替换算法？
如何完成页的换入换出操作？

这些问题在下面会逐一进行分析。注意，在实验三中仅实现了简单的页面置换机制，但现在还没有涉及实验四和实验五才实现的内核线程和用户进程，所以还无法通过内核线程机制实现一个完整意义上的虚拟内存页面置换功能。

1. 可以被换出的页

在操作系统的设计中，一个基本的原则是：并非所有的物理页都可以交换出去的，只有映射到用户空间且被用户程序直接访问的页面才能被交换，而被内核直接使用的内核空间的页面不能被换出。这里面的原因是什么呢？操作系统是执行的关键代码，需要保证运行的高效性和实时性，如果在操作系统执行过程中，发生了缺页现象，则操作系统不得不等很长时间（硬盘的访问速度比内存的访问速度慢2~3个数量级），这将导致整个系统运行低效。而且，不难想象，处理缺页过程所用到的内核代码或者数据如果被换出，整个内核都面临崩溃的危险。

但在实验三实现的ucore中，我们只是实现了换入换出机制，还没有设计用户态执行的程序，所以我们在实验三中仅仅通过执行check_swap函数在内核中分配一些页，模拟对这些页的访问，然后通过do_pgfault来调用swap_map_swappable函数来查询这些页的访问情况并间接调用相关函数，换出“不常用”的页到磁盘上。

2. 虚存中的页与硬盘上的扇区之间的映射关系

如果一个页被置换到了硬盘上，那操作系统如何能简捷来表示这种情况呢？在ucore的设计上，充分利用了页表中的PTE来表示这种情况：当一个PTE用来描述一般意义上的物理页时，显然它应该维护各种权限和映射关系，以及应该有PTE_P标记；但当它用来描述一个被置换出去的物理页时，它被用来维护该物理页与 swap 磁盘上扇区的映射关系，并且该 PTE 不应该由 MMU 将它解释成物理页映射(即没有 PTE_P 标记)，与此同时对应的权限则交由 mm_struct 来维护，当对位于该页的内存地址进行访问的时候，必然导致 page fault，然后ucore能够根据 PTE 描述的 swap 项将相应的物理页重新建立起来，并根据虚存所描述的权限重新设置好 PTE 使得内存访问能够继续正常进行。

如果一个页（4KB/页）被置换到了硬盘某8个扇区（0.5KB/扇区），该PTE的最低位–present位应该为0 （即 PTE_P 标记为空，表示虚实地址映射关系不存在），接下来的7位暂时保留，可以用作各种扩展；而包括原来高20位页帧号的高24位数据，恰好可以用来表示此页在硬盘上的起始扇区的位置（其从第几个扇区开始）。为了在页表项中区别 0 和 swap 分区的映射，将 swap 分区的一个 page 空出来不用，也就是说一个高24位不为0，而最低位为0的PTE表示了一个放在硬盘上的页的起始扇区号（见swap.h中对swap_entry_t的描述）：

swap_entry_t
-------------------------
| offset | reserved | 0 |
-------------------------
24 bits    7 bits   1 bit

考虑到硬盘的最小访问单位是一个扇区，而一个扇区的大小为512（2\^8）字节，所以需要8个连续扇区才能放置一个4KB的页。在ucore中，用了第二个IDE硬盘来保存被换出的扇区，根据实验三的输出信息

“ide 1: 262144(sectors), 'QEMU HARDDISK'.”

我们可以知道实验三可以保存262144/8=32768个页，即128MB的内存空间。swap 分区的大小是 swapfs_init 里面根据磁盘驱动的接口计算出来的，目前 ucore 里面要求 swap 磁盘至少包含 1000 个 page，并且至多能使用 1«24 个page。

3. 执行换入换出的时机

在实验三中， check_mm_struct变量这个数据结构表示了目前 ucore认为合法的所有虚拟内存空间集合，而mm中的每个vma表示了一段地址连续的合法虚拟空间。当ucore或应用程序访问地址所在的页不在内存时，就会产生page fault异常，引起调用do_pgfault函数，此函数会判断产生访问异常的地址属于check_mm_struct某个vma表示的合法虚拟地址空间，且保存在硬盘swap文件中（即对应的PTE的高24位不为0，而最低位为0），则是执行页换入的时机，将调用swap_in函数完成页面换入。

换出页面的时机相对复杂一些，针对不同的策略有不同的时机。ucore目前大致有两种策略，即积极换出策略和消极换出策略。积极换出策略是指操作系统周期性地（或在系统不忙的时候）主动把某些认为“不常用”的页换出到硬盘上，从而确保系统中总有一定数量的空闲页存在，这样当需要空闲页时，基本上能够及时满足需求；消极换出策略是指，只是当试图得到空闲页时，发现当前没有空闲的物理页可供分配，这时才开始查找“不常用”页面，并把一个或多个这样的页换出到硬盘上。

在实验三中的基本练习中，支持上述的第二种情况。对于第一种积极换出策略，即每隔1秒执行一次的实现积极的换出策略，可考虑在扩展练习中实现。对于第二种消极的换出策略，则是在ucore调用alloc_pages函数获取空闲页时，此函数如果发现无法从物理内存页分配器获得空闲页，就会进一步调用swap_out函数换出某页，实现一种消极的换出策略。

4. 页替换算法的数据结构设计

到实验二为止，我们知道目前表示内存中物理页使用情况的变量是基于数据结构Page的全局变量pages数组，pages的每一项表示了计算机系统中一个物理页的使用情况。为了表示物理页可被换出或已被换出的情况，可对Page数据结构进行扩展：

struct Page {  
……   
list_entry_t pra_page_link;   
uintptr_t pra_vaddr;   
};

pra_page_link可用来构造按页的第一次访问时间进行排序的一个链表，这个链表的开始表示第一次访问时间最近的页，链表结尾表示第一次访问时间最远的页。当然链表头可以就可设置为pra_list_head（定义在swap_fifo.c中），构造的时机是在page fault发生后，进行do_pgfault函数时。pra_vaddr可以用来记录此物理页对应的虚拟页起始地址。

当一个物理页（struct Page）需要被 swap 出去的时候，首先需要确保它已经分配了一个位于磁盘上的swap page（由连续的8个扇区组成）。这里为了简化设计，在swap_check函数中建立了每个虚拟页唯一对应的swap page，其对应关系设定为：虚拟页对应的PTE的索引值 = swap page的扇区起始位置*8。

为了实现各种页替换算法，我们设计了一个页替换算法的类框架swap_manager:

struct swap_manager  
{  
    const char *name;  
    /* Global initialization for the swap manager */  
    int (*init) (void);  
    /* Initialize the priv data inside mm_struct */  
    int (*init_mm) (struct mm_struct *mm);  
    /* Called when tick interrupt occured */  
    int (*tick_event) (struct mm_struct *mm);  
    /* Called when map a swappable page into the mm_struct */  
    int (*map_swappable) (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in);   
    /* When a page is marked as shared, this routine is called to delete the addr entry from the swap manager */
    int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);  
    /* Try to swap out a page, return then victim */  
    int (*swap_out_victim) (struct mm_struct *mm, struct Page *ptr_page, int in_tick);  
    /* check the page relpacement algorithm */  
    int (*check\_swap)(void);   
};

这里关键的两个函数指针是map_swappable和swap_out_vistim，前一个函数用于记录页访问情况相关属性，后一个函数用于挑选需要换出的页。显然第二个函数依赖于第一个函数记录的页访问情况。tick_event函数指针也很重要，结合定时产生的中断，可以实现一种积极的换页策略。

5. swap_check的检查实现

下面具体讲述一下实验三中实现置换算法的页面置换的检查执行逻辑，便于大家实现练习2。实验三的检查过程在函数swap_check（kern/mm/swap.c中）中，其大致流程如下。

调用mm_create建立mm变量，并调用vma_create创建vma变量，设置合法的访问范围为4KB~24KB；
调用free_page等操作，模拟形成一个只有4个空闲 physical page；并设置了从4KB~24KB的连续5个虚拟页的访问操作；
设置记录缺页次数的变量pgfault_num=0，执行check_content_set函数，使得起始地址分别对起始地址为0x1000, 0x2000, 0x3000, 0x4000的虚拟页按时间顺序先后写操作访问，由于之前没有建立页表，所以会产生page fault异常，如果完成练习1，则这些从4KB~20KB的4虚拟页会与ucore保存的4个物理页帧建立映射关系；
然后对虚页对应的新产生的页表项进行合法性检查；
然后进入测试页替换算法的主体，执行函数check_content_access，并进一步调用到_fifo_check_swap函数，如果通过了所有的assert。这进一步表示FIFO页替换算法基本正确实现；
最后恢复ucore环境。

完成 do_pgfault 函数

如果查询到的PTE不为0，则表示对应的物理页可能在内存中或者在外存中，则需要将其换入内存，之后中断返回之后便可以进行正常的访问处理

练习二相关代码填写如下，相关解释已经写在注释中了：

else { // if this pte is a swap entry, then load data from disk to a page with phy addr
       // and call page_insert to map the phy addr with logical addr
    // 如果不是全为0，说明可能是之前被交换到了swap磁盘中
    if(swap_init_ok) {
        // 如果开启了swap磁盘虚拟内存交换机制
        struct Page *page=NULL;
        // 将addr线性地址对应的物理页数据从磁盘交换到物理内存中(令Page指针指向交换成功后的物理页)
        if ((ret = swap_in(mm, addr, &page)) != 0) {
            // swap_in返回值不为0，表示换入失败
            cprintf("swap_in in do_pgfault failed\n");
            goto failed;
        }    
        // 将交换进来的page页与mm->padir页表中对应addr的二级页表项建立映射关系(perm标识这个二级页表的各个权限位)
        page_insert(mm->pgdir, page, addr, perm);
        // 当前page是为可交换的，将其插入到FIFO算法中维护的可被交换出去的物理页面链表中的末尾
        swap_map_swappable(mm, addr, page, 1);
        page->pra_vaddr = addr;
    }
    else {
        // 如果没有开启swap磁盘虚拟内存交换机制，但是却执行至此，则出现了问题
        cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
        goto failed;
    }
}

完成 map_swappable 函数

函数功能: 将当前的物理页面插入到FIFO算法中维护的可被交换出去的物理页面链表中的末尾，从而保证该链表中越接近链表头的物理页面在内存中的驻留时间越长

主要思想是使用list_add(head, entry)将最新到达的页面链接到链表pra_list_head队列最后

填写的完整代码如下：

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);
    
    //将新到达的页面链接到链表pra_list_head队列最后
    list_add(head, entry);
    return 0;
}

完成 swap_out_victim 函数

当调用swap_in函数的时候，会继续调用alloc_page函数分配物理页，一旦没有足够的物理页，则会使用swap_out函数将当前物理空间的某一页换出到外存，该函数会进一步调用sm（swap manager）中封装的swap_out_victim函数来选择需要换出的物理页，该函数是一个函数指针进行调用的，具体对应到了_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);
     /* Select the victim */
     /*LAB3 EXERCISE 2: YOUR CODE*/ 
     //(1)  unlink the  earliest arrival page in front of pra_list_head qeueue
     //(2)  assign the value of *ptr_page to the addr of this page
     //选择最早进入队列的项
     list_entry_t *le = head->prev;
     assert(head!=le);
     //将这一项转化为其对应的页
     struct Page *p = le2page(le, pra_page_link);
     //在队列中删除这一项
     list_del(le);
     assert(p !=NULL);
     //指针指向要换出的页
     *ptr_page = p;
     return 0;
}

问题回答

1. 如果要在ucore上实现”extended clock页替换算法”请给你的设计方案，现有的swap_manager框架是否足以支持在ucore中实现此算法？如果是，请给你的设计方案。如果不是，请给出你的新的扩展和基此扩展的设计方案。

答案是在现有的swap_manager框架是足以支持在ucore中实现此extended clock页替换算法的

在FIFO的基础上，实现extended clock页替换算法的swap_out_victim函数即可。
该函数中查找一块可用于换出的物理页，最多只需要遍历三次：
- 第一次查找 !PTE_A & !PTE_D，同时重置当前页的PTE_A，为第二次遍历的条件打基础
- 第二次查找 !PTE_A & !PTE_D，同时重置当前页的PTE_D，为第三次遍历的条件打基础
- 第三次查找，肯定能找到
这里需要注意对于PTE_D的操作，若第一次、第二次遍历都找不到符合要求的物理页，则必须对PTE_D下手，重置该标志位。还有一点需要注意，在每次修改PTE标志位后，都需要重置TLB缓存。

swap_out_victim相关代码如下

COPYstatic int
_extend_clock_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);
  
    // 第一次查找 !PTE_A & !PTE_D，同时重置当前页的PTE_A
    // 第二次查找 !PTE_A & !PTE_D， 同时重置当前页的PTE_D
    // 第三次查找，肯定能找到
    for(int i = 0; i < 3; i++)
    {
        list_entry_t *le = head->prev;
        assert(head!=le);
        while(le != head)
        {
            struct Page *p = le2page(le, pra_page_link);
            pte_t* ptep = get_pte(mm->pgdir, p->pra_vaddr, 0);
            // 如果满足未使用未修改这两个条件，则直接分配
            if(!(*ptep & PTE_A) && !(*ptep & PTE_D))
            {
                list_del(le);
                assert(p !=NULL);
                *ptr_page = p;
                return 0;
            }
            // 如果在第一次查找中，访问到了一个已经使用过的PTE，则标记为未使用。
            if(i == 0)
                *ptep &= ~PTE_A;
            // 如果在第二次查找中，访问到了一个已修改过的PTE，则标记为未修改。
            else if(i == 1)
                *ptep &= ~PTE_D;
  
            le = le->prev;
            // 遍历了一回，肯定修改了标志位，所以要刷新TLB
            tlb_invalidate(mm->pgdir, le);
        }
    }
    // 按照前面的assert与if，不可能会执行到此处，所以return -1
    return -1;
}
  
struct swap_manager swap_manager_fifo =
{
     .name            = "extend_clock swap manager",
     .init            = &_fifo_init,
     .init_mm         = &_fifo_init_mm,
     .tick_event      = &_fifo_tick_event,
     .map_swappable   = &_fifo_map_swappable,
     .set_unswappable = &_fifo_set_unswappable,
     .swap_out_victim = &_extend_clock_swap_out_victim,
     .check_swap      = &_fifo_check_swap,
};

2. 需要被换出的页的特征是什么？

PTE_A(Access)和PTE_D(Dirty)位均为0
并且只有映射到用户空间且被用户程序直接访问的页面才能被交换，而被内核直接使用的内核空间的页面不能被换出

3. 在ucore中如何判断具有这样特征的页？

获取线性地址所对应的页表项，之后使用位运算判断PTE_A和PTE_D（具体可以看上面的代码实现）

4. 何时进行换入和换出操作？

缺页时换入。
物理页帧满时换出，不过需要注意dirtybit的处理。可以在修改dirty的时候写入外存，或者可以在最终要删除该物理页时再写入外存。后者有利于多个写操作的合并，降低缺页代价，但此时的页替换算法却退化成普通的clock算法，而不是extended clock算法了。

检验

填写完代码后在终端输入 make qemu ，得到如下结果：

可以看到标红处：

check_swap( ) succeeded!

说明检验成功，练习 2 实现正确

扩展练习 Challenge 1：实现识别dirty bit的 extended clock页替换算法

其实这个扩展练习在练习二中的问题回答中已经实现了

实现方案如下：

在FIFO的基础上，实现swap_out_victim函数即可。
该函数中查找一块可用于换出的物理页，最多只需要遍历三次：
- 第一次查找 !PTE_A & !PTE_D，同时重置当前页的PTE_A，为第二次遍历的条件打基础
- 第二次查找 !PTE_A & !PTE_D，同时重置当前页的PTE_D，为第三次遍历的条件打基础
- 第三次查找，肯定能找到
这里需要注意对于PTE_D的操作，若第一次、第二次遍历都找不到符合要求的物理页，则必须对PTE_D下手，重置该标志位。还有一点需要注意，在每次修改PTE标志位后，都需要重置TLB缓存。

swap_out_victim相关代码如下（偷了个小懒，每次遍历链表都是从头开始，同时其余函数沿用FIFO）：

COPYstatic int
_extend_clock_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);
  
    // 第一次查找 !PTE_A & !PTE_D，同时重置当前页的PTE_A
    // 第二次查找 !PTE_A & !PTE_D， 同时重置当前页的PTE_D
    // 第三次查找，肯定能找到
    for(int i = 0; i < 3; i++)
    {
        list_entry_t *le = head->prev;
        assert(head!=le);
        while(le != head)
        {
            struct Page *p = le2page(le, pra_page_link);
            pte_t* ptep = get_pte(mm->pgdir, p->pra_vaddr, 0);
            // 如果满足未使用未修改这两个条件，则直接分配
            if(!(*ptep & PTE_A) && !(*ptep & PTE_D))
            {
                list_del(le);
                assert(p !=NULL);
                *ptr_page = p;
                return 0;
            }
            // 如果在第一次查找中，访问到了一个已经使用过的PTE，则标记为未使用。
            if(i == 0)
                *ptep &= ~PTE_A;
            // 如果在第二次查找中，访问到了一个已修改过的PTE，则标记为未修改。
            else if(i == 1)
                *ptep &= ~PTE_D;
  
            le = le->prev;
            // 遍历了一回，肯定修改了标志位，所以要刷新TLB
            tlb_invalidate(mm->pgdir, le);
        }
    }
    // 按照前面的assert与if，不可能会执行到此处，所以return -1
    return -1;
}
  
struct swap_manager swap_manager_fifo =
{
     .name            = "extend_clock swap manager",
     .init            = &_fifo_init,
     .init_mm         = &_fifo_init_mm,
     .tick_event      = &_fifo_tick_event,
     .map_swappable   = &_fifo_map_swappable,
     .set_unswappable = &_fifo_set_unswappable,
     .swap_out_victim = &_extend_clock_swap_out_victim,
     .check_swap      = &_fifo_check_swap,
};

扩展练习 Challenge 2：实现不考虑实现开销和效率的LRU页替换算法

重要知识点

虚拟内存

虚拟内存是CPU可以看到的“内存”。
- 虚拟内存所对应的实际物理内存单元可能不存在。
- 虚拟内存的地址和对应物理内存的地址可能不一致。
- 通过操作系统所实现的某种内存映射机制，可以达到访问的虚拟内存地址转换为物理内存地址的目的。
当程序访问内存遇上特殊情况时，CPU会执行第十四号中断处理程序——缺页处理程序来处理。
- 特殊情况有以下两种
  - 写入一个存在物理页的虚拟页——写时复制。
  - 读写一个不存在物理页的虚拟页——缺页。
  - 不满足访问权限。
- 当程序触发缺页中断时，CPU会把产生异常的线性地址存储在CR2寄存器中，并且把页访问异常错误码保存在中断栈中。
  
  其中，页访问异常错误码的位0为１表示对应物理页不存在；位１为１表示写异常；位２为１表示访问权限异常。
由于虚拟内存空间比物理内存空间大得多，所以必须在合适的情况下，将不常用的页面调至外存，或者将待用的页面从外存调入内存中。 这个过程对应用程序无感。 而什么时候调进调出，选择哪个页面调出，这都是值得考究的，这就是使用页面置换算法的目的。

Page Fault异常处理

目标页帧不存在（页表项全为0，即该线性地址与物理地址尚未建立映射或者已经撤销)；
相应的物理页帧不在内存中（页表项非空，但Present标志位=0，比如在swap分区或磁盘文件上)，这在本次实验中会出现，我们将在下面介绍换页机制实现时进一步讲解如何处理；
不满足访问权限(此时页表项P标志=1，但低权限的程序试图访问高权限的地址空间，或者有程序试图写只读页面).

[提示]页访问异常错误码有32位。位0为１表示对应物理页不存在；位１为１表示写异常（比如写了只读页；位２为１表示访问权限异常（比如用户态程序访问内核空间的数据）

[提示]　CR2是页故障线性地址寄存器，保存最后一次出现页故障的全32位线性地址。CR2用于发生页异常时报告出错信息。当发生页异常时，处理器把引起页异常的线性地址保存在CR2中。操作系统中对应的中断服务例程可以检查CR2的内容，从而查出线性地址空间中的哪个页引起本次异常。

trap–> trap_dispatch–>pgfault_handler–>do_pgfault

下面需要具体分析一下do_pgfault函数。do_pgfault的调用关系如下图所示：

图 do_pgfault的调用关系图

页替换算法

先进先出(First In First Out, FIFO)页替换算法：该算法总是淘汰最先进入内存的页，即选择在内存中驻留时间最久的页予以淘汰。只需把一个应用程序在执行过程中已调入内存的页按先后次序链接成一个队列，队列头指向内存中驻留时间最久的页，队列尾指向最近被调入内存的页。这样需要淘汰页时，从队列头很容易查找到需要淘汰的页。FIFO算法只是在应用程序按线性顺序访问地址空间时效果才好，否则效率不高。因为那些常被访问的页，往往在内存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO算法的另一个缺点是，它有一种异常现象（Belady现象），即在增加放置页的页帧的情况下，反而使页访问异常次数增多。
时钟（Clock）页替换算法：是LRU算法的一种近似实现。时钟页替换算法把各个页面组织成环形链表的形式，类似于一个钟的表面。然后把一个指针（简称当前指针）指向最老的那个页面，即最先进来的那个页面。另外，时钟算法需要在页表项（PTE）中设置了一位访问位来表示此页表项对应的页当前是否被访问过。当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当操作系统需要淘汰页时，对当前指针指向的页所对应的页表项进行查询，如果访问位为“0”，则淘汰该页，如果该页被写过，则还要把它换出到硬盘上；如果访问位为“1”，则将该页表项的此位置“0”，继续访问下一个页。该算法近似地体现了LRU的思想，且易于实现，开销少，需要硬件支持来设置访问位。时钟页替换算法在本质上与FIFO算法是类似的，不同之处是在时钟页替换算法中跳过了访问位为1的页。
改进的时钟（Enhanced Clock）页替换算法：在时钟置换算法中，淘汰一个页面时只考虑了页面是否被访问过，但在实际情况中，还应考虑被淘汰的页面是否被修改过。因为淘汰修改过的页面还需要写回硬盘，使得其置换代价大于未修改过的页面，所以优先淘汰没有修改的页，减少磁盘操作次数。改进的时钟置换算法除了考虑页面的访问情况，还需考虑页面的修改情况。即该算法不但希望淘汰的页面是最近未使用的页，而且还希望被淘汰的页是在主存驻留期间其页面内容未被修改过的。这需要为每一页的对应页表项内容中增加一位引用位和一位修改位。当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当该页被“写”时，CPU中的MMU硬件将把修改位置“1”。这样这两位就存在四种可能的组合情况：（0，0）表示最近未被引用也未被修改，首先选择此页淘汰；（0，1）最近未被使用，但被修改，其次选择；（1，0）最近使用而未修改，再次选择；（1，1）最近使用且修改，最后选择。该算法与时钟算法相比，可进一步减少磁盘的I/O操作次数，但为了查找到一个尽可能适合淘汰的页面，可能需要经过多次扫描，增加了算法本身的执行开销。

页面置换机制

如果要实现页面置换机制，只考虑页替换算法的设计与实现是远远不够的，还需考虑其他问题：

哪些页可以被换出？
一个虚拟的页如何与硬盘上的扇区建立对应关系？
何时进行换入和换出操作？
如何设计数据结构以支持页替换算法？
如何完成页的换入换出操作？

1. 可以被换出的页

2. 虚存中的页与硬盘上的扇区之间的映射关系

swap_entry_t
-------------------------
| offset | reserved | 0 |
-------------------------
24 bits    7 bits   1 bit

“ide 1: 262144(sectors), 'QEMU HARDDISK'.”

3. 执行换入换出的时机

4. 页替换算法的数据结构设计

struct Page {  
……   
list_entry_t pra_page_link;   
uintptr_t pra_vaddr;   
};

为了实现各种页替换算法，我们设计了一个页替换算法的类框架swap_manager:

struct swap_manager  
{  
    const char *name;  
    /* Global initialization for the swap manager */  
    int (*init) (void);  
    /* Initialize the priv data inside mm_struct */  
    int (*init_mm) (struct mm_struct *mm);  
    /* Called when tick interrupt occured */  
    int (*tick_event) (struct mm_struct *mm);  
    /* Called when map a swappable page into the mm_struct */  
    int (*map_swappable) (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in);   
    /* When a page is marked as shared, this routine is called to delete the addr entry from the swap manager */
    int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);  
    /* Try to swap out a page, return then victim */  
    int (*swap_out_victim) (struct mm_struct *mm, struct Page *ptr_page, int in_tick);  
    /* check the page relpacement algorithm */  
    int (*check\_swap)(void);   
};

5. swap_check的检查实现

调用mm_create建立mm变量，并调用vma_create创建vma变量，设置合法的访问范围为4KB~24KB；
调用free_page等操作，模拟形成一个只有4个空闲 physical page；并设置了从4KB~24KB的连续5个虚拟页的访问操作；
设置记录缺页次数的变量pgfault_num=0，执行check_content_set函数，使得起始地址分别对起始地址为0x1000, 0x2000, 0x3000, 0x4000的虚拟页按时间顺序先后写操作访问，由于之前没有建立页表，所以会产生page fault异常，如果完成练习1，则这些从4KB~20KB的4虚拟页会与ucore保存的4个物理页帧建立映射关系；
然后对虚页对应的新产生的页表项进行合法性检查；
然后进入测试页替换算法的主体，执行函数check_content_access，并进一步调用到_fifo_check_swap函数，如果通过了所有的assert。这进一步表示FIFO页替换算法基本正确实现；
最后恢复ucore环境。

uCore虚拟内存机制的实现

I. 虚拟内存管理

结构体变量check_mm_struct用于管理虚拟内存页面，其结构体如下

COPY// the control struct for a set of vma using the same PDT
struct mm_struct {
    list_entry_t mmap_list;        // 按照虚拟地址顺序双向连接的虚拟页链表
    struct vma_struct *mmap_cache; // 当前使用的虚拟页地址，该成员加速页索引速度。
    pde_t *pgdir;                  // 虚拟页对应的PDT
    int map_count;                 // 虚拟页个数
    void *sm_priv;                 // 用于指向swap manager的某个链表,在FIFO算法中，该双向链表用于将可交换的已分配物理页串起来
};

当分配出新的虚拟页时，程序会执行insert_vma_struct函数，此时虚拟页vma_struct就会被插入mm_struct::mmap_list双向链表中。
若程序首次访问该内存而触发缺页中断时，程序会在缺页处理程序中为该虚拟页划分出一块新的物理页。同时，还会更新mm_struct::pgdir上的对应页表条目，之后该页的内存访问即可正常执行。
在FIFO页面置换算法中，初始时，mm_struct中的sm_priv会被设置为pra_list_head。而pra_list_head是一个双向链表的起始结点，该双向链表用于将可交换的已分配物理页串起来。

II. 页面置换

swap_manager与pmm_manager类似，都设置了一个用于管理某个功能的模块。

COPYstruct swap_manager
{
     const char *name;
     /* Global initialization for the swap manager */
     int (*init)            (void);
     /* Initialize the priv data inside mm_struct */
     int (*init_mm)         (struct mm_struct *mm);
     /* Called when tick interrupt occured */
     int (*tick_event)      (struct mm_struct *mm);
     /* Called when map a swappable page into the mm_struct */
     int (*map_swappable)   (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in);
     /* When a page is marked as shared, this routine is called to
      * delete the addr entry from the swap manager */
     int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);
     /* Try to swap out a page, return then victim */
     int (*swap_out_victim) (struct mm_struct *mm, struct Page **ptr_page, int in_tick);
     /* check the page relpacement algorithm */
     int (*check_swap)(void);
};

若使用FIFO页面置换算法，则在缺页中断程序中，程序只会换入目标物理页，而不会主动换出。

只有在分配空闲物理页时，若pmm_manager->alloc_pages(n)失败，则程序才会执行一次页面换出，以腾出空闲的物理页，并重新分配。

swap_in函数只会将目标物理页加载进内存中，而不会修改页表条目。所以相关的标志位设置必须在swap_in函数的外部手动处理。而swap_out函数会先执行swap_out_victim，找出最适合换出的物理页，并将其换出，最后刷新TLB。需要注意的是swap_out函数会在函数内部设置PTE，当某个页面被换出后，PTE会被设置为所换出物理页在硬盘上的偏移。

COPYcprintf("swap_out: i %d, store page in vaddr 0x%x to disk swap entry %d\n", i, v, page->pra_vaddr/PGSIZE+1);
*ptep = (page->pra_vaddr/PGSIZE+1)<<8;
free_page(page);

当PTE所对应的物理页存在于内存中，那么该PTE就是正常的页表条目，可被CPU直接寻址用于转换地址。但当所对应的物理页不在内存时，该PTE就成为swap_entry_t，保存该物理页数据在外存的偏移位置。相关代码如下：

COPY/*
 * swap_entry_t
 * --------------------------------------------
 * |         offset        |   reserved   | 0 |
 * --------------------------------------------
 *           24 bits            7 bits    1 bit
 * /
 /* *
 * swap_offset - takes a swap_entry (saved in pte), and returns
 * the corresponding offset in swap mem_map.
 * */
#define swap_offset(entry) ({                                       \
               size_t __offset = (entry >> 8);                        \
               if (!(__offset > 0 && __offset < max_swap_offset)) {    \
                    panic("invalid swap_entry_t = %08x.\n", entry);    \
               }                                                    \
               __offset;                                            \
          })

同时，不是所有物理页面都可以置换，例如内核关键代码和数据等等，所以在分配物理页时，需要对于那些可被置换的物理页执行swap_map_swappable函数，将该物理页加入到mm_struct::sm_priv指针所指向的双向链表中，换入和换出操作都会操作该链表（插入/移除可交换的已分配物理页）。

数据结构Page和vma_struct分别用于管理物理页和虚拟页，其结构如下：

COPY// 用于描述某个虚拟页的结构
struct vma_struct {
    struct mm_struct *vm_mm; // 管理该虚拟页的mm_struct
    uintptr_t vm_start;      // 虚拟页起始地址，包括当前地址  
    uintptr_t vm_end;        // 虚拟页终止地址，不包括当前地址（地址前闭后开）  
    uint32_t vm_flags;       // 相关标志位
    list_entry_t list_link;  // 用于连接各个虚拟页的双向指针
};
  
// 数据结构Page相关成员的用途已在uCore-2中介绍过，这里只提它新增的两个成员pra_*
struct Page {
    int ref;
    uint32_t flags;
    unsigned int property;
    list_entry_t page_link;
    list_entry_t pra_page_link;     // 用于连接上一个和下一个*可交换已分配*的物理页
    uintptr_t pra_vaddr;            // 用于保存该物理页所对应的虚拟地址。
};

当分配某个虚拟页vma_struct时，程序会在insert_vma_struct函数中设置其vm_mm成员为某个mm_struct，这样便于后续的管理。
在函数pgdir_alloc_page中，程序会设置Page的pra_vaddr成员，将其设置为当前物理页所对应的虚拟地址，之后便可通过Page->pra_vaddr->pte一条链，直接找到当前物理页地址所对应的PTE条目。同时，也可通过pra_vaddr来确定对应外存的相对偏移page->pra_vaddr/PGSIZE+1。
Page::page_link用于将空闲物理页连接至双向链表中，而page::pra_page_link用于将可交换的已分配物理页连接至另一个双向链表中，注意两者的用途是不同的。

实验中涉及的知识点列举

在本次实验中所涉及到的知识点有：

虚拟内存管理的基本概念与原理；
page fault异常的处理流程；
页替换算法；
物理内存的管理；

对应到的操作系统中的知识点分别有：

操作系统中虚拟内存机制的实现；
操作系统中对具体某一个页面替换算法的实现；
操作系统中的中断处理机制；

它们之间的关系为，前者的知识点为后者中操作系统中的具体实现提供了理论基础(比如说页替换算法就为OS中具体实现swap out的机制提供了基础)；

实验中未涉及的知识点列举

在本次实验中未涉及到的知识点有：

操作系统中的进程、线程的管理与调度；
操作系统中的进程间的同步互斥机制；
操作系统访问外设或者外存所使用的文件系统以及虚拟文件系统；
操作系统的启动过程；
操作系统对IO设备的管理机制；

实验心得

从这次实验中，我对物理内存管理有了一个更好的理解，我们都知道 Linux 操作系统创始人 Linus 曾经说过

Talk is cheap. Show me the code.

我可以说，如果仅仅只是从课本上学理论知识，会做一些题，应付一下考试，这是完全没有什么问题的，你的成绩肯定不会差，但是我想问，这又能学到多少呢？让你自己写一些简单的代码都不会，最多也就只能纸上谈兵罢了

ucore 真的是一个很好地帮助我们理解操作系统的实验，让我们在自己实现动手的时候去理解操作系统，通过做实验指导书上的练习来一步步完善 ucore 操作系统，在这个过程中学习相关知识

在这次 lab3 中，我对虚拟内存管理有了一个更好的理解，在教材中虽然也有提到页错误的处理过程，但是远远没有是实验中的这么详细，教材中只会告诉你什么时候会发生页错误，还有就是使用哪种页替换算法的时候该将哪一个页给替换掉，但是这中间其实还有很多细节不会提到，像页错误异常的具体处理过程，具体的过程如下：

将发生错误的线性地址（虚拟地址）保存至CR2寄存器中。
压入EFLAGS，CS, EIP，错误码和中断号至当前内核栈中。
保存上下文。
执行缺页中断程序。
恢复上下文。
继续执行上一级服务例程。

还有就是在进行页替换的时候不仅仅就是将两个物理页进行替换这么简单，根据具体的算法选择出要换出的页后，将要换入的页换入后，还需要建立好二级页表的映射关系，还得将已经换入的页加入到可被交换出去的物理页面链表中

老师上课和书上对时钟算法的介绍都十分地简单，之前我自己对这方面的了解确实也没有那么深刻，但是在仔细阅读了官方文档，完成了练习二中的问题回答和扩展练习 1 后，我对始终算法可谓是熟悉了不少，简单来说就是加了条件的 FIFO 算法

还有就是在阅读官方文档时我了解了页换出的两种机制，即积极换出策略和消极换出策略，在课上和课本上说的应该都是消极换出策略，积极换出策略是指操作系统周期性地（或在系统不忙的时候）主动把某些认为“不常用”的页换出到硬盘上，从而确保系统中总有一定数量的空闲页存在，这样当需要空闲页时，基本上能够及时满足需求；消极换出策略是指，只是当试图得到空闲页时，发现当前没有空闲的物理页可供分配，这时才开始查找“不常用”页面，并把一个或多个这样的页换出到硬盘上。

实验题目

实验目的

实验内容

练习0：填写已有实验

练习1：给未被映射的地址映射上物理页

基本原理概述

关键数据结构和相关函数分析

Page Fault异常处理

do_pgfault函数分析

填写 do_pgfault 函数

问题回答

检验

练习2：补充完成基于FIFO的页面替换算法

页替换算法

页面置换机制

1. 可以被换出的页

2. 虚存中的页与硬盘上的扇区之间的映射关系

3. 执行换入换出的时机

4. 页替换算法的数据结构设计

5. swap_check的检查实现

完成 do_pgfault 函数

完成 map_swappable 函数

完成 swap_out_victim 函数

问题回答

检验

扩展练习 Challenge 1：实现识别dirty bit的 extended clock页替换算法

扩展练习 Challenge 2：实现不考虑实现开销和效率的LRU页替换算法

重要知识点

虚拟内存

Page Fault异常处理

页替换算法

页面置换机制

1. 可以被换出的页

2. 虚存中的页与硬盘上的扇区之间的映射关系

3. 执行换入换出的时机

4. 页替换算法的数据结构设计

5. swap_check的检查实现

uCore虚拟内存机制的实现

I. 虚拟内存管理

II. 页面置换

实验中涉及的知识点列举

实验中未涉及的知识点列举

实验心得

参考资料

CATALOG

FEATURED TAGS

FRIENDS