ucorelab3

LAB 3

实验目的

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

实验内容

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

练习

练习0：填写已有实验

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

解：这里使用meld将lab2修改的default_pmm.c和pmm.c中有注释的部分移入lab3中对应位置，同时将lab1中修改的debug.c,trap.c以及init.c中有注释的部分移入lab3中对应的位置。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3vQjGKG2-1652150932796)(C:\Users\zhaolv\AppData\Roaming\Typora\typora-user-images\image-20220508223041924.png)]

练习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的缺页服务例程在执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

解：首先，我们需要了解关于页异常的相关知识：

页异常：

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

目标页面不存在（页表项全为0，即该线性地址与物理地址尚未建立映射或者已经撤销），相应的物理页面不在内存中（页表项非空，但Present标志位=0，比如在swap分区或磁盘文件上，访问权限不符合（此时页表项P标志=1，比如企图写只读页面）。

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

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

在于实验二中有关内存的数据结构和相关操作都是直接针对实际存在的资源–物理内存空间的管理，没有从一般应用程序对内存的“需求”考虑，即需要有相关的数据结构和操作来体现一般应用程序对虚拟内存的“需求”。一般应用程序的对虚拟内存的“需求”与物理内存空间的“供给”没有直接的对应关系，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 {
      
        struct mm_struct *vm_mm;  //指向一个比vma_struct更高的抽象层次的数据结构mm_struct 
        uintptr_t vm_start;      //vma的开始地址
        uintptr_t vm_end;      // vma的结束地址
        uint32_t vm_flags;     // 虚拟内存空间的属性
        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 {
      
        list_entry_t mmap_list;  //双向链表头，链接了所有属于同一页目录表的虚拟内存空间
        struct vma_struct *mmap_cache;  //指向当前正在使用的虚拟内存空间
        pde_t *pgdir; //指向的就是 mm_struct数据结构所维护的页表
        int map_count; //记录mmap_list里面链接的vma_struct的个数
        void *sm_priv; //指向用来链接记录页访问情况的链表头
 };  

mmap_list是双向链表头，链接了所有属于同一页目录表的虚拟内存空间，mmap_cache是指向当前正在使用的虚拟内存空间，由于操作系统执行的“局部性”原理，当前正在用到的虚拟内存空间在接下来的操作中可能还会用到，这时就不需要查链表，而是直接使用此指针就可找到下一次要用到的虚拟内存空间。pgdir 所指向的就是 mm_struct数据结构所维护的页表。通过访问pgdir可以查找某虚拟地址对应的页表项是否存在以及页表项的属性等。map_count记录mmap_list 里面链接的 vma_struct的个数。sm_priv指向用来链接记录页访问情况的链表头，这建立了mm_struct和后续要讲到的swap_manager之间的联系。

页异常之后的处理机制：

trap–> trap_dispatch–>pgfault_handler–>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_pgfult的执行过程：
出现page fault后，会有一个中断状态指针tf，传到trap()中处理：

void
trap(struct trapframe *tf) {
    
    // dispatch based on what type of trap occurred
    trap_dispatch(tf);
}

trap中调用了trap_dispatch函数：

static void
trap_dispatch(struct trapframe *tf) {
    
    char c;

    int ret;

    switch (tf->tf_trapno) {
    
    case T_PGFLT:  //page fault
        if ((ret = pgfault_handler(tf)) != 0) {
    
            print_trapframe(tf);
            panic("handle pgfault failed. %e\n", ret);
        }
        break;

因为此时应该是page fault，所以调用pgfault_handler()：

static int
pgfault_handler(struct trapframe *tf) {
    
    extern struct mm_struct *check_mm_struct;
    print_pgfault(tf);
    if (check_mm_struct != NULL) {
    
        return do_pgfault(check_mm_struct, tf->tf_err, rcr2());
    }
    panic("unhandled page fault.\n");
}

最后调用了do_pgfault()函数：

do_pgfault()函数:

首先查看 do_pgfault函数原型：

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

传入的三个参数分别为

• mm:应用程序虚拟存储总管
• error_code:错误的类型
• addr:具体出错的虚拟地址

具体的函数代码为：

int do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    
    int ret = -E_INVAL; 
 /*对虚拟地址进行判断，如果虚拟地址的范围超过了限制， 或者是虚拟地址无法被查找到，即可以说该地址是不合法的， 进行了一次非法访问，那么可以直接报错。*/
    //尝试寻找包括addr的vma
    struct vma_struct *vma = find_vma(mm, addr);
    pgfault_num++;
    //判断addr是否在vma的范围中
    if (vma == NULL || vma->vm_start > addr) {
    
        cprintf("not valid addr %x, and can not find it in vma\n", addr);
        goto failed;
    }
    //错误类型检查
    /*错误码的低2位分别是：P标志（位0）最低位：表示当前的错误是 由于不存在页面（0）引起，还是由于违反访问权限（1）引起。 W / R标志（位1）：表示当前错误是由于读操作（0） 引起还是还是写操作（1）引起。*/
    switch (error_code & 3) {
    
    default:
            /* error code flag : default is 3 ( W/R=1, P=1): write, present */
    case 2: /* 申请写操作，物理内存中不存在，并且对应地址的内容不允许写*/
        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: /* 申请读操作，并且物理内存中存在（因此已经报错，所以是权限不够） */
        cprintf("do_pgfault failed: error code flag = read AND present\n");
        goto failed;
    case 0: /* 申请读操作但是物理内存中不存在，并且该地址数据不允许被读或者加载*/ 
        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;
        }
    }
    uint32_t perm = PTE_U;//prem:给物理页赋予权限的中间变量
    if (vma->vm_flags & VM_WRITE) {
    
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE);
    ret = -E_NO_MEM;
    pte_t *ptep=NULL;
    
    //修改部分
    //查找页目录，如果不存在则失败
    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;
        }
    }
   //练习二实现 
   //页表项非空，尝试换入页面
    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);
	    //建立虚拟地址和物理地址之间的对应关系，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;
        }
   }
