操作系统详解
首页 死磕 Java 优质系列 Java 技术总览 Java 面试宝典 关于我

linux内存管理笔记(二二)--伙伴系统原理

转
 2023-06-11
©版权
原文作者：奇小葩 原文地址：https://blog.csdn.net/u012489236/category_9614673.html

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

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

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

1. 内存碎片问题

在前面的章节中，我们知道在内存管理中，存在两种碎片情况

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

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

202306111242411731.png

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

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

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

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

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

2. 伙伴系统的原理

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

202306111242427033.png

伙伴系统的实现

  • 数据结构

    • 空闲块按大小和起始地址组织成二维数组
    • 初始状态：只有一个大小为2^u的空闲块

  • 分配过程

    • 由小到大在空闲块数组中找最小的可用空闲块
    • 如空闲块过大，对可用空闲块进行二等分，直到得到合适的可用空闲块

  • 释放过程

    • 把释放的块放入空闲数组
    • 合并满足条件的空闲块

  • 合并过程

    • 大小相同2^i
    • 地址相邻
    • 低地址空闲块起始地址为2^(i+1)的位数

    3. 分配实例

    202306111242434714.png

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

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

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

202306111242443545.png

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

4. 优缺点

优点：

  • 较好的解决了外部碎片问题
  • 只要申请的块不超过1024个页面(4M)，内核就尽量分配连续的页面
  • 针对大内存分配设计

缺点：

  • 合并的要求太过严格，只能是满足伙伴关系的块才能合并。一个很小的块往往会阻碍一个大块的合并，一个系统中，对内存块的分配，大小是随机的，一片内存中仅一个小的内存块没有释放，旁边两个大的就不能合并
  • 浪费问题：伙伴系统是按2的幂次方大小进行分配内存块，如果所需内存大小不是2的幂次方，就会有部分页面浪费，有时候还很严重。
  • 拆分和合并开销很大

5. 总结

inux针对 大内存的物理地址分配，采用伙伴算法 ，如果是针对小于一个page的内存，频繁的分配和释放，有更加适宜的解决方案，如slab，后面章节会学习关于linux内核是如何进行伙伴系统的软件实现方式。

6. 参考资料

  • 清华大学操作系统
  • 内核工匠(oppo)
阅读全文