玻尔百科内存分配是计算机科学中最基本的一项挑战：操作系统如何安全高效地在多个相互竞争的程序之间共享物理内存这一有限资源？这个问题驱动了数十年的创新，产生了一层层巧妙的抽象，从复杂的物理现实中创造出一种简洁的幻象。这些解决方案致力于解决核心问题，即为每个程序提供其专属的私有工作空间，同时不干扰其他程序或浪费宝贵的资源。
本文深入探讨内存分配的世界，全面概述了现代系统如何处理这项基本任务。在“原理与机制”一章中，我们将揭示基础技术，从直接但有缺陷的连续分配方法开始，逐步深入到革命性的虚拟内存概念，并探索实现它的软硬件机制。随后，“应用与跨学科联系”一章将展示为何这些机制至关重要，揭示它们在从高性能设备通信和服务器架构到基本数据结构设计和编译器优化等各个方面的实际影响。
想象一下，主内存是一片广阔、空旷的仓库地面，上面标记着数百万甚至数十亿个微小的、带编号的方格。每个方格，即一个字节，都有一个唯一的地址。当一个程序运行时，它需要这片地面的一部分来存储其指令、数据和临时计算结果。我们作为仓库管理员（操作系统），该如何决定将哪些方格分配给哪个程序，尤其是在许多程序都想同时使用这个仓库时？这就是内存分配的根本问题。答案是一个关于思想演进的美妙故事，其中每一层新的抽象都是为了解决前一层问题而设计的巧妙技巧。
最直接的想法是给每个程序一块属于自己的、矩形的、不间断的地面空间。我们称之为连续分配。当一个程序启动时，操作系统会找到一块足够大的空闲内存块，然后说：“给你。你的空间从地址 开始，你可以使用 个字节。请待在你的矩形区域内。”
为了强制执行这一规则，硬件提供了一些帮助。CPU 中的两个特殊寄存器，一个基址寄存器和一个界限寄存stg，会为每个正在运行的程序进行设置。基址寄存器存放起始物理地址 ，界限寄存器则存放分配块的大小 。每当程序试图访问一个内存位置时，它都是在自己的小世界里思考，使用一个*逻辑地址——即相对于其内存起始位置的偏移量。例如，它可能会请求“我位置 2048 处的字节”。硬件的内存管理单元 (MMU) 会立即采取行动。它首先检查逻辑地址（我们称之为 ）是否在界限内： 是否小于 ？如果不是，说明程序试图踏出其分配的矩形区域，MMU 会触发一个警报（向操作系统发出陷阱）。如果检查通过，MMU 会通过加上基址来计算物理地址*：。
这种基址加界限的方案非常有效。它允许操作系统将程序放置在物理内存的任何位置——这一特性称为重定位——因为程序本身只看到相对于零的逻辑地址。如果操作系统决定将程序的整个内存块移动到不同的位置，它只需更新基址寄存器，程序对此毫不知情。其所有内部指针（以逻辑偏移量存储）都将被正确地转换为新的物理位置。
但这个简单的天堂也存在着隐患。随着程序的启动和结束，它们会留下一些空闲内存的“洞”。一个请求 50MB 的新程序可能会发现总共有 100MB 的空闲空间，但这些空间被分割成了五个 20MB 的洞。这就是外部碎片，就像一个停车场里有很多空车位，但没有一个足够大，停不下你需要停放的巴士。为了决定使用哪个洞，分配器采用了一些简单的策略，如首次适应（选择第一个足够大的洞）或最佳适应（选择最小的但足够大的洞）。通过一系列分配和释放操作来追踪这些策略，可以揭示它们如何产生不同的碎片模式，每种模式都在速度和内存利用率之间有着不同的权衡。
我们该如何处理所有这些无用的小洞呢？我们可以执行紧凑操作：暂停所有活动，将已分配的块 shuffling 在一起，就像把书架上的所有书都推到一边，从而创造一个大的、连续的空闲块。得益于基址寄存器，程序的 CPU 相关部分不会出错。
但如果一个程序或它使用的库在某个地方存储了一个绝对的物理地址呢？这种情况经常发生在高性能硬件上，例如直接内存访问 (DMA) 控制器，它们被编程使用原始物理地址来传输数据，而无需 CPU 介入。如果操作系统进行了内存紧凑，那个存储的物理地址现在指向了垃圾数据，系统就会崩溃或损坏数据。重定位这个简单的抽象出现了漏洞。内存的物理性质再次抬头。你不能简单地假装不相邻的内存块是一个整体，并承诺为间隙提供“填充字节”；像 DMA 控制器这样的硬件是一个简单的机器，它只会递增一个物理地址计数器，并且会直接越过不属于你的内存。
连续分配带来的难题——外部碎片和重定位的复杂性——催生了计算机科学中最深刻的思想之一：虚拟内存。其核心洞见是革命性的：如果给予程序的连续地址空间的幻象，根本不需要对应于一块物理上连续的内存块呢？
这是通过分页实现的。操作系统将程序的逻辑地址空间划分为固定大小的块，称为页（例如，）。物理内存也被划分为同样大小的块，称为帧。现在，MMU 为每个进程持有一个更复杂的映射表，即页表。这个表充当翻译器：对于程序想要访问的每一个虚拟页，页表会告诉 MMU 它实际存储在哪个物理帧中。
结果是神奇的。一个程序的虚拟页，在其看来是无缝的序列 ，可以散布在物理内存的各处。页 1 可能在帧 100，页 2 在帧 305，页 3 在帧 101。从程序的角度看，内存仍然是一个简单的线性数组。但从操作系统的角度看，进程内存的外部碎片被完全消除了。只要内存中有足够的空闲帧在某个地方可以满足请求，分配就能成功。
这层间接寻址带来的不仅仅是解决了碎片问题。它解锁了一整套强大的功能。
首先也是最重要的是保护。通过虚拟内存，每个进程都获得自己独立的页表和私有的虚拟地址空间。它在一个沙箱中运行，相信自己拥有整个内存范围（例如，在 64 位系统上是 字节）。它无论如何都无法生成一个会访问到另一个进程内存的地址，因为它的页表中根本不包含到那些物理帧的映射。
但是谁来守护守卫者呢？谁来保护页表本身？这时 CPU 的特权模式就派上用场了。你的程序运行在低特权的用户模式下，而操作系统内核则运行在高特权的监督模式下。硬件强制执行严格的规则：修改内存管理系统的指令，比如更改页表根寄存器，是特权指令，只能在监督模式下执行。页表本身位于物理内存中，操作系统会在页表条目中将其标记为“仅限监督模式”。用户模式程序任何篡改这些关键数据结构的行为都会导致硬件故障，立即将控制权转移给操作系统。这套强大的硬件检查确保了用户进程被困在操作系统为其创建的虚拟世界中。
虚拟内存还允许操作系统玩一些聪明的把戏。其中最有用的一招是创建哨兵页。一个调试内存分配器可以在动态分配的缓冲区之后放置一个未映射的页。这个哨兵页存在于虚拟地址空间中，但没有任何物理帧支持它。如果程序存在缓冲区溢出错误，试图在分配的缓冲区之外多写一个字节，它就会触碰到哨兵页。MMU 发现没有有效的映射，就会触发一个故障，操作系统便可以终止程序并给出精确的错误报告。这个强大的安全特性在虚拟地址空间上花费巨大，但在宝贵的物理内存上成本恰好为零。
这突显了从操作系统角度和从程序员角度看待内存管理的一个重要区别。即使有了这些强大的操作系统和硬件特性，在 C++ 等语言中，程序员仍然需要承担手动释放内存的责任。如果一个程序分配了内存然后丢失了指向它的指针（也许是因为发生了异常），这块内存就泄漏了——它仍然处于分配状态但永远无法访问。现代软件工程通过资源获取即初始化 (RAII) 等设计模式解决了这个问题，使用智能指针对象，在它们被销毁时自动释放其拥有的内存，即使在异常期间也是如此。这将资源的生命周期绑定到一个行为良好的软件对象上，确保清理工作永远不会被忘记 [@problem-id:3251937]。
当然，没有解决方案是没有成本的。分页引入了内部碎片：如果一个程序请求 4097 字节，它需要两个 4096 字节的页，在第二个页中浪费了将近 4KB。此外，分配器本身也增加了开销：每次分配的元数据头部，以及为确保数据起始于 CPU 高效访问的地址而进行的对齐填充。一些分配器，比如伙伴系统，甚至会将分配大小向上舍入到下一个 2 的幂次方，这样做可能简单快速，但也可能浪费大量空间。根据分配模式，进行多次小的单独分配可能比一次大的分配然后手动分区造成的总浪费要少，这是因为头部和舍入规则之间复杂的相互作用。
旅程并未就此结束。正是使虚拟内存如此强大的机制——页表转换——也可能成为性能瓶颈。每次内存访问都要遍历多级页表会非常慢。为了解决这个问题，CPU 有一个特殊的、用于缓存近期翻译结果的高速缓存，称为转译后备缓冲器 (TLB)。
但随着内存容量的爆炸式增长，即使是 TLB 也可能不堪重负。如果一个程序正活跃地使用分布在数百万个 4KB 页上的数 GB 内存，TLB 会不断未命中，从而强制进行缓慢的页表遍历。解决方案是什么？大页（或超级页）。操作系统可以使用单个页表条目来映射一个 2MB 甚至 1GB 的块，而不是以 4KB 的块来映射内存。这极大地减轻了 TLB 的压力并提高了性能。
然而，这也带回了一个旧日的幽灵。一个大页，就像一个基页一样，对 MMU 来说是一个原子单位。你不能有一个大部分已映射的 2MB 大页，但在中间有一个 4KB 的“洞”用作哨兵页。这个新的限制迫使内存 sanitizer 面临一个艰难的选择：要么完全放弃大页，要么必须通过使哨兵本身也变成大页大小来适应。使用一个 2MB 的未映射页来保护一个 256KB 的分配，在虚拟地址空间方面是极其浪费的，并且在用于有效载荷的大页内部造成了巨大的内部碎片。这是系统设计者面临的永恒权衡的一个完美例子。
最后，我们那个老朋友 DMA 控制器呢？在一个分页系统中，虚拟内存中连续的缓冲区很可能在物理内存中是分散的。一个需要单个、物理上连续的缓冲区的简单 DMA 设备就束手无策了。现代系统通过两种方式解决这个问题。更智能的设备支持分散-聚集 DMA，操作系统可以提供一个物理块位置列表，供设备按顺序处理。对于更简单的设备，操作系统必须退回到使用反弹缓冲区：它分配一块宝贵的、物理上连续的内存，将用户的分散数据复制到其中，告诉设备在该缓冲区上工作，然后再将结果复制回来。最终的解决方案，输入/输出内存管理单元 (IOMMU)，本质上是为设备服务的第二个 MMU，允许它们在自己的虚拟地址空间中操作，从而优雅地一劳永逸地解决了这个问题。
从简单、直线的连续内存到错综复杂、虚幻的虚拟页世界，内存分配的原理是人类智慧的证明。这是一个问题催生解决方案，而解决方案反过来又产生新的、更微妙的问题的故事——一场硬件与软件之间为了管理一项基础资源而持续进行的舞蹈，一切都是为了让我们的计算机更强大、更可靠、更安全。
在我们迄今为止的旅程中，我们已经探索了内存分配的基本原理，即那些在我们计算机器深处运作的齿轮和杠杆。我们已经看到了分配器如何划分和管理这一宝贵的资源。但要真正欣赏这些机制的 genius 之处，我们必须看到它们的实际应用。我们必须超越“如何做”并追问“为什么”。为什么会采用这些特定的策略？它们在哪些地方产生了影响？
内存分配的故事并非一本枯燥的技术手册。它是一部宏大、 unfolding 的叙事，将最基本的硬件与最抽象的软件联系在一起。这是一个驯服混乱、从混乱的物理现实中创造出秩序和简洁幻象的故事。现在让我们踏上这片风景的旅程，看看我们学到的概念是如何成为编织现代计算结构（从操作系统核心到我们日常使用的应用程序）的无形之线。
操作系统（OS）是软件逻辑的纯净世界与物理硬件的狂野、常常 idiosyncratic 的世界之间的主要中介。它对内存的管理不仅仅是记账；它是一种动态的翻译和外交行为。
想象一个简单的、老式的硬件——一块来自 bygone 时代的网卡或图形处理器。这样的设备可能需要直接从系统内存中读取大量数据，比如说，一个视频帧。这个过程，即直接内存访问（DMA），允许设备独立工作而无需打扰主CPU。然而，这个 legacy 设备并不很聪明。它期望数据位于一个单一的、不间断的、物理上连续的块中。它只知道从一个物理地址开始，读取一定的长度，仅此而已。它不理解操作系统关于虚拟内存和分散页的巧妙障眼法。
这里就存在一个经典的操作系统挑战。在运行一段时间后，系统的物理内存会变得碎片化，就像一本书的页面被撕下并打乱了顺序。为我们的视频帧找到一个大的、 连续块变成了一项不可能的任务。操作系统能做什么呢？
一个直接但僵化的解决方案是在启动时，在碎片开始形成之前，就简单地留出一大块内存。这块“保留内存”与通用分配器隔离开来，保持原始状态，直到我们的特殊设备需要它。这种方法是确定性的、可靠的，但也很浪费，因为即使设备空闲，那块内存也不能用于任何其他目的。
在像 Linux 这样的现代系统中，有一个更优雅的解决方案，即连续内存分配器（CMA）。CMA 同样在启动时保留一个区域，但有一个关键的区别：它允许操作系统将这块内存“借出”用于临时的、可移动的用途，比如缓存来自磁盘的文件。当我们的设备驱动程序请求其连续块时，CMA 机制会优雅地将这些临时占用者迁移到别处，整合空间以满足请求。这提供了与静态保留相同的保证，但灵活性要大得多，确保可以为高清摄像机流水线等关键任务按需形成大的连续块，而不会让内存闲置。
当我们向故事中引入另一件硬件：输入-输出内存管理单元（IOMMU）时，真正的魔力便开始了。IOMMU 对于外围设备而言，就像 CPU 自己的 MMU 对于进程一样。它是一个位于设备和物理内存之间的硬件翻译器。
现在，我们的应用程序可以正常地分配它的 缓冲区，导致数千个页面散布在物理 RAM 中。那个仍然需要连续块的设备无法直接使用这些分散的页面。但现在，操作系统不必手忙脚乱地寻找物理上连续的块，而是可以施展一个更复杂的魔法。驱动程序收集所有分散的物理页地址列表，并对 IOMMU进行编程。它告诉 IOMMU：“为设备创建一个虚拟的连续块。让这个虚拟块的第一页指向这个物理页，第二虚拟页指向那个其他物理页”，以此类推。
然后，设备得到一个单一的起始地址——不是物理地址，而是一个I/O 虚拟地址（IOVA）。从设备的角度看，它看到了一个完美的连续 缓冲区。它执行 DMA 操作，而 IOMMU 则动态地将每个 IOVA 访问转换为正确的、分散的物理地址。
这种“零拷贝”方法效率极高。原始数据从未被移动或复制。替代方案——分配一个临时的、物理上连续的“反弹缓冲区”并复制数据——是一种消耗 CPU 周期并将传输所需内存带宽加倍的暴力方法。IOMMU 允许操作系统向设备呈现一个简单、理想化的内存视图，同时管理着底下复杂、碎片化的现实。这证明了增加另一层间接性的强大力量。
很长一段时间里，我们可以将主内存想象成一个单一、均匀的池。任何字节的访问速度都与其他字节一样快。在大型现代服务器中，这已不再是事实。这些机器通常有多个 CPU 插槽，每个插槽都有自己专用的、物理上相连的内存。这种架构称为非一致性内存访问（NUMA）。访问连接到 CPU 自身插槽的内存（“本地”内存）速度很快。访问连接到不同 CPU 插槽的内存（“远程”内存）需要穿越一个互连，使其显著变慢。
这个物理现实打破了“平坦”内存空间的简单抽象。操作系统不能再对数据放置的位置掉以轻心。考虑一个对延迟敏感的应用程序，其性能合同要求其平均内存访问时间不超过 。在一台 NUMA 机器上，本地访问需要 ，远程访问需要 ，一个简单的计算揭示了一个惊人的事实：为了达到目标，该应用程序至少有 的内存访问必须是本地内存 [@problemid:3664553]。
一个天真的操作系统如果将应用程序的线程和内存均匀地分布在所有节点上，将导致只有 的本地访问，平均延迟为 ——这是一次灾难性的性能失败。为了尊重 NUMA 架构，操作系统必须进化。它的内存分配器和进程调度器必须变得“拓扑感知”。解决方案是划分机器，使用像控制组（cgroups）这样的机制将对延迟敏感的应用程序的线程和内存限制在单个 NUMA 节点上。这保证了它的所有访问都是本地的，满足了严格的性能目标，并将其与在其他节点上运行的嘈杂邻居隔离开来。内存不再仅仅是一系列地址；它有了地理位置，而操作系统必须是一位专家级的地图绘制师。
从操作系统层面再往上走，我们会发现内存分配的原理对构成我们应用程序基石的数据结构的设计和分析产生了深远的影响。
考虑一下任何程序员工具箱中的必备品——不起眼的动态数组。它提供了按需增长列表的便利。当空间用尽时，它会分配一块更大的内存并将旧元素复制过去。但是这个高级操作如何与低级内存分配器交互呢？
如果我们的底层分配器是伙伴系统，它处理的是 2 的幂次大小的块，我们会看到一个有趣的相互作用。一个需要为 17 个 8 字节元素（ 字节）空间的动态数组，可能会被伙伴分配器分配一个 字节的块。分配的块大小与真正需要的空间之间的差异是一种内部碎片。随着数组的增长和缩小，它会在伙伴系统中引发一连串的分配、释放、分裂和合并操作，揭示了简单的 push 和 pop 操作背后隐藏的成本。
这引出了一个更深刻、更优美的问题：当动态数组需要增长时，它应该增长多少？传统智慧是将其容量加倍（增长因子 ）。这个策略确保了插入的摊还成本保持不变，即 。但是 总是最佳选择吗？
让我们想象一个场景，其中复制一个元素的成本与为其分配内存的成本相比极高。比如说，复制比分配昂贵 1000 倍。我们的直觉在这里可能很模糊，但一个正式的摊还分析给出了一个清晰无比，或许还令人惊讶的答案。
一次调整大小操作的总成本分为复制旧元素的成本和分配新空间的成本。这个成本由随后新空间 ermöglicht 的“廉价”插入“支付”。如果我们想平衡每次插入的摊还复制成本与每次插入的摊还分配成本，我们必须解一个简单的方程。结果是，最佳增长因子 应该是 ，其中 是复制成本与分配成本的比率。
如果复制比分配昂贵 1000 倍，那么最佳增长因子是 ！这意味着我们应该让我们的数组增长得非常巨大，但非常不频繁。通过这样做，我们最大限度地减少了我们必须支付高昂复制代价的次数。这是一个深刻的洞见：抽象的算法分析可以为设计高效的、现实世界的系统提供具体、非显而易见的指导。
到目前为止，我们已经看到操作系统和程序员是内存分配这出戏剧中的主要角色。但还有第三个，常常被忽视的角色：编译器或语言运行时，它们可以执行自己复杂的优化。
考虑一个在每次迭代中都在堆上分配一个小对象的循环。如果循环运行一百万次，那就是一百万次对内存分配器的调用，这可能是一个显著的性能瓶颈。然而，一个聪明的编译器可以分析代码以确定对象的生命周期。如果它能证明没有指向该对象的指针“逃逸”出循环迭代——也就是说，它没有被存储在任何比迭代生命周期更长的地方——它就可以执行一个非凡的转换。
编译器不是调用堆分配器一百万次，而是可以将分配提升到循环之外。它只在循环开始前分配一次一个可重用的内存区域，一个“竞技场”。在每次迭代内部，“分配”变成了一个微不足道的操作：简单地获取这个预分配竞技场的地址。因为第 次迭代的对象在第 次迭代开始时就已经死亡，所以内存可以安全地重用。这通常是通过一个“碰撞指针”来实现的，该指针在每次迭代结束时简单地重置到竞技场的开始处。这种由静态分析技术（如逃逸分析）驱动的优化，将一个昂贵的操作转变为一个几乎免费的操作，展示了工具链中的智能如何显著提高性能。
在现代软件中，许多应用程序运行在像 Java 虚拟机（JVM）或 WebAssembly（WASM）运行时这样的托管环境中。这些运行时本身是复杂的软件，它们执行自己的内存管理。这就创建了一个分层系统。那么，谁负责什么呢？
边界是由硬件的特权级别划定的。操作系统内核运行在特权模式下，这给了它对物理内存、页表和直接硬件访问的独占控制权。语言运行时，像任何其他应用程序一样，运行在用户模式下。它可以非常复杂，实现自己的垃圾收集器来自动管理其堆中对象的生命周期，或者在一小组原生操作系统线程上调度数千个轻量级的“绿色线程”。
然而，运行时不能破坏规则。它在操作系统赋予它的虚拟地址空间内管理内存。当它需要更多内存用于其堆时，它必须向内核发出系统调用以请求更多页面。它不能直接操纵页表或与设备对话。操作系统内核仍然是物理资源的最终仲裁者和进程间保护的执行者，而运行时则为应用程序代码本身提供了一个更高级别、更抽象、通常也更安全的环境。
尽管有所有这些复杂的管理层，事情仍然可能出错。在具有手动内存管理的语言中，一个常见且令人沮丧的错误是内存泄漏：内存被分配但从未被释放。一个长期运行的服务器中的小泄漏会随着时间的推移累积，最终耗尽所有可用内存并导致系统崩溃。在一个拥有数百万行代码的代码库中，我们如何找到这种泄漏的源头呢？
这个任务看似艰巨，但我们可以用算法的方式来处理它。当内存被分配时，我们不仅可以记录它的大小，还可以记录分配瞬间的*调用栈*——导致它的函数调用链。在程序结束时，我们可以识别所有从未被释放的分配。
现在，我们有了一个泄漏块的列表，每个块都标记了一个调用栈。绝妙的洞见是将这些调用栈视为一棵树中的路径。然后我们可以为每个唯一的调用栈前缀聚合泄漏内存的总量。例如，我们可能会发现 的泄漏内存来自其调用栈以 main() -> process_request() -> create_object() 开头的分配。通过找到占泄漏字节数最多的前缀，我们可以以惊人的精确度 pinpoint 问题的可能来源。这将一个大海捞针式的调试过程转变为一个结构化的数据分析问题，这是计算机科学原理在软件工程实践艺术中的一个美丽应用。
我们的旅程结束了。我们已经看到，内存分配远非一个已解决或 mundane 的问题。它是一个充满活力且至关重要的领域，构成了硬件架构、操作系统、编译器理论、算法设计和软件工程之间的十字路口。从确保摄像头能流畅地传输视频，到让 Web 服务器在微秒内响应，到帮助编译器优化循环，再到追查内存泄漏，内存分配的原理无处不在。这是一个充满权衡、优雅抽象和深刻、统一思想的世界，这些思想是我们数字世界运作方式的基础。