/*#################修改部分#######################*/
   ret = 0;
failed:
    return ret;
}

最后的运行的结果为：

可以看到，通过check_pgfault函数的测试，练习1通过。

问题的回答：

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

分页机制的实现，确保了虚拟地址和物理地址之间的对应关系，一方面，通过查找虚拟地址是否存在于一二级页表中，可以容易发现该地址是否是合法的，同时可以通过修改映射关系即可实现页替换操作。另一方面，在实现页替换时涉及到换入换出：换入时需要将某个虚拟地址对应的磁盘的一页内容读入到内存中，换出时需要将某个虚拟页的内容写到磁盘中的某个位置。

另外，基于页表实现了地址的分段操作，在这里，一个物理地址不同的位数上，会存储一系列不同的信息，比如，pg_fault函数中的权限判断就用到了这方面的操作，观察代码中的宏定义，我们得到部分标记位的含义如下：

/* page table/directory entry flags */
#define PTE_P 0x001 // Present
#define PTE_W 0x002 // Writeable
#define PTE_U 0x004 // User
#define PTE_PWT 0x008 // Write-Through
#define PTE_PCD 0x010 // Cache-Disable
#define PTE_A 0x020 // Accessed
#define PTE_D 0x040 // Dirty
#define PTE_PS 0x080 // Page Size
#define PTE_MBZ 0x180 // Bits must be zero
#define PTE_AVAIL 0xE00 // Available for software use
                                                // The PTE_AVAIL bits aren't used by the kernel or interpreted by the
                                                // hardware, so user processes are allowed to set them arbitrarily.

#define PTE_USER (PTE_U | PTE_W | PTE_P)

无论是页目录项还是页表项，表项中均保留了3位供操作系统进行使用，可以为实现一些页替换算法的时候提供支持。

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

