Linux内存管理伙伴算法


在系统初始化进行到伙伴系统分配器能够承担内存管理的责任后,必须停用bootmem分配器,毕竟不能同时用两个分配器管理内存。在UMA和NUMA系统上,停用分别由free_all_bootmem和free_all_bootmem_node完成(前面的博客已经详细讨论过)。伙伴系统基于一种相对简单而令人吃惊的强大算法,它结合了优秀内存分配器的两个关键特性:速度和效率。Linux内核中采用了一种同时适用于32位和64位系统的内存分页模型,对于32位系统来说,两级页表足够用了,而在x86_64系统中,用到了四级页表,四级页表分别为:

页全局目录(Page Global Directory)

页上级目录(Page Upper Directory)

页中间目录(Page Middle Directory)

页表(Page Table)

页全局目录包含若干页上级目录的地址,页上级目录又依次包含若干页中间目录的地址,而页中间目录又包含若干页表的地址,每一个页表项指向一个页框。Linux中采用4KB

大小的页框作为标准的内存分配单元。

在实际应用中,经常需要分配一组连续的页框,而频繁地申请和释放不同大小的连续页框,必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样,即使这些页框

是空闲的,其他需要分配连续页框的应用也很难得到满足。为了避免出现这种情况,Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请1024个连续页框,对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。假设要申请一个256个页框的块,先从256个页框的链表中查找空闲块,如果没有,就去512个页框的链表中找,找到了则将页框块分为2个256个页框的块,一个分配给应用,另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块,继续向1024个页框的链表查找,如果仍然没有,则返回错误。

页框块在释放时,会主动将两个连续的页框块合并为一个较大的页框块。

为清楚了解其分配制度,先给个伙伴系统数据的存储框图如下:

也就是每个order对应一个free_area结构,free_area以不同的类型以链表的方式存储这些内存块。

主要的数据域结构分析:

  1. struct zone  
  2. {  
  3.       ...  
  4.       ...  
  5.       struct free_area free_area[MAX_ORDER];  
  6.       ...  
  7. };  
  1. struct free_area {  
  2.     struct list_head    free_list[MIGRATE_TYPES];  
  3.     unsigned long       nr_free;  
  4. };  

nr_free指定了当前内存区中空闲页块的数目(对0阶内存区逐页计算,对1阶内存区计算页对的数目,对2阶内存区计算4页集合的数目,依此类推)。free_list是用于连接空闲页的链表。order(阶)是伙伴系统中一个非常重要的概念,它描述了内存分配的数量单位,内存块的长度是2的order次方,其中order的范围从0到MAX_ORDER,而MAX_ORDER的值通常设置为11,这意味着一次分配可以请求的页数最大是2048(2的11次方)。但如果特定于体系结构的代码设置了FORCE_MAX_ZONEORDER配置选项,该值也可以手工改变。MIGRATE_TYPES指定了迁移类型的种类数。

  1. #define MIGRATE_UNMOVABLE     0   //不可移动页:在内存中有固定位置,不能移动到其他地方   
  2. #define MIGRATE_RECLAIMABLE   1   //可回收页:不能直接移动,但可以删除,其内容可以从某些源重新生成   
  3. #define MIGRATE_MOVABLE       2   //可移动页:可以随意的移动   
  4. #define MIGRATE_RESERVE       3   //如果向具有特定可移动性地列表请求分配内存失败,这种紧急情况下可以从MIGRATE_RESERVE分配内存   
  5. #define MIGRATE_ISOLATE       4  //是一个特殊的虚拟区域,用于跨域NUMA结点移动物理内存页,在大型系统上,它有益于将物理内存页移动到接近于是用该页最频繁的CPU   
  6. #define MIGRATE_TYPES         5  //只是表示迁移类型的数目,不代表具体的区域  

在伙伴系统中,每种迁移类型都对应于一个空闲列表。

注:我只是一个内核的初学者,如果有哪些地方说的不对或是不准确,请指正;如果你有什么问题希望能提出来,一起分析讨论一下,以求共同进步。谢谢

  • 1
  • 2
  • 3
  • 4
  • 下一页
【内容导航】
第1页:基本概念介绍 第2页:初始化内存域和数据结构
第3页:分配页 第4页:释放页

相关内容