请教物理页面管理区结构free_area[MAX_ORDER]成员

fireaway7

《Linux内核源代码情景分析》第44页：
因为常常需要成“块”地分配在物理空间内连续的多个页面，所以在zone_struct数据结构中有一组“空闲区间”队列（free_area[MAX_ORDER]），有连续长度为1的离散页面，也有连续长度为2、4、8、...、2^MAX_ORDER的页面块，那麽请问像图中画的，意思有没有理解错啊？

Tinnal

回复 1# fireaway7

把相关的书的内容拷过来吧。


   

fireaway7

书中完整的一段是这样的：
每个管理区都有一个数据结构，即zone_struct数据结构。在zone_struct数据结构中有一组“空闲区间”（free_area_t）队列。为什么是“一组”队列，而不是“一个”队列呢？这也是因为常常需要成“块”地分配在物理空间内连续的多个页面，所以要按块的大小分别加以管理。因此，在管理区数据结构中既要有一个队列来保持一些离散（连续长度为1）的物理页面，还要有一个队列来保持一些连续长度为2的页面块以及连续长度为4、8、16、……、直至2^MAX_ORDER的页面块。常数MAX_ORDER定义为10，也就是说最大的连续页面块可以达到2^10=1024个页面，即4M字节。这两个数据结构以及几个常数都在文件include/linux/mmzone.h中定义的:

typedef struct free_area_struct {
    struct list_head free_list;
    unsigned int     *map;
} free_area_t;

typedef struct zone_struct {
    ......
    free_area_t free_area[MAX_ORDER];
    ......
} zone_t;


   

fireaway7

书中完整的一段是这样的：
每个管理区都有一个数据结构，即zone_struct数据结构。在zone_struct数据结构中有一组“空闲区间”（free_area_t）队列。为什么是“一组”队列，而不是“一个”队列呢？这也是因为常常需要成“块”地分配在物理空间内连续的多个页面，所以要按块的大小分别加以管理。因此，在管理区数据结构中既要有一个队列来保持一些离散（连续长度为1）的物理页面，还要有一个队列来保持一些连续长度为2的页面块以及连续长度为4、8、16、……、直至2^MAX_ORDER的页面块。常数MAX_ORDER定义为10，也就是说最大的连续页面块可以达到2^10=1024个页面，即4M字节。这两个数据结构以及几个常数都在文件include/linux/mmzone.h中定义的:

typedef struct free_area_struct {
    struct list_head free_list;
    unsigned int     *map;
} free_area_t;

typedef struct zone_struct {
    ......
    free_area_t free_area[MAX_ORDER];
    ......
} zone_t;
回复 3# fireaway7


   

fireaway7

书中完整的一段是这样的：
每个管理区都有一个数据结构，即zone_struct数据结构。在zone_struct数据结构中有一组“空闲区间”（free_area_t）队列。为什么是“一组”队列，而不是“一个”队列呢？这也是因为常常需要成“块”地分配在物理空间内连续的多个页面，所以要按块的大小分别加以管理。因此，在管理区数据结构中既要有一个队列来保持一些离散（连续长度为1）的物理页面，还要有一个队列来保持一些连续长度为2的页面块以及连续长度为4、8、16、……、直至2^MAX_ORDER的页面块。常数MAX_ORDER定义为10，也就是说最大的连续页面块可以达到2^10=1024个页面，即4M字节。这两个数据结构以及几个常数都在文件include/linux/mmzone.h中定义的:

typedef struct free_area_struct {
    struct list_head free_list;
    unsigned int     *map;
} free_area_t;

typedef struct zone_struct {
    ......
    free_area_t free_area[MAX_ORDER];
    ......
} zone_t;
回复 2# Tinnal


   

humjb_1983

这个应该是描述伙伴系统的，看起来就是这样的。

Tinnal

这是伙伴分配算法呀，数据结构的书里头就会描述，典型的解决外碎片的内存分析算法。是一个来链表。
1 page的空闲页面组成一个链表。
2 page的空闲页面组成一个链表。
4 page的空闲页面组成一个链表。
8 page的空闲页面组成一个链表。
。。。
2^MAX_ORDER page 的空闲页面组成一个链表。

这样就是一组链表的呀。

之所以称之为伙伴，是因为如果低order（如1^2大小的块，也就是4个page)的页面不够，会从高一级order(在1^3大小的块）的链表中取一个出来，裂变为两个oder（两个4个page）大小的块，一块返回给用户，一块存在order的空闲链表中。裂变出来的两个块就是一个“伙伴”。
同样，如果一个块释放了，而他人伙伴也是空闲没有分配出去的，那这队伙伴就会合并成一个大块，从低一组order的链表中移到高一级的链表中去。


如果还是不清楚，建议你百度一下”伙伴分配算法“， 有很多的带图的文章。

fireaway7

谢谢，之前都没听说过。
回复 6# humjb_1983


   

fireaway7

谢谢，“2.7物理页面的分配”可以看出来这个过程。
http://www.cnblogs.com/hoys/archive/2011/09/09/2172087.html
回复 7# Tinnal