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)
阅读全文