提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
伙伴系统（buddy system）如何分配内存
前言
Linux操作系统是如何实现内存管理的？
在Linux中，伙伴系统用来管理物理内存页面，SLAB分配器用来分配比页更小的内存对象。
一、如何表示一个页？
Linux也是使用分页机制管理物理内存的，Linux将物理内存分成4KB大小的页面进行管理。早期Linux使用位图，后来使用字节数组，现在Linux定义了一个page结构体来表示一个页。page结构中大量使用了union联合定义结构字段，所以page实际占用20~40个字节空间。page通过flags表示它处于哪种状态，根据不同的状态来使用union联合体变量表示的数据信息。如果page处于空闲状态，它就会使用union联合体中的lru字段，挂载到对应空闲链表中。（一个page结构表示一个物理内存页面）。
二、如何表示一个区
Linux内核中也有区的逻辑概念，因为硬件的限制，Linux内核不能对所有的物理内存页面同一对待，所以就把属性相同的物理内存页面，归结到一个区中。
不同硬件平台，区的划分也不一样。比如在32位的x86平台中，一些使用DMA的设备只能访问0~16MB的物理空间，因此将这个划分为DMA区。
高内存区适合要访问的物理内存地址空间大于虚拟内存地址空间，Linux内核不能建立直接映射的情况。除开这两个内存区，物理内存中剩余页面就划分到常规的内存区中了。
Linux内核用zone数据结构表示一个区。其中_watermark表示内存页面总量的水位线有min、low、high三种状态，可以作为启动内存页面回收的判断标准。spanned_pages是该内存区总的页面数。
present_pages字段表示真正存在的页面数。（内存区中存在内存空洞，空洞对应的page结构不能用。）
在zone结构中，真正要关注free_area结构的数组，这个数组就是用于实现伙伴系统的。其中MAX_ORDER的默认值是11，分别表示挂载地址连续page的数目为1,2,4…最大为1024。
free_area结构中，又是一个list_head链表数组，该数组将具有相同迁移类型的page尽可能分组，有的页面可以迁移，有的不可以迁移，同一类型的所有相同oreder的page结构，就构成一组page结构块。
分配的时候，会按请求的migratetype从对应的page结构块中寻找，如果不成功，才会从其他migratetype的page结构块中分配。这样做是为了让内存页迁移更加高效，可以有效降低内存碎片。
三、怎样表示一个内存节点
1.NUMA–Non-Uniform Memory Access（非一致性内存访问）
在很多服务器和大型计算机上，如果物理内存是分布式的，有多个计算节点组成，那么每个CPU核都会有自己的本地内存，CPU在访问它的本地内存的时候就会比较快，访问其他CPU核内存的时候就比较慢。
Linux 对 NUMA 进行了抽象，它可以将一整块连续物理内存的划分成几个内存节点，也可以把不是连续的物理内存当成真正的 NUMA。
用pglist_data表示内存节点，pglist_data结构中包含了zonelist数组。第一个zonelist类型的元素指向本节点内的zone数组，第二个zonelist类型的元素指向其他节点的zone数组，而一个zone结构中的free_area数组中又挂载着page结构。
这样在本节点分配不到内存页面，就会在其他节点中分配内存页面，当计算机不是NUMA时，Linux就只创建一个节点。
三、数据结构之间的关系
四、伙伴系统
首先最小的 page（0,1）是伙伴，page（2,3）是伙伴，page（4,5）是伙伴，page（6,7）是伙伴，然后 A 与 B 是伙伴，C 与 D 是伙伴，最后 E 与 F 是伙伴.
五、分配页面
首先要找到内存节点，接着找到内存区，然后合适的空闲链表，最后在其中找到页的page结构，完成物理内存的分配。
六、通过接口找到内存节点
上图中，虚线框中为接口函数，下面则是分配内存页面的核心实现，所有的接口函数都会调用到 alloc_pages 函数，而这个函数最终会调用 __alloc_pages_nodemask 函数完成内存页面的分配。
只要知道alloc_pages_current 函数最终要调用 __alloc_pages_nodemask 函数，而且我们还要搞清楚它的参数，order 很好理解，它表示请求分配 2 的 order 次方个页面，重点是 gfp_t 类型的 gfp_mask。
七、开始分配
__alloc_pages_nodemask 函数主要干了三件事：
1.准备分配页面的参数；
2.进入快速分配路径；
3.若快速分配路径没有分配到页面，就进入慢速分配阶段。
1.准备分配页面的参数
__alloc_pages_nodemask 函数中，一定看到了一个变量 ac 是 alloc_context 类型的，顾名思义，分配参数就保存在了 ac 这个分配上下文的变量中。prepare_alloc_pages 函数根据传递进入的参数，就能找出要分配内存区、候选内存区以及内存区中空闲链表的 migratetype 类型。它把这些全部收集到 ac 结构中，只要它返回 true，就说明分配内存页面的参数已经准备好了。
2.Plan A：快速分配路径
为了优化内存页面的分配性能，在一定情况下可以进入快速分配路径，请注意快速分配路径不会处理内存页面合并和回收。
遍历所有的候选内存区，然后针对每个内存区检查水位线，是不是执行内存回收机制，当一切检查通过之后，就开始调用 rmqueue 函数执行内存页面分配。
3.Plan B：慢速分配路径
当快速分配路径没有分配到页面的时候，就会进入慢速分配路径。跟快速路径相比，慢速路径最主要的不同是它会执行页面回收，回收页面之后会进行多次重复分配，直到最后分配到内存页面，或者分配失败。__alloc_pages_slowpath 函数一开始会唤醒所有用于内存交换回收的线程 get_page_from_freelist 函数分配失败了就会进行内存回收，内存回收主要是释放一些文件占用的内存页面。如果内存回收不行，就会就进入到内存压缩环节。内存压缩不是指压缩内存中的数据，而是指移动内存页面，进行内存碎片整理，腾出更大的连续的内存空间。
4.如何分配内存页面
实际完成分配任务的是 rmqueue 函数.
rmqueue_pcplist 函数，在请求分配一个页面的时候，就是用它从 pcplist 中分配页面的。所谓的 pcp 是指，每个 CPU 都有一个内存页面高速缓冲，由数据结构 per_cpu_pageset 描述，包含在内存区中。在 Linux 内核中，系统会经常请求和释放单个页面。如果针对每个 CPU，都建立出预先分配了单个内存页面的链表，用于满足本地 CPU 发出的单一内存请求，就能提升系统的性能。