Linux 内存管理（七）之伙伴系统算法

admin管理员组

文章数量:1130349

目录

• 前言
• 一、伙伴系统的由来
• 二、伙伴系统
• • 1、基本思想
  • 2、工作原理
  • 3、伙伴系统信息查看
• 三、内核实现
• • 1、数据结构
  • 2、分配块
  • • 2.1 requeue
    • 2.2 __rmqueue_smallest
    • 2.3 总结
  • 3、释放块

---

前言

伙伴系统算法是一种用来管理分配和释放内存的算法，它在 Linux 内核中被广泛使用。其设计目标是高效地管理内存碎片，并且具有快速的分配和释放速度。

接下来将详细探讨一下 Linux 中的伙伴系统算法。

一、伙伴系统的由来

在 Linux 内存管理（三）之分页机制 一文中，我曾提到过内存碎片，频繁地请求和释放不同大小的一组连续页框，必然导致在已分配页框的块内分散了许多小块的空闲页框。由此带来的问题是，即使有足够的空闲页框可以满足请求，但要分配一个大块的连续页框就可能无法满足。

从本质上说，避免外碎片的方法有两种：

• 利用分页单元把一组非连续的空闲页框映射到连续的线性地址区间。
• 开发一种适当的技术来记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲块。

而今天要讨论的 伙伴系统采用的是第二种方法。

二、伙伴系统

1、基本思想

Linux 采用著名的伙伴系统（buddy system）算法来解决外碎片问题。把所有的空闲页框分组为 11 个块链表，每个块链表分别包含大小为 1,2,4,8,16,32,64,128,256,512 和 1024 个连续的页框。对 1024 个页框的最大请求对应着 4MB 大小的连续 RAM块。每个块的第一个页框的物理地址是该块大小的整数倍。例如，大小为 16 个页框的块，其起始地址是 16 ∗ 2 12 16*2^{12} 16∗212（ 2 12 = 4096 2^{12}=4096 212=4096，这是一个常规页的大小）的倍数。

MAX_ORDER 通常定义为 11，即内核管理的最大的连续空闲物理内存为 2 ( 11 − 1 ) = 4 M B 2^{(11 - 1)} = 4MB 2(11−1)=4MB.

/* Free memory management - zoned buddy allocator.  */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif

2、工作原理

下面通过一个简单的例子来说明该算法的工作原理。

假设要请求一个 256 个页框的块。算法先在 256 个页框的链表中检查是否有一个空闲块。如果没有这样的块，算法会查找下一个更大的页块，也就是，在 512 个页框的链表中找一个空闲块。如果存在这样的块，内核就把 256 的页框分成两等份，一半用作满足请求，另一半插入到 256 个页框的链表中。如果在 512 个页框的块链表中也没找到空闲块，就继续找更大的块——1024 个页框的块。如果这样的块存在，内核把 1024 个页框块的 256 个页框用作请求，然后从剩余的 768 个页框中拿 512 个插入到 512 个页框的链表中，再把最后的 256 个插入到 256 个页框的链表中。如果 1024 个页框的链表还是空的，算法就放弃并发出错信号。

简而言之，就是当程序释放内存时，操作系统首先将该内存回收，然后检查与该内存相邻的内存是否是同样大小并且同样处于空闲的状态，如果是，则将这两块内存合并，然后程序递归进行同样的检查。

以上过程的逆过程就是页框块的释放过程，也是该算法名字的由来。内核试图把大小为 b 的一对空闲伙伴块合并为一个大小为 2b 的单独块。满足以下条件的两个块称为伙伴：

• 两个块具有相同的大小，记作 b。
• 它们的物理地址是连续的。
• 第一块的第一个页框的物理地址是 2 ∗ b ∗ 2 12 2*b*2^{12} 2∗b∗212 的倍数。

该算法是迭代的，如果它成功合并所释放的块，它会试图合并 2b 的块，以再次试图形成更大的块。

3、伙伴系统信息查看

通过命令 cat /proc/buddyinfo 可以查看当前系统的伙伴系统信

