天天看点
返回

反碎片化技术(外部碎片)的原理反碎片化技术(外部碎片)

主要参考了《深入linux内核》和《Linux内核深度解析》，另外简单浅析了一下相关内容

文章目录

  • 反碎片化技术(外部碎片)
    • 虚拟可移动区域
      • 使用方法
      • 技术原理
        • 解析内核引导参数
        • 确定可移动区域的范围
        • 从可移动区域分配物理页
    • 内存碎片整理
      • 使用方法
      • 技术原理
      • 内存碎片整理流程源码分析
        • alloc _pages _slowpath页分配器慢速路径
        • __alloc_pages_direct_compact 内存碎片整理

反碎片化技术(外部碎片)

如何避免Linux的物理内存碎片化

内存碎片可分为内部碎片和外部碎片，

  • 内部碎片指内存页里面的碎片
  • 外部碎片指空闲的内存页分散，很难找到一组物理地址连续的空闲内存页，无法满足超过一页的内存分配请示。

对于内核来说，外部碎片是一个问题，内核有时候需要分配超过一页的物理内存，因为内核使用线性映射区域的虚拟地址，所以必须分配连续的物理页。

意思是内核的虚拟地址已经于物理地址进行了一对一的线性映射（总体），除了vmalloc，只能分配连续的物理页（对应连续的虚拟地址）。

为解决外部碎片问题，内核引入反碎片技术：

a)2.6.33版本引入虚拟可移动区域;

b)2.6.23版本引入成块回收(集中回收)，从3.5版本废除，被内存碎片整理技术取代。

成块回收不是一个完整的解决方案，它只是缓解了碎片问题。成块回收，就是尝试成块回收目标页相邻的页面，以形成一块满足需求的高阶连续页块。这种方法有其局限性，就是成块回收时没有考虑被连带回收的页面可能是“热页”，即被高强度使用的页，这对系统性能是损伤。

c）2.6.24版本引入了根据可移动性分组的技术，把物理页分为不可移动页、可移动页和可回收页3种类型，伙伴分配器中已经介绍了这种反碎片技术。

  1. 不可移动页面 unmoveable：在内存中位置必须固定，无法移动到其他地方，核心内核分配的大部分页面都属于这一类。
  2. 可回收页面 reclaimable：不能直接移动，但是可以回收，因为还可以从某些源重建页面，比如映射文件的数据属于这种类别，kswapd会按照一定的规则，周期性的回收这类页面。
  3. 可移动页面 movable：可以随意的移动。属于用户空间应用程序的页属于此类页面，它们是通过页表映射的，因此我们只需要更新页表项，并把数据复制到新位置就可以了，当然要注意，一个页面可能被多个进程共享，对应着多个页表项。

d）2.6.35版本引入了内存碎片整理技术。

虚拟可移动区域 和 根据可移动性分组 是 预防 外部碎片的技术，成块回收 和 内存碎片整理 是在出现外部碎片以后 消除 外部碎片的技术。

虚拟可移动区域

ZONE_MOVABLE和页面分类方法好处是很明显的：固定UNMOVABLE zone的大小（页面分类链表是动态生成的），UNMOVABLE zone供内核关键分配函数使用。系统频繁申请的MOVABLE分配，不会导致unmovable zone的碎片化。但是缺点仍然很明显，即RECLAIMABLE分配还是使用unmovable zone，频繁的分配回收仍然使得unmovable zone碎片化。

所以看起来，ZONE_MOVABLE方法只是缓解了物理内存碎片化，但是并没有完全解决。

可移动区域(ZONE_MOVABLE)是一个伪内存区域，基本思想是：把物理内存分为两个区域，一个区域用于分配不可移动的页，另一个区域用于分配可移动的页，防止不可移动页向可移动区域（无碎片）引入碎片。

使用方法

可移动区域必须由管理员配置，配置方法如下。

