清华大学操作系统Lab3实验报告
课程主页：http://os.cs.tsinghua.edu.cn/oscourse/OS2018spring
实验指导书：https://chyyuu.gitbooks.io/ucore_os_docs/content/
github：https://github.com/chyyuu/ucore_os_lab

实验目的

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

实验内容

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

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

在kern/mm/vmm.c中，（解释见注释）

//(1) try to find a pte, if pte's PT(Page Table) isn't existed, then create a 
//    PT.
    ptep = get_pte(mm -> pgdir, addr, 1);              
    if (*ptep == 0) {
//(2) if the phy addr isn't exist, then alloc a page & map the phy addr 
//    with logical addr
        pgdir_alloc_page(mm -> pgdir, addr, perm);

    }
    else { ... }

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

页目录项（Page Director Entry）：使用双向链表存储了目前所有的页的物理地址和逻辑地址的对应，即在物理内存中的所有页。替换算法中被换出的页从pgdir中选出。

页表（Page Table Entry）存储了替换算法中被换入的页的信息，替换后会将其映射到一物理地址。页表项中的dirty bit和访问位可以帮助实现一些页替换算法（比如extended clock）。

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

• 发生异常，将产生异常的地址保存在CR2寄存器中，同时还要将EFLAGS，CS，EIP，ErrorCode等保存在内核栈上。ErrorCode设为页访问异常的编码，即0xE
• CPU将页访问异常的中断服务例程的地址加载到CS和EIP中，并开始执行中断服务程序。
• OS：OS首先将寄存器保存在内核栈中，接下来按照trap--> trap_dispatch-->pgfault_handler-->do_pgfault的调用关系来执行中断服务程序。
• OS：在do_pgfault里，OS可以获得ErrorCode，并根据ErrorCode为页访问异常，OS将执行上面补充的代码段，并完成中断服务例程。

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

在kern/mm/vmm.c中，补全*ptep != 0分支后的内容。

        if(swap_init_ok) {
            struct Page *page=NULL;
            //swap_in(mm, addr, &page);           
//(1）According to the mm AND addr, try to load the content of right .
//    disk page into the memory which page managed.     
//(2) According to the mm, addr AND page, setup the map of phy addr. 
//    <---> logical addr   
            if (!swap_in(mm, addr, &page) && !page_insert(mm -> pgdir, page, addr, perm)) {
//(3) make the page swappable.
                swap_map_swappable(mm, addr, page, 0);
                page -> pra_vaddr = addr;
            }                       
        }
        else {
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }

在kern/mm/swap_fifo.c中，补全_fifo_map_swappable和_fifo_swap_out_victim两个函数。

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: 2015011346*/
    //(1)link the most recent arrival page at the back of the pra_list_head qeueue.
    list_add(head -> prev, entry);
    return 0;
}

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: 2015011346*/
     //(1)  unlink the  earliest arrival page in front of pra_list_head qeueue
     //(2)  set the addr of addr of this page to ptr_page
     list_entry_t *p = list_next(head);
     *ptr_page = le2page(p, pra_page_link);
     list_del(p);
     return 0;
}

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

设计方案见challenge部分的实现。用现有的swap_manager框架可以支持ucore实现extended clock页替换算法（用dirty bit作为该算法的访问标记）。

• 需要被换出的页的特征是什么？
  extended clock算法可以看成一种改进的LRU算法，它避免了LRU中在访问页或找替换页时必须对所有页进行扫描。因此被换出的页基本满足最久未被访问的特征。
• 在ucore中如何判断具有这样特征的页？
  指针扫描到的第一个dirty bit为0的页。
• 何时进行换入和换出操作？
  当需要调入的页不在页表中，且页表已满时，进行换入换出操作。

练习1、2测试结果

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

模仿kern/mm/swap_fifo.h和kern/mm/swap_fifo.c，写出针对extended clock算法的kern/mm/swap_clock.h和kern/mm/swap_clock.c。代码和解释如下：

#include <defs.h>
#include <x86.h>
#include <stdio.h>
#include <string.h>
#include <swap.h>
#include <swap_clock.h>
#include <list.h>

list_entry_t pra_list_head;

/*
 * (2) _clock_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 extend clock PRA
 */
static int
_clock_init_mm(struct mm_struct *mm)
{
     list_init(&pra_list_head);
     mm->sm_priv = &pra_list_head;
     //cprintf(" mm->sm_priv %x in clock_init_mm\n",mm->sm_priv);
     return 0;
}

/*
 * (3)_clock_map_swappable: 按照课件的说法，应该将换入页插入到被换出页的位置。
*    实际操作中，换入页的在链表中的位置并不影响，因此将其插入到链表最末端。
 */
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;
}
/*
 *  (4)_clock_swap_out_victim: 找到换出页，仿佛是指针沿链表扫描。
 *   如果扫描到的页dirty bit为1，则改为0；如果为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);
// 如果dirty bit为1，改为0
         if ((*pte & PTE_D) == 1) {
             *pte &= ~PTE_D;
         } else {
// 如果dirty bit为0，则标记为换出页
             *ptr_page = ptr;
             list_del(p);
             break;
         }
     }
     return 0;
}

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; }


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 clock算法，将swap.c中swap_init函数的

sm = &swap_manager_fifo;

改为

sm = &swap_manager_clock;

测试结果如下：

extended clock页替换算法

覆盖的知识点

• Page Fault异常处理
• 页面置换机制

与参考答案的区别

• 练习1：自己完成的。但是实现中没有加入对各种异常情况的处理（即goto fault），参考答案后补充上去了。
• 练习2：自己完成的，差别是我的链表按照插入时间从早到晚排列，而答案的链表按照插入时间由晚到早排列。在阅读答案后，发现找到链表最后一个元素并不需要遍历一边，而是通过哨兵的prev指针就能找到，这样能够加速插入过程，遂按照答案的方法改正。
• Challenge：自己完成。

总结

在经过了两个Lab的磕磕绊绊之后，终于意识到在开始实验之前应该认真观看Mooc并认真阅读实验指导书（特别是基本原理概述部分）。
虽然代码不到十行，却出现了三个bug。特别是最后一个，我发现lab1时的challenge实现已经不足以支持这次实验的页面替换了，所以一直在报一个奇怪的缺页错误。最后多亏多次make qemu了lab3_answer发现它没有输出set user mode才发现了这个这个问题。看来我对user mode和kernel mode的转换还缺乏了解。在发现无法借助Mooc的原理部分解决现有的问题后，我决定认真阅读一下Intel Manual来加深对操作系统的理解。