操作系统实践之路——六、内存（3.如何实现内存页的分配与释放？）

前言
本章节主要是简单介绍了一下如何实现内存页的分配与释放。

1.内存页的分配

下面举个例子来演绎一下内存页分配的这个算法，帮助理解。比如现在我们要分配一个页面，这个算法将执行如下步骤：

1. 根据一个页面的请求，会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构。

2. 如果第 0 个 bafhlst_t 结构中有 msadsc_t 结构就直接返回，若没有 msadsc_t 结构，就会继续查找 m_mdmlielst 数组中的第 1 个 bafhlst_t 结构。

3. 如果第 1 个 bafhlst_t 结构中也没有 msadsc_t 结构，就会继续查找 m_mdmlielst 数组中的第 2 个 bafhlst_t 结构。

4. 如果第 2 个 bafhlst_t 结构中有 msadsc_t 结构，记住第 2 个 bafhlst_t 结构中对应是 4 个连续的 msadsc_t 结构。这时让这 4 个连续的 msadsc_t 结构从第 2 个 bafhlst_t 结构中脱离。

5. 把这 4 个连续的 msadsc_t 结构，对半分割成 2 个双 msadsc_t 结构，把其中一个双 msadsc_t 结构挂载到第 1 个 bafhlst_t 结构中。

6. 把剩下一个双 msadsc_t 结构，继续对半分割成两个单 msadsc_t 结构，把其中一个单 msadsc_t 结构挂载到第 0 个 bafhlst_t 结构中，剩下一个单 msadsc_t 结构返回给请求者，完成内存分配。

我画幅图表示这个过程，如下图所示：

​ 我们实现了内存分配接口、框架、核心处理函数，其分配算法是：如果能在 dm_mdmlielst 数组中找到对应请求页面数的 msadsc_t 结构就直接返回，如果没有就寻找下一个 dm_mdmlielst 数组中元素，依次迭代直到最大的 dm_mdmlielst 数组元素，然后依次对半分割，直到分割到请求的页面数为止。

2.内存页的释放

​ 其实，内存页的释放就是内存页分配的逆向过程。我们从内存页分配过程了解到，可以一次分配一个或者多个页面，那么释放内存页也必须支持一次释放一个或者多个页面。

​ 整个释放页面逻辑，最核心的还是要对空闲页面进行合并，合并成更大的连续的内存页面，这是这个释放算法的核心逻辑。

还是老规矩，同样举个例子来演绎一下这个算法。比如，现在我们要释放一个页面，这个算法将执行如下步骤。

​ 1.释放一个页面，会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构。

​ 2.设置这个页面对应的 msadsc_t 结构的相关信息，表示已经执行了释放操作。

​ 3.开始查看第 0 个 bafhlst_t 结构中有没有空闲的 msadsc_t，并且它和要释放的 msadsc_t 对应的物理地址是连续的。没有则把这个释放的 msadsc_t 挂载第 0 个 bafhlst_t 结构中，算法结束，否则进入下一步。

​ 4.把第 0 个 bafhlst_t 结构中的 msadsc_t 结构拿出来与释放的 msadsc_t 结构，合并成 2 个连续且更大的 msadsc_t。

​ 5.继续查看第 1 个 bafhlst_t 结构中有没有空闲的 msadsc_t，而且这个空闲 msadsc_t 要和上一步合并的 2 个 msadsc_t 对应的物理地址是连续的。没有则把这个合并的 2 个 msadsc_t 挂载第 1 个 bafhlst_t 结构中，算法结束，否则进入下一步。

​ 6.把第 1 个 bafhlst_t 结构中的 2 个连续的 msadsc_t 结构，还有合并的 2 个地址连续的 msadsc_t 结构拿出来，合并成 4 个连续且更大的 msadsc_t 结构。

​ 7.继续查看第 2 个 bafhlst_t 结构，有没有空闲的 msadsc_t 结构，并且它要和上一步合并的 4 个 msadsc_t 结构对应的物理地址是连续的。没有则把这个合并的 4 个 msadsc_t 挂载第 2 个 bafhlst_t 结构中，算法结束。

上述步骤，我们只要在一个循环中执行就行。我用一幅图表示这个过程，如下所示：

​ 对应于内存分配过程，我们实现了释放页面的接口、框架、核心处理函数，其释放算法则是分配算法的逆向过程，会查找相邻且物理地址连续的 msadsc_t 结构，进行合并，合并工作也是迭代过程，直到合并到最大的连续 msadsc_t 结构或者后面不能合并为止，最后把这个合并到最大的连续 msadsc_t 结构，挂载到对应的 dm_mdmlielst 数组中。

流程图如下：

思考题

在内存页面分配过程中，是怎样尽可能保证内存页面连续的呢？

1. 先找到能满足的需要的内存 在m_mdmlielst中的位置。

2. 如果内存段大于所需，就要把多出来的内存不断除以2挂载到上一个bafhlst_t，直到达到所需长度。
   例如需要9k内存: 先定位到第 4 个 bafhlst_t 结构中的 4 个连续的 msadsc_t 结构16k(4K*4)。分出9K 内存，往上一个bafhlst_t挂载，直到把剩余的内存挂载完。
   16K --> 9K 4K 2K 1K

其实无论采用哪种分配方式，内存的碎片化都是难以彻底避免的。无论是操作系统、虚拟机还是应用，都要面对这个问题。业界有多种思路来解决或缓解此问题：
1、把不可移动内存单独管理，系统内存分区其实在一定程度上解决了这些问题
2、linux采用了 buddy system来缓解内存碎片问题，本节已经介绍
3、linux中为了处理特别小的内存请求，引入了slab技术，来辅助buddy system
4、windows有一种LFH技术，在程序启动时，会额外分配一定的连续内存给这个进程备用，从而降低系统层面的内存管理负担
5、windows在进程退出后，不会立即释放dll文件相关内存，一方面提速，一方面也缓解了操作系统内存管理负担。其实，看下你手机的APP，切换到后台时，就是这个效果
6、无论是linux还是windows都有低优先级进程，在后台默默做着内存规整工作，类似于磁盘碎片清理
7、类似与LFH，可以考虑在内存分配时额外预留一部分，下次分配在预留的地方继续分配
8、为了内存规整方便，可以考虑靠近应用已分配内存区域进行分配

参考资料

以上内容是我学习彭东老师的《操作系统实战45讲》后所进行的一个笔记记录，如有错误，还请各位大佬多多指教。

我主要参考了以下资料，十分感谢：

操作系统实战45讲——彭东老师

评论区大佬——neohope、Fan