CPU会把产生异常的线性地址存储在CR2寄存器中，并且把表示页访问异常类型的error Code保存在中断栈中。之后通过上述分析的trap–> trap_dispatch–>pgfault_handler–>do_pgfault调用关系，一步步做出处理。

练习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中如何判断具有这样特征的页？
  • 何时进行换入和换出操作？

解：根据实验指导书：

由于操作系统给用户态的应用程序提供了一个虚拟的“大容量”内存空间，而实际的物理内存空间又没有那么大。所以操作系统就就“瞒着”应用程序，只把应用程序中“常用”的数据和代码放在物理内存中，而不常用的数据和代码放在了硬盘这样的存储介质上。但应用程序访问到这些不常用的数据和代码时，因为页面保存在swap区或者磁盘中，会导致页错误异常，所以要通过页面替换算法解决这个问题。

而练习1和这里的关联就在于：页面替换主要分为两个方面，页面换出和页面换入。练习1实现的是页面换入，主要在上述的do_pgfault()函数实现；而练习2这里主要实现，页面换出，主要是在swap_out_vistim()函数。另外，在练习1还有一个函数叫做swappable，代表将该页面设置为可交换的。于是，练习2主要是对于这两个函数的实现。

页面换入部分：

do_pgfault()函数中的部分代码：

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;
        }
   }
   ret = 0;
failed:
    return ret;
}

在换入时，需要先检查产生访问异常的地址是否属于某个vma表示的合法虚拟地址，并且保存在硬盘的swap文件中（对应的PTE的高24位不为0）。如果满足以上亮点，则执行swap_in() 函数换入页面。

页面换出部分：

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

同时，此实验的基础实验中采用的上述的第二种策略。

整个的页面替换策略采用的FIFO策略：

先进先出(First In First Out, FIFO)页替换算法：该算法总是淘汰最先进入内存的页，即选择在内存中驻留时间最久的页予以淘汰。只需把一个应用程序在执行过程中已调入内存的页按先后次序链接成一个队列，队列头指向内存中驻留时间最久的页，队列尾指向最近被调入内存的页。这样需要淘汰页时，从队列头很容易查找到需要淘汰的页。FIFO算法只是在应用程序按线性顺序访问地址空间时效果才好，否则效率不高。因为那些常被访问的页，往往在内存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO算法的另一个缺点是，它有一种异常现象（Belady现象），即在增加放置页的页帧的情况下，反而使页访问异常次数增多。

类框架swap_manager

为了实现各种页替换算法，我们设计了一个页替换算法的类框架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函数指针也很重要，结合定时产生的中断，可以实现一种积极的换页策略。

实现：

首先是FiFO的初始化：

list_entry_t pra_list_head;
/* * (2) _fifo_init_mm: init pra_list_head and let mm->sm_priv point to the addr of pra_list_head. * Now, From the memory control struct mm_struct, we can access FIFO PRA */
static int
_fifo_init_mm(struct mm_struct *mm)
{
         
     list_init(&pra_list_head);
     mm->sm_priv = &pra_list_head;
     //cprintf(" mm->sm_priv %x in fifo_init_mm\n",mm->sm_priv);
     return 0;
}
//清空，表头指向队列的头

调用_fifo_map_swappable()函数：

将最近被用到的页面添加到算法所维护的次序队列。这里建立一个指针指向最近使用的页面，然后在列表中新建一个空指针，将最近用到的页面添加到次序队尾。

/* * (3)_fifo_map_swappable: According FIFO PRA, we should link the most recent arrival page at the back of pra_list_head qeueue */
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);
    //record the page access situlation
    /*LAB3 EXERCISE 2: YOUR CODE*/ 
    //(1)link the most recent arrival page at the back of the pra_list_head qeueue.
    list_add(head, entry);//在表头后加入新的page
    return 0;
}

_fifo_swap_out_victim()函数：

_fifo_swap_out_victim()函数是用来查询哪个页面需要被换出，它的主要作用是用来查询哪个页面需要被换出。使用链表操作，删除掉最早进入的那个页，并按照注释将这个页面给到传入参数ptr_page。

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; //将进来最早的页面从队列中删除
     return 0;
}

