請(qǐng)教物理頁(yè)面管理區(qū)結(jié)構(gòu)free_area[MAX_ORDER]成員

fireaway7

《Linux內(nèi)核源代碼情景分析》第44頁(yè)：
因?yàn)槌３Ｐ枰�成“塊”地分配在物理空間內(nèi)連續(xù)的多個(gè)頁(yè)面，所以在zone_struct數(shù)據(jù)結(jié)構(gòu)中有一組“空閑區(qū)間”隊(duì)列（free_area[MAX_ORDER]），有連續(xù)長(zhǎng)度為1的離散頁(yè)面，也有連續(xù)長(zhǎng)度為2、4、8、...、2^MAX_ORDER的頁(yè)面塊，那麼請(qǐng)問(wèn)像圖中畫(huà)的，意思有沒(méi)有理解錯(cuò)��？

Tinnal

回復(fù) 1# fireaway7

把相關(guān)的書(shū)的內(nèi)容拷過(guò)來(lái)吧。


   

fireaway7

書(shū)中完整的一段是這樣的：
每個(gè)管理區(qū)都有一個(gè)數(shù)據(jù)結(jié)構(gòu)，即zone_struct數(shù)據(jù)結(jié)構(gòu)。在zone_struct數(shù)據(jù)結(jié)構(gòu)中有一組“空閑區(qū)間”（free_area_t）隊(duì)列。為什么是“一組”隊(duì)列，而不是“一個(gè)”隊(duì)列呢？這也是因?yàn)槌３Ｐ枰�成“塊”地分配在物理空間內(nèi)連續(xù)的多個(gè)頁(yè)面，所以要按塊的大小分別加以管理。因此，在管理區(qū)數(shù)據(jù)結(jié)構(gòu)中既要有一個(gè)隊(duì)列來(lái)保持一些離散（連續(xù)長(zhǎng)度為1）的物理頁(yè)面，還要有一個(gè)隊(duì)列來(lái)保持一些連續(xù)長(zhǎng)度為2的頁(yè)面塊以及連續(xù)長(zhǎng)度為4、8、16、……、直至2^MAX_ORDER的頁(yè)面塊。常數(shù)MAX_ORDER定義為10，也就是說(shuō)最大的連續(xù)頁(yè)面塊可以達(dá)到2^10=1024個(gè)頁(yè)面，即4M字節(jié)。這兩個(gè)數(shù)據(jù)結(jié)構(gòu)以及幾個(gè)常數(shù)都在文件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

書(shū)中完整的一段是這樣的：
每個(gè)管理區(qū)都有一個(gè)數(shù)據(jù)結(jié)構(gòu)，即zone_struct數(shù)據(jù)結(jié)構(gòu)。在zone_struct數(shù)據(jù)結(jié)構(gòu)中有一組“空閑區(qū)間”（free_area_t）隊(duì)列。為什么是“一組”隊(duì)列，而不是“一個(gè)”隊(duì)列呢？這也是因?yàn)槌３Ｐ枰�成“塊”地分配在物理空間內(nèi)連續(xù)的多個(gè)頁(yè)面，所以要按塊的大小分別加以管理。因此，在管理區(qū)數(shù)據(jù)結(jié)構(gòu)中既要有一個(gè)隊(duì)列來(lái)保持一些離散（連續(xù)長(zhǎng)度為1）的物理頁(yè)面，還要有一個(gè)隊(duì)列來(lái)保持一些連續(xù)長(zhǎng)度為2的頁(yè)面塊以及連續(xù)長(zhǎng)度為4、8、16、……、直至2^MAX_ORDER的頁(yè)面塊。常數(shù)MAX_ORDER定義為10，也就是說(shuō)最大的連續(xù)頁(yè)面塊可以達(dá)到2^10=1024個(gè)頁(yè)面，即4M字節(jié)。這兩個(gè)數(shù)據(jù)結(jié)構(gòu)以及幾個(gè)常數(shù)都在文件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;
回復(fù) 3# fireaway7


   

fireaway7

書(shū)中完整的一段是這樣的：
每個(gè)管理區(qū)都有一個(gè)數(shù)據(jù)結(jié)構(gòu)，即zone_struct數(shù)據(jù)結(jié)構(gòu)。在zone_struct數(shù)據(jù)結(jié)構(gòu)中有一組“空閑區(qū)間”（free_area_t）隊(duì)列。為什么是“一組”隊(duì)列，而不是“一個(gè)”隊(duì)列呢？這也是因?yàn)槌３Ｐ枰�成“塊”地分配在物理空間內(nèi)連續(xù)的多個(gè)頁(yè)面，所以要按塊的大小分別加以管理。因此，在管理區(qū)數(shù)據(jù)結(jié)構(gòu)中既要有一個(gè)隊(duì)列來(lái)保持一些離散（連續(xù)長(zhǎng)度為1）的物理頁(yè)面，還要有一個(gè)隊(duì)列來(lái)保持一些連續(xù)長(zhǎng)度為2的頁(yè)面塊以及連續(xù)長(zhǎng)度為4、8、16、……、直至2^MAX_ORDER的頁(yè)面塊。常數(shù)MAX_ORDER定義為10，也就是說(shuō)最大的連續(xù)頁(yè)面塊可以達(dá)到2^10=1024個(gè)頁(yè)面，即4M字節(jié)。這兩個(gè)數(shù)據(jù)結(jié)構(gòu)以及幾個(gè)常數(shù)都在文件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;
回復(fù) 2# Tinnal


   

humjb_1983

這個(gè)應(yīng)該是描述伙伴系統(tǒng)的，看起來(lái)就是這樣的。

Tinnal

這是伙伴分配算法呀，數(shù)據(jù)結(jié)構(gòu)的書(shū)里頭就會(huì)描述，典型的解決外碎片的內(nèi)存分析算法。是一個(gè)來(lái)鏈表。
1 page的空閑頁(yè)面組成一個(gè)鏈表。
2 page的空閑頁(yè)面組成一個(gè)鏈表。
4 page的空閑頁(yè)面組成一個(gè)鏈表。
8 page的空閑頁(yè)面組成一個(gè)鏈表。
。。。
2^MAX_ORDER page 的空閑頁(yè)面組成一個(gè)鏈表。

這樣就是一組鏈表的呀。

之所以稱(chēng)之為伙伴，是因?yàn)槿绻�低order（如1^2大小的塊，也就是4個(gè)page)的頁(yè)面不夠，會(huì)從高一級(jí)order(在1^3大小的塊）的鏈表中取一個(gè)出來(lái)，裂變?yōu)閮蓚�(gè)oder（兩個(gè)4個(gè)page）大小的塊，一塊返回給用戶(hù)，一塊存在order的空閑鏈表中。裂變出來(lái)的兩個(gè)塊就是一個(gè)“伙伴”。
同樣，如果一個(gè)塊釋放了，而他人伙伴也是空閑沒(méi)有分配出去的，那這隊(duì)伙伴就會(huì)合并成一個(gè)大塊，從低一組order的鏈表中移到高一級(jí)的鏈表中去。


如果還是不清楚，建議你百度一下”伙伴分配算法“， 有很多的帶圖的文章。

fireaway7

謝謝，之前都沒(méi)聽(tīng)說(shuō)過(guò)。
回復(fù) 6# humjb_1983


   

fireaway7

謝謝，“2.7物理頁(yè)面的分配”可以看出來(lái)這個(gè)過(guò)程。
http://www.cnblogs.com/hoys/archive/2011/09/09/2172087.html
回復(fù) 7# Tinnal