（1）使用内核引导参数“kernelcore=nn[KMGTPE]”（K表示单位是KB，M表示单位是MB）指定不可移动区域的大小；也可以使用“kernelcore=mirror”指定使用镜像的内存作为不可移动区域，使用其他内存作为可移动区域。

内存镜像是内存冗余技术的一种，是为了提高服务器的可靠性，防止内存故障导致服务器的数据永久丢失或者系统宕机。内存镜像的工作原理与硬盘的热备份类似，内存镜像是将内存数据做两个拷贝，分别放在主内存和镜像内存中。系统工作时会向两个内存中同时写入数据，因此使得内存数据有两套完整的备份。

（2）使用内核引导参数“movablecore=nn[KMG]”指定可移动区域的大小。

（3）如果同时指定参数kernelcore和movablecore，那么不可移动区域的大小取参数kernelcore和（物理内存容量 − 参数movablecore）的最大值。

默认认为巨型页是不可移动的，不会从可移动区域分配巨型页，可以通过文件“/proc/ sys/vm/hugepages_treat_as_movable”配置允许从可移动区

域分配巨型页。

在NUMA系统上，如果打开配置宏CONFIG_MOVABLE_NODE（允许一个内存节点只有可移动的内存），并且指定内核引导参数“movable_node”，那么忽略内核引导参数“kernelcore”和“movablecore”，所有可以热插拔的物理内存都作为可移动区域。

技术原理

可移动区域(ZONE_MOVABLE)没有包含任何物理内存，所以我们说它是伪内存区域，或者说是虚拟的内存区域。可移动区域借用最高内存区域的内存，在32位系统上最高的内存区域通常是高端内存区域(ZONE_HIGHMEM)，在64位系统上最高的内存区域通常是普通区域(ZONE_NORMAL)。

解析内核引导参数

  1. 函数cmdline_parse_kernelcore解析内核引导参数“kernelcore”，其代码如下：

mm/page_alloc.c

static int __init cmdline_parse_kernelcore(char *p)
{
    /* 解析kernelcore=mirror */
    // 如果值是“mirror”，那么把全局变量mirrored_kernelcore设置为真，表示把镜像的内存作为不可移动区域。
    if (parse_option_str(p, "mirror")) {
         mirrored_kernelcore = true;
         return 0;
    }
    
    // 如果值是不可移动区域的大小，那么使用全局变量required_kernelcore保存不可移动区域的大小。
    return cmdline_parse_core(p, &required_kernelcore);
}
early_param("kernelcore", cmdline_parse_kernelcore);
  1. 函数cmdline_parse_movablecore解析内核引导参数“movablecore”，使用全局变量required_movablecore保存可移动区域的大小，其代码如下：

mm/page_alloc.c

static int __init cmdline_parse_movablecore(char *p)
{
     return cmdline_parse_core(p, &required_movablecore);
}
early_param("movablecore", cmdline_parse_movablecore);
  1. 函数 cmdline_parse_movable_node 解析内核引导参数“movable_node”，把全局变量movable_node_enabled设置为真，表示所有可以热插拔的物理内存都作为可移动区域，其代码如下 
static int __init cmdline_parse_movable_node(char *p)
{
#ifdef CONFIG_MOVABLE_NODE
     movable_node_enabled = true;
#else
     pr_warn("movable_node option not supported\n");
#endif
     return 0;
}
early_param("movable_node", cmdline_parse_movable_node);

确定可移动区域的范围

函数find_zone_movable_pfns_for_nodes确定可移动区域的范围。

1）确定可移动区域从哪个内存区域借用物理页：调用函数find_usable_zone_for_movable以查找包含物理页的最高内存区域，全局变量movable_zone保存借用区域的索引。

2）确定每个内存节点中可移动区域的起始物理页号，使用全局数组zone_movable_pfn[MAX_NUMNODES]保存，分3种情况。

  • 使用可以热插拔的物理内存作为可移动区域。
  • 使用镜像内存作为不可移动区域，使用其他内存作为可移动区域。
  • 如果管理员配置了不可移动区域或可移动区域的大小，处理如下：
    • 如果同时指定参数kernelcore和movablecore，那么不可移动区域的大小取参数kernelcore和（物理内存容量 − 参数movablecore）的最大值；把不可移动区域的内存按比例分布到所有内存节点上。

