1 前景提要

1.1 碎片化问题

分页与分段

页是信息的物理单位, 分页是为了实现非连续分配, 以便解决内存碎片问题, 或者说分页是由于系统管理的需要. 段是信息的逻辑单位,它含有一组意义相对完整的信息, 分段的目的是为了更好地实现共享, 满足用户的需要.

页的大小固定且由系统确定, 将逻辑地址划分为页号和页内地址是由机器硬件实现的. 而段的长度却不固定, 决定于用户所编写的程序, 通常由编译程序在对源程序进行编译时根据信息的性质来划分.

分页的作业地址空间是一维的. 分段的地址空间是二维的.

内部碎片与外部碎片

在页式虚拟存储系统中, 用户作业的地址空间被划分成若干大小相等的页面, 存储空间也分成也页大小相等的物理块, 但一般情况下, 作业的大小不可能都是物理块大小的整数倍, 因此作业的最后一页中仍有部分空间被浪费掉了. 由此可知, 页式虚拟存储系统中存在内碎片.

在段式虚拟存储系统中, 作业的地址空间由若干个逻辑分段组成, 每段分配一个连续的内存区, 但各段之间不要求连续, 其内存的分配方式类似于动态分区分配.由此可知, 段式虚拟存储系统中存在外碎片.

在内存管理中, “内零头”和”外零头”个指的是什么?

在固定式分区分配, 可变式分区分配, 页式虚拟存储系统, 段式虚拟存储系统中, 各会存在何种碎片? 为什么?

解答:

在存储管理中

• 内碎片是指分配给作业的存储空间中未被利用的部分

在固定式分区分配中, 为将一个用户作业装入内存, 内存分配程序从系统分区表中找出一个能满足作业要求的空闲分区分配给作业, 由于一个作业的大小并不一定与分区大小相等, 因此, 分区中有一部分存储空间浪费掉了. 由此可知, 固定式分区分配中存在内碎片.

• 外碎片是指系统中无法利用的小存储块.

在可变式分区分配中, 为把一个作业装入内存, 应按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业, 如果这个空闲分区的容量比作业申请的空间容量要大, 则将该分区一分为二, 一部分分配给作业, 剩下的部分仍然留作系统的空闲分区。由此可知，可变式分区分配中存在外碎片.

简言之

随着存储区的分配和释放过程的进行, 在各个被分配出去的分区之间会存在很多的小空闲区, 暂时不能被利用, 这就是”外部碎片”.

在固定分区管理算法中, 分给程序的内存空间往往大于程序所需的空间, 这剩余部分的空间不能被其他程序所用, 这就是”内部碎片”

1.2 今日内容(buddy伙伴系统如何避免碎片)

Linux伙伴系统分配内存的大小要求2的幂指数页, 这也会产生严重的内部碎片.

伙伴系统的基本原理已经在前面已经讨论过, 一个双链表即可满足伙伴系统的所有需求, 其方案在最近几年间确实工作得非常好。但在Linux内存管理方面，有一个长期存在的问题 : 在系统启动并长期运行后，物理内存会产生很多碎片。该情形如下图所示

但对内核来说，碎片是一个问题. 由于(大多数)物理内存一致映射到地址空间的内核部分, 那么在左图的场景中, 无法映射比一页更大的内存区. 尽管许多时候内核都分配的是比较小的内存, 但也有时候需要分配多于一页的内存. 显而易见, 在分配较大内存的情况下, 右图中所有已分配页和空闲页都处于连续内存区的情形，是更为可取的.

很有趣的一点是, 在大部分内存仍然未分配时, 就也可能发生碎片问题. 考虑下图所示的情形.

只分配了4页，但可分配的最大连续区只有8页，因为伙伴系统所能工作的分配范围只能是2的幂次.

我提到内存碎片只涉及内核，这只是部分正确的。大多数现代CPU都提供了使用巨型页的可能性，比普通页大得多。这对内存使用密集的应用程序有好处。在使用更大的页时，地址转换后备缓冲器只需处理较少的项，降低了TLB缓存失效的可能性。但分配巨型页需要连续的空闲物理内存!

很长时间以来，物理内存的碎片确实是Linux的弱点之一。尽管已经提出了许多方法，但没有哪个方法能够既满足Linux需要处理的各种类型工作负荷提出的苛刻需求，同时又对其他事务影响不大。

目前Linux内核为解决内存碎片的方案提供了两类解决方案

• 依据可移动性组织页避免内存碎片
• 虚拟可移动内存域避免内存碎片

2 依据可移动性组织页避免内存碎片

依据可移动性组织页是方式物理内存碎片的一种可能方法.

2.1 依据可移动性组织页

在内核2.6.24开发期间，防止碎片的方法最终加入内核。在我讨论具体策略之前，有一点需要澄清。

文件系统也有碎片，该领域的碎片问题主要通过碎片合并工具解决。它们分析文件系统，重新排序已分配存储块，从而建立较大的连续存储区. 理论上，该方法对物理内存也是可能的，但由于许多物理内存页不能移动到任意位置，阻碍了该方法的实施。因此，内核的方法是反碎片(anti-fragmentation), 即试图从最初开始尽可能防止碎片.

反碎片的工作原理如何?

为理解该方法，我们必须知道内核将已分配页划分为下面3种不同类型。

页面类型	描述	举例
不可移动页	在内存中有固定位置, 不能移动到其他地方.	核心内核分配的大多数内存属于该类别
可移动页	可以随意地移动.	属于用户空间应用程序的页属于该类别. 它们是通过页表映射的 如果它们复制到新位置，页表项可以相应地更新，应用程序不会注意到任何事
可回收页	不能直接移动, 但可以删除, 其内容可以从某些源重新生成.	例如，映射自文件的数据属于该类别 kswapd守护进程会根据可回收页访问的频繁程度，周期性释放此类内存. , 页面回收本身就是一个复杂的过程. 内核会在可回收页占据了太多内存时进行回收, 在内存短缺(即分配失败)时也可以发起页面回收.

页的可移动性，依赖该页属于3种类别的哪一种. 内核使用的反碎片技术, 即基于将具有相同可移动性的页分组的思想.

为什么这种方法有助于减少碎片

由于页无法移动, 导致在原本几乎全空的内存区中无法进行连续分配. 根据页的可移动性, 将其分配到不同的列表中, 即可防止这种情形. 例如, 不可移动的页不能位于可移动内存区的中间, 否则就无法从该内存区分配较大的连续内存块.

想一下, 上图中大多数空闲页都属于可回收的类别, 而分配的页则是不可移动的. 如果这些页聚集到两个不同的列表中, 如下图所示. 在不可移动页中仍然难以找到较大的连续空闲空间, 但对可回收的页, 就容易多了.

但要注意, 从最初开始, 内存并未划分为可移动性不同的区. 这些是在运行时形成的. 内核的另一种方法确实将内存分区, 分别用于可移动页和不可移动页的分配, 我会下文讨论其工作原理. 但这种划分对这里描述的方法是不必要的

2.2 迁移类型

尽管内核使用的反碎片技术卓有成效，它对伙伴分配器的代码和数据结构几乎没有影响。内核定义了一些枚举常量(早期用宏来实现)来表示不同的迁移类型, 参见include/linux/mmzone.h?v=4.7, line 38

enum {
        MIGRATE_UNMOVABLE,
        MIGRATE_MOVABLE,
        MIGRATE_RECLAIMABLE,
        MIGRATE_PCPTYPES,       /* the number of types on the pcp lists */
        MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
        /*
         * MIGRATE_CMA migration type is designed to mimic the way
         * ZO