目录

• 前言
• 一、伙伴系统的由来
• 二、伙伴系统
• • 1、基本思想
  • 2、工作原理
  • 3、伙伴系统信息查看
• 三、内核实现
• • 1、数据结构
  • 2、分配块
  • • 2.1 requeue
    • 2.2 __rmqueue_smallest
    • 2.3 总结
  • 3、释放块

---

前言

伙伴系统算法是一种用来管理分配和释放内存的算法，它在 Linux 内核中被广泛使用。其设计目标是高效地管理内存碎片，并且具有快速的分配和释放速度。

接下来将详细探讨一下 Linux 中的伙伴系统算法。

一、伙伴系统的由来

在 Linux 内存管理（三）之分页机制 一文中，我曾提到过内存碎片，频繁地请求和释放不同大小的一组连续页框，必然导致在已分配页框的块内分散了许多小块的空闲页框。由此带来的问题是，即使有足够的空闲页框可以满足请求，但要分配一个大块的连续页框就可能无法满足。

从本质上说，避免外碎片的方法有两种：

• 利用分页单元把一组非连续的空闲页框映射到连续的线性地址区间。
• 开发一种适当的技术来记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲块。

而今天要讨论的 伙伴系统采用的是第二种方法。

二、伙伴系统

1、基本思想

Linux 采用著名的伙伴系统（buddy system）算法来解决外碎片问题。把所有的空闲页框分组为 11 个块链表，每个块链表分别包含大小为 1,2,4,8,16,32,64,128,256,512 和 1024 个连续的页框。对 1024 个页框的最大请求对应着 4MB 大小的连续 RAM块。每个块的第一个页框的物理地址是该块大小的整数倍。例如，大小为 16 个页框的块，其起始地址是 16 ∗ 2 12 16*2^{12} 16∗212（ 2 12 = 4096 2^{12}=4096 212=4096，这是一个常规页的大小）的倍数。

MAX_ORDER 通常定义为 11，即内核管理的最大的连续空闲物理内存为 2 ( 11 − 1 ) = 4 M B 2^{(11 - 1)} = 4MB 2(11−1)=4MB.

/* Free memory management - zoned buddy allocator.  */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif

2、工作原理

下面通过一个简单的例子来说明该算法的工作原理。

假设要请求一个 256 个页框的块。算法先在 256 个页框的链表中检查是否有一个空闲块。如果没有这样的块，算法会查找下一个更大的页块，也就是，在 512 个页框的链表中找一个空闲块。如果存在这样的块，内核就把 256 的页框分成两等份，一半用作满足请求，另一半插入到 256 个页框的链表中。如果在 512 个页框的块链表中也没找到空闲块，就继续找更大的块——1024 个页框的块。如果这样的块存在，内核把 1024 个页框块的 256 个页框用作请求，然后从剩余的 768 个页框中拿 512 个插入到 512 个页框的链表中，再把最后的 256 个插入到 256 个页框的链表中。如果 1024 个页框的链表还是空的，算法就放弃并发出错信号。

简而言之，就是当程序释放内存时，操作系统首先将该内存回收，然后检查与该内存相邻的内存是否是同样大小并且同样处于空闲的状态，如果是，则将这两块内存合并，然后程序递归进行同样的检查。

以上过程的逆过程就是页框块的释放过程，也是该算法名字的由来。内核试图把大小为 b 的一对空闲伙伴块合并为一个大小为 2b 的单独块。满足以下条件的两个块称为伙伴：

• 两个块具有相同的大小，记作 b。
• 它们的物理地址是连续的。
• 第一块的第一个页框的物理地址是 2 ∗ b ∗ 2 12 2*b*2^{12} 2∗b∗212 的倍数。

该算法是迭代的，如果它成功合并所释放的块，它会试图合并 2b 的块，以再次试图形成更大的块。

3、伙伴系统信息查看

通过命令 cat /proc/buddyinfo 可以查看当前系统的伙伴系统信

本文标签： 算法内存管理伙伴系统Linux