Lab3 report

练习0：填写已有实验

手动合并：修改lab3\kern\debug\kdebug.c、lab3\kern\trap\trap.c、lab3\kern\mm\pmm.c以及lab3\kern\mm\default_pmm.c文件即可。

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

实验思路

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

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

当出现上面情况之一，那么就会产生页面page fault异常。产生异常的线性地址存储在CR2中，并且将page fault的产生类型保存在 error code 中。
那么do_pgfault()函数的作用就是：
从CR2寄存器中获取页错误异常的虚拟地址，根据error code来查找这个虚拟地址是否在某一个VMA的地址范围内，并且具有正确的权限。如果满足以上条件，那么就给它分配一个物理页。

实验过程

do_pgfault()函数：

int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    ......
    //尝试找到pte，如果对应的页表项不存在则创建一个
    //找不到入口，非法访问，退出
     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; 
        }
    }
    ......
}

思考题

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

页目录项（Pag Director Entry）作为一个双向链表存储了目前所有的页的物理地址和逻辑地址的对应，即在实内存中的所有页。替换算法中被换出的页从pgdir中选出。
页表（Page Table Entry）存储了替换算法中被换入的页的信息，替换后会将其映射到一物理地址。

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

产生页访问异常后，CPU把引起页访问异常的线性地址装到寄存器CR2中，并给出了出错码error Code，说明了页访问异常的类型。ucore OS会把这个值保存在struct trapframe 中tf_err成员变量中。而中断服务例程会调用页访问异常处理函数do_pgfault进行具体处理。

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

实验思路

页错误异常发生时，有可能是因为页面保存在swap区或者磁盘文件造成的，所以我们需要通过页面分配解决这个问题。
页面替换主要分为两个方面，页面换出和页面换入。

1. 页面换入在vmm.c的do_pgfault()函数实现；
2. 页面换出在swap_fifo.c的_fifo_map_swappable()和_fifo_swap_out_victim()函数实现。

在换入时，需要先检查产生访问异常的地址是否属于某个VMA表示的合法虚 拟地址，并且保存在硬盘的swap文件中（对应的PTE的高24位不为0）。如果满足以上两点，则执行swap_in() 函数换入页面。
换出则相对简单，当申请空闲页面时，alloc_pages()函数不能获得空闲页，则需要调用swap_out()函数换出不常用的页面。

实现过程

do_pgfault()函数：

int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    ......
    else {
        //如果pte是需要交换的表项，那么就从硬盘的物理地址将数据读到页中然后调用page_insert()建立物理地址和逻辑地址映射
        if(swap_init_ok) {
            struct Page *page=NULL;
            //换页失败，退出
            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;
}

_fifo_map_swappable()函数：

static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
    ......
    //将最近分配的页插入到队列的尾部
    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)
{
    ......
    //选择应该被换出的页表，即FIFO中最早调入的页表
    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
    *ptr_page = p;
     return 0;
}

思考题

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

现有的swap_manager框架可以支持在ucore中实现"extended clock页替换算法"。

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

在FIFO中，需要被换出的页是目前所有页中最早被调入的那一页。

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

需要被换出的页位于队列的前端，即mm->sm_priv->next指示的那一页。

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

当需要调用的页不在页表中时，并且页表已满，这时候需要进行换入和换出操作。