實(shí)驗(yàn)三：虛擬內(nèi)存管理

• 專業(yè)班級(jí)：
• 學(xué)號(hào)：
• 姓名：
• 上課老師：

一跛溉、實(shí)驗(yàn)?zāi)康?/h2>

1.了解虛擬內(nèi)存的Page Fault異常處理實(shí)現(xiàn)
2.了解頁(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)侨核。如果大家有余力草穆，可以嘗試完成擴(kuò)展練習(xí)，實(shí)現(xiàn)extended clock頁(yè)替換法搓译。

三悲柱、實(shí)驗(yàn)步驟

練習(xí)0：填寫(xiě)已有實(shí)驗(yàn)

練習(xí)1：給末被映射的地址映射上物理頁(yè)（需要編程）

完成do_pgfault（mm/vmm.c）函數(shù)，給未被映射的地址映射上物理頁(yè)侥衬。設(shè)置訪問(wèn)權(quán)限的時(shí)候需要參考頁(yè)面所在 VMA 的權(quán)限诗祸，同時(shí)需要注意映射物理頁(yè)時(shí)需要操作內(nèi)存控制結(jié)構(gòu)所指定的頁(yè)表，而不是內(nèi)核的頁(yè)表轴总。注意：在LAB2 EXERCISE 1處填寫(xiě)代碼直颅。執(zhí)行

make qemu

后，如果通過(guò)check_pgfault函數(shù)的測(cè)試后怀樟，會(huì)有“check_pgfault() succeeded!”的輸出功偿，表示練習(xí)1基本正確。

請(qǐng)?jiān)趯?shí)驗(yàn)報(bào)告中簡(jiǎn)要說(shuō)明你的設(shè)計(jì)實(shí)現(xiàn)過(guò)程。請(qǐng)回答如下問(wèn)題：

• 請(qǐng)描述頁(yè)目錄項(xiàng)（Pag Director Entry）和頁(yè)表（Page Table Entry）中組成部分對(duì)ucore實(shí)現(xiàn)頁(yè)替換算法的潛在用處械荷。
• 如果ucore的缺頁(yè)服務(wù)例程在執(zhí)行過(guò)程中訪問(wèn)內(nèi)存共耍，出現(xiàn)了頁(yè)訪問(wèn)異常，請(qǐng)問(wèn)硬件要做哪些事情吨瞎？

解析

lab3的總體執(zhí)行流程如下:

• 首先是初始化過(guò)程痹兜。參考ucore總控函數(shù)init的代碼，可以看到在調(diào)用完成虛擬內(nèi)存初始化的vmm_init函數(shù)之前颤诀，需要首先調(diào)用pmm_init函數(shù)完成物理內(nèi)存的管理字旭，這也是我們lab2已經(jīng)完成的內(nèi)容。
• 接著是執(zhí)行中斷和異常相關(guān)的初始化工作崖叫，即調(diào)用pic_init函數(shù)和idt_init函數(shù)等遗淳，這些工作與lab1的中斷異常初始化工作的內(nèi)容是相同的。
• 在調(diào)用完idt_init函數(shù)之后心傀，將進(jìn)一步調(diào)用三個(gè)lab3中才有的新函數(shù)vmm_init屈暗、ide_init和swap_init。這三個(gè)函數(shù)設(shè)計(jì)了本次實(shí)驗(yàn)中的兩個(gè)練習(xí)脂男。第一個(gè)函數(shù)vmm_init是檢查我們的練習(xí)1是否正確實(shí)現(xiàn)了养叛。為了表述不在物理內(nèi)存中的“合法”虛擬頁(yè)，需要有數(shù)據(jù)結(jié)構(gòu)來(lái)描述這樣的頁(yè)宰翅，為此ucore建立了mm_struct和vma_struct數(shù)據(jù)結(jié)構(gòu)（接下來(lái)的小節(jié)中有進(jìn)一步詳細(xì)描述）一铅，假定我們已經(jīng)描述好了這樣的“合法”虛擬頁(yè)，當(dāng)ucore訪問(wèn)這些“合法”虛擬頁(yè)時(shí)堕油，會(huì)由于沒(méi)有虛實(shí)地址映射而產(chǎn)生頁(yè)訪問(wèn)異常。

do_pgfault函數(shù)會(huì)申請(qǐng)一個(gè)空閑物理頁(yè)肮之，并建立好虛實(shí)映射關(guān)系掉缺，從而使得這樣的“合法”虛擬頁(yè)有實(shí)際的物理頁(yè)幀對(duì)應(yīng)。