实验结果：

回答问题：

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

• 需要被换出的页的特征是什么？
• 在ucore中如何判断具有这样特征的页？
• 何时进行换入和换出操作？

解：

首先，我们需要了解extended clock页替换算法的具体表示：

在时钟置换算法中，淘汰一个页面时只考虑了页面是否被访问过，但在实际情况中，还应考虑被淘汰的页面是否被修改过。因为淘汰修改过的页面还需要写回硬盘，使得其置换代价大于未修改过的页面，所以优先淘汰没有修改的页，减少磁盘操作次数。改进的时钟置换算法除了考虑页面的访问情况，还需考虑页面的修改情况。即该算法不但希望淘汰的页面是最近未使用的页，而且还希望被淘汰的页是在主存驻留期间其页面内容未被修改过的。

这需要为每一页的对应页表项内容中增加一位引用位和一位修改位。

当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当该页被“写”时，CPU中的MMU硬件将把修改位置“1”。这样这两位就存在四种可能的组合情况：

• （0，0）表示最近未被引用也未被修改，首先选择此页淘汰；
• （0，1）最近未被使用，但被修改，其次选择；
• （1，0）最近使用而未修改，再次选择；
• （1，1）最近使用且修改，最后选择。

该算法与时钟算法相比，可进一步减少磁盘的I/O操作次数，但为了查找到一个尽可能适合淘汰的页面，可能需要经过多次扫描，增加了算法本身的执行开销。

接下来，回答问题：

1、需要被换出的页的特征是什么？

1. 该物理页在当前指针上一次扫过之前没有被访问过；
2. 该物理页的内容与其在外存中保存的数据是一致的,。（即没有被修改过）

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

指针扫描到的第一个dirty bit为0且没被访问过的页。

3、何时进行换入和换出操作？

当需要调用的页不在页表中时，并且在页表已满的情况下，会引发PageFault，此时需要进行换入和换出操作。具体是当保存在磁盘中的内存需要被访问时，需要进行换入操作；当位于物理页框中的内存被页面替换算法选择时，需要进行换出操作。

扩展练习 Challenge 1：实现识别dirty bit的 extended clock页替换算法（需要编程）

准备知识：

时钟页替换算法把各个页面组织成环形链表的形式，类似于一个钟的表面。然后把一个指针（简称当前指针）指向最老的那个页面，即最先进来的那个页面。另外，时钟算法需要在页表项（PTE）中设置了一位访问位来表示此页表项对应的页当前是否被访问过。当该页被访问时，CPU中的MMU硬件将把访问位置“1”。当操作系统需要淘汰页时，对当前指针指向的页所对应的页表项进行查询，如果访问位为“0”，则淘汰该页，如果该页被写过，则还要把它换出到硬盘上；如果访问位为“1”，则将该页表项的此位置“0”，继续访问下一个页。

实现这个算法也就是沿着链表遍历，将最近未被访问且未被修改的页换出内存。

插入：

如果环形链表为空，那么这个页面就是整个链表，将指针指向这个页面。否则，只需要将页面插入指针指向的页面之前即可。

换出：

该函数中查找一块可用于换出的物理页，最多只需要遍历四次：

• 首先，查找标记为<0,0>的页面；
• 如果上一步没有找到，查找标记<0,1>，并将访问过的页面的访问位清零；
• 如果上一步没有找到，再次查找标记为<0,0>的页面；
• 如果上一步没有找到，再次查找标记为<0,1>的页面；

将PTE中的PTE_A清除后，需要调用tlb_invalidate刷新TLB，否则当页面被再次访问的时候，PTE中的PTE_A不会被设置。

实现如下：

kern/mm/mmu.h文件有如下定义：

#define PTE_A 0x020 // Accessed
#define PTE_D 0x040 // Dirty

PTE_A是表示访问的标志位，PTE_D是表示修改的标志位

list_entry_t pra_list_head;

