Linux深入理解内存管理22-CSDN博客

本文链接：https://blog.csdn.net/zouhaicheng/article/details/144890774

Linux深入理解内存管理22（基于Linux6.6）---伙伴系统原理介绍

一、概述

1.1、伙伴系统的工作原理

1、内存分配

当请求内存时，伙伴系统会按照以下步骤工作：

查找空闲块：
- 系统会检查每个大小的空闲链表，找到第一个能够满足请求的内存块。
- 如果请求的内存块大小正好是某个空闲块的大小，就直接分配该块。
- 如果请求的内存块大小小于某个空闲块的大小，系统会尝试将该空闲块分割成两个较小的块，直到找到一个足够小的块。
分割内存块：
- 假设请求的内存大小为 2^k，但是系统找到的最小空闲块大小为 2^n，其中 n > k。
- 系统会将 2^n 的空闲块分割成两个 2^(n-1) 大小的块。然后将其中一个 2^(n-1) 大小的块分配给请求的任务，另一个块继续进入对应的空闲链表。
- 这个过程会递归进行，直到找到合适大小的块为止。
分配块：
- 一旦找到合适的块，系统会将该块从空闲链表中移除，并将其标记为已分配。

2、内存释放

当一个内存块释放时，伙伴系统会按以下步骤进行合并：

合并伙伴：
- 假设释放的块大小为 2^n，系统会检查其伙伴块是否空闲。
- 如果伙伴块也为空闲状态，则将它们合并成一个 2^(n+1) 大小的块，并将该块加入到空闲链表中。
- 如果合并后的新块的伙伴也为空闲，则继续合并，直到没有伙伴可以合并。
更新空闲链表：
- 每次合并后，都会更新空闲链表，将合并后的大块插入到合适的链表中，保持链表的排序。

3、递归分割与合并

分割：分割操作通过递归将一个大块逐渐分割成两个小块，直到找到一个合适的块大小为止。
合并：合并操作也可以递归进行，直到没有更多可以合并的伙伴。

在内核初始化完成后，内存管理将成为一项重要的工作。如何频繁的申请释放内存的情况下，如何避免碎片的产生，这就要求内核采取灵活而恰当的分配策略。通常，内存分配一般有以下两种情况

大对象(大的连续空间分配)。
小对象(小的空间分配)。

针对不同的需求，Linux采取了不同的方式来解决这两种问题导致的内存碎片问题。从原理上分析内核如何通过伙伴系统算法，如何解决了内存碎片问题。

二、内存碎片问题

在内存管理中，存在两种碎片情况：

内部碎片：是指已经分配出去的内存空间，却不能被利用的内存空间。也就是说已经被分配出去的内存空间大约请求所需的内存空间，而导致有些内存不能有效使用，自己无法使用，其他的进程也无法使用。

例如进程需要使用3K bytes物理内存，于是向系统申请了大小等于3Kbytes的内存，但是由于Linux内核伙伴系统算法最小颗粒是4K bytes，所以分配的是4Kbytes内存，那么其中1K bytes未被使用的内存就是内存内碎片：

外部碎片：是指还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。内存被分割成很小很小的一些块，这些块虽然是空闲的，但是却小到无法使用。随着申请和释放次数的增加，内存将变得越来越不连续，最终导致整个内存将只剩下碎片。即使有足够的内存可以满足请求，但是要分配一个大块的连续内存却无法满足。

例如系统剩余内存为16K bytes，但是这16K bytes内存是由4个4K bytes的页面组成，即16K内存物理页帧号#1不连续。在系统剩余16K bytes内存的情况下，系统却无法成功分配大于4K的连续物理内存，该情况就是内存外碎片导致，本文中阐述的就是物理内存外碎片化。

对于外部碎片，有两种解决方法：

采用非连续的内存分配，如果内存需要使用物理内存连续，暂时无法做到。
采用一种有效的方法来监控内存，保证在内核只要申请一小块内存的情况下，不会从大块的连续内存中分配，从而保证大块内存的连续性和完整性。

