计算机上的所有程序都有一个共同点，那就是对内存的需求。
程序需要从你的硬盘加载到内存之前，他们可以运行。
在运行时，大多数程序所做的是从内存中加载值，对它们进行一些计算，然后将结果存储回内存中。
在这篇文章中，我将向你介绍内存分配的基础知识。
分配器之所以存在，是因为它不足以使内存可用，您需要有效地使用它。
我们将直观地探索简单分配器是如何工作的。
我们将看到他们试图解决的一些问题，以及用于解决这些问题的一些技术。在这篇文章的最后，您应该知道编写自己的分配程序所需要知道的一切。
malloc & free
要理解内存分配器的工作，必须了解程序如何请求和返回内存。Malloc 和 free 是在1979年 UNIX v7中以可识别的形式首次引入的函数(!).让我们来看一个简短的 C 程序演示它们的用法。
如果您对另一种语言(如 JavaScript、 Python 或 C #)有初级水平的熟悉程度，那么跟着学习应该没有问题。
你不需要理解每一个字，只要你明白整体的概念。
这是文章中唯一的 C 代码。
#include <stdlib.h>
int main() {
void *ptr = malloc(4);
free(ptr);
return 0;
}
在上面的程序中，我们通过调用 malloc (4)来获取4个字节的内存，我们将返回的值存储在一个名为 ptr 的变量中，然后通过调用 free (ptr)来表示已经处理完了内存。
这两个函数是几乎所有程序管理它们使用的内存的方式。即使您没有编写 C 语言，正在执行 Java、 Python、 Ruby、 JavaScript 等的代码也会使用 malloc 和 free。
什么是内存
分配器使用的最小内存单元称为“字节”。
一个字节可以存储0到255之间的任何数字。
您可以将内存想象成一个长长的字节序列。
我们将把这个序列表示为一个正方形网格，每个正方形代表一个内存字节。
image.png
在之前的 C 代码中，malloc (4)分配4个字节的内存。我们要表示的内存，已被分配为较暗的方块。
image.png
然后 free (ptr)告诉分配器我们已经处理完该内存，它被返回到可用内存池。
下面是4个 malloc 调用之后4个可用分配的样子。
你会发现现在有一个滑块。
拖动滑块到右边会使时间向前推进，然后拖动它向左倒退。
您还可以单击网格上的任何位置，然后使用键盘上的箭头键，或者使用左键和右键。
滑块上的刻度表示对 malloc 和 free 的调用。
image.png
Malloc 返回的内容称为“指针”或“内存地址”这个数字标识了内存中的一个字节。
我们通常以“十六进制”的形式写地址十六进制数的前缀为0x，以便与十进制数区分开来。
移动下面的滑块可以看到十进制数和十六进制数之间的比较。
这是我们熟悉的记忆网格。每个字节都以十六进制形式标注其地址。由于空间原因，我省略了0x 前缀。
image.png
我们在本文中使用的示例假设您的计算机只有非常少量的内存，但是在现实生活中您有数十亿字节可以使用。
真正的地址比我们现在使用的要大得多，但是想法是完全一样的。
内存地址是指内存中特定字节的数字。
最简单的 malloc
Malloc 实现的“ hello world”将通过跟踪前一个块的结束位置并在结束后立即启动下一个块来分发内存块。
下面我们用一个灰色方块表示下一个块应该从哪里开始。
image.png
您会注意到没有释放任何内存。如果我们只是跟踪下一个块应该从哪里开始，而不知道前一个块从哪里开始或结束，那么 free 就没有足够的信息来做任何事情。所以不会。这被称为“内存泄漏”，因为一旦分配了内存，就再也不能使用了。
信不信由你，这并不是一个完全无用的实现。对于使用已知内存量的程序，这可能是一个非常有效的策略。
它非常快，非常简单。
但是，作为一个通用的内存分配器，我们不能没有可用的实现。
最简单的通用 malloc
为了释放内存，我们需要更好地跟踪内存。
我们可以通过保存所有分配的地址和大小，以及空闲内存块的地址和大小来实现这一点。
我们分别称它们为“分配列表”和“空闲列表”。
image.png
我们表示可用列表条目作为2灰色方块链接在一起的一条线。可以想象这个条目在代码中表示为 address = 0和 size = 32。当我们的程序启动时，所有的内存都被标记为空闲。
当调用 malloc 时，我们循环访问空闲列表，直到找到一个足够大的块来容纳它。
当我们找到一个时，我们将分配的地址和大小保存在我们的分配列表中，并相应地缩小空闲列表条目。
image.png
释放内存？因为我们已经在分配列表中保存了分配的地址和大小，所以我们可以搜索该列表并将分配移回空闲列表中。没有内存大小信息，我们不可能做到。
image.png
我们的空闲列表现在有2个条目。
这可能看起来无害，但实际上代表了一个重大问题。
让我们看看这个问题的实际情况。
我们分配了8块内存，每块4字节。
然后我们释放了它们，产生了8个空闲列表条目。
现在的问题是，如果我们尝试执行 malloc (8) ，空闲列表中没有可以容纳8个字节的项，malloc (8)将失败。
为了解决这个问题，我们需要做更多的工作。
释放内存时，我们应该确保如果返回到空闲列表的块与其他任何空闲块相邻，则将它们组合在一起。
这就是所谓的“结合”。
分段存储
一个完美结合的免费列表并不能解决我们所有的问题。下面的示例显示较长的分配序列。看看状态记忆是在最后。
image.png
我们以32字节中的6个空闲结束这个序列，但是它们被分成2个3字节的块。如果我们必须服务 malloc (6) ，虽然理论上我们有足够的自由内存，但是我们不能这样做。这就是所谓的“分段存储”。
可惜不是。还记得之前我们讨论过 malloc 的返回值是内存中一个字节的地址吗？
移动分配不会改变我们已经从 malloc 返回的指针。
我们将更改这些指针所指向的值，从而有效地破坏它们。
这是 malloc/free API 的缺点之一。
如果我们不能在创建它们之后移动分配，那么我们需要更加小心地从哪里开始放置它们。
令人困惑的是，对抗分裂的一种方法是过度配置。
如果我们总是分配至少4个字节，即使请求是1个字节，看看会发生什么。
这与上面的分配顺序完全相同。
现在我们可以为 malloc (6)提供服务了。
值得记住的是，这只是一个例子。
程序将根据它们所做的事情以非常不同的模式调用 malloc 和 free，这使得设计一个始终性能良好的分配器变得非常具有挑战性。
不，那是过度分配的副作用。可视化显示了“真实”的内存使用情况，而空闲列表是从分配器的角度更新的。
因此，当第一个 malloc 发生时，分配了1字节的内存，但是空闲列表条目向前移动了4个字节。
我们用一些被浪费的空间来换取更少的碎片。
值得注意的是，由于过度分配而导致的这种未使用的空间是另一种形式的碎片。在释放创建它的分配之前，无法使用的是内存。因此，我们不希望过度分配。例如，如果我们的程序一次只分配1个字节，我们将浪费75% 的内存。
防止内存碎片化的另一种方法是将内存分割成一个用于小分配的空间和一个用于大分配的空间。在下一个可视化中，我们从两个空闲列表开始。浅灰色的用于分配3个字节或更小的字节，深灰色的用于分配4个字节或更大的字节。同样，这与之前的分配顺序完全相同。
漂亮！这也减少了分裂。但是，如果我们在第一个段中严格地只允许3字节或更少的分配，那么我们就不能为 malloc (6)提供服务。这里的权衡是，为较小的分配保留一个内存段，这样可以减少处理较大内存段的内存。
又骗到我了。我编写的这个实现将在浅灰色空间已满时在暗灰色空间中进行小的分配。当它这样做的时候，它就会过度分配，否则由于分配很少，我们最终会在黑暗的灰色空间中出现可避免的碎片。
一个快速的 malloc 拼图
如果你使用 malloc (0)会发生什么? 在使用下面的滑块之前，请考虑一下这个问题。
这是使用我们的空闲列表实现，要求分配的最小大小为4个字节。所有内存都得到了分配，但实际上没有使用任何内存。你认为这是正确的行为吗？
事实证明，当 malloc (0)在不同的实现之间发生的情况是不同的。
他们中的一些人的行为和上面一样，分配他们可能不必分配的空间。
其他程序将返回所谓的“空指针”，一个特殊的指针，如果你试图读取或写入程序指向的内存，它将使程序崩溃。
另一些则在内存中选择一个特定的位置，并为所有对 malloc (0)的调用返回相同的位置，而不管调用次数如何。
网友评论