共计 5426 个字符，预计需要花费 14 分钟才能阅读完成。
介绍
利用基址和界线寄存器，操作系统很容易将不同过程重定位到不同的物理内存区域。然而，对于这些内存区域，栈和堆之间，有一大块“闲暇”空间。栈和堆之间的空间并没有被过程应用，却仍然占用了理论的物理内存。因而，简略的通过基址寄存器和界线寄存器实现的虚拟内存很节约。
泛化的基址 / 界线
为了解决这个问题，分段（segmentation）的概念应运而生。这个想法很简略，在 MMU 中引入不止一个基址和界线寄存器对，而是给地址空间内的每个逻辑段（segment）一对。一个段只是地址空间里的一个间断定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈和堆。分段的机制使得操作系统可能将不同的段放到不同的物理内存区域，从而防止了虚拟地址空间中的未应用局部占用物理内存。
咱们来看一个例子，如图所示，64KB 的物理内存中搁置了 3 个段。
你会想到，须要 MMU 中的硬件构造来反对分段：在这种状况下，须要一组 3 对基址和界线寄存器。下表展现了下面的例子中的寄存器值，每个界线寄存器记录了一个段的大小。
援用的是哪个段
硬件在地址转换时应用段寄存器。它如何晓得段内的偏移量，以及地址援用了哪个段？
一种常见的形式，有时称为显式（explicit）形式，就是用虚拟地址的结尾几位来标识不同的段。在咱们之前的例子中，有 3 个段，因而须要两位来标识。如果咱们用 14 位虚拟地址的前两位来标识，那么虚拟地址如下所示：
前两位通知硬件咱们援用哪个段，剩下的 12 位是段内偏移。因而，硬件就用前两位来决定应用哪个段寄存器，而后用后 12 位作为段内偏移。偏移量与基址寄存器相加，硬件就失去了最终的物理地址。请留神，偏移量也简化了对段边界的判断。咱们只有查看偏移量是否小于界线，大于界线的为非法地址。
下面应用两位来辨别段，但理论只有 3 个段（代码、堆、栈），因而有一个段的地址空间被节约。因而有些零碎中会将堆和栈当作同一个段，因而只须要一位来做标识。
硬件还有其余办法来决定特定地址在哪个段。在隐式（implicit）形式中，硬件通过地址产生的形式来确定段。例如，如果地址由程序计数器产生（即它是指令获取），那么地址在代码段。如果基于栈或基址指针，它肯定在栈段。其余地址则在堆段。
栈的问题
栈和其余的内存段有一点要害区别，就是它反向增长，因而地址转换必须有所不同。首先，咱们须要一点硬件反对。除了基址和界线外，硬件还须要晓得段的增长方向（用一位辨别，比方 1 代表自小而大增长，0 反之）。
反对共享
随着分段机制的不断改进，人们很快意识到，通过再多一点的硬件反对，就能实现新的效率晋升。具体来说，要节俭内存，有时候在地址空间之间共享（share）某些内存段是有用的。
为了反对共享，须要一些额定的硬件反对，这就是爱护位（protection bit）。基本上就是为每个段减少了几个位，标识程序是否可能读写该段，或执行其中的代码。通过将代码段标记为只读，同样的代码能够被多个过程共享，而不必放心毁坏隔离。尽管每个过程都认为本人独占这块内存，但操作系统机密地共享了内存，过程不能批改这些内存，所以假象得以放弃。
有了爱护位，后面形容的硬件算法也必须扭转。除了查看虚拟地址是否越界，硬件还须要查看特定拜访是否容许。如果用户过程试图写入只读段，或从非执行段执行指令，硬件会触发异样，让操作系统来解决出错过程。
操作系统反对
分段也带来了一些新的问题。第一个是老问题：操作系统在上下文切换时应该做什么？答案不言而喻：各个段寄存器中的内容必须保留和复原。每个过程都有本人独立的虚拟地址空间，操作系统必须在过程运行前，确保这些寄存器被正确地赋值。
第二个问题更重要，即治理物理内存的闲暇空间。新的地址空间被创立时，操作系统须要在物理内存中为它的段找到空间。之前，咱们假如所有的地址空间大小雷同，物理内存能够被认为是一些槽块，过程能够放进去。当初，每个过程都有一些段，每个段的大小也可能不同。
个别会遇到的问题是，物理内存很快充斥了许多闲暇空间的小洞，因此很难调配给新的段，或扩充已有的段。这种问题被称为内部碎片（external fragmentation）[R69]，如图所示。
该问题的一种解决方案是紧凑（compact）物理内存，重新安排原有的段。例如，操作系统先终止运行的过程，将它们的数据复制到间断的内存区域中去，扭转它们的段寄存器中的值，指向新的物理地址，从而失去了足够大的间断闲暇空间。然而，内存紧凑老本很高，因为拷贝段是内存密集型的，个别会占用大量的处理器工夫。
一种更简略的做法是利用闲暇列表治理算法，试图保留大的内存块用于调配。相干的算法可能有成千盈百种，包含传统的最优匹配（best-fit，从闲暇链表中找最靠近须要调配空间的闲暇块返回）、最坏匹配（worst-fit）、首次匹配（first-fit）以及像搭档算法（buddy algorithm）这样更简单的算法。但遗憾的是，无论算法如许精妙，都无奈齐全打消内部碎片，因而，好的算法只是试图减小它。
闲暇空间治理
咱们暂且将对虚拟内存的探讨放在一边，先来探讨闲暇空间治理（free-space management）的一些问题。在操作系统用分段（segmentation）的形式实现虚拟内存时，以及在用户级的内存调配库（如 malloc()和 free()）中，须要治理的闲暇空间由大小不同的单元形成。在这两种状况下，会呈现内部碎片的问题，让治理变得较为艰难。
假如
首先，咱们假设根本的接口就像 malloc()和 free()提供的那样。具体来说，void * malloc(size t size)须要一个参数 size，它是应用程序申请的字节数。函数返回一个指针，指向这样大小的一块空间。对应的函数 void free(void *ptr)函数承受一个指针，开释对应的内存块。
进一步假如，咱们次要关怀的是内部碎片的问题，先将外部碎片问题置之脑后。咱们还假如，内存一旦被调配给客户，就不能够被重定位到其余地位。最初咱们假如，分配程序所治理的是间断的一块字节区域。
底层机制
分隔与合并
闲暇列表蕴含一组元素，记录了堆中的哪些空间还没有调配。假如有上面的 30 字节的堆：
这个堆对应的闲暇列表如下：
能够看出，任何大于 10 字节的调配申请都会失败（返回 NULL），因为没有足够的间断可用空间。然而，如果申请小于 10 字节空间，会产生什么？假如咱们只申请一个字节的内存，此时分配程序会执行所谓的宰割（splitting）动作：它找到一块能够满足申请的闲暇空间，将其宰割，第一块返回给用户，第二块留在闲暇列表中。在咱们的例子中，假如这时遇到申请一个字节的申请，分配程序抉择应用第二块闲暇空间，对 malloc()的调用会返回 20（1 字节调配区域的地址），闲暇列表会变成这样：
许多分配程序中也有一种机制，名为合并（coalescing）。如果应用程序调用 free(10)，偿还堆两头的空间，会产生什么？分配程序不只是简略地将这块闲暇空间退出闲暇列表，还会在开释一块内存时合并可用空间。通过合并，最初闲暇列表应该像这样：
追踪已调配空间的大小
能够看到，free(void *ptr)接口没有块大小的参数。要实现这个工作，大多数分配程序都会在头构造（header）中保留一点额定的信息，它在内存中的地位通常就在返回的内存块之前。该头块中至多蕴含所调配空间的大小，它也可能蕴含一些额定的指针来减速空间开释，蕴含一个幻数来提供完整性检查，以及其余信息。咱们假设，一个简略的头块蕴含了调配空间的大小和一个幻数：
typedef struct header_t {
int size;
int magic;
} header_t;在内存中看起来像是这样：
用户调用 free(ptr)时，库会通过简略的指针运算失去头块的地位。取得头块的指针后，库能够很容易地确定幻数是否合乎预期的值，作为正常性查看（assert（hptr->magic == 1234567）），并简略计算要开释的空间大小（即头块的大小加区域长度）。因而，如果用户申请 N 字节的内存，库不是寻找大小为 N 的闲暇块，而是寻找 N 加上头块大小的闲暇块。
让堆增长
大多数传统的分配程序会从很小的堆开始，当空间耗尽时，再向操作系统申请更大的空间。通常，这意味着它们进行了某种零碎调用（例如，大多数 UNIX 零碎中的 sbrk），让堆增长。操作系统在执行 sbrk 零碎调用时，会找到闲暇的物理内存页，将它们映射到申请过程的地址空间中去，并返回新的堆的开端地址。这时，就有了更大的堆，申请就能够胜利满足。
根本策略
现实的分配程序能够同时保障疾速和碎片最小化。遗憾的是，因为调配及开释的申请序列是任意的，任何策略在某些特定的输出下都会变得十分差。
最优匹配
最优匹配（best fit）策略非常简单：首先遍历整个闲暇列表，找到和申请大小一样或更大的闲暇块，而后返回这组候选者中最小的一块。最优匹配背地的想法很简略：抉择最靠近用户申请大小的块，从而尽量避免空间节约。然而，简略的实现在遍历查找正确的闲暇块时，要付出较高的性能代价。
最差匹配
最差匹配（worst fit）办法与最优匹配相同，它尝试找最大的闲暇块，宰割并满足用户需要后，将残余的块退出闲暇列表。最差匹配尝试在闲暇列表中保留较大的块，而不是像最优匹配那样可能剩下很多难以利用的小块。最差匹配同样须要遍历整个闲暇列表，大多数钻研表明它的体现十分差，导致适量的碎片，同时还有很高的开销。
首次匹配
首次匹配（first fit）策略就是找到第一个足够大的块，将申请的空间返回给用户。首次匹配有速度劣势（不须要遍历所有闲暇块），但有时会让闲暇列表结尾的局部有很多小块。因而，分配程序如何治理闲暇列表的程序就变得很重要。一种形式是基于地址排序（address-basedordering），通过放弃闲暇块按内存地址有序，合并操作会很容易，从而缩小了内存碎片。
下次匹配
不同于首次匹配每次都从列表的开始查找，下次匹配（next fit）算法多保护一个指针，指向上一次查找完结的地位。其想法是将对闲暇空间的查找操作扩散到整个列表中去，防止对列表结尾频繁的宰割。这种策略的性能与首次匹配很靠近，同样防止了遍历查找。
其余形式
除了上述根本策略外，人们还提出了许多技术和算法，来改良内存调配。
拆散闲暇列表
它的根本想法很简略：如果某个应用程序常常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只治理这样大小的对象。其余大小的申请都交给更通用的内存分配程序。
这种办法的益处不言而喻。通过拿出一部分内存专门满足某种大小的申请，碎片就不再是问题了。而且，因为没有简单的列表查找过程，这种特定大小的内存调配和开释都很快。
不过这种形式也为零碎引入了新的复杂性。例如，应该拿出多少内存来专门为某种大小的申请服务，而将残余的用来满足个别申请？Solaris 零碎内核设计的厚块分配程序（slab allocator），很优雅地解决了这个问题。
具体来说，在内核启动时，它为可能频繁申请的内核对象创立一些对象缓存（object cache），如锁和文件系统 inode 等。这些的对象缓存每个拆散了特定大小的闲暇列表，因而可能很快地响应内存申请和开释。如果某个缓存中的闲暇空间快耗尽时，它就向通用内存分配程序申请一些内存厚块（slab）（总量是页大小和对象大小的公倍数）。相同，如果给定厚块中对象的援用计数变为 0，通用的内存分配程序能够从专门的分配程序中回收这些空间，这通常产生在虚拟内存零碎须要更多的空间的时候。
厚块分配程序比大多数拆散闲暇列表做得更多，它将列表中的闲暇对象放弃在预初始化的状态。数据结构的初始化和销毁的开销很大，通过将闲暇对象放弃在初始化状态，厚块分配程序防止了频繁的初始化和销毁，从而显著升高了开销。
搭档零碎
因为合并对分配程序很要害，所以人们设计了一些办法，让合并变得简略，一个好例子就是二分搭档分配程序（binary buddy allocator）。
在这种零碎中，闲暇空间首先从概念上被看成大小为 2ⁿ的大空间。当有一个内存调配申请时，闲暇空间被递归地一分为二，直到刚好能够满足申请的大小。这时，申请的块被返回给用户。在上面的例子中，一个 64KB 大小的闲暇空间被切分，以便提供 7KB 的块：
请留神，这种调配策略只容许调配 2 的整数次幂大小的闲暇块，因而会有外部碎片（internal fragment）的麻烦。
搭档零碎的精华在于内存被开释的时候。如果将这个 8KB 的块归还给闲暇列表，分配程序会查看“搭档”8KB 是否闲暇。如果是，就合二为一，变成 16KB 的块。而后会查看这个 16KB 块的搭档是否闲暇，如果是，就合并这两块。这个递归合并过程持续上溯，直到合并整个内存区域，或者某一个块的搭档还没有被开释。
搭档零碎运行良好的起因，在于很容易确定某个块的搭档。仔细观察的话，就会发现 每对互为搭档的块只有一位不同，正是这一位决定了它们在整个搭档树中的档次。
其余想法
下面提到的泛滥办法都有一个重要的问题，不足可扩展性（scaling）。具体来说，就是查找列表可能很慢。因而，更先进的分配程序采纳更简单的数据结构来优化这个开销，就义简略性来换取性能。例子包含均衡二叉树、舒展树和偏序树。
思考到古代操作系统通常会有多核，同时会运行多线程的程序，因而人们做了许多工作，晋升分配程序在多核零碎上的体现。感兴趣的话能够深刻浏览 glibc 分配程序的工作原理。