但page_fault函數(shù)不知道哪些是“合法”的虛擬頁(yè)戈擒，原因是ucore還缺少一定的數(shù)據(jù)結(jié)構(gòu)來(lái)描述這種不在物理內(nèi)存中的“合法”虛擬頁(yè)眶明。為此ucore通過(guò)建立mm_struct和vma_struct數(shù)據(jù)結(jié)構(gòu)，描述了ucore模擬應(yīng)用程序運(yùn)行所需的合法內(nèi)存空間筐高。

vma_struct的定義如下：

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

• vm_mm是一個(gè)指針搜囱，指向一個(gè)比vma_struct更高的抽象層次的數(shù)據(jù)結(jié)構(gòu)mm_struct
• vm_start和vm_end描述的是一個(gè)合理的地址空間范圍（即嚴(yán)格確保 vm_start < vm_end的關(guān)系）；
• list_link是一個(gè)雙向鏈表柑土，按照從小到大的順序把一系列用vma_struct表示的虛擬內(nèi)存空間鏈接起來(lái)蜀肘，并且還要求這些鏈起來(lái)的vma_struct應(yīng)該是不相交的，即vma之間的地址空間無(wú)交集稽屏；
• vm_flags表示了這個(gè)虛擬內(nèi)存空間的屬性扮宠，目前的屬性包括

#define VM_READ 0x00000001 //只讀
#define VM_WRITE 0x00000002 //可讀寫(xiě)
#define VM_EXEC 0x00000004 //可執(zhí)行

mm_struct的定義如下：

