伙伴算法

chenzhanyiczy

伙伴算法里分为 2^0 -2^11 ,有free_area[11]数组，每个数组都有free_list，指向空闲的page

伙伴算法初始化的后，free_area数组每个元素里的free_list是不是空的？

baozhao

伙伴算法初始化的后，free_area数组每个元素里的free_list是不是空的？

要看你怎么理解初始化了. 实际上,伙伴系统的初始化是一个过程, 伙伴系统初始化可以看成是由 bootmem allocator完成, 与伙伴系统相关的主要有两步

以2.6.11代码为例:

1  bootmem的早期, 在初始化zone的过程共会调用free_area_init_core, 该函数调用  zone_init_free_lists.
可以看到,free_area数组每个元素里的free_list的确是空的.

1. void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone,
   
2.                                 unsigned long size)
   
3. {
   
4.         int order;
   
5.         for (order = 0; order < MAX_ORDER ; order++) {
   
6.                 INIT_LIST_HEAD(&zone->free_area[order].free_list);
   
7.                 zone->free_area[order].nr_free = 0;
   
8.         }
   
9. }

复制代码

2. 在bootmem的后期, 会把初始化后未用到的页面全部释放给buddy.
在mem_init()函数中有如下代码, 注意最初的注释以及__free_all_bootmem和set_highmem_pages_init函数,这两个函数都将调用__free_pages或__free_page函数将空闲页面加入相关的freelist

1. /* this will put all low memory onto the freelists */
   
2.         totalram_pages += __free_all_bootmem();
   
3. 
   
4.         reservedpages = 0;
   
5.         for (tmp = 0; tmp < max_low_pfn; tmp++)
   
6.                 /*
   
7.                  * Only count reserved RAM pages
   
8.                  */
   
9.                 if (page_is_ram(tmp) && PageReserved(pfn_to_page(tmp)))
   
10.                         reservedpages++;
    
11. 
    
12.         set_highmem_pages_init(bad_ppro);
    

复制代码

superfight

我刚看的伙伴系统初始化~ arm架构 2.6.29内核~

分为2部分:
1.使用bitmap来管理内存页,每bit代表1页内存的状态,使用bitmap来静态分配内存,多用于固定的资源初始化,例如页表,必须使用的IO映射,initrd之类
2.初始化完成以后释放bitmap,bitmap中的空闲页将归伙伴系统管理,伙伴系统一开始是个空链表,bitmap每释放N页个页面就按照N个页面的order值来组成伙伴系统

chenzhanyiczy

多谢两位