xyl*_*fur 8 memory swap defragmentation
我在跑步Fedora 26。
这是我的算法教授给的一个非常奇怪的作业。作业说：
C 中的内存碎片：
设计、实现和执行执行以下操作的 C 程序： 为3m每个数组大小为 800,000 个元素的序列分配内存；然后它显式地释放所有偶数数组并分配一个m大小为 900,000 个元素的数组序列。测量您的程序分配第一个序列和第二个序列所需的时间。选择m耗尽程序可用的几乎所有主内存。”
这样做的总体目标是对内存进行分段，然后请求比作为连续块可用的内存稍多的内存，从而迫使操作系统压缩或整理内存。
在课堂上我问我们应该如何做这件事，因为记忆是可视化的，实际上并不是连续的，他回答说：“好吧，你必须关闭 [虚拟记忆]。” 有同学在课堂上问我们怎么知道什么时候打到了这个“垃圾收集”，他说：“因为垃圾收集需要时间，所以第二次分配的时间应该比第一次大”
在四处搜索之后，我能找到的最接近禁用虚拟内存的方法是使用swapoff -a. 我禁用了我的桌面环境，并从本机终端编译并运行了我的程序（以避免可能受到其他进程的干扰，尤其是像桌面环境这样的繁重进程）。我这样做并以递增的方式运行我的程序，m直到达到第二次分配的时间大于第一次的时间点。
我用递增的方式运行程序，m最终发现第二次分配的时间比第一次分配的时间多。然而，在此过程中，我遇到了在第二次分配之前进程被终止的情况。我检查了一下dmesg，发现它是被oom-killer杀死的。我发现并阅读了几篇关于oom-killer 的文章，并发现您可以禁用内核过度分配内存。
我这样做并再次运行我的程序，只是这次我无法找到m第二个时间高于第一个的时间。最终，随着 m 越来越大（虽然比启用过度分配时小得多），malloc 将失败，我的程序将终止。
我有三个问题，其中第一个问题并不那么重要：
垃圾收集是正确的术语吗？我的教授非常坚定地说这是垃圾收集，但我假设垃圾收集是由编程语言完成的，并且这会被认为是更多的碎片整理。
在 linux 系统上是否可以像他想要的那样进行压缩？
当我禁用交换但仍然启用内存过度分配时，为什么我能够达到第二次分配的时间高于第一次分配的时间？压实真的发生了吗？如果是这样，为什么在禁用内存过度分配后我无法达到压缩发生的程度？
到目前为止，感谢您的研究，这确实是一组有趣的问题。
这里有一个重要的方面需要考虑：内存分配部分是操作系统的责任，部分是每个运行进程的责任（忽略没有内存保护和虚拟地址空间的旧系统）。操作系统负责为每个进程提供自己的地址空间，并在必要时为进程分配物理内存。每个进程都负责分配其地址空间（在某种程度上）并确保它被正确使用。请注意，进程的职责对程序员来说在很大程度上是不可见的，因为运行时环境会处理大多数事情。
现在，回答你的问题...
在我看来，垃圾收集与您在这里所做的工作相比仅一步之遥。我想你是用 C 编写的，使用malloc()和free()。垃圾收集，在编程语言和运行时环境的支持下，负责后面的部分：它识别先前分配但不再使用（并且，重要的是，永远不能再次使用）的内存块，并返回它们到分配器。链接的问题在JdeBP的意见提供了一些背景，但我觉得它主要是有趣的，因为它表明，不同的人对垃圾收集很不同的意见，甚至什么是垃圾收集。
在我们感兴趣的上下文中，我将使用“内存压缩”来讨论正在讨论的过程。
从用户空间编程的角度来看，你的教授所要求的在 C 中，在 Linux 下是不可能的，原因很简单：我们在这里关心的不是物理内存碎片，而是地址空间碎片。当您分配许多 800,000 字节的块时，您最终会得到同样多的指向每个块的指针。在 Linux 上，在这一点上，操作系统本身并没有做太多事情，并且您不一定有支持每个分配的物理内存（顺便说一句，如果分配较小，操作系统根本不会参与，只是您的C 库的分配器；但这里的分配足够大，C 库将使用mmap，由内核处理）。当您释放奇数块时，您会取回这些地址空间块，但您无法更改指向其他块的指针。如果你边走边打印这些指针，你会发现它们之间的区别并不比分配请求大多少（我的系统上为 802,816 字节）；对于 900,000 字节的块，两个指针之间没有空间。因为您的程序具有指向每个块的实际指针，而不是一些更抽象的值（在其他上下文中，一个句柄），运行时环境对此无能为力，因此它无法压缩其内存以合并空闲块。
如果您使用的编程语言指针不是程序员可见的概念，那么在 Linux 下内存压缩是可能的。另一种可能性是使用内存分配 API，其中返回的值不是指针；例如，参见 Windows 下基于句柄的堆分配函数（其中指针仅在句柄被锁定时有效）。
您教授的练习有效地衡量了 的性能mmap，其中包括其自由块行走算法。你首先分配 3 × m个块，然后释放其中的一半，然后再次开始分配m个块；释放所有这些块会在内核的分配器上转储大量空闲块，它需要跟踪（并且free调用所花费的时间表明此时没有进行优化）。如果您跟踪每个单独块的分配时间，您将看到第一个 900k 分配需要很多很多比其他分配更长（在我的系统上是三个数量级），第二个要快得多，但仍然需要更长的时间（两个数量级），第三个分配又回到了典型的性能水平。所以发生了一些事情，但返回的指针表明它不是内存压缩，至少不是分配块压缩（如上所述，这是不可能的）——大概时间对应于处理内核使用的数据结构的时间跟踪进程中的可用地址空间（我正在检查这一点，稍后会更新）。这些冗长的分配可能会使您正在测量的整体分配序列相形见绌，即 900k 分配最终比 800k 分配花费的时间更长。
过度使用会改变您看到的行为的原因是它将练习从纯粹的操作地址空间更改为实际分配内存，从而减少了您的游乐场的大小。当您可以过量使用时，内核仅受进程地址空间的限制，因此您可以分配更多的块并对分配器施加更大的压力。当您禁用过量使用时，内核会受到可用内存的限制，这会将您可以拥有的值m降低到分配器压力不足以导致分配时间爆炸的级别。