[内核内存] 伙伴系统2---基本原理

我会带着你远行 2023-01-13 04:12 144阅读 0赞

Linux系统中经常需要分配一组连续的内存块。当重复地申请和释放不同大小的连续内存块后，会导致系统内存在已经分配的的页块周围分布着许多不连续的空闲内存块。这样即使系统中空闲的页框还有很多，但是当系统需要分配一块较大的连续内存块时内存管理模块很难去提供。这就是老大难的内存碎片化的问题。

为了避免内存的碎片化问题，linux引入了伙伴系统算法。伙伴系统是一个高效且简单的内存分配策略。当我们找到了待分配内存的zone后，内核将从对应zone的空闲链表中去分配内存。在释放内存时，内核有将相应的内存还回对应zone的空闲内存链表中。同时伙伴系统通过相关的去碎片化算法能有效的减少系统内存的碎片化程度但并不能完全避免内存的碎片化问题。

# 1.伙伴系统原理 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]

前面介绍过内存中每个zone区域的结构体中有一个成员数组free\_area.该成员负责维护该zone区域的空闲页面的列表。如图1所示free\_area数组大小为MAX\_ORDER。数组存放着MAX\_ORDER个链表，每个链表的元素存放的页块大小为2的n次幂，其中n为该链表在free\_area数组中的索引位置。由图1中我们还会看到在同一个order的内存块中，伙伴系统会根据内存块的migrate type类型将内存块存放在不同的链表中，这也是减少内存碎片化程度的一种优化手段。

## 1.1 伙伴系统内存块分配 ##

如果内核要分配2^n个连续页框的内存块，伙伴系统处理的方式如下：

1.  检查n的大小，假设n=4（-1< n <11），在free\_area数组中找到对应的空闲块链表,检查里面是否存在满足要求的空闲页块。若有则直接返回。
2.  若没有找到满足要求的内存块，则查找n=5的数组链表，若找到了空闲的内存块,将n=5的内存块拆分成大小相等的且连续的两块内存块，将一块返回给内核使用,另外一块则添加到n=4的数组链表中。
3.  若n=5中仍然没有找到,则继续向上寻找,并逐步向下拆分,循环上述操作直到找到满足要求的内存块或n>10为止.

## 1.2 伙伴系统内存合并 ##

为了防止内存碎片化，当系统中出现两块满足如下要求的空闲内存块时伙伴系统会将这两块内存合并成一块大一阶的空闲内存块存入数组链表:(a)两个buddy块的大小一致，（b）他们的物理地址连续，（c）两块内存中靠前的内存块的物理起始地址是2*N*4K的整数倍，其中N为内存块的大小，4K为页面大小。合并过程如下图2所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center 1]

图2中蓝色的部分表示伙伴系统n=2中的某个迁移类型的空闲物理页块链表，红色部分则表示内核中4个page大小的连续的非空闲内存块。若当非空闲内存块释放以后，伙伴系统会对自身free\_area进行检查，然后它会发现free\_area数组链表中起始页框号为1的空闲内存块满足和刚释放的红色内存块进行合并的条件。于是伙伴系统将该两块内存块合并即获得了order=3的大一阶的新连续内存块。接下来伙伴系统会在order=3链表中继续进行搜索，看是否存在一个满足要求的空闲的内存块能和刚合并的新内存块进行合并。若不存在则直接将新合并的内存块放入n=3的链表中去，若存在则继续重复上述操作直到内存块不能合并为止，并将最终获得的大内存块添加到对应order的空闲内存块链表中去（order<11）。

从上图中我们可以看出页框结构体struct page中有几个成员变量和伙伴系统有着很大的关系。如下表所示:

<table> 
 <thead> 
  <tr> 
   <th>__mapcount</th> 
   <th>标记page是否在伙伴系统中（-1或-128，128表示在伙伴系统中）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>private</td> 
   <td>页块中第一个页的private字段存放了内存块的order值</td> 
  </tr> 
  <tr> 
   <td>index</td> 
   <td>存放块的MIGRATE的类型</td> 
  </tr> 
  <tr> 
   <td>__refcount</td> 
   <td>用户的使用计数（初始为0，每多一个用户+1）</td> 
  </tr> 
 </tbody> 
</table>

## 1.3 迁移类型（内存碎片化优化） ##

伙伴系统在系统初期能很高效的运行，但是当系统运行时间过久后，内核会大量的进行内存的分配和释放工作，这必然会照成大量的内存碎片。这时内存虽然有很多空闲内存，但是已经分配的内存分布在内存的各个不同位置，这样会导致大块内存很少甚至不存在的情况出现。如图3所示左右两图空闲内存页是相同的，但是由于内存碎片化为题，左边的最大块连续内存只有一个页，而右边的空闲内存的连续性远远好于左边。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center 2]

为了缓解内存碎片化的问题，内核伙伴系统引入了migrate type的概率，会将同等大小的内存块分为不同的类型：

1.  MIGRATE\_ UNMOVABLE：页框中的内容不可移动，内核分配的大部分内存属于这种类型
2.  MIGRATE\_MOVABLE：页框中的内容可移动，用户空间分配的内存大部分属于这种类型。移动页框的方法为将老页框中的内容拷贝到新页框中，然后将页表的pte entry指向新页框地址即可。用户应用程序并不会注意到上面的改变过程。
3.  MIGRATE\_RECLAIMABLE：这种页框一般用于文件缓存，它们虽然不能被移动，但可以被回收，当再次需要时可通过源文件重建
4.  MIGRATE\_CMA：这段内存被预留给驱动使用，当驱动未使用时，伙伴系统可以将其分配给用户进程使用。但驱动需要时，就需要用户进程通过回收或迁移的方式返还它们，以供驱动使用
5.  MIGRATE\_ISOLATE：它用于numa节点之间移动内存，从而将内存迁移到访问它最频繁cpu的node上内核将可移动和可回收的内存页块通过移动物理内存或者回收内存的方法将内存碎片合并成连续的大块内存以此来缓解内存碎片。

伙伴系统在分配连续内存块时，当一个指定迁移类型所对应的链表中没有空闲内存块时，内核将会按照静态定义的顺序在其他迁移类型的链表中进行寻找。定义顺序如下所示：

static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = { 
        [MIGRATE_UNMOVABLE]   = {  MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
        [MIGRATE_RECLAIMABLE] = {  MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
        [MIGRATE_MOVABLE]     = {  MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
        /* Never used */
        [MIGRATE_RESERVE]     ={  MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE },
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/fbff2c689c444d06a5d67c36e3bf41fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/78feac13515145548feb804fe5f27941.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/540c9fe49d7240d1b32e52fbcf206932.png