Chinaunix首页 | 论坛 | 博客
  • 博客访问: 124832
  • 博文数量: 27
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 193
  • 用 户 组: 普通用户
  • 注册时间: 2015-06-10 22:38
文章分类

全部博文(27)

文章存档

2016年(1)

2015年(26)

分类: LINUX

2015-09-05 22:47:52

    本文内容均基于内核版本Linux-v3.2.40。

    内存碎片是内存管理中非常重要又非常棘手的问题,就算强大的Linux也没有办法完全解决,但好在经过多年的发展,Linux已经有一套相当成熟的反碎片技术,包括:针对页外碎片的伙伴系统和针对页内碎片的slab分配技术。本文主要对伙伴系统及其涉及的内存分类进行说明。

1. 伙伴系统
1.1 什么是伙伴系统
    伙伴系统是基于内存块的内存管理策略,它将物理内存分成许多大小为2^n个page的内存块(其中n=0,1,2.....10),相同大小的内存块被链入同一个链表中。

1.2 实现
    伙伴系统是借助内存域zone实现的,在zone的数据结构中有一个free_area数组:

点击(此处)折叠或打开

  1. struct zone {
  2.     ......
  3.     struct free_area    free_area[MAX_ORDER]; /* MAX_ORDER默认为11,除非在配置文件中配置了选项CONFIG_FORCE_MAX_ZONEORDER */
  4.     ......
  5. };
    该数组的下标称为阶(order),每个阶对应一个链表,用于链接由阶确定的相同大小(2^order)的内存块。
    比如free_area[0]的阶为0,它链接的所有内存块的大小为2^0=1个page;而free_area[2]的阶为2,它链接的所有内存块的大小为2^2=4个page,如图1所示:
    
                       图1
1.3 什么样的内存块才算是伙伴?
    伙伴必须满足以下几个条件:
    1) 两个块大小必须相同,假设为2^order个page
    2) 两个块的物理地址必须是连续的
    3) 第一个块的起始地址必须是2 * 2^order * page_size的倍数
    比如图2:
    
                       图2
    0和1是伙伴,2和3是伙伴;而1和2不是伙伴,因为1*page_size不是2*2^0*page_size=2*page_size的倍数。
    4、5组成的内存块和6、7组成的内存块是伙伴,因为4*page_size是2*2^1*page_size=2*2*page_size的倍数;而2、3组成的内存块和4、5组成的内存块不是伙伴,因为2*page_size不是2*2^1*page_size=2*2*page_size的倍数

1.4 分配/释放原理
    伙伴系统只能分配内存块,而且其大小为2^order个page。
    假设要分配一个order=3即2^3=8个page的内存块,算法首先搜索free_area[3]指定的链表,检查是否有空闲的内存块。如果有,直接从链表上摘取一个内存块;如果没有,算法会检查更大内存块的链表,即free_area[4]指定的链表,如果该链表有空闲块,则摘取一个空闲块并分割为大小相同的两部分(伙伴),一部分返回给内存申请者,另一部分加入到free_area[3]指定的链表中。如果free_area[4]指定的链表中也没有空闲块,则继续搜索更大的内存块链表,直至free_area[10]。
    当内存块被释放时,算法首先会检查它的伙伴是否存在,如果不存在,直接将内存块加入到对应的链表中;如果存在,将两个伙伴合并为一个更大的内存块,并继续检查该内存块的伙伴是否存在,如果存在,继续向上合并,否则链入相应的链表。


1.5 总结
    1) 伙伴系统是基于内存域zone实现的,也就是说每个zone都有一套自己的伙伴系统。
    2) 伙伴系统只能分配特定大小的内存块,即2^order个page(order=0,1,2.....MAX_ORDER),因此内核可分配的最大内存块为2^MAX_ORDER=4M。
    3) 内存块中的page是连续的
    4) 相同大小的内存块通过内存块中的第一个page的page->lru链入链表,且page->private存放了该内存块的order。

2. 内存分类技术
    尽管伙伴系统在内存管理中已经工作的很好,但是当系统运行较长一段时间后,分配大的内存块仍然是困难的,如图3:
    
                               图3
     一个由16个page组成的内存块,尽管只有2个page被使用,但要从中申请8个page的空闲块却是不行的,因为没有那么多的连续page可用。为此,在2.6.24中提出了一种反碎片技术-内存分类。
    我们知道Linux中使用的内存大体可分为以下三类:
    1) 不可移动页:在内存中的位置固定,不能移动到其他地方。内核分配的内存都属于这种类型。
    2) 可回收页:不能直接移动,但可以删除,因为其内容可从某些源重新生成,如文件映射产生的页。
    3) 可移动页:在内存中的位置可随便移动,只要修改其对应的页表即可。用户态应用程序使用的页属于这种类型。

    虽然对于不可移动页,图3所展现出来的缺陷仍然无法解决,但是可回收页和可移动页却可以有极大的改善,尤其是可移动页,如图4所示,申请8个page的空闲块已经不再是问题了:
    
                                图4
     