因此Linux采用后者来解决外部碎片的问题，也就是著名的伙伴系统。

三、伙伴系统的原理

伙伴系统的宗旨就是用最小的内存块来满足内核的对于内存的请求，其基本的设计思路如下：

伙伴系统的实现：

1、数据结构初始化

+------------------------+
| 空闲块数组（二维）     |
|   索引从 0 到 u        |
|   初始只有一个大小为2^u |
+------------------------+

2、分配过程

+-------------------------+
| 查找最小可用块           |
| 在空闲块数组中查找      |
| 从小到大逐个比较         |
+-------------------------+
        |
        v
+-------------------------+
| 找到最小的合适空闲块     |
|   (大小 >= 请求大小)     |
+-------------------------+
        |
        v
+-------------------------+
| 需要分割空闲块?          |
| 是 -> 分割块             |
| 否 -> 分配该块           |
+-------------------------+
        |
        v
+-------------------------+
| 分割空闲块：递归分割     |
| 直到找到合适大小的块    |
+-------------------------+
        |
        v
+-------------------------+
| 从空闲链表中移除该块     |
| 将其分配给请求进程       |
+-------------------------+

3、释放过程

+-------------------------+
| 释放块放回空闲链表       |
+-------------------------+
        |
        v
+-------------------------+
| 检查是否可以合并伙伴块   |
| (地址相邻，大小相同)     |
+-------------------------+
        |
        v
+-------------------------+
| 可以合并伙伴块?          |
| 是 -> 合并伙伴           |
| 否 -> 不合并             |
+-------------------------+
        |
        v
+-------------------------+
| 合并后更新空闲链表       |
| 如果有多个块可以合并     |
+-------------------------+
        |
        v
+-------------------------+
| 继续检查合并条件         |
| 直到无法合并为止         |
+-------------------------+

4、合并过程

+-------------------------+
| 检查是否可以合并伙伴块   |
| 两个块的大小相同         |
| 他们的地址相邻           |
+-------------------------+
        |
        v
+-------------------------+
| 合并成功: 更新空闲链表    |
+-------------------------+
        |
        v
+-------------------------+
| 合并后的块插入到空闲链表中 |
+-------------------------+

如下：

数据结构。
空闲块按大小和起始地址组织成二维数组。
初始状态：只有一个大小为2^u的空闲块。
分配过程。
由小到大在空闲块数组中找最小的可用空闲块。
如空闲块过大，对可用空闲块进行二等分，直到得到合适的可用空闲块。
释放过程。
把释放的块放入空闲数组。
合并满足条件的空闲块。
合并过程。
大小相同2^i。
地址相邻。
低地址空闲块起始地址为2^(i+1)的位数。

四、分配实例

如下：

首先，假设有一个1M空间的内存：

如果第一次需要一个100K的空间，那么对于1M的空间进行分块处理，第一次分成两个512K，而对于此时还是不满足2i-1 <100 < 2i，继续分片，对第一个512K进行分片，分成2个256K，而256K还是不满足，所有对第一个256K继续进行分片，分成2个128K，满足了条件，所以此时会将第一个A=128K分出去。
此时第二个分配请求，分配240K的空间，那么直接就从B=256K分配出去。
第三个分配请求，分配64K的空间，从空间查找发现有128K的空间可以分成2个64K的空间，直接分配出去C=64K。
第四个分配请求，分配256K的空间，发现只有512K的空间满足要求，直接分配D=256K。
第五个释放请求，释放B空间，发现不满足合并规则，那么内存中有3块内存独立的内存空间。
第六个释放请求，释放A空间，发现A空间与后面的地址空间被C地址隔离，导致不满足合并规则。
第七个分配请求，申请75K的空间，发现第一个128K满足条件，直接分配E=128K。
第八个释放请求，释放C空间，发现C相邻的地址空间，满足合并请求，直接合并成128K，合并后与前后相邻的无法再合并。
第九个释放请求，释放E空间，发现E释放后，与后面的128K空间合并成256K，又与后面的256K合并成512K，那么现在只剩下D空间。
第十个释放请求，释放D空间，发现D释放后，与后面的256K空间合并成512K，而前面的512K又满足合并条件，可以合并成1M的空间。

