UCORE中的伙伴算法

1、ucore中的物理內(nèi)存分配 ucore系統(tǒng)中的物理內(nèi)存分配使用的是buddy伙伴算法，算法與Linux中的buddy算法有很高的相似度。 以下介紹ucore源碼中buddy實現(xiàn)物理內(nèi)存分配的算法。123塊分配算法：buddy_alloc_pages_sub(size_t order)static inline struct Page *buddy_alloc_pages_sub(size_t order) assert(order = MAX_ORDER); /檢驗傳入?yún)?shù)的合法性 size_t cur_order; /定義變量current_order for (cur_order = or

2、der; cur_order = MAX_ORDER; cur_order +) if (!list_empty(&free_list(cur_order) list_entry_t *le = list_next(&free_list(cur_order); struct Page *page = le2page(le, page_link);/找到page結(jié)構(gòu) nr_free(cur_order) -; list_del(le); size_t size = 1 order) cur_order -; size = 1; struct Page *buddy = page + size;

3、buddy-property = cur_order; SetPageProperty(buddy); nr_free(cur_order) +; list_add(&free_list(cur_order), &(buddy-page_link); ClearPageProperty(page); return page; return NULL; 4 內(nèi)核使用該函數(shù)來在管理區(qū)中找到一個空閑塊。該函數(shù)需要一個參數(shù)：order，order表示請求的空閑頁塊大小的對數(shù)值（0 表示一個單頁塊，1 表示一個雙頁塊，2表示四頁塊）。如果頁框被成功分配，函數(shù)就返回第一個被分配頁框的頁描述符。否則，函數(shù)返

4、回NULL。 在函數(shù)中，從所請求order的鏈表開始，它掃描每個可用塊鏈表進(jìn)行循環(huán)搜索，如果當(dāng)前order找不到合適空閑塊，那么需要搜索更大的order，就繼續(xù)搜索： for (cur_order = order; cur_order = MAX_ORDER; cur_order +) if (!list_empty(&free_list(cur_order) return null;56關(guān)于塊釋放，由于是要求我們自己寫的內(nèi)容，就不做介紹了。下面是幾個ucore中buddy system的其他幾個函數(shù)：判斷是否為buddystatic inline boolpage_is_buddy(stru

5、ct Page *page, size_t order, int zone_num) if (page2ppn(page) zone_num = zone_num) return !PageReserved(page) & PageProperty(page) & property = order; return 0; 正如所見，要想成為伙伴，必須滿足以下四個條件：（1）它必定和page在同一個zone內(nèi)；（2）它必須屬于動態(tài)內(nèi)存（ PageReserved位 清零）；（3）它的property字段必須有意義（PageProperty位 置位）；（4）它的property字段必須存放將要被釋放的塊的order。7Getorder函數(shù)static inline size_t /根據(jù)需要的頁數(shù)求出order的大小，如n=15，則order=4getorder(size_t n) size_t order, order_size; for (order = 0, order_size = 1; order = MAX_ORDER; order +, order_size = 1) /orde