2.1 迁移类型
    在前文的基础上,内核定义了多种内存类型(也称为迁移类型),如:

点击(此处)折叠或打开

  1. #define MIGRATE_UNMOVABLE 0
  2. #define MIGRATE_RECLAIMABLE 1
  3. #define MIGRATE_MOVABLE 2

  4. #define MIGRATE_PCPTYPES 3 /* the number of types on the pcp lists */
  5. #define MIGRATE_RESERVE 3
  6. #define MIGRATE_ISOLATE 4 /* can't allocate from here */
  7. #define MIGRATE_TYPES 5
    MIGRATE_UNMOVABLE:不可移动内存页
    MIGRATE_RECLAIMABLE:可回收内存页
    MIGRATE_MOVABLE:可移动内存页
    MIGRATE_PCPTYPES:不是一种类型,只用于表示pcp list中内存类型的个数,pcp list在后文会进行说明
    MIGRATE_RESERVE:紧急情况下,如果从前三种类型中申请不到内存,可从该类型下申请内存
    MIGRATE_ISOLATE:特殊的虚拟区域,用于跨域NUMA节点移动物理内存页,将内存页移动到使用该页最频繁的CPU所在的节点上
    MIGRATE_TYPES:迁移类型的种类数

    内存分类是在伙伴系统的基础上实现的,因此图1所示的框图应该修正为图5:
    
                               图5
    每种阶数(order)又按照迁移类型分为了多个链表,free_list才是空闲块的最终管理者:

点击(此处)折叠或打开

  1. struct free_area {
  2.     struct list_head    free_list[MIGRATE_TYPES]; /* 按迁移类型分类的空闲块链表 */
  3.     unsigned long        nr_free; /* 该阶数下所有链表上空闲块的个数 */
  4. };
2.2 既然伙伴系统对内存进行了分类,那对于给定的分配请求如何确定应该从哪个free_list链表上进行?
    需要借助内存分配请求给定的分配掩码,___GFP_MOVABLE表示要分配可移动的内存,___GFP_RECLAIMABLE表示要分配可回收的内存,如果二者都不指定,表示要分配不可移动的内存。比如常见的GFP_KERNEL( #define GFP_KERNEL (__GFP_WAIT | __GFP_IO | __GFP_FS) )由于未指定以上两个标志,所以申请到的内存是不可移动的。

2.3 迁移类型的备用列表
    如果内核无法满足针对某一给定迁移类型的分配请求,会怎么样呢?
    针对这种情况,内核提供了一个迁移类型的备用列表,如图6:
    
                               图6
    比如第一项,当需要分配不可移动的内存页时,如果对应的free_list链表为空,则从可回收页链表中申请,如果仍然为空,则从可移动页链表中申请,最后到紧急分配链表。

2.4 内存块迁移类型的跟踪
    在内存释放时,为了能够快速的将内存块返回到正确的迁移链表上,内核提供了一个专门的字段pageblock_flags,用来跟踪包含pageblock_nr_pages个页的内存块的迁移类型,在启用大页的情况下pageblock_nr_pages与大页大小(2M)相同,否则pageblock_nr_pages=2^(MAX_ORDER-1)=2^10个page。
    pageblock_flags是一个比特位空间,每3位(保证能表示5种迁移类型)对应一个内存块;在使能SPARSEMEM(稀疏内存模型)的系统上,pageblock_flags被定义在struct mem_section中,否则定义在struct zone中。

    几点说明:
    1) pageblock_flags的空间是根据内存大小,在内存初始化时就分配好的,它的比特位总是可用的,与page是否由伙伴系统管理无关。
    2) 函数set_pageblock_migratetype(page, migratetype)用于设置以page为首的内存块的迁移类型,而get_pageblock_migratetype(page)用于获取以page为首的内存块的迁移类型
    3) 所有页最开始都被标记为可移动的。
    4) 分配内存时,如果需要从备用列表中申请,内核优先申请更大的内存块。比如计划申请1个page的不可移动内存块,优先查找是否存在2^10个page的可回收内存块,如果不存在再查找是否存在2^9个page的可回收内存块,直到2^0。这样做是为了尽量避免向可回收和可移动内存块中引入碎片。

    以上就是对伙伴系统的简单总结,后续会从代码的角度再进行分析。
    如有错误,欢迎批评指正。
    

阅读(2057) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

镇水铁牛2015-09-06 22:22:48

不错。