struct mm_struct{
    list_entry_t mmap_list;        // linear list link which sorted by start addr of vma
    struct vma_struct *mmap_cache; // current accessed vma, used for speed purpose
    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是雙向鏈表頭，鏈接了所有屬于同一頁(yè)目錄表的虛擬內(nèi)存空間狐榔，
• mmap_cache是指向當(dāng)前正在使用的虛擬內(nèi)存空間坛增，由于操作系統(tǒng)執(zhí)行的“局部性”原理获雕，當(dāng)前正在用到的虛擬內(nèi)存空間在接下來(lái)的操作中可能還會(huì)用到，這時(shí)就不需要查鏈表收捣，而是直接使用此指針就可找到下一次要用到的虛擬內(nèi)存空間届案。由于mmap_cache 的引入，可使得 mm_struct 數(shù)據(jù)結(jié)構(gòu)的查詢加速 30% 以上罢艾。
• pgdir所指向的就是 mm_struct數(shù)據(jù)結(jié)構(gòu)所維護(hù)的頁(yè)表楣颠。通過(guò)訪問(wèn)pgdir可以查找某虛擬地址對(duì)應(yīng)的頁(yè)表項(xiàng)是否存在以及頁(yè)表項(xiàng)的屬性等。

• map_count記錄mmap_list 里面鏈接的 vma_struct的個(gè)數(shù)昆婿。
• sm_priv指向用來(lái)鏈接記錄頁(yè)訪問(wèn)情況的鏈表頭球碉，這建立了mm_struct和后續(xù)要講到的swap_manager之間的聯(lián)系。

當(dāng)啟動(dòng)分頁(yè)機(jī)制以后仓蛆，如果一條指令或數(shù)據(jù)的虛擬地址所對(duì)應(yīng)的物理頁(yè)框不在內(nèi)存中或者訪問(wèn)的類型有錯(cuò)誤（比如寫(xiě)一個(gè)只讀頁(yè)或用戶態(tài)程序訪問(wèn)內(nèi)核態(tài)的數(shù)據(jù)等）睁冬，就會(huì)發(fā)生頁(yè)錯(cuò)誤異常。產(chǎn)生頁(yè)面異常的原因主要有:

• 目標(biāo)頁(yè)面不存在（頁(yè)表項(xiàng)全為0看疙，即該線性地址與物理地址尚未建立映射或者已經(jīng)撤銷）;
• 相應(yīng)的物理頁(yè)面不在內(nèi)存中（頁(yè)表項(xiàng)非空豆拨，但Present標(biāo)志位=0，比如在swap分區(qū)或磁盤(pán)文件上）
• 訪問(wèn)權(quán)限不符合（此時(shí)頁(yè)表項(xiàng)P標(biāo)志=1能庆，比如企圖寫(xiě)只讀頁(yè)面）.
  當(dāng)出現(xiàn)上面情況之一,那么就會(huì)產(chǎn)生頁(yè)面page fault(#PF)異常施禾。

產(chǎn)生頁(yè)訪問(wèn)異常后，CPU把引起頁(yè)訪問(wèn)異常的線性地址裝到寄存器CR2中搁胆，并給出了出錯(cuò)碼errorCode弥搞，說(shuō)明了頁(yè)訪問(wèn)異常的類型。ucore OS會(huì)把這個(gè)值保存在struct trapframe 中tf_err成員變量中渠旁。而中斷服務(wù)例程會(huì)調(diào)用頁(yè)訪問(wèn)異常處理函數(shù)do_pgfault進(jìn)行具體處理攀例。這里的頁(yè)訪問(wèn)異常處理是實(shí)現(xiàn)按需分頁(yè)、頁(yè)換入換出機(jī)制的關(guān)鍵之處顾腊。

ucore中do_pgfault函數(shù)是完成頁(yè)訪問(wèn)異常處理的主要函數(shù)粤铭，它根據(jù)從CPU的控制寄存器CR2中獲取的頁(yè)訪問(wèn)異常的物理地址以及根據(jù)errorCode的錯(cuò)誤類型來(lái)查找此地址是否在某個(gè)VMA的地址范圍內(nèi)以及是否滿足正確的讀寫(xiě)權(quán)限，如果在此范圍內(nèi)并且權(quán)限也正確杂靶，這認(rèn)為這是一次合法訪問(wèn)梆惯，但沒(méi)有建立虛實(shí)對(duì)應(yīng)關(guān)系。所以需要

分配一個(gè)空閑的內(nèi)存頁(yè)吗垮，并修改頁(yè)表完成虛地址到物理地址的映射垛吗，刷新TLB，然后調(diào)用iret中斷烁登，返回到產(chǎn)生頁(yè)訪問(wèn)異常的指令處重新執(zhí)行此指令职烧。

如果該虛地址不在某VMA范圍內(nèi)，則認(rèn)為是一次非法訪問(wèn)。

do_pgfault部分具體實(shí)現(xiàn)如下：

// try to find a pte, if pte's PT(Page Table) isn't existed, then create a PT.
if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
    cprintf("get_pte in do_pgfault failed\n");//如果找不到入口蚀之，是非法訪問(wèn)蝗敢，退出
    goto failed;
}
// if the phy addr isn't exist, then alloc a page & map the phy addr with logical addr
if (*ptep == 0) { 
    if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
        cprintf("pgdir_alloc_page in do_pgfault failed\n");
        //嘗試申請(qǐng)一個(gè)頁(yè)，如果申請(qǐng)失敗足删，就是內(nèi)存不足了寿谴，退出
        goto failed;
    }
}

練習(xí)2：補(bǔ)充完成基于FIFO的頁(yè)面置換算法（需要編程）

完成vmm.c中的do_pgfault函數(shù)，并且在實(shí)現(xiàn)FIFO算法的swap_fifo.c中完成map_swappable swap_out_vistim函數(shù)失受。通過(guò)對(duì)swap的測(cè)試讶泰。注意：在LAB2 EXERCISE 2處填寫(xiě)代碼。執(zhí)行

make qemu

后拂到，如果通過(guò)check_swap函數(shù)的測(cè)試后痪署，會(huì)有“check_swap() succeeded!”的輸出，表示練習(xí)2基本正確兄旬。
請(qǐng)?jiān)趯?shí)驗(yàn)報(bào)告中簡(jiǎn)要說(shuō)明你的設(shè)計(jì)實(shí)現(xiàn)過(guò)程狼犯。

請(qǐng)?jiān)趯?shí)驗(yàn)報(bào)告中回答如下問(wèn)題：

• 如果要在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)題:
  1. 需要被換出的頁(yè)的特征是什么？
  2. 在ucore中如何判斷具有這樣特征的頁(yè)音诈？
  3. 何時(shí)進(jìn)行換入和換出操作幻碱？

解析