对于合并的其原理满足下图：

通过以上的算法可以看出，伙伴系统虽然解决了外部碎片，但是会导致内部碎片，例如，针对上图，如果需要一个257K的内存空间，那么伙伴系统的算法会怎么处理呢？按照其算法，针对该问题会分配一个512K的内存空间，那么就会有255K的内存空间浪费。

五、优缺点

5.1、伙伴系统的优点

减少内存碎片：
- 由于每次分配和释放时都按大小为2的幂次方进行，内存块的合并和分割过程能有效减少内存的外部碎片问题。
高效的合并与分割：
- 由于内存块按大小为2的幂次方组织，合并和分割操作非常简单且高效。当需要合并两个块时，只需要简单地检查它们的伙伴是否空闲，若空闲则合并。分割时只需不断将大块分成两个更小的块，直到达到所需的大小。
内存管理结构简单：
- 伙伴系统的内存管理结构通常是一个二维数组，每个大小的空闲块都有一个链表。链表节点存储了块的地址，结构简单，易于实现和维护。
不需要复杂的查找算法：
- 查找空闲块时，不需要进行复杂的查找算法。伙伴系统通过维护固定大小的空闲块链表，可以快速定位合适的空闲块。
适合大内存区域的动态分配：
- 适用于大内存区域的动态分配（如操作系统内存管理），特别是在内存需求大小不固定的情况下，伙伴系统可以灵活调整内存分配的大小。

5.2、伙伴系统的缺点

内存浪费：
- 伙伴系统的主要缺点是可能会导致内存浪费。例如，分配一个大小为 2n2^n2n 的块时，即使需要的内存量较少（比如 2n−12^n - 12n−1），剩余的部分依然无法被有效利用。这会导致一定的内存浪费，尤其是在内存请求较为零散的情况下。
只能分配2的幂次方大小的块：
- 由于内存块大小必须是2的幂次方，某些情况下会导致无法满足内存请求，尤其是在需要精确匹配特定大小时。例如，某个请求需要16KB内存，而系统只能提供一个32KB的块，这时16KB的内存就被浪费了。
合并操作的复杂度：
- 尽管合并操作相对简单，但在一些场景下，频繁的内存分配和释放可能导致多个合并操作，增加了内存管理的复杂度。尤其是在内存分配和释放不均匀的情况下，合并操作可能需要多次才能完成。
性能问题：
- 在某些情况下，尤其是在内存分配频繁且请求大小不均匀的情况下，可能会出现频繁的分割和合并操作，从而影响系统的性能。频繁的合并和分割可能导致CPU开销增加，降低系统效率。
内存碎片问题：
- 尽管伙伴系统能减少外部碎片，但它无法完全避免内存碎片，特别是当内存请求的大小比较小且随机时。在这种情况下，内存碎片问题依然存在，尤其是在长时间运行后，合并时可能不能完全解决所有碎片。
静态的内存管理结构：
- 伙伴系统通常使用固定大小的内存块进行管理，在内存需求动态变化时，可能会导致某些内存区域被过度分配或长期未使用，导致内存的利用率降低。

优点	缺点
减少内存碎片：通过合并和分割减少外部碎片问题	内存浪费：分配固定大小的内存块可能导致内存浪费
高效的合并和分割：合并和分割操作简单高效	只能分配2的幂次方块：可能无法精确满足需求
结构简单：管理结构简单，易于实现	频繁合并可能导致性能问题
快速查找空闲块：通过空闲链表快速定位空闲块	合并操作可能增加复杂度
适合动态内存分配：适应大内存需求	内存碎片问题依然存在