前言
本文介绍虚拟内存如何工作以及应用程序如何使用和管理虚拟内存。虚拟内存由硬件异常、硬件地址翻译、主存、磁盘文件和内核交互，为每个进程提供一个大的、一致的和私有的地址空间，提供如下三个重要功能：
- 作为主存和磁盘的高速缓存，在主存中只保存活动区域
- 为每个进程提供了一致的地址空间，从而简化内存管理
- 保护每个进程的地址空间不被其他进程破坏
虚拟内存作为缓存的工具
磁盘和主存间的传输单元为虚拟页(Virtual Page, VP)。虚拟页和物理页(页帧)为相同的固定大小的块。虚拟存储在磁盘上，物理页存储在主存中。在任意时刻，虚拟页集合分为三个不相交的子集：未分配的，缓存的和未缓存的。
术语SRAM缓存表示CPU和主存之间的L1、L2和L3高速缓存，DRAM缓存表示虚拟内存系统的缓存，在主存中缓存虚拟页。因为大的不命中处罚和访问磁盘第一个字节的开销，所以虚拟页往往很大，通常在4KB~2MB。由于大的不命中处罚，DRAM缓存是全相联，即任何虚拟页都可以放置在任何的物理页中。最后，因为对磁盘的访问时间长，DRAM缓存总是使用写回，而不是直写。
页表
页表就是一个页表条目(Page Table Entry,PTE)的数组。虚拟地址空间中的每个页在页表中一个固定的偏移量处都有一个PTE。每个PTE项包括一个有效位和一个n位地址字段。有效位表明该虚拟页当前是否被缓存在DRAM中，如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么一个空地址表示这个虚拟页还未分配。否则，这个地址就指向该虚拟页在磁盘上的起始位置。为了控制内存系统的访问，PTE表项中添加一些额外的许可位来控制对一个虚拟页面内容的访问。如果指令违反了许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell一般将这种异常报告为”段错误(segmentaion fault)”。PTE示意图如下：
局部性
虚拟内存系统能够工作良好，是由于局部性，局部性保证程序在一个较小的活动页面集合上工作，这个集合叫做工作集或者常驻集合。只要我们的程序有好的时间局部性，虚拟内存系统就能工作良好。如果程序性能低下，考虑是否发生了抖动，即页面不断的换进换出。可以使用Linux的getrusage函数检测缺页的数量以及其他信息。
动态内存分配
实现问题
- 空闲块组织：如何记录空闲块？
- 放置：如何选择一个合适的空闲块来放置新分配的块？
- 分割：在将一个新分配的块放置到某个空闲块之后，如何处理这个空闲块的剩余部分？
- 合并：如何处理一个刚刚被释放的块？
隐式空闲链表
分配器需要一个数据结构来区别块边界，以及区别已分配块和空闲块。大多数的分配器将这些信息嵌入块本身。一个块由4Byte的头部，有效载荷以及可选的额外填充组成。头部编码块的大小(包括头部和所有填充)以及这个块是已分配还是空闲的。如果强加一个8Byte的对齐约束，那么块大小总是8的倍数，因此块大小的最低3bit总是零。从而，块大小表示使用头部的高29bit，剩余的3bit来编码其他信息。在这种情况下，我们用其中最低位来指示块是已分配的还是空闲的。填充块用来满足对齐或者对付外部碎片。简单的堆块格式如下：
将堆组织为一个连续的已分配块和空闲块的序列，这种结构称为隐式空闲链表。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。在该示例中，设置了已分配位而大小为零的终止头部的结束块。隐式链表结构如下图所示：
隐式空闲链表的优点是简单，显著的缺点是任何操作的开销，例如放置分配的块，要对空闲链表进行搜索，该搜索所需时间与堆中已分配块和空闲块的总数呈线性关系。
放置已分配的块
当应用程序请求分配k字节时，分配器搜索空闲链表，查找一个足够大可以放置所请求块的空闲块。这种搜索方式称为放置策略，常见的包括首次适配、下一次适配和最佳适配。
首次适配从头开始搜索空闲链表，选择第一个合适的空闲块。下一次适配和首次适配相似，只不过不是从头开始搜索，而不是从上一次查询结束的地方开始。最佳适配检查每个空闲块，选择所需请求大小的最小空闲块。
分割空闲块
分配器找到一个匹配的空闲块，接下来的决策就是分配这个空闲块中多少空间。一个选择是用整个空闲块，简单快捷，但缺点是造成内部碎片。另外就是将空闲块分割成两部分，第一部分变成分配块，而剩下的变成一个新的空闲块。下图展示从6个字节的空闲块中分配4个字节，剩余的2个字节变成新的空闲块:
释放内存
释放内存仅仅需要清除堆块中头部的标志信息，具体过程如下所示：
获取额外的堆内存
如果分配器不能为请求块找到合适的空闲块将发生什么？一个方案是合并内存中相邻的空闲块，如果空闲块已经最大程度合并仍然不能生成足够大的内存块，那么分配器会通过调用sbrk函数，向内核请求额外的堆内存，然后将块插入到空闲链表中，最后将请求的块放置在这个新的空闲块中。
合并空闲块
为了解决假碎片问题，任何实际的分配器必须合并相邻的空闲块，这个过程称为合并(coalescing)。执行合并的时期包含不同的策略：立即合并(immediate coalescing)，也就是在每次一个块释放时，就合并所有的相邻的块。或者也可以使用推迟合并(deferred coalescing)，即等到某个稍晚的时候再合并空闲块。立即合并简单明了，可以在常数时间内执行完成，但对于某些请求模式，这个方式会产生一种抖动，块反复合并，然后马上分割。快速的分配器通常会选择某种形式的推迟合并。
带边界标记的合并
合并下一个空闲块十分简单，因为当前块的头部指向下一个块的头部，通过判断下一个块的头部是否空闲，如果是，就将它的大小简单地加到当前块头部的大小上，这两个块在常数时间内被合并。合并当前块的下一个块如下所示：
困难在于如何合并当前块前面的块呢？Knuth提出了一种聪明而通用的技术，叫做边界标记(boundary tag)，允许在常数时间内进行对前面块的合并。该思想在每个块的结尾处添加一个脚部(footer，边界标记)，其中脚部就是头部的一个副本。如果每个块包括这样一个脚部，那么分配器就可以通过它的脚部，判断前面一个块的起始位置和状态，因为脚部总是在距当前块开始位置4Byte的距离。使用边界标记的堆块格式如下所示：
边界标记的概念简单优雅，对许多不同类型的分配器和空闲链表组织都是通用的。缺点就是要求每个块都保持一个头部和一个脚部，在应用程序操作许多小块时，会产生显著的内存开销。另外一种更聪明的边界标记优化方法，能够使得在已分配块中不再需要脚部。因为我们试图合并当前块以及前面的块和后面的块时，只有前面的块是空闲时，才会需要用它的脚部。如果我们把前面块的已分配/空闲位存放在当前块中多余的低位中，那么已分配的块就不需要脚部了，这样我们就可以将这个多出来的空间用作有效载荷了。不过注意，空闲块仍然需要脚部。当分配器释放当前块时包含如下四中情形：
case 1）前面的块和后面的块都被分配
case 2）前面的块分配，后面的块空闲
case 3）前面的块空闲，后面的块分配
case 4）前面的块和后面的块都空闲
上述情形合并过程如下所示：