函数calculate_node_totalpages负责计算一个内存节点中所有内存区域的起始物理页号和物理页总数，针对每个内存区域，调用函数

zone_spanned_pages_in_node来计算内存区域的起始物理页号和结束物理页号。

1）从全局数组arch_zone_lowest_possible_pfn和arch_zone_highest_possible_pfn中分别得到内存区域的起始物理页号和结束物理页号。

2）调用函数adjust_zone_range_for_zone_movable，根据数组zone_movable_pfn修正借用区域的结束物理页号，以及得到可移动区域的起始物理页号。

从可移动区域分配物理页

申请物理页的时候，如果同时指定了分配标志 __GFP_HIGHMEM 和 __GFP_MOVABLE ，页分配器的核心函数 __alloc_pages_nodemask（->prepare_alloc_pages -> gfp_zone）计算出首选的内存区域是可移动区域，首先尝试从可移动区域分配物理页。如果可移动区域分配失败，从备用的内存区域借用物理页。

分配标志 __GFP_MOVABLE有两个用处。

1）和 __GFP_HIGHMEM组合表示从可移动区域分配物理页。

2）在根据可移动性分组技术中表示申请迁移类型是可移动类型的物理页。为用户空间分配物理页时，通常使用分配标志组合GFP_HIGHUSER_MOVABLE，这个组合包含标志 __GFP_HIGHMEM和 __GFP_MOVABLE。

include/linux/gfp.h

#define GFP_USER     (__GFP_RECLAIM | __GFP_IO | __GFP_FS | __GFP_HARDWALL)
#define GFP_HIGHUSER            (GFP_USER | __GFP_HIGHMEM)
#define GFP_HIGHUSER_MOVABLE    (GFP_HIGHUSER | __GFP_MOVABLE)

例如，进程访问匿名页的时候，如果没有映射到物理页，生成页错误异常。页错误异常处理程序在函数do_anonymous_page中调用函数

alloc_zeroed_user_highpage_movable以分配物理页，函数alloc_zeroed_user_highpage_movable使用分配标志组合GFP_HIGHUSER_MOVABLE分配物理页。

内存碎片整理

内存碎片整理（memory compaction，直译为“内存紧缩”，意译为“内存碎片整理”）的基本思想是：从内存区域的底部扫描已分配的可移动页，从内存区域的顶部扫描空闲页，把底部的可移动页移到顶部的空闲页，在底部形成连续的空闲页。

使用方法

编译内核时，如果需要内存碎片整理功能，必须开启配置文件“mm/kconfig"定义的配置宏CONFIG_COMPACTION，默认开启状态。

内存碎片整理技术提供配置文件:

  1. 文件" /proc/sys/vm/compact_memory":向这个文件写入任何整数值（数值没有意义)，触发内存碎片整理。
  2. 文件"proc/sys/vm/compact _unevictable_allowed”:此文件用来是否允许内存碎片整理移动不可回收的页（进程使用系统调用mlock把页锁定在内存当中)，如果设置为1，表示允许,默认值是1。

  3. 文件“proc/sys/vm/extfrag_threshold":用来设置外部碎片的阈值，取值范围是0-1000，默认值是500。这个参数影响内核在申请连续页失败的时候选择直接回收页还是选择内存碎片整理。

    内核计算出内存区域的碎片指数，碎片指数趋向0表示分配失败是因为内存不足，碎片指数趋向1000表示分配失败是因为内存碎片。如果碎片指数小于或等于外部碎片的阈值，选择直接回收页；如果碎片指数大于阈值，那么选择内存碎片整理。

技术原理

我们假设有一个很小的内存区域，包含16个页，如图3.97所示。

