这篇文章主要介绍操作系统的连续内存分配，包括内存的内碎片与外碎片、内存的动态分配算法、压缩式碎片整理与交换式碎片整理。
连续内存分配
连续内存分配：给进程分配一块不小于指定大小的、连续的物理内存区域。
内存碎片问题
内存碎片问题指的是空闲的内存无法被利用，细分为外部碎片和内部碎片。
- 外部碎片：分配单元（进程）间的未使用内存
- 内部碎片：分配单元（进程）内的不能被利用的内存
分区的动态分配
动态分区分配：当程序被加载执行时，分配给进程一个指定大小可变的分区（块、内存块），且分区的物理地址是连续的。
分区的动态分配方式有以下三种：
- 第一匹配分配（first fit）：在空闲的内存块中，从低内存往高内存顺序搜索，找到 第一个 比需求大的空闲块, 分配给应用程序。
- 最优适配分配（best fit）：在空闲的内存块中，找到比需求大的 最小的 空闲块, 分配给应用程序。
- 最差适配分配（worst fit）：在空闲的内存块中，找到 最大的 空闲块, 分配给应用程序。
1 | |....| 500bytes |.......| 1k bytes |...| 400bytes |...| |
例如，现在有一个应用程序，需要 300bytes 的内存块，那么第一匹配分配将会选择 500bytes 的内存块，最优适配分配将会选择 400bytes 的内存块，最差适配分配将会选择 1k bytes 的内存块。
分配方式的区别：
| 第一匹配分配 | 最优适配分配 | 最差适配分配 | |
|---|---|---|---|
| 分配方式原理 & 实现 | 按地址排序的空闲块列表、需要寻找合适的分区、重分配时需检查合并相邻空闲分区 | 按尺寸排序的空闲块列表、需要寻找合适的分区、重分配时需检查合并相邻空闲分区 | 按尺寸排序的空闲块列表、分配最大分区、重分配时需检查合并相邻空闲分区，并调整空闲分区列表顺序 |
| 优势 | 简单易实现、容易产生更大空闲块 | 相对简单、对小尺寸分配高效、可避免大的空闲分区被拆分 | 分配快、对中尺寸分配高效 |
| 劣势 | 容易产生外部碎片、不确定性、分配大块时较慢 | 容易产生外部碎片、重分配慢（释放分区较慢）、产生微小碎片 | 容易产生外部碎片、重分配慢（释放分区较慢）、容易破坏大的空闲分区，后续难以分配大的分区 |
三种分配方式并无优劣之分，因为我们无法判断内存请求的大小。
碎片整理
可以看到的是，三种分区动态分配的方式都会产生外部碎片，因此我们可以对碎片进行一定的整理来解决碎片问题。
何为碎片整理？即通过调整应用程序（进程）占用的分区位置来减少或避免分区碎片，以腾出更大的内存块。
压缩式碎片整理
- 方式：重置程序以合并外部碎片
- 条件：要求所有程序是动态可重定位的
- 需要解决的问题：
- 何时重置？（在程序处于等待状态时才可以重置）
- 需要考虑内存拷贝的开销
一个压缩式碎片整理的示例：
1 | // 原始应用程序的内存块和外部碎片 |
交换式碎片整理
- 方式：运行程序需要更多的内存时，抢占等待的程序并且回收它们的内存，以增大可用内存空间
- 需要解决的问题：
- 哪些程序应该被回收？
一个交换式碎片整理的示例：
- 运行中：P3
- 等待中：P1，P2，P4
- 内存分布，主存：OS / P1 / P3 / P2 / P4，磁盘：空
- 当 P3 程序需要更大的内存时，可将等待中的 P4 程序先放入虚拟内存中 -> 内存分布，主存：OS / P1 / P3 / P2，磁盘：P4
参考资料：
1：https://github.com/OXygenMoon/OperatingSystemInDepth
2：https://blog.csdn.net/weixin_53407527/article/details/124891795