清華大學(xué)操作系統(tǒng)Lab3實(shí)驗(yàn)報(bào)告
課程主頁(yè)：http://os.cs.tsinghua.edu.cn/oscourse/OS2018spring
實(shí)驗(yàn)指導(dǎo)書(shū)：https://chyyuu.gitbooks.io/ucore_os_docs/content/
github：https://github.com/chyyuu/ucore_os_lab

實(shí)驗(yàn)?zāi)康?/h3>

• 了解虛擬內(nèi)存的Page Fault異常處理實(shí)現(xiàn)
• 了解頁(yè)替換算法在操作系統(tǒng)中的實(shí)現(xiàn)

實(shí)驗(yàn)內(nèi)容

本次實(shí)驗(yàn)是在實(shí)驗(yàn)二的基礎(chǔ)上，借助于頁(yè)表機(jī)制和實(shí)驗(yàn)一中涉及的中斷異常處理機(jī)制，完成Page Fault異常處理和FIFO頁(yè)替換算法的實(shí)現(xiàn)，結(jié)合磁盤(pán)提供的緩存空間，從而能夠支持虛存管理，提供一個(gè)比實(shí)際物理內(nèi)存空間“更大”的虛擬內(nèi)存空間給系統(tǒng)使用。這個(gè)實(shí)驗(yàn)與實(shí)際操作系統(tǒng)中的實(shí)現(xiàn)比較起來(lái)要簡(jiǎn)單，不過(guò)需要了解實(shí)驗(yàn)一和實(shí)驗(yàn)二的具體實(shí)現(xiàn)。實(shí)際操作系統(tǒng)系統(tǒng)中的虛擬內(nèi)存管理設(shè)計(jì)與實(shí)現(xiàn)是相當(dāng)復(fù)雜的，涉及到與進(jìn)程管理系統(tǒng)、文件系統(tǒng)等的交叉訪問(wèn)。

練習(xí)1：給未被映射的地址映射上物理頁(yè)

在kern/mm/vmm.c中，（解釋見(jiàn)注釋）

//(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 { ... }

請(qǐng)描述頁(yè)目錄項(xiàng)（Page Director Entry）和頁(yè)表（Page Table Entry）中組成部分對(duì)ucore實(shí)現(xiàn)頁(yè)替換算法的潛在用處。

頁(yè)目錄項(xiàng)（Page Director Entry）：使用雙向鏈表存儲(chǔ)了目前所有的頁(yè)的物理地址和邏輯地址的對(duì)應(yīng)，即在物理內(nèi)存中的所有頁(yè)。替換算法中被換出的頁(yè)從pgdir中選出。

頁(yè)表（Page Table Entry）存儲(chǔ)了替換算法中被換入的頁(yè)的信息，替換后會(huì)將其映射到一物理地址。頁(yè)表項(xiàng)中的dirty bit和訪問(wèn)位可以幫助實(shí)現(xiàn)一些頁(yè)替換算法（比如extended clock）。

如果ucore的缺頁(yè)服務(wù)例程在執(zhí)行過(guò)程中訪問(wèn)內(nèi)存，出現(xiàn)了頁(yè)訪問(wèn)異常，請(qǐng)問(wèn)硬件要做哪些事情？

• 發(fā)生異常，將產(chǎn)生異常的地址保存在CR2寄存器中，同時(shí)還要將EFLAGS，CS，EIP，ErrorCode等保存在內(nèi)核棧上。ErrorCode設(shè)為頁(yè)訪問(wèn)異常的編碼，即0xE
• CPU將頁(yè)訪問(wèn)異常的中斷服務(wù)例程的地址加載到CS和EIP中，并開(kāi)始執(zhí)行中斷服務(wù)程序。
• OS：OS首先將寄存器保存在內(nèi)核棧中，接下來(lái)按照trap--> trap_dispatch-->pgfault_handler-->do_pgfault的調(diào)用關(guān)系來(lái)執(zhí)行中斷服務(wù)程序。
• OS：在do_pgfault里，OS可以獲得ErrorCode，并根據(jù)ErrorCode為頁(yè)訪問(wèn)異常，OS將執(zhí)行上面補(bǔ)充的代碼段，并完成中斷服務(wù)例程。

練習(xí)2：補(bǔ)充完成基于FIFO的頁(yè)面替換算法

在kern/mm/vmm.c中，補(bǔ)全*ptep != 0分支后的內(nèi)容。

        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中，補(bǔ)全_fifo_map_swappable和_fifo_swap_out_victim兩個(gè)函數(shù)。

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上實(shí)現(xiàn)"extended clock頁(yè)替換算法"請(qǐng)給你的設(shè)計(jì)方案，現(xiàn)有的swap_manager框架是否足以支持在ucore中實(shí)現(xiàn)此算法？如果是，請(qǐng)給你的設(shè)計(jì)方案。如果不是，請(qǐng)給出你的新的擴(kuò)展和基此擴(kuò)展的設(shè)計(jì)方案。并需要回答如下問(wèn)題

