UCORE中的伙伴算法

1、ucore中的物理内存分配 ucore系统中的物理内存分配使用的是buddy伙伴算法，算法与Linux中的buddy算法有很高的相似度。 以下介绍ucore源码中buddy实现物理内存分配的算法。123块分配算法：buddy_alloc_pages_sub(size_t order)static inline struct Page *buddy_alloc_pages_sub(size_t order) assert(order = MAX_ORDER); /检验传入参数的合法性 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结构 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 内核使用该函数来在管理区中找到一个空闲块。该函数需要一个参数：order，order表示请求的空闲页块大小的对数值（0 表示一个单页块，1 表示一个双页块，2表示四页块）。如果页框被成功分配，函数就返回第一个被分配页框的页描述符。否则，函数返

4、回NULL。 在函数中，从所请求order的链表开始，它扫描每个可用块链表进行循环搜索，如果当前order找不到合适空闲块，那么需要搜索更大的order，就继续搜索： for (cur_order = order; cur_order = MAX_ORDER; cur_order +) if (!list_empty(&free_list(cur_order) return null;56关于块释放，由于是要求我们自己写的内容，就不做介绍了。下面是几个ucore中buddy system的其他几个函数：判断是否为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内；（2）它必须属于动态内存（ PageReserved位 清零）；（3）它的property字段必须有意义（PageProperty位 置位）；（4）它的property字段必须存放将要被释放的块的order。7Getorder函数static inline size_t /根据需要的页数求出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