反碎片化技术(外部碎片)的原理反碎片化技术(外部碎片)

白色表示页是空闲的，这个内存区域已经碎片化。最大的连续空闲页是两页，从这个区域分配四页将会失败，甚至分配两页也会失败，因为连续的两个空闲页的起始地址没有对齐到两页的整数倍。

首先，内存碎片整理算法从内存区域的底部向顶部扫描，把可以移动的已分配页组成一条链表，我们把这个扫描称为迁移扫描器，如图3.98所示。

反碎片化技术(外部碎片)的原理反碎片化技术(外部碎片)

然后，内存碎片整理算法从内存区域的顶部向底部扫描，把空闲的页组成一条链表，我们把这个扫描称为空闲扫描器，如图3.99所示。

反碎片化技术(外部碎片)的原理反碎片化技术(外部碎片)

最后，迁移扫描器和空闲扫描器在内存区域的中间相遇，把可以移动的已分配页移到顶部的空闲页，形成连续的8个空闲页，可以满足申请连续8页的需求，如图3.100所示。

反碎片化技术(外部碎片)的原理反碎片化技术(外部碎片)

在真实的系统中，内存区域大得多，内存碎片整理以内存区域 (zone) 为单位执行，在内存区域内部以分组页块（参考3.7.3节）为单位执行。

内存碎片整理算法

  1. 首先从内存区域的底部向顶部以页块为单位扫描，在页块内部从起始页向结束页扫描把这个页块里面的可移动页组成一条链表;
  2. 然后从内存区域的顶部向底部以页块为单位扫描，在页块内部也是从起始页向结束页扫描，把空闲页组成一条链表;
  3. 相遇停止或者有足够的空闲页，最后把底部的可移动页的数据复制到顶部的空闲页，修改进程的页表，把虚拟页映射到新的物理页。

内存碎片整理优先级:

（1）COMPACT_PRIO_SYNC_FULL：完全同步模式，允许阻塞，允许把脏的文件页回写到存储设备上，并且等待回写完成。

（2）COMPACT_PRIO_SYNC_LIGHT：轻量级同步模式，允许大多数操作阻塞，但是不允许把脏的文件页回写到存储设备上（因为可能需要等待很长的时间）。

（3）COMPACT_PRIO_ASYNC：异步模式，不允许阻塞。

完全同步模式成本最高，轻量级同步模式的成本其次，异步模式的成本最低。

执行内存碎片整理的时机如下

（1）页分配器使用最低水线分配页失败以后，如果调用者允许直接回收页（即设置了分配标志__GFP_DIRECT_RECLAIM）和写存储设备（即设置了分配标志__GFP_IO），并且是昂贵的分配（申请的阶数大于 3）或者申请不可移动类型的连续页，那么在尝试直接回收页之前，先尝试执行异步模式的内存碎片整理。

（2）页分配器直接回收页以后分配连续页仍然失败，如果调用者允许写存储设备，尝试执行轻量级同步模式的内存碎片整理。

（3）每个内存节点有一个页回收线程和一个内存碎片整理线程，当页回收线程准备睡眠一小段时间的时候，唤醒内存碎片整理线程，内存碎片整理线程执行轻量级同步模式的内存碎片整理。内存碎片整理线程的名称是“kcompactd<node_id>”，内存节点的pglist_data 实例的成员“kcompactd”指向内存碎片整理线程的进程描述符。

（4）当管理员向文件“/proc/sys/vm/compact_memory”写入任何整数值的时候，在所有内存节点的所有内存区域上执行完全同步的内存碎片整理。

