清華大學(xué)操作系統(tǒng)Lab2實(shí)驗(yàn)報(bào)告
課程主頁：http://os.cs.tsinghua.edu.cn/oscourse/OS2018spring
實(shí)驗(yàn)指導(dǎo)書：https://chyyuu.gitbooks.io/ucore_os_docs/content/
github：https://github.com/chyyuu/ucore_os_lab
實(shí)驗(yàn)?zāi)康?/h3>
- 理解基于段頁式內(nèi)存地址的轉(zhuǎn)換機(jī)制
- 理解頁表的建立和使用方法
- 理解物理內(nèi)存的管理方法
練習(xí)0：填寫已有實(shí)驗(yàn)
![]()
Eclipse的compare with工具
在Project Explorer中選取lab1和lab2目錄蒸健，右鍵選擇Compare With -> Each Other，得到如圖界面渣叛。隨后盯捌，按照需要將lab1中的代碼搬入lab2目錄。
練習(xí)1：實(shí)現(xiàn) first-fit 連續(xù)物理內(nèi)存分配算法
在kern/mm/default_pmm.c中箫攀，主要改動(dòng)了default_alloc_pages和default_free_pages兩個(gè)函數(shù)幼衰。注釋中說明了我的做法：
static struct Page *
default_alloc_pages(size_t n) {
assert(n > 0);
if (n > nr_free) {
return NULL;
}
struct Page *page = NULL;
list_entry_t *le = &free_list;
// Step1：找到第一個(gè)長度大于等于n的塊
while ((le = list_next(le)) != &free_list) {
struct Page *p = le2page(le, page_link);
if (p->property >= n) {
page = p;
break;
}
}
// Step2：如果可以找到長度大于等于n的塊渡嚣，則
// (1) 如果長度大于n，在從這個(gè)塊中取走長度為n的存儲空間识椰，并將剩下的存儲空間插入到列表中
// (2) 刪除原來的塊
if (page != NULL) {
if (page->property > n) {
struct Page *p = page + n;
p->property = page->property - n;
SetPageProperty(p);
list_add_after(&(page->page_link), &(p->page_link));
}
list_del(&(page->page_link));
nr_free -= n;
ClearPageProperty(page);
}
return page;
}
static void
default_free_pages(struct Page *base, size_t n) {
assert(n > 0);
struct Page *p = base;
// 原來的代碼腹鹉，檢查每個(gè)block中的各個(gè)page property是否合法
for (; p != base + n; p ++) {
assert(!PageReserved(p) && !PageProperty(p));
p->flags = 0;
set_page_ref(p, 0);
}
// 原來的代碼，設(shè)置好釋放空間的長度和page property
base->property = n;
SetPageProperty(base);
// Step1：找到插入鏈表的位置（鏈表已按照地址從大到小排序）
list_entry_t *le = list_next(&free_list);
list_entry_t *prev = &free_list;
while (le != &free_list) {
p = le2page(le, page_link);
if (base < p) {
break;
}
prev = le;
le = list_next(le);
}
// Step2：檢查是否可以和鏈表的前一項(xiàng)中的空間合并
p = le2page(prev, page_link);
if (prev != &free_list && p + p -> property == base) {
p -> property += base -> property;
ClearPageProperty(base);
} else {
list_add_after(prev, &(base -> page_link));
p = base;
}
// Step3：檢查是否可以和鏈表的后一項(xiàng)中的空間合并
struct Page *nextp = le2page(le, page_link);
if (le != &free_list && p + p -> property == nextp) {
p -> property += nextp -> property;
ClearPageProperty(nextp);
list_del(le);
}
nr_free += n;
}
你的first fit算法是否有進(jìn)一步的改進(jìn)空間
分析以上first fit算法的代碼，可以看到無論是alloc過程還是free過程都需要O(n)的復(fù)雜度航瞭。如果使用first fit算法坦辟，我認(rèn)為以上代碼效率低的主要原因在于使用雙向鏈表組織所有的block，這導(dǎo)致訪問必須耗費(fèi)線性時(shí)間滨彻。
如果使用樹狀結(jié)構(gòu)組織，如下圖所示休偶，alloc過程將變成DFS辜羊，復(fù)雜度依舊是O(n)，但是free過程在查找插入位置時(shí)可以二分查找碱妆，從而達(dá)到O(logn)的復(fù)雜度昔驱。
此外，first-fit算法還可以改成best-fit算法（適用于大部分分配的尺寸較小時(shí)）或worst-fit算法（適用于大部分分配的尺度適中時(shí)）朴艰。
練習(xí)2：實(shí)現(xiàn)尋找虛擬地址對應(yīng)的頁表項(xiàng)
//(1) find page directory entry
pde_t *pdep = pgdir + PDX(la);
//(2) check if entry is not present
if (!(*pdep & PTE_P)) {
//(3) check if creating is needed, then alloc page for page table
if (create) {
struct Page *page = alloc_page();
if (page != NULL) {
//(4) set page reference
set_page_ref(page, 1);
//(5) get linear address of page
pte_t page_la = KADDR(page2pa(page));
//(6) clear page content using memset
memset(page_la, 0, PGSIZE);
//(7) set page directory entry's permission
*pdep = page2pa(page) | PTE_P | PTE_W | PTE_U;
//(8) return page table entry
return ((pte_t *)(KADDR(PDE_ADDR(*pdep)))) + PTX(la);
} else {
return NULL;
}
} else {
return NULL;
}
}
//(8) return page table entry
return ((pte_t *)(KADDR(PDE_ADDR(*pdep)))) + PTX(la);
請描述頁目錄項(xiàng)（ Page Director Entry） 和頁表（ Page Table Entry） 中每個(gè)組成部分的含義和以及對ucore而言的潛在用處混移。
頁目錄項(xiàng)包括一些幾部分：
| 名稱 | 地址 | ucore中的對應(yīng) |
|---|---|---|
| Page Table 4KB Aligned Address | 31 downto 12 | 對應(yīng)的頁表地址 |
| Avail | 11 downto 9 | PTE_AVAIL |
| Ignored | 8 | |
| Page Size | 7 | PTE_PS |
| 0 | 6 | PTE_MBZ |
| Accessed | 5 | PTE_A |
| Cache Disabled | 4 | PTE_PCD |
| Write Through | 3 | PTE_PWT |
| User/Supervisor | 2 | PTE_U |
| Read/Write | 1 | PTE_W |
| Present | 0 | PTE_P |
頁表項(xiàng)包括一些幾部分：
| 名稱 | 地址 | ucore中的對應(yīng) |
|---|---|---|
| Physical Page Address | 31 downto 12 | 對應(yīng)的物理地址高20位 |
| Avail | 11 downto 9 | PTE_AVAIL |
| Global | 8 | |
| 0 | 7 | PTE_MBZ |
| Dirty | 6 | PTE_D |
| Accessed | 5 | PTE_A |
| Cache Disabled | 4 | PTE_PCD |
| Write Through | 3 | PTE_PWT |
| User/Supervisor | 2 | PTE_U |
| Read/Write | 1 | PTE_W |
| Present | 0 | PTE_P |
如果ucore執(zhí)行過程中訪問內(nèi)存毁嗦，出現(xiàn)了頁訪問異常回铛，請問硬件要做哪些事情？
- 將引發(fā)頁訪問異常的地址將被保存在cr2寄存器中
- 設(shè)置錯(cuò)誤代碼
- 引發(fā)Page Fault
練習(xí)3：釋放某虛地址所在的頁并取消對應(yīng)二級頁表項(xiàng)的映射
//(1) check if this page table entry is present
if (*ptep & PTE_P) {
//(2) find corresponding page to pte
struct Page *page = pte2page(*ptep);
//(3) decrease page reference
page_ref_dec(page);
//(4) and free this page when page reference reachs 0
if (page -> ref == 0) {
free_page(page);
}
//(5) clear second page table entry
*ptep = 0;
//(6) flush tlb
tlb_invalidate(pgdir, la);
}
數(shù)據(jù)結(jié)構(gòu)Page的全局變量（ 其實(shí)是一個(gè)數(shù)組） 的每一項(xiàng)與頁表中的頁目錄項(xiàng)和頁表項(xiàng)有無對應(yīng)關(guān)系腔长？如果有验残，其對應(yīng)關(guān)系是啥？
有關(guān)系鸟召。頁目錄項(xiàng)保存的物理頁面地址（即某個(gè)頁表）以及頁表項(xiàng)保存的物理頁面地址都對應(yīng)于Page數(shù)組中的某一頁。
如果希望虛擬地址與物理地址相等欧募，則需要如何修改lab2槽片，完成此事？ 鼓勵(lì)通過編程來具體完成這個(gè)問題
由于在lab1中是對等映射關(guān)系还栓，即
virtual address = linear address = physical address
可以考慮將lab2中的和段頁式映射有關(guān)的代碼恢復(fù)到lab1狀態(tài)。
參考實(shí)驗(yàn)指導(dǎo)書中“系統(tǒng)執(zhí)行中地址映射的四個(gè)階段”一節(jié)谷婆，逐階段修改辽聊。
- 更改鏈接腳本tools/kernel.ld，將虛擬地址改為0x100000：
SECTIONS { /* Load the kernel at this address: "." means the current address */ . = 0x0100000; - 把kernel基地址改回0：
/* All physical memory mapped at this address */ #define KERNBASE 0x00000000 - 注釋掉取消0~4M區(qū)域內(nèi)存頁映射的代碼
//disable the map of virtual_addr 0~4M // boot_pgdir[0] = 0;
覆蓋的知識點(diǎn)
- 內(nèi)存分配
- 二級頁表的創(chuàng)建
未覆蓋的知識點(diǎn)
- 段表的相關(guān)內(nèi)容
與參考答案的區(qū)別
- 練習(xí)1：自己完成异袄。
- 練習(xí)2：寫完后未能自己調(diào)出bug烤蜕，后參考了答案中的實(shí)現(xiàn)迹冤。
- 練習(xí)3：自己完成。
總結(jié)
在完成本實(shí)驗(yàn)代碼部分時(shí)泡徙，由于各個(gè)練習(xí)需要填寫的代碼處有完整的指導(dǎo)堪藐，因此實(shí)現(xiàn)的時(shí)候并不困難。但是在回答思考題的時(shí)候礁竞，發(fā)現(xiàn)對OS的理解還遠(yuǎn)遠(yuǎn)不夠。
最大的困難在于理解練習(xí)2中給頁中內(nèi)容清0時(shí)，memset的參數(shù)填寫的是線性地址而非物理地址枫绅。之后查看同學(xué)討論后，有同學(xué)表示是因?yàn)榇颂幰呀?jīng)開啟了頁表并淋，因此這里硬件會(huì)完成線性地址到物理地址的轉(zhuǎn)換。不過目前來看句喷，雖然完成了相應(yīng)的實(shí)驗(yàn)內(nèi)容兔毙，但是對于OS啟動(dòng)時(shí)頁表相關(guān)操作的理解還不夠。在實(shí)驗(yàn)解釋后锡溯，我還需要閱讀Intel Manual等資料進(jìn)一步了解x86中的段表頁表哑姚。