當(dāng)應(yīng)用程序訪問(wèn)它認(rèn)為應(yīng)該在內(nèi)存中的的數(shù)據(jù)或代碼時(shí)，如果這些數(shù)據(jù)或代碼不在內(nèi)存中细溅，則根據(jù)上一小節(jié)的介紹收班，會(huì)產(chǎn)生頁(yè)訪問(wèn)異常。這時(shí)谒兄，操作系統(tǒng)必須能夠應(yīng)對(duì)這種頁(yè)訪問(wèn)異常，即盡快把應(yīng)用程序當(dāng)前需要的數(shù)據(jù)或代碼放到內(nèi)存中來(lái)社付，然后重新執(zhí)行應(yīng)用程序產(chǎn)生異常的訪存指令承疲。(換入）

如果在把硬盤(pán)中對(duì)應(yīng)的數(shù)據(jù)或代碼調(diào)入內(nèi)存前，操作系統(tǒng)發(fā)現(xiàn)物理內(nèi)存已經(jīng)沒(méi)有空閑空間了鸥咖，這時(shí)操作系統(tǒng)必須把它認(rèn)為“不常用”的頁(yè)換出到磁盤(pán)上去燕鸽，以騰出內(nèi)存空閑空間給應(yīng)用程序所需的數(shù)據(jù)或代碼。（換出）

頁(yè)面替換主要分為兩個(gè)方面啼辣，頁(yè)面換出和頁(yè)面換入啊研。
頁(yè)面換入主要在vmm.c中的do_pgfault()函數(shù)實(shí)現(xiàn)；頁(yè)面換出主要在swap_fifo.c中的swap_out_vistim()函數(shù)實(shí)現(xiàn)。

• 在換入時(shí)党远，需要先檢查產(chǎn)生訪問(wèn)異常的地址是否屬于某個(gè)vma表示的合法虛擬地址削解，并且保存在硬盤(pán)的swap文件中（對(duì)應(yīng)的PTE的高24位不為0）。如果滿足以上兩點(diǎn)沟娱，則執(zhí)行swap_in()函數(shù)換入頁(yè)面氛驮。
• 換出則相對(duì)簡(jiǎn)單，當(dāng)申請(qǐng)空閑頁(yè)面時(shí)济似，alloc_pages()函數(shù)不能獲得空閑頁(yè)矫废，則需要調(diào)用swap_out()函數(shù)換出不常用的頁(yè)面。

換入

else {//頁(yè)表項(xiàng)非空砰蠢，可以嘗試換入頁(yè)面          
    if(swap_init_ok) {
        struct Page *page=NULL;
        //根據(jù)mm結(jié)構(gòu)和addr地址蓖扑，嘗試將硬盤(pán)中的內(nèi)容換入至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);//建立虛擬地址和物理地址之間的對(duì)應(yīng)關(guān)系
        swap_map_swappable(mm, addr, page, 1);//將此頁(yè)面設(shè)置為可交換的
        page->pra_vaddr = addr;
    }
    else {
        cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
        goto failed;
    }
}

換出

FIFO替換算法會(huì)維護(hù)一個(gè)隊(duì)列，隊(duì)列按照頁(yè)面調(diào)用的次序排列台舱，越早被加載到內(nèi)存的頁(yè)面會(huì)越早被換出律杠。
具體實(shí)現(xiàn)的函數(shù)如下：
首先是_fifo_map_swappable()，它的主要作用是將最近被用到的頁(yè)面添加到算法所維護(hù)的次序隊(duì)列柿赊。

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);   
    list_add(head, entry); //將最近用到的頁(yè)面添加到次序隊(duì)尾  
    return 0;   
} 

然后是_fifo_swap_out_victim()函數(shù)是用來(lái)查詢哪個(gè)頁(yè)面需要被換出俩功，它的主要作用是用來(lái)查詢哪個(gè)頁(yè)面需要被換出。

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指示需要被換出的頁(yè)             
    assert(head!=le);  
    struct Page *p = le2page(le, pra_page_link);//le2page宏可以根據(jù)鏈表元素獲得對(duì)應(yīng)的Page指針p      
    list_del(le);      //將進(jìn)來(lái)最早的頁(yè)面從隊(duì)列中刪除      
    assert(p !=NULL);       
    *ptr_page = p; //將這一頁(yè)的地址存儲(chǔ)在ptr_page中
    return 0; 
}

實(shí)驗(yàn)結(jié)果

擴(kuò)展練習(xí)

實(shí)驗(yàn)總結(jié)

經(jīng)過(guò)本次試驗(yàn)碰声，明白了頁(yè)面置換诡蜓。
可以說(shuō)非常有用了。