如何判断一个内存区域是否适合执行内存碎片整理标准?

  1. 如果系统管理员通过写文件"proc/sys/vm/compact_memory”触发内存碎片整理，那么这个内存区域强制执行内存碎片整理。
  2. 如果内存区域同步满足3个条件，适合执行内存碎片整理:
    1. 如果(空闲页数-申请页数)低于水线，或者虽然大于或等于水线但是没有一个足够大的空闲页块，那么这个内存区域适合执行内存碎片整理。
    2. 如果（空闲页数-两倍的申请页数)大于或等于水线，说明有足够多的空闲页作为迁移的目的地，那么这个内存区域适合执行内存碎片整理。
    3. 对于昂贵的分配（阶数大于3)，计算碎片指数，如果碎片指数在范围[0,外部碎片的阈值]以内，说明分配失败是内存不足够导致的，不是外部碎片导致的，那么这个内存区域不适合执行内存碎片整理。
      • 如果不存在空闲页块，那么碎片指数 = 0。
      • 如果至少存在一个足够大的空闲页块，那么碎片指数 = −1000。
      • 其他情况，碎片指数 = 1000 −（1000 + 1000 * 空闲页数 / 申请页数）/ 空闲页块的总数。

    碎片指数趋向0表示分配失败是因为内存不足，趋向1000表示分配失败是因为外部碎片。外部碎片的阈值是内存不足和外部碎片的分界线：如果碎片指

    数小于或等于阈值，分配失败是因为内存不足，应该直接回收页；如果碎片指数大于阈值，分配失败是因为外部碎片，应该执行内存碎片整理。

内存碎片整理结束条件如下

  • 如果迁移扫描器和空闲扫描器相遇，那么内存碎片整理结束
  • 如果迁移扫描器和空闲扫描器没有相遇，但是申请或备用的迁移类型至少有一个足够大的空闲页块，那么内存碎片整理结束。

内存碎片整理推迟

内存碎片整理成功的标准是：（空闲页数 − 申请页数）大于或等于水线，并且申请或备用的迁移类型至少有一个足够大的空闲页块。

执行完全同步模式或轻量级同步模式的内存碎片整理，当迁移扫描器和空闲扫描器相遇的时候，没有达到成功标准，以后试图执行轻量级同步或异步模式的内存碎片整理，如果申请阶数大于或等于内存碎片整理失败时的申请阶数，需要推迟若干次。

内核在内存区域中增加了3个成员用来记录内存碎片整理推迟的信息：

struct zone {
     …
#ifdef CONFIG_COMPACTION
     unsigned int   compact_considered;
     unsigned int   compact_defer_shift;
     int            compact_order_failed;
#endif
    …
}

（1）成员compact_considered记录推迟的次数。

（2）成员compact_defer_shift是推迟的最大次数以2为底的对数，当推迟的次数达到（1 << compact_defer_shift）时，不能推迟。

  • 每次内存碎片整理执行失败，把成员compact_defer_shift加1（每次失败，推迟次数翻倍），不允许超过COMPACT_MAX_DEFER_SHIFT（值为6），即把推迟的最大次数翻倍，但是不能超过64。
  • 页分配器在执行内存碎片整理以后，如果分配页成功，那么把成员compact_defer_shift设置为0。

（3）成员compact_order_failed记录内存碎片整理失败时的申请阶数。

内存碎片整理执行成功的时候，如果申请阶数order大于或等于成员compact_order_failed，那么把成员compact_order_failed设置为（order+1）。

内存碎片整理执行失败的时候，如果申请阶数order小于成员compact_order_failed，那么把成员compact_order_failed设置为order。

内存碎片整理流程源码分析

alloc _pages _slowpath页分配器慢速路径

  • 函数_alloc _pages_nodemask是页分配器的核心函数，函数alloc _pages _slowpath是页分配器慢速路径，执行内存碎片整理，页分配器执行内存碎片整理流程如下:
反碎片化技术(外部碎片)的原理反碎片化技术(外部碎片)

__alloc_pages_direct_compact 内存碎片整理

反碎片化技术(外部碎片)的原理反碎片化技术(外部碎片)
linux 内核内存管理 Linux 反碎片化
上一篇: 需求管理手册-需求工程的流程环节（4）需求获取
下一篇: 《Effective Java 3rd》读书笔记——创建和销毁对象

继续阅读