操作系統(tǒng)第一次實驗報告.docx

操作系統(tǒng)課程實驗報告題目： Lab 2 學(xué)生姓名： 王家威 學(xué)生學(xué)號： 201308070217 專業(yè)班級： 智能 1302 指導(dǎo)老師： 李蕊 完成日期：2015年12月24日一、 實驗內(nèi)容1、 實現(xiàn)first_fit連續(xù)物理內(nèi)存分配算法2、 實現(xiàn)尋找虛擬地址對應(yīng)頁表項3、 釋放某虛地址所在頁并取消對應(yīng)二級頁表的映射二、 實驗原理1、 首次適配算法指存儲管理器，沿著段鏈表進行搜索直到找到一個足夠大的空閑區(qū)域。如果空閑區(qū)域和進程所需要的區(qū)域剛好相等那么剛好，如果大則將該區(qū)域分為兩部分，一部分供進程使用，另一部分成為新的空閑區(qū)域。首次適配算法很快因為它減少了搜索的次數(shù)，只要搜索到就分配。2、 在改寫代碼前，需要弄清楚描述物理頁的數(shù)據(jù)結(jié)構(gòu)，雙向鏈表以及管理物理頁的數(shù)據(jù)結(jié)構(gòu)Page。（1） 雙向鏈表結(jié)構(gòu)用來表示每個頁幀，鏈表頭用free_area_t結(jié)構(gòu)體表示，包含了一個list_entry的雙向鏈表指針和紀錄當前空閑頁的個數(shù)的無符號整型變量nr_free。typedef struct list_entry_t free_list; / the list headerunsigned int nr_free; / # of free pages in this free list free_area_t;（2） Page結(jié)構(gòu)體是實現(xiàn)連續(xù)物理內(nèi)存分配算法的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，可通過此數(shù)據(jù)結(jié)構(gòu)來完成空閑塊的鏈接和信息存儲，而基于這個數(shù)據(jù)結(jié)構(gòu)的管理物理頁數(shù)組起始地址就是全局變量pagesstruct Page int ref; / 映射此物理頁的虛擬頁個數(shù) uint32_t flags; / 物理頁屬性（空或不空）unsigned int property; / 連續(xù)空頁有多少(只在地址最低頁有值，其余為0)list_entry_t page_link; / 雙向鏈接各個Page結(jié)構(gòu)的page_link雙向鏈表(用于釋放);三、 實驗內(nèi)容與實現(xiàn)1、 練習(xí)1：實現(xiàn)first_fit連續(xù)物理內(nèi)存分配算法;整體思路：物理內(nèi)存頁管理器順著雙向鏈表進行搜索空閑內(nèi)存區(qū)域，直到找到一個足夠大的空閑區(qū)域，這是一種速度很快的算法，因為它盡可能少地搜索鏈表。如果空閑區(qū)域的大小和申請分配的大小正好一樣，則把這個空閑區(qū)域分配出去，成功返回;否則將該空閑區(qū)分為兩部分，一部分區(qū)域與申請分配的大小相等，把它分配出去，剩下的一部分區(qū)域形成新的空閑區(qū)。其釋放內(nèi)存的設(shè)計思路很簡單，只需把這塊區(qū)域重新放回雙向鏈表中即可。實現(xiàn)目標：重寫default_init_memmap()，default_alloc_pages()，default_free_pages()函數(shù)。(1)default_init_memmap()函數(shù)用于內(nèi)存塊的初始化，base塊中首頁，通過指針遍歷塊中的n頁，將每個頁的flags位設(shè)置為0，表明當前頁空閑可用，然后將頁的property屬性設(shè)置為set_page_refdefault_init_memmap(struct Page *base, size_t n) assert(n 0); struct Page *p = base; for (; p != base + n; p +) /檢查此頁是否為保留頁 assert(PageReserved(p); /設(shè)置標志位 p-flags = p-property = 0; SetPageProperty(p);/清零此頁的引用計數(shù) set_page_ref(p, 0); /將空閑頁插入到鏈表list_add_before(&free_list, &(p-page_link); base-property = n; /計算空閑頁總數(shù) nr_free += n;（2） default_alloc_pages()函數(shù)主要是用于為進程分配空閑頁。其分配步驟主要為：尋找足夠大的空閑塊，如果找到了，重新設(shè)置標志位從空閑鏈表中刪除此頁判斷空閑塊大小是否合適，如果不合適，分割頁塊，如果合適則不進行操作計算剩余空閑頁個數(shù)返回分配的頁塊地址代碼：static struct Page *default_alloc_pages(size_t n) assert(n 0); if (n nr_free) return NULL; list_entry_t *len;list_entry_t *le = &free_list;/在空閑鏈表中尋找合適大小的頁塊 while (le = list_next(le) != &free_list) struct Page *p = le2page(le, page_link);/找到了合適大小的頁塊 if (p-property = n) int i;for(i=0;ipropertyn)/分割的頁需要重新設(shè)置空閑大小(le2page(le,page_link)-property = p-property - n;/第一頁重置標志位ClearPageProperty(p);SetPageReserved(p);nr_free -= n;return p;/否則分配失敗 return NULL;（3） default_free_pages()作用是釋放已經(jīng)使用完的頁，并把它們合并到free_list中，具體步驟為：在free_list中查找合適的位置以供插入改變被釋放頁的標志位，以及頭部的計數(shù)器嘗試在free_list中向高地址或低地址合并代碼如下：static voiddefault_free_pages(struct Page *base, size_t n) assert(n 0);assert(PageReserved(base);struct Page *p = base;/查找該插入的位置lelist_entry_t *le = &free_list;while(le=list_next(le) != &free_list)p = le2page(le, page_link);if(pbase) break;/向le之前插入n個頁（空閑），并設(shè)置標志位 for (p = base;ppage_link); p-flags = 0; set_page_ref(p, 0);ClearPageProperty(p);SetPageProperty(p);/將頁塊信息記錄在頭部 base-property = n;/是否需要合并/向高地址合并p = le2page(le, page_link); if (base + n = p) base-property += p-property; list_del(&(p-page_link);/向低地址合并le = list_prev(&(base-page_link);p = le2page(le, page_link);/若低地址已分配則不需要合并if(le!=&free_list & p=base-1)while(le!=&free_list)if(p-property)p-property +=base-property;base-property = 0;break;le = list_prev(le);p = le2page(le,page_link); nr_free += n；2、 練習(xí)2：實現(xiàn)尋找虛擬地址對應(yīng)頁表項；思路：pde_t全稱為 page directory entry，也就是一級頁表的表項（注意：pgdir實際不是表項，而是一級頁表本身。實際上應(yīng)該新定義一個類型pgd_t來表示一級頁表本身）。pte t全稱為 page table entry，表示二級頁表的表項。uintptr t表示為線性地址，由于段式管理只做直接映射，所以它也是邏輯地址。pgdir給出頁表起始地址。通過查找這個頁表，我們需要給出二級頁表中對應(yīng)項的地址。雖然目前我們只有boot_pgdir一個頁表，但是引入進程的概念之后每個進程都會有自己的頁表。有可能根本就沒有對應(yīng)的二級頁表的情況，所以二級頁表不必要一開始就分配，而是等到需要的時候再添加對應(yīng)的二級頁表。如果在查找二級頁表項時，發(fā)現(xiàn)對應(yīng)的二級頁表不存在，則需要根據(jù)create參數(shù)的值來處理是否創(chuàng)建新的二級頁表。如果create參數(shù)為0，則get_pte返回NULL；如果create參數(shù)不為0，則get_pte需要申請一個新的物理頁（通過alloc_page來實現(xiàn)，可在mm/pmm.h中找到它的定義），再在一級頁表中添加頁目錄項指向表示二級頁表的新物理頁。注意，新申請的頁必須全部設(shè)定為零，因為這個頁所代表的虛擬地址都沒有被映射。當建立從一級頁表到二級頁表的映射時，需要注意設(shè)置控制位。這里應(yīng)該設(shè)置同時設(shè)置上PTE_U、PTE_W和PTE_P（定義可在mm/mmu.h）。如果原來就有二級頁表，或者新建立了頁表，則只需返回對應(yīng)項的地址即可。代碼：pte_t *get_pte(pde_t *pgdir, uintptr_t la, bool create) /* * MACROs or Functions: * PDX(la) = the index of page directory entry of VIRTUAL ADDRESS la. * KADDR(pa) : takes a physical address and returns the corresponding kernel virtual address. * set_page_ref(page,1) : means the page be referenced by one time * page2pa(page): get the physical address of memory which this (struct Page *) page manages * struct Page * alloc_page() : allocation a page *memset(void *s, char c, size_t n) : sets the first n bytes of the memory area pointed by s * to the specified value c. * DEFINEs: * PTE_P 0x001 / page table/directory entry flags bit : Present * PTE_W 0x002 / page table/directory entry flags bit : Writeable * PTE_U 0x004 / page table/directory entry flags bit : User can access */嘗試獲取頁表，注：typedef uintptr_t pte_t; pde_t *pdep = &pgdirPDX(la); / (1) find page directory entry /若獲取不成功則執(zhí)行下面的語句if (!(*pdep & PTE_P) /申請一頁struct Page *page;if(!creat | (page = all_page()=NULL)return NULL; /引用次數(shù)需要加1set_page_ref(page, 1);/獲取頁的線性地址 uintptr_t pa = page2pa(page); memset(KADDR(pa), 0, PGSIZE); /設(shè)置權(quán)限*pdep = pa | PTE_U | PTE_W | PTE_P; /返回頁表地址return &(pte_t *)KADDR(PDE_ADDR(*pdep)PTX(la); 3、 練習(xí)3：思路：判斷此頁被引用的次數(shù)，如果僅僅被引用一次，則這個頁也可以被釋放。否則，只能釋放頁表入口。代碼：static inline voidpage_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) /* MACROs or Functions: *struct Page *page pte2page(*ptep): get the according page from the value of a ptep *free_page : free a page *page_ref_dec(page) : decrease page-ref. NOTICE: ff page-ref = 0 , then this page should be free. *tlb_invalidate(pde_t *pgdir, uintptr_t la) : Invalidate a TLB entry, but only if the page tables being * edited are the ones currently in use by the processor. * DEFINEs: * PTE_P 0x001 / page table/directory entry flags bit : Presen