http://blog.chinaunix.net/uid-26859697-id-4882194.html

前面分析了伙伴管理算法的初始化,在切入分析代码实现之前,例行先分析一下其实现原理。

伙伴管理算法(也称之为<span style="-ms-word-wrap: break-word;">Buddy</span>算法),该算法将所有空闲的页面分组划分为<span style="-ms-word-wrap: break-word;">MAX_ORDER</span>个页面块链表进行管理,其中<span style="-ms-word-wrap: break-word;">MAX_ORDER</span>定义:

&nbsp;


1. 【file:/include/linux/mmzone.h】
2. #ifndef CONFIG_FORCE_MAX_ZONEORDER
3. #define MAX_ORDER 11
4. #else
5. #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
6. #endif
<span style="text-align: left; color: rgb(102, 102, 102); text-transform: none; text-indent: 0px; letter-spacing: normal; font-family: 宋体, Arial; font-size: 16px; font-style: normal; font-weight: normal; word-spacing: 0px; float: none; display: inline !important; white-space: normal; orphans: 2; widows: 2; background-color: rgb(255, 255, 255); font-variant-ligatures: normal; font-variant-caps: normal; -webkit-text-stroke-width: 0px;">&nbsp; &nbsp;&nbsp;通常该值都是定义为</span><span style="text-align: left; color: rgb(102, 102, 102); text-transform: none; text-indent: 0px; letter-spacing: normal; font-family: 宋体, Arial; font-size: 16px; font-style: normal; font-weight: normal; word-spacing: 0px; white-space: normal; -ms-word-wrap: break-word; orphans: 2; widows: 2; background-color: rgb(255, 255, 255); font-variant-ligatures: normal; font-variant-caps: normal; -webkit-text-stroke-width: 0px;">11</span><span style="text-align: left; color: rgb(102, 102, 102); text-transform: none; text-indent: 0px; letter-spacing: normal; font-family: 宋体, Arial; font-size: 16px; font-style: normal; font-weight: normal; word-spacing: 0px; float: none; display: inline !important; white-space: normal; orphans: 2; widows: 2; background-color: rgb(255, 255, 255); font-variant-ligatures: normal; font-variant-caps: normal; -webkit-text-stroke-width: 0px;">,而</span><span style="text-align: left; color: rgb(102, 102, 102); text-transform: none; text-indent: 0px; letter-spacing: normal; font-family: 宋体, Arial; font-size: 16px; font-style: normal; font-weight: normal; word-spacing: 0px; white-space: normal; -ms-word-wrap: break-word; orphans: 2; widows: 2; background-color: rgb(255, 255, 255); font-variant-ligatures: normal; font-variant-caps: normal; -webkit-text-stroke-width: 0px;">CONFIG_FORCE_MAX_ZONEORDER</span><span style="text-align: left; color: rgb(102, 102, 102); text-transform: none; text-indent: 0px; letter-spacing: normal; font-family: 宋体, Arial; font-size: 16px; font-style: normal; font-weight: normal; word-spacing: 0px; float: none; display: inline !important; white-space: normal; orphans: 2; widows: 2; background-color: rgb(255, 255, 255); font-variant-ligatures: normal; font-variant-caps: normal; -webkit-text-stroke-width: 0px;">定义:</span>


1. 【file:/arch/tile/include/asm/page.h】
2. /
3.   If the Kconfig doesn't specify, set a maximum zone order that
4.   is enough so that we can create huge pages from small pages given
5.   the respective sizes of the two page types. See <linux/mmzone.h>.
6.  */
7. #ifndef CONFIG_FORCE_MAX_ZONEORDER
8. #define CONFIG_FORCE_MAX_ZONEORDER (HPAGE_SHIFT - PAGE_SHIFT + 1)
9. #endif
&nbsp;

该值具体多少没细入分析。其中<span style="-ms-word-wrap: break-word;">tile</span>是指<span style="-ms-word-wrap: break-word;">Tilera</span>处理器,顺带介绍一下:<span style="-ms-word-wrap: break-word;">Tilera</span>公司是位于硅谷的新创无晶圆半导体公司,该公司创始人之一是麻省理工学院(<span style="-ms-word-wrap: break-word;">MIT</span>)教授阿南特&middot;阿加瓦尔(<span style="-ms-word-wrap: break-word;">Anant Agarwal</span>),他在<span style="-ms-word-wrap: break-word;">2004</span>年创建了该公司,因为在多核技术方面拥有独家的先进技术,该公司曾被美国知名媒体<span style="-ms-word-wrap: break-word;">EETIMES</span>评为全球最有希望的<span style="-ms-word-wrap: break-word;">60</span>家新兴企业之一。该公司的处理器功耗据说很低,但是性能却是杠杠滴。迄今为止本人还没接触过该公司的处理器,惭愧惭愧,路漫漫其修远兮。

接着,基于<span style="-ms-word-wrap: break-word;">MAX_ORDER</span>为<span style="-ms-word-wrap: break-word;">11</span>的情况,伙伴管理算法每个页面块链表分别包含了:<span style="-ms-word-wrap: break-word;">1</span>、<span style="-ms-word-wrap: break-word;">2</span>、<span style="-ms-word-wrap: break-word;">4</span>、<span style="-ms-word-wrap: break-word;">8</span>、<span style="-ms-word-wrap: break-word;">16</span>、<span style="-ms-word-wrap: break-word;">32</span>、<span style="-ms-word-wrap: break-word;">64</span>、<span style="-ms-word-wrap: break-word;">128</span>、<span style="-ms-word-wrap: break-word;">256</span>、<span style="-ms-word-wrap: break-word;">512</span>、<span style="-ms-word-wrap: break-word;">1024</span>个连续的页面,每个页面块的第一个页面的物理地址是该块大小的整数倍。假设连续的物理内存,各页面块左右的页面,要么是等同大小,要么就是整数倍,而且还是偶数,形同伙伴。

其管理起来如图:

&nbsp;

伙伴管理算法的释放过程是,满足条件的两个页面块称之为伙伴:两个页面块的大小相同且两者的物理地址连续。当某块页面被释放时,且其存在空闲的伙伴页面块,则算法会将其两者合并为一个大的页面块,合并后的页面块如果还可以找到伙伴页面块,则将会继续与相邻的块进行合并,直至到大小为<span style="-ms-word-wrap: break-word;">2^MAX_ORDER</span>个页面为止。

释放如图:

&nbsp;

&nbsp;

而伙伴管理算法的申请过程则相反,如果申请指定大小的页面在其页面块链表中不存在,则会往高阶的页面块链表进行查找,如果依旧没找到,则继续往高阶进行查找,直到找到为止,否则就是申请失败了。如果在高阶的页面块链表找到空闲的页面块,则会将其拆分为两块,如果拆分后仍比需要的大,那么继续拆分,直至到大小刚好为止,这样避免了资源浪费。

具体的申请如图:

&nbsp;