如何让内核压缩碎片内存

Question

我在跑步Fedora 26。

这是我的算法教授布置的一项非常奇怪的作业。作业说：

C 中的内存碎片：
设计、实现和执行执行以下操作的 C 程序： 为3m每个大小为 800,000 个元素的数组序列分配内存；然后它显式释放所有偶数数组并分配m每个大小为 900,000 个元素的数组序列。测量程序分配第一个序列和第二个序列所需的时间。选择m耗尽程序可用的几乎所有主内存。”

这样做的总体目标是对内存进行碎片化，然后请求略多于可用的连续块的内存，从而迫使操作系统压缩内存或对内存进行碎片整理。

在课堂上，我问我们应该如何做到这一点，因为内存是可视化的而不是实际上连续的，他回答说：“好吧，你必须关闭[虚拟内存]。”其他一些学生在课堂上问我们如何知道何时遇到“垃圾收集”，他说：“由于垃圾收集所花费的时间，第二次分配的时间应该大于第一次分配的时间”

经过一番搜索后，我能找到的最接近禁用虚拟内存的方法是使用swapoff -a.我禁用了桌面环境，并从本机终端编译并运行了我的程序（以避免其他进程的可能干扰，尤其是像桌面环境这样的繁重进程）。我这样做了，并以递增的速度运行我的程序m，直到达到第二次分配的时间大于第一次的时间点。

我以递增的速度运行该程序m，最终发现第二次分配的时间比第一次分配的时间多。然而，在此过程中，我遇到了一个问题，即该进程在第二次分配之前被终止。我查了一下dmesg，发现是被oom-killer杀掉的。我找到并阅读了几篇有关oom-killer 的文章，并发现您可以禁用内核对内存的过度分配。

我这样做并再次运行我的程序，只是这次我无法找到m第二个时间比第一个时间更高的时间。最终，随着 m 越来越大（尽管比启用过度分配时小得多），malloc 将失败，我的程序将终止。

我有三个问题，其中第一个问题并不是那么重要：

1. 垃圾收集是正确的术语吗？我的教授非常坚定地说这是垃圾收集，但我假设垃圾收集是由编程语言完成的，并且这会被认为是更多的碎片整理。

2. 在Linux系统上可以实现他想要的压缩吗？

3. 当我禁用交换但仍然启用内存过度分配时，为什么我能够达到第二次分配的时间高于第一次分配的时间？压缩真的发生了吗？如果是这样，为什么在禁用内存过度分配后我无法达到压缩发生的程度？

Answer 1

感谢您迄今为止的研究，这确实是一组有趣的问题。

这里一般需要考虑一个重要的方面：内存分配部分是操作系统的责任，部分是每个正在运行的进程的责任（忽略没有内存保护和虚拟地址空间的旧系统）。操作系统负责为每个进程提供自己的地址空间，并在必要时为进程分配物理内存。每个进程都负责划分其地址空间（在某种程度上）并确保其得到适当使用。请注意，进程的职责对于程序员来说基本上是不可见的，因为运行时环境会处理大部分事情。

现在，回答您的问题...

1. 在我看来，垃圾收集与您在这里所做的事情相比只是一步之遥。我想你正在用 C 语言编写，使用malloc()和free()。垃圾收集，在编程语言支持的情况下和运行时环境，负责后一部分：它识别先前分配但不再使用的内存块（并且重要的是，永远不能再次使用），并将它们返回给分配器。问题已链接在杰德BP的评论提供了一些背景知识，但我发现它最有趣，因为它表明不同的人对垃圾收集，甚至垃圾收集的构成有非常不同的看法。

   在我们感兴趣的上下文中，我会使用“内存压缩”来谈论正在讨论的过程。

2. 从用户空间编程的角度来看，你的教授所要求的在 Linux 下的 C 语言中是不可能的，原因很简单：我们关心的不是物理内存碎片，而是地址空间碎片。当您分配许多 800,000 字节的块时，您最终会得到同样多的指向每个块的指针。在 Linux 上，此时操作系统本身还没有做太多事情，并且您不一定有物理内存支持每个分配（顺便说一句，对于较小的分配，操作系统根本不会参与，只是您的C 库的分配器；但是这里的分配足够大，C 库将使用mmap，这是由内核处理的）。当您释放奇数块时，您将取回这些地址空间块，但无法更改指向其他块的指针。如果您随时打印出指针，您会发现它们之间的差异并不比分配请求大多少（在我的系统上为 802,816 字节）；对于 900,000 字节的块，两个指针之间没有空间。因为您的程序具有指向每个块的实际指针，而不是一些更抽象的值（在其他上下文中是句柄），所以运行时环境对此无能为力，因此它无法压缩其内存以合并空闲块。

   如果您使用的编程语言中指针不是程序员可见的概念，那么在 Linux 下内存压缩是可能的。另一种可能性是使用内存分配 API，其中返回值不是指针；而是使用内存分配 API。例如，参见 Windows 下基于句柄的堆分配函数（其中指针仅在句柄被锁定时才有效）。

3. 您教授的练习是有效测量 的性能mmap，其中包括其自由块行走算法。你首先分配 3 ×米块，然后释放一半，然后开始分配米再次阻塞；释放所有这些块会在内核分配器上转储大量空闲块，内核需要跟踪这些空闲块（调用所花费的时间free表明此时尚未进行优化）。如果您跟踪每个单独块的分配时间，您会发现第一个 900k 分配需要很多时间，很多比其他分配要长（在我的系统上是三个数量级），第二个分配要快得多，但仍然需要更长的时间（两个数量级），第三个分配又回到了典型的性能水平。所以发生了一些事情，但返回的指针表明它不是内存压缩，至少不是分配块压缩（如上所述，这是不可能的）——大概时间对应于处理内核用来处理数据结构的时间跟踪进程中的可用地址空间（我正在检查这一点，稍后会更新）。这些冗长的分配可能会导致您正在测量的总体分配序列相形见绌，即 900k 分配最终比 800k 分配花费更长的时间。

   过度使用改变您所看到的行为的原因是，它将练习从纯粹操作地址空间更改为实际分配内存，从而减少了游乐场的大小。当您可以过量使用时，内核仅受进程地址空间的限制，因此您可以分配更多的块并对分配器施加更大的压力。当您禁用过度使用时，内核会受到可用内存的限制，这会将您可以拥有的值降低m到分配器压力不足以导致分配时间爆炸的水平。