linux伙伴系统

前段时间由于实验室相关项目的需要+OS课的presentation,看了linux2.6.24内核伙伴系统的源码。写一下总结。

引言
    伙伴系统作为一种古老而历经检验的系统,也被Linux内核所采用。伙伴系统的提出是为了管理和记录内存的分配和使用。在X86架构的Linux内核版本 2.6.24及之后,Linux对原本的伙伴系统做了改进,在原来的基础上加入了反碎片机制,使得内核能够更好的管理内存的外部碎片。
    本文的分析针对X86架构。首先介绍了什么是伙伴系统,以及伙伴系统的相关数据结构。然后分析了X86架构上Linux 2.6.24这个版本对伙伴系统做的改进(加入了反碎片机制)。最后从源代码出发,深入揭示了伙伴系统的内核工作流程。
什么是伙伴系统
    伙伴系统的宗旨就是用最小的内存块来满足内核对于内存的请求。在最初,只有一个块,也就是整个内存,假如为1M大小,而允许的最小块为64K,那么当我们申请一块200K大小的内存时,就要先将1M的块分裂成两等分,各为512K,这两份之间的关系就称为伙伴,然后再将第一个512K的内存块分裂成两等分,各为256K,将第一个256K的内存块分配给内存,这样就是一个分配的过程。下面我们结合示意图来了解伙伴系统分配和回收内存块的过程。
图1 伙伴系统示意图
1. 初始化时,系统拥有1M的连续内存,允许的最小的内存块为64K,图中白色的部分为空闲的内存块,着色的代表分配出去了的内存块。
2. 程序A申请一块大小为34K的内存,对应的order为0,即2^0=1个最小内存块
   2.1 系统中不存在order 0(64K)的内存块,因此order 4(1M)的内存块分裂成两个order 3的内存块(512K)
   2.2 仍然没有order 0的内存块,因此order 3的内存块分裂成两个order 2的内存块(256K)
   2.3 仍然没有order 0的内存块,因此order 2的内存块分裂成两个order 1的内存块(128K)
   2.4 仍然没有order 0的内存块,因此order 1的内存块分裂成两个order 0的内存块(64K)
   2.5 找到了order 0的内存块,将其中的一个分配给程序A,现在伙伴系统的内存为一个order 0的内存块,一个order 1的内存块,一个order 2的内存块以及一个order 3的内存块
3.程序B申请一块大小为66K的内存,对应的order为1,即2^1=2个最小内存块,由于系统中正好存在一个order 1的内存块,所以直接用来分配
4 程序C申请一块大小为35K的内存,对应的order为0,同样由于系统中正好存在一个order 0的内存块,直接用来分配
5 程序D申请一块大小为67K的内存,对应的order为1
   5.1 系统中不存在order 1的内存块,于是将order 2的内存块分裂成两块order 1的内存块
   5.2 找到order 1的内存块,进行分配
6 程序B释放了它申请的内存,即一个order 1的内存块
7 程序D释放了它申请的内存
   7.1 一个order 1的内存块回收到内存当中
   7.2由于该内存块的伙伴也是空闲的,因此两个order 1的内存块合并成一个order 2的内存块
8 程序A释放了它申请的内存,即一个order 0的内存块
9 程序C释放了它申请的内存
   9.1 一个order 0的内存块被释放
   9.2 两个order 0伙伴块都是空闲的,进行合并,生成一个order 1的内存块m
   9.3 两个order 1伙伴块都是空闲的,进行合并,生成一个order 2的内存块
   9.4 两个order 2伙伴块都是空闲的,进行合并,生成一个order 3的内存块
   9.5 两个order 3伙伴块都是空闲的,进行合并,生成一个order 4的内存块
 从上述例子中,我们可以总结出伙伴系统分配内存释放内存的算法:
分配内存
1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂)
  • 1.1.如果找到了,分配给应用程序
  • 1.2.如果没找到,分出合适的内存块
  • 1.2.1.对半分离出高于所需大小的空闲内存块
  • 1.2.2.如果分到最低限度,分配这个大小
  • 1.2.3.回溯到步骤1
  • 1.2.4.重复该步骤直到一个合适的块
释放内存
1.释放该内存块
  • 1.1.寻找相邻的块,看其是否释放了。
  • 1.2.如果相邻块也释放了,合并这两个块,重复上述步骤直到遇上未释放的相邻块,或者达到最高上限(即所有内存都释放了)
