一、Linux物理内存外碎片概述什么是Linux物理内存碎片？Linux物理内存碎片包括两种类型：1.物理内存内碎片：指分配给用户的内存中未使用的部分空间。比如一个进程需要使用3K字节的物理内存，所以它向系统申请了等于3K字节的内存，但是由于Linux内核伙伴系统算法的最小粒度是4K字节，所以它分配了4K字节的内存，未使用的1K字节内存为In-memoryfragmentation。FragmentationinLinuxphysicalmemory2.Fragmentationoutsidephysicalmemory：指系统中不能使用的小内存块。例如，剩余系统内存为16K字节，但是16K字节内存是由4个4K字节的页组成的，即16K内存的物理页框号#1是不连续的。在系统剩余16K字节内存的情况下，系统无法成功分配大于4K的连续物理内存。这种情况是由内存碎片不足引起的。本文介绍物理内存碎片。注：#1物理页框号：Linux物理内存是通过页来管理的，每页都有编号，称为页框号。如果有两个连续的物理页，则页框号是连续的。Linux物理内存外分片二、Linux物理内存管理框架在讲解物理内存外分片的来??龙去脉之前，首先要了解Linux是如何管理物理内存的？Linux内核使用buddysystemallocation，大名鼎鼎的buddysystemallocator。1.设计思路伙伴系统分配器的核心思想：将系统的空闲页划分为11个块列表，每个块列表管理1、2、4、8、16、32、64、128、256、512和1024个物理页框是连续的页。每个页面大小为4K字节，buddy管理的块大小从4K字节到4M字节，以2的倍数递增。Linux物理内存管理框架图2.管理逻辑Linux的物理页面管理框架如上图数字。由于本文描述的是物理内存之外的碎片，本文只对伙伴系统做简单的分析，不涉及具体细节。它没有详细说明percpupageset等内容，如果读者有兴趣，可以参考内核源码。Linux将物理内存划分为不同的节点和区域进行管理：节点：为了支持NUMA结构，即CPU对不同的内存簇有不同的访问速度，Linux设计了节点结构，将物理内存划分为多个内存管理节点；对于UMA结构，只有一个node节点。zone：为了兼容不同平台的硬件限制，比如80x86架构的硬件总线访问，Linux将node节点下的内存划分为多个zone；目前在ARM平台上，不再需要多区域管理。zone管理单元下的内存是通过free_area数组将内存分成11个块链表来管理的：free_area数组一共有11个索引，每个索引管理不同大小的块链表。free_area[0]管理的内存单元为2^0页，即4K字节内存；free_area[1]管理的内存单元为2^1个物理页框号连续页，即8K字节内存；等等;free_areamanagement内存也被细分为各种类型，比如不可移动的页面和可移动的页面，每一种页面类型对应一个free_list链表，链接页面结构。伙伴系统在分配页面时，采取以下步骤：（不考虑内存慢路径）根据分配的页面类型找到对应的内存节点node和内存管理单元zone；根据分配的页面大小找到对应的free_area结构根据分配页面的类型，找到对应的free_list链表并分配页面；伙伴系统释放页面时，buddy释放页面的步骤如下：根据分配页面的类型，找到对应的内存节点node和内存管理单元zone；判断与物理页框号相连的空闲内存块是否可以与释放的内存块合并，形成更大的块内存。合并条件：物理帧必须连续；相同类型和相同尺寸；合并后的块内存第一页的物理地址满足“2*blocksize*4K”的倍数。根据释放页面的大小或者合并的大小，找到对应大小的free_area结构体；根据释放页面的类型，找到对应的free_list链表，释放页面；3.Linux对物理内存外碎片的措施从《2.Linux物理内存管理架构》可以发现伙伴系统的内存管理框架可以有效改善物理内存外的碎片，因为伙伴系统有下面两种管理逻辑，可以减少外部碎片的产生：小块内存由小块链表分配，减少大块链表被污染的概率；当内存释放时，会尝试整合大块内存的逻辑，有助于大块内存的合成；此外，内核还支持以下措施来改善物理内存之外的碎片化（仅列出主要机制）：1.memorycompaction（1）内存压缩原理Linux物理页面压缩机制，类似于磁盘碎片整理，主要应用内核的页面迁移机制sm，这是一种迁移可移动页面以释放连续页面的方法。物理内存的方法。假设有一个非常小的内存域如下：蓝色表示空闲页面，白色表示已经分配的页面。可以看到上面内存域中的空闲页面（蓝色）非常碎片化，无法分配大于两个页面的连续物理内存。.下面演示内存正则化的简化工作原理。内核会运行两个独立的扫描动作：第一次扫描从内存域底部开始，扫描时将分配的可移动（MOVABLE）页记录到一个列表中：另外，第二次扫描从内存域顶部开始，扫描可以作为页面迁移目标的空闲页面位置，然后记录在一个列表中：当两次扫描在域中间相遇时，表示扫描结束，再扫描左边将得到的分配页迁移到右边的空闲页，左边形成连续的物理内存，完成页正则化。(2)如何使用如果要开启内存正则化，内核需要开启相关配置（默认为y）。启用上述配置后，会自动触发内存正则化。触发内存正则化的方式如下：当一个进程试图分配高位内存不能满足并完成direct_reclaim#1后（costly_order情况暂不分析），系统会根据判断是否触发内存正则化到剩余的内存；注意：#1direct_reclaim：当进程在分配内存时发现内存不足，就开始直接回收内存。在这种模式下，分配和回收是同步的关系，也就是说分配内存的进程会因为等待内存回收而被阻塞。内核还为用户提供了一个接口来触发压缩操作。接口如下：/proc/sys/vm/compact_memory只需向该节点写入一个值，即可触发系统中所有由节点管理的内存的内存压缩。2.kcompactd(1)kcompact设计原则kcompactd是一个常规的内核后台进程。它和memorycompaction的区别在于，memorycompaction是内存分配到direct_reclaim中触发的（costly_order暂不分析），系统会根据剩余内存判断是否触发memorycompaction，还是用户手动触发;当kswapd唤醒或kswapd进入睡眠时，kcompactd主动触发内存压缩。kcompactd的触发路径如下：主要有两种方式：在唤醒kswapd之前触发正则化，触发条件为：本次分配不支持direct_reclaim，节点内存节点均衡，kswapd失败次数大于MAX_RECLAIM_RETRIES（默认16）。当kswapd即将进入休眠状态时：(2)如何使用如果要开启内存正则化，内核需要开启相关配置（默认为y）3.其他优化思路内核一直在不断优化，所以为什么Linux在物理内存之外还有碎片？碎片化呢？那是因为物理内存之外的碎片虽然可以不断优化，但是无法根除。在目前的内核中，物理环境之外的碎片我认为主要有两个原因：不可移动的页面污染了内存环境，导致页面正则化失败；随着系统不断申请和释放页面，导致伙伴系统分配的物理内存页帧数越随机，内存被隔离的概率越高，碎片化程度越高，在3.2中解释.基于以上两点原因，以下优化措施可能会达到一定的优化效果：(1)减少UNMOVABLE页面对内存环境的污染，限制不可移动页面的页面窃取行为。Linux内存分配支持fallback机制，也称为pagestealing机制。这种机制是为了避免同一区域管理单元中剩余页类型不均衡的问题。例如，在同一个区域中，页面类型A的空闲内存较多，而页面类型B的空闲内存很少。如果没有pagestealing机制，分配的pagetypeB就会进入内存分配的慢路。有了pagestealing机制，在同一个zonemanagementunit中，如果没有UNMOVABLE类型的空闲页，但是MOVABLE类型的页还有空闲页，pagestealing机制支持list_head[UNMOVABLE]不能分配页到的情况list_head[MOVABLE]]来分配页面。以下数组指定了各种页面类型可以窃取的页面类型。比如第一行表示UNMOVABLEpages可以窃取RECLAIMABLE和MOVABLEpages，其他类似。如果不可移动页经常被盗，那么不可移动页会很快污染内存环境，尤其是可移动页的内存，对内存正则化的成功率有很大的影响。基于以上情况，可以在窃页机制中加入allocationsizelimit的判断。只有大块内存分配的不可移动页面才允许窃取页面，以减少不可移动页面对内存环境的污染。不可移动类页面盗页后主动还款法主要是针对不可移动类页面盗页的一种补偿方法。如果一个不可移动页面被盗，我们将该页面记录在一个列表中，当后续的不可移动页面类型有空闲页面时，我们将被盗页面迁移回不可移动页面，从而减少污染不可移动的页面。(2)降低分配页框号的随机性假设有一块较小的内存区域如下，下面两种内存分配方式，哪种会造成严重的内存碎片？页是从头到尾分配的；页面是从任何位置随机分配的。显然，第二种内存分配方式对out-of-memoryfragmentation不太友好，这也是伙伴系统还没有解决的问题。虽然伙伴系统将内存规划成各种大小的内存块，让小内存分配在小块链表中，尽量不污染大块内存链表，但是没办法保证哪个页框小内存块在范围分配中的物理内存。系统运行时间越长，小块内存分配的物理页框数越随机，产生碎片的概率就越高。根据这种情况，可以相应优化预订方式。保留一定量的内存用于小块内存分配。通过这种优化措施，可以有效降低小块内存分配的物理页框数的随机性，从而降低小块内存污染内存环境的概率。保留一定量的内存用于大块内存的分配。经过这种优化措施后，保留内存被小块内存污染的概率会降低，可以提高从保留内存中分配大块内存的成功率。此外，还有很多优化措施来降低伙伴系统分配的页框号的随机性。后续会根据需要开发一篇文章对这部分优化进行说明。读者有兴趣的话，到时候可以参考一下。参考资料1、内核源码2、http://tinylab.org/lwn-368869/3、https://patchwork.kernel.org/patch/