static int
_clock_init_mm(struct mm_struct *mm)
{
         
     list_init(&pra_list_head);
     mm->sm_priv = &pra_list_head;
     return 0;
}
//此处和FIFO的初始化方法相同

static int
_clock_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 -> prev, entry);// 新插入的页dirty bit标记为0.
    struct Page *ptr = le2page(entry, pra_page_link);
    pte_t *pte = get_pte(mm -> pgdir, ptr -> pra_vaddr, 0);
    *pte &= ~PTE_D;
    return 0;
}

static int
_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);

     list_entry_t *p = head;
     while (1) {
    
         p = list_next(p);
         if (p == head) {
    
             p = list_next(p);
         }
         struct Page *ptr = le2page(p, pra_page_link);
         pte_t *pte = get_pte(mm -> pgdir, ptr -> pra_vaddr, 0);
         //获取页表项
         if ((*pte & PTE_D) == 1) {
    // 如果dirty bit为1，改为0
             *pte &= ~PTE_D;
         } 
         else 
         {
    // 如果dirty bit为0，则标记为换出页
             *ptr_page = ptr;
             list_del(p);
             break;
         }
     }
     return 0;
}

仿照swap_fifo.c中的_fifo_check_swap，编写_clock_check_swap:

static int
_clock_check_swap(void) {
    
    cprintf("write Virt Page c in clock_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c;
    assert(pgfault_num==4);
    cprintf("write Virt Page a in clock_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==4);
    cprintf("write Virt Page d in clock_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d;
    assert(pgfault_num==4);
    cprintf("write Virt Page b in clock_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==4);
    cprintf("write Virt Page e in clock_check_swap\n");
    *(unsigned char *)0x5000 = 0x0e;
    assert(pgfault_num==5);
    cprintf("write Virt Page b in clock_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==5);
    cprintf("write Virt Page a in clock_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==6);
    cprintf("write Virt Page b in clock_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==7);
    cprintf("write Virt Page c in clock_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c;
    assert(pgfault_num==8);
    cprintf("write Virt Page d in clock_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d;
    assert(pgfault_num==9);
    cprintf("write Virt Page e in clock_check_swap\n");
    *(unsigned char *)0x5000 = 0x0e;
    assert(pgfault_num==10);
    cprintf("write Virt Page a in clock_check_swap\n");
    assert(*(unsigned char *)0x1000 == 0x0a);
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==11);
    return 0;
}

这些也同样进行仿写：

static int
_clock_init(void)
{
    
    return 0;
}

static int
_clock_set_unswappable(struct mm_struct *mm, uintptr_t addr)
{
    
    return 0;
}

static int
_clock_tick_event(struct mm_struct *mm)
{
     return 0; }

最后对swap_manager_clock进行初始化：

struct swap_manager swap_manager_clock =
{
    
     .name            = "extend_clock swap manager",
     .init            = &_clock_init,
     .init_mm         = &_clock_init_mm,
     .tick_event      = &_clock_tick_event,
     .map_swappable   = &_clock_map_swappable,
     .set_unswappable = &_clock_set_unswappable,
     .swap_out_victim = &_clock_swap_out_victim,
     .check_swap      = &_clock_check_swap,
};

以上就是extended clcok页替换算法的实现。但是这里需要调用swap_manager_clock才能验证代码所写的是否正确。为了调用extended clock算法，将swap.c中swap_init函数的sm = &swap_manager_fifo;**改成**sm = &swap_manager_clock;

以下就是实验结果：

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

challenge部分不是必做部分，不过在正确最后会酌情加分。需写出有详细的设计、分析和测试的实验报告。完成出色的可获得适当加分。

参考答案分析

与参考答案思路几乎一致。

实验中涉及的知识点列举

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

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

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

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

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

心得和体会：

这次实验比起lab1和lab2实验，总体来说实验的内容更少了，但是所需要的知识却更加的深入了。了解到了页替换策略等等平时不会接触到的知识点，感觉很有收获。