伙伴系统的数据结构
    我们首先来看一下伙伴系统相关的数据结构,首先看一下free_area。
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list;
    unsigned long     nr_free;
};
    其中nr_free指定了当前内存区中空闲页块的数目。free_list是用于链接空闲页的链表,页链表包含大小相同的连续内存区。是伙伴系统里非常重要的概念,它描述了内存分配的数量单位,例如2^order,order就是阶,并且其范围从0到MAX_ORDER。order通常设置为11,这意味着一次分配可以请求的页的最大数是2^11=2048。
    free_area[]数组中的各个元素索引也可以理解为索引,第0个链表代表内存管理区里的单页,第1个链表代表内存管理区里的两页。从下图可以看出,free_area[0]每个元素代表单个页帧,free_area[2]的每个元素代表4个页帧。
伙伴系统的反碎片机制
    本文研究的是X86平台Linux2.6.24版本的内核。在该版本中,对于伙伴系统加入了反碎片机制(anti-fragmentation),试图从最初开始就尽可能防止碎片。
    首先我们必须知道,内核将已分配页分为以下三种不同的类型:
  不可移动页(UNMOVABLE): 这些页在内存中有固定的位置,不能够移动。
  可回收页(RECLAIMABLE): 这些页不能移动,但可以删除。内核在回收页占据了太多的内存时或者内存短缺时进行页面回收。
  可移动页(MOVABLE): 这些页可以任意移动,用户空间应用程序使用的页都属于该类别。它们是通过页表映射的。当它们移动到新的位置,页表项也会相应的更新。
  在内存子系统初始化期间,所有的页都被标记为可移动的。在启动期间,核心内核分配的内存是不可移动的。此时内核的策略是分配一个尽可能大的连续内存块,将其从可移动列表转换到不可移动列表。原因如下:
   例如:现有一块可移动的具有16页的连续空闲内存块。当内核需要分配1页不可移动内存页时。分配器选择后8页(而不是一页)转移到不可移动列表,然后从 不可移动列表中选择1页用于分配。如果内核又需要分配1页不可移动内存页则从不可移动列表中选择一页用于分配,下图显示了进行4次分配后内存的分布。
        但如果内核只选择1页用于分配将其加入到不可移动列表,当下次需要分配时又选择一页加入到不可移动列表,下图显示了按照这种方式进行4次分配后内存的分布。
        因此,当没有满足可用于分配的不可移动空闲块时,分配器会在可移动列表中迁移一个尽可能大的连续内存块给不可移动列表。这样避免了启动期间内核分配的内存散列到物理内存各处,从而使其他类型的内存分配免受碎片的干扰。
        内核定义了一些宏来表示不同的迁移类型:
<include/linux/mmzone.h>
    #define MIGRATE_UNMOVABLE     0
    #define MIGRATE_RECLAIMABLE   1
    #define MIGRATE_MOVABLE       2
    #define MIGRATE_RESERVE       3
    #define MIGRATE_ISOLATE       4 /*用于跨越NUMA结点移动物理内存页*/
    #define MIGRATE_TYPES         5
    2.6.24版本对伙伴系统结构的主要调整,是将空闲列表分解成MIGRATE_TYPE个列表,数据结构如下(注意变化的部分):
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list[MIGRATE_TYPE];
    unsigned long     nr_free;
};
    也就是说每一个free_area又根据MIGRATE_TYPE分成了5种类型,每种类型里面分别都有一个head_list结构体。
    如果内核无法满足针对某一给定迁移类型的分配请求的话,内核提供了一个备用列表,规定了在指定列表中无法满足分配请求时,接下来应使用哪一种迁移类型:
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 },  
  • [MIGRATE_RESERVE] = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, 
}; 
    内核想要分配不可移动页时,如果对应链表为空,则后退到可回收链表,接下来到可移动页链表,最后到紧急分配链表。
    在X86架构中存在着三种内存域ZONE_DMA、ZONE_NORMAL、ZONE_HIGHMEM,那么每个内存域都有一个free_area数据结构:
<mm/mmzone.h>
struct zone {
  • struct free_area    free_area[MAX_ORDER];
}
    而如果是在NUMA架构中,可能存在着多块物理内存,其结构可能是如下图所示:
    基于伙伴系统的内存管理专注于某个节点的某个内存域,例如DMA或高端内存域。但所有内存管理区和节点的伙伴系统都通过备用分配列表链接起来。在首选内存 管理区或节点无法满足分配请求时,首先尝试用同一节点的另一个内存管理区分配,反复尝试下一个结点直到满足请求。

页的分配以及源代码剖析
       就伙伴系统的接口而言,NUMA或UMA体系结构是没有差别的,二者的调用语法都是相同的。所有函数的一个共同点是:只能分配2的整数幂个页。

从函数关系图上可以看到,最终的分配任务落在__alloc_pages()上。我们来看这个函数的代码
————————————————————————————待续————————————————-——————

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>