伙伴系统算法，有两个问题不太清楚？

PCliangtao

MARK上... 回学校解决... 这个问题很有意思..

PCliangtao

1.ULK中说，伙伴系统中每一个块的第一个页框的物理地址是块大小的整数倍，请问这是为什么?

只有根据源代码来说了...2.4.X的MM部分我比较熟悉..就用它了,算法思想是一样的。做个例子而已...
  伙伴系统是在bootmem allocator被撤销的同时初始化的...(实质的初始化是在freearea_init()貌似..但只是初始化了free_area_t结构中的一些字段而已..无关痛痒...)
bootmem allocator所管理的每个空闲页都通过调用free_page()来"回收"并归并到伙伴系统所管理的空闲页面集中。实质上最终调用__free_pages_ok()。 任意找一个页框X。其起始地址的低12位一定是0。
对这个页框调用__free_pages_ok()时,会得到其相对于zone_mem_map的偏移page_idx.然后通过这个偏移得到其所属伙伴块在free_area_t->map中的偏移index。这个index所表示的两个伙伴块就包含了这个页面。如果两个伙伴块都空闲.则会合并成更高一级ORDER的伙伴块之一。上代码描述:

1. 
   
2. base = zone->zone_mem_map;
   
3. page_idx = page - base;
   
4. index = page_idx >> (1 + order);    伙伴块在位图中对应的比特位偏移
   
5. ...
   
6. page_idx &= mask;   mask 即 (~0UL) << ORDER。
   
7. ...
   
8. list_add(&(base + page_idx)->list, &area->free_list);  将这个伙伴块的第一个页面添加到free_list
   

复制代码

从page_idx &= mask 即page_idx &= (~0UL) << ORDER
以及最后的list_add可以看出...base+page_idx就是这个ORDER的伙伴块的第一个页面在zone_mem_map中的索引。这个索引是2**ORDER的整数倍。而zone_mem_map是struct page *类型的数组。所以其元素就表示一个页面。一个页面的大小是2**12,即任意一个页面的物理地址是2**12的整数倍。所以伙伴块的第一个页面的物理地址也就是2**12 * 2**ORDER的整数倍。
而这个式子就是或板块的大小。 翻译成白话文就是你问的问题了...
   废话说了蛮多... 只有看具体的代码或者对算法有个清晰的了解才能明白... 我只是心里明白...
这样表达出来就不知道怎样简单明了的了...希望哪位大侠能够精简一下...
    第二个问题明天在回答吧... 要熄灯了... 不好意思... 赶了一天的车... 累死了... 睡觉咯...

PCliangtao

伙伴系统中有一个zone_mem_map数组，zone_mem_map数组中的页描述是不是和free_area数组指向的页描述符严格的一一对应？
例如，free_area[0]中第一个块的起始页描述符就是zone_mem_map中下标为0的元素对应的页描述符。free_area[k]的第一个块的起始页描述符
就是zone_mem_map中下标为：（将0---k-1中所有的块包含的页数相加的和-1）的元素对应的页描述符？

   不知道楼主根据怎样的信息得到这样的臆测... 先不说内核怎样实现.你自己想一下.如果按你所说.会浪费掉多少内存呢？再者... 楼主看ULK的时候最好能够把上面所描述的数据结构能够回过头来看一遍。
free_area是声明为:

1. 
   
2. struct free_area {
   
3.         struct list_head        free_list[MIGRATE_TYPES];
   
4.         unsigned long                nr_free;
   
5. };
   

复制代码

而一个ZONE里面仅有MAX_ORDER个free_area结构。
free_area[index]中的index表示这个free_area结构所管理的内存chunk为2<<index个页框。
free_area[index].free_list就是这些内存chunk的链表头。每个chunk的第一个页框描述符page的list字段作为结点链接到这个链表中。仅有每个伙伴块的第一个页面被链接到free_list上。因为伙伴系统以固定块大小来分配内存.只需要知道起始页框以及ORDER就可以分配一个内存块了。

希望有帮助... 上课去嘞..