設(shè)計(jì)方案見(jiàn)challenge部分的實(shí)現(xiàn)。用現(xiàn)有的swap_manager框架可以支持ucore實(shí)現(xiàn)extended clock頁(yè)替換算法（用dirty bit作為該算法的訪問(wèn)標(biāo)記）。

• 需要被換出的頁(yè)的特征是什么？
  extended clock算法可以看成一種改進(jìn)的LRU算法，它避免了LRU中在訪問(wèn)頁(yè)或找替換頁(yè)時(shí)必須對(duì)所有頁(yè)進(jìn)行掃描。因此被換出的頁(yè)基本滿足最久未被訪問(wèn)的特征。
• 在ucore中如何判斷具有這樣特征的頁(yè)？
  指針掃描到的第一個(gè)dirty bit為0的頁(yè)。
• 何時(shí)進(jìn)行換入和換出操作？
  當(dāng)需要調(diào)入的頁(yè)不在頁(yè)表中，且頁(yè)表已滿時(shí)，進(jìn)行換入換出操作。

練習(xí)1、2測(cè)試結(jié)果

擴(kuò)展練習(xí) Challenge：實(shí)現(xiàn)識(shí)別dirty bit的 extended clock頁(yè)替換算法

模仿kern/mm/swap_fifo.h和kern/mm/swap_fifo.c，寫(xiě)出針對(duì)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: 按照課件的說(shuō)法，應(yīng)該將換入頁(yè)插入到被換出頁(yè)的位置。
*    實(shí)際操作中，換入頁(yè)的在鏈表中的位置并不影響，因此將其插入到鏈表最末端。
 */
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);
// 將新頁(yè)插入到鏈表最后
    list_add(head -> prev, entry);
// 新插入的頁(yè)dirty bit標(biāo)記為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: 找到換出頁(yè)，仿佛是指針沿鏈表掃描。
 *   如果掃描到的頁(yè)dirty bit為1，則改為0；如果為0，則標(biāo)記為換出頁(yè)。
 */
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，則標(biāo)記為換出頁(yè)
             *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函數(shù)的

sm = &swap_manager_fifo;

改為

sm = &swap_manager_clock;

測(cè)試結(jié)果如下：

extended clock頁(yè)替換算法

覆蓋的知識(shí)點(diǎn)

• Page Fault異常處理
• 頁(yè)面置換機(jī)制

與參考答案的區(qū)別

• 練習(xí)1：自己完成的。但是實(shí)現(xiàn)中沒(méi)有加入對(duì)各種異常情況的處理（即goto fault），參考答案后補(bǔ)充上去了。
• 練習(xí)2：自己完成的，差別是我的鏈表按照插入時(shí)間從早到晚排列，而答案的鏈表按照插入時(shí)間由晚到早排列。在閱讀答案后，發(fā)現(xiàn)找到鏈表最后一個(gè)元素并不需要遍歷一邊，而是通過(guò)哨兵的prev指針就能找到，這樣能夠加速插入過(guò)程，遂按照答案的方法改正。
• Challenge：自己完成。

總結(jié)

在經(jīng)過(guò)了兩個(gè)Lab的磕磕絆絆之后，終于意識(shí)到在開(kāi)始實(shí)驗(yàn)之前應(yīng)該認(rèn)真觀看Mooc并認(rèn)真閱讀實(shí)驗(yàn)指導(dǎo)書(shū)（特別是基本原理概述部分）。
雖然代碼不到十行，卻出現(xiàn)了三個(gè)bug。特別是最后一個(gè)，我發(fā)現(xiàn)lab1時(shí)的challenge實(shí)現(xiàn)已經(jīng)不足以支持這次實(shí)驗(yàn)的頁(yè)面替換了，所以一直在報(bào)一個(gè)奇怪的缺頁(yè)錯(cuò)誤。最后多虧多次make qemu了lab3_answer發(fā)現(xiàn)它沒(méi)有輸出set user mode才發(fā)現(xiàn)了這個(gè)這個(gè)問(wèn)題。看來(lái)我對(duì)user mode和kernel mode的轉(zhuǎn)換還缺乏了解。在發(fā)現(xiàn)無(wú)法借助Mooc的原理部分解決現(xiàn)有的問(wèn)題后，我決定認(rèn)真閱讀一下Intel Manual來(lái)加深對(duì)操作系統(tǒng)的理解。