内存管理专题04 伙伴分配器原理 _分配

伙伴分配器
当系统内核初始化完毕后，使用页分配器管理物理页，当使用的页分配器是伙伴分配器，伙伴分配器的特点是算法简单且高效。
连续的物理页称为页块（page block）。阶（order）是伙伴分配器的一个专业术语，是页的数量单位，2^n个连续页称为n阶页块。
满足以下条件的两个n阶页块称为伙伴
1、两个页块是相邻的，即物理地址是连续的；
2、页块的第一页的物理页号必须是2n的整数倍；
3、如果合并成（n+1）阶页块，第一页的物理页号必须是2n+1的整数倍。
比如：0号页和1号页是伙伴，2号页和3号页是伙伴，那么1号页和2号页就不是伙伴，为什么？因为1号页和2号页合并组成一个页块，第一个的物理页号不是2的整数倍。
伙伴分配器分配和释放物理页的数量单位为阶。分配n阶页块的过程如下：
1、查看是否有空闲的n阶页块，如果有直接分配；否则，继续执行下一步；
2、查看是否存在空闲的（n+1）阶页块，如果有，把（n+1）阶页块分裂为两个n阶页块，一个插入空闲n阶页块链表，另一个分配出去；否则继续执行下一步。
3、查看是否存在空闲的（n+2）阶页块，如果有把（n+2）阶页块分裂为两个（n+1）阶页块，一个插入空闲（n+1）阶页块链表，另一个分裂为两个n阶页块，一个插入空间n阶页块链表，另一个分配出去；如果没有，继续查看更高阶是否存在空闲页块。
一、分区的伙伴分配器源码分析
内核在基本的伙伴分配器基础改进拓展：
1）支持内存节点和区域，称为分区的伙伴分配器(zond buddy )；
2）为了预防内存碎片，把物理地址根据可移动性分组；
3）针对分配单页做了性能优化，为了减少处理器之间的锁竞争，在内存区域增加1个每处理器页集合。
1.数据结构
分区的伙伴分配器专注于某个内存节点的某个区域。内存区域的结构体成员用来维护空闲页块，数组下标对应页块的阶数。内核源码结构：
备注：是最大的阶数，意味着伙伴分配器一次最多可分配2^10页。
#，是用来指定最大阶数。
2.结构体内核源码如下：
用枚举方式来定义，最大是4 。
3.根据分配标志获取首选区域类型
申请页时，最低的四个标志位用来指定首选的内存区域类型，内核源码如下：
上下关系：上面是标志组合，下面是对应内存区域的类型。
一个问题，内核为什有个TABLE？
原因：内核使用宏定义了标志组合到区域类型的映射表，其中是区域类型所占用的位数，把每种标志组合映射到32位整数的某个位置，偏移是（标志组合*区域类型位数），从这个偏移开始的个二进制位存放区域类型。
【内存管理专题04 伙伴分配器原理】

文章插图
4.备用区域列表
如果首选的内存节点或区域不能满足分配请求，可以从备用的内存区域借用物理页。借用必须遵守相应的规则：
1）一个内存节点的某个区域类型可以从另一个内存节点的相同区域类型借用物理页，比如节点0的普通区域可以从节点1的普通区域借用物理页；
2）高区域类型可以从低区域类型借用物理页，比如普通区域可以从DMA区域借用物理页；
3）低区域类型不可以从高区域类型借用物理页，比如DMA区域不可以从普通区域借用物理页。
内存节点的实例已定义备用区域列表，内核源码如下：
UMA系统只有一个区域备用列表，按区域类型从高到低排序。假设UMA系统包含普通区域和DMA区域，那么备用区域列表：{普通区域，DMA区域} 。相当于UMA系统每个内存节点有两个备用区域列表。一个包含所有内存节点的区域，另一个包含当前内存节点的区域。