虚拟内存
概述
本文首先介绍虚拟内存的基本概念，随后依次介绍它的三大用途：缓存工具、内存保护、内存映射，最后介绍基于此的动态内存分配。
就计算机执行程序而言，其具有两种执行方式：物理寻址 (程序代码直接放入物理主存之中，并依照物理地址按序访问指令)、虚拟寻址 (程序代码以某种方式放入主存之中，借助于硬件翻译指令的虚拟地址，以实现按序访问指令)。
早期计算机使用前种方式执行程序，而现有计算机均基于后种方式执行程序。
根据虚拟寻址的解释，可以知道：对于任意一条指令而言，其分别具有一个虚拟地址和一个物理地址。
将虚拟地址的集合称为虚拟地址空间，将物理地址的集合称为物理地址空间，那么虚拟寻址便是构建了两者间的映射关系，并以此执行程序。
缓存工具
虚拟地址空间存在于磁盘 (因为目标文件位于磁盘)，而物理地址空间存在于主存。根据存储器金字塔结构，因为局部性原理，主存可作为磁盘的高速缓存；又因为程序通常存在局部性原理，那么物理地址空间也可作为虚拟地址空间的高速缓存。
计算机内部以页作为两者之间的传输单位，物理地址空间中的页称为物理页，虚拟地址空间中的页称为虚拟页。对于虚拟页而言，其具有如下分类：
- 未分配页，即尚未被虚拟内存分配的页，这是由于其中并不包含代码或数据，因而无需存储。
- 缓存页，即已被缓存至物理主存的页。
- 未缓存页，即虚拟内存已分配而尚未被物理主存缓存的页。
因为虚拟地址空间位于磁盘，而物理地址空间位于主存，两者之间不命中代价过大，因此两者之间的高速缓存 (即页表) 具有如下结构特征：
- 页容量较大，通常为 4KB ~ 2MB。
- 基于全相联结构。
- 采用较为复杂的页面替换策略。
- 采用写回策略。
页表的具体结构如下：
另外，考虑到主存页表访问缓慢，因此计算机还提供高速缓存以缓存页表条目，称为 TLB (Translation Lookaside Buffer)，其结构为组相联：
此时，计算机翻译虚拟地址为物理地址，并执行指令的流程如下：
- CPU 获取一个虚拟地址
- MMU 尝试从 TLB 中获取该虚拟页的映射条目，若获得，则翻译得到物理地址并从高速缓存/主存中取得指令。
- 若无法获得，尝试从高速缓存/主存中获取该虚拟页的映射条目，若获得，则翻译得到物理地址并从高速缓存/主存中取得指令。
- 若无法获得，则表明该虚拟页并没有缓存于物理主存之中，则调用缺页中断处理程序，调取相关页至物理主存，随后即可获得该虚拟页的映射条目，然后翻译得到物理地址并从高速缓存/主存中取得指令。
注：页表条目可能存在于 TLB、高速缓存、主存页表之中。
上面所谈页表均指代单张页表，然而如此组织会大大占用物理主存空间。为解决此问题，现有计算机往往实现多级页表以压缩页表大小：即拆分单张页表为多张页表，一级页表条目索引二级页表位置、二级页表条目索引三级页表位置、……、最后一级页表定位虚拟页与物理页映射，其示意结构与地址翻译过程如下示：
实现多级页表具有如下优点：
- 如果某些虚拟页从未被使用，则可无需分配相关页表，从而降低总体页表大小。
- 仅一级页表必须存入物理主存，其余页表或放入主存或放入交换空间，从而降低物理主存压力。
内存保护
基于虚拟内存的内存保护机制实现于页表条目之上：首先为页表条目添加若干位信息 (例如，某位表示当前物理页是否可写，某位表示当前物理页是否能运行于内核模式之下)，随后载入虚拟页与物理页映射信息时设置相关位信息，最后在 MMU 翻译虚拟地址时查看位信息的约束条件以判断当前访问是否合法，从而实现内存保护。
内存映射
内存映射具体可细分为内存映射 IO 和内存映射文件，在此仅介绍内存映射文件。
内存映射文件指代将一个虚拟内存区域与一个磁盘对象关联起来，并以此文件内容初始化此虚拟内存区域。
针对内存映射文件而言，磁盘对象具有如下两种类别：
普通文件
建立关联后，只有当 CPU 第一次访问该虚拟内存区域的虚拟地址时，系统才会基于缺页中断获取文件内容、选择合适的物理页进行映射，并以此内容填充物理页。
mmap(void *start, size_t length, xxxx,int fd, off_t offset)用于将文件描述符 fd 偏移 offset 处、长度为 length 的数据映射至虚拟内存 start 处、长度为 length 的空间。匿名文件
匿名文件为内核创建的、内容全为二进制零的文件。
建立关联后，只有当 CPU 第一次访问该虚拟内存区域的虚拟地址时，系统才会换出一个物理页、将该物理页内容置为全零，并建立该物理页与虚拟页间的映射关系。mmap(void *start, size_t length, xxxx,-1, off_t offset)用于将匿名文件映射至虚拟内存 start 处、长度为 length 的空间，实质就是向内核申请一块物理主存。
根据映射对象的共享程度，又可细分为如下两种类别：
共享映射
所映射的对象共享于多个进程，并且某进程的任何修改都会反映至各进程及磁盘。
私有映射
所映射的对象虽可共享于多个进程，但是某进程的修改仅自己可见 (基于写时复制技术实现，即当进程欲修改私有对象时，系统会发现此为私有对象，便重新分配一个物理页至当前虚拟页，然后允许进程修改此物理页)。
可以看到：无论是共享映射，还是私有映射，都是在尽最大程度地利用物理主存。
当 fork() 函数被当前进程调用时，内核会为新进程分配各种数据结构 (例如，PID)，然后创建当前进程虚拟内存相关数据结构的一个副本，以此实现当前进程与新进程私有映射虚拟内存。如此操作，造成的效果便是：当前进程与新进程具有相同的虚拟地址空间，但是两者仍不相干。
当 execve() 函数被当前进程调用时，内核会删除现有的虚拟内存，并基于私有映射以映射私有数据，基于共享映射以映射共享数据，最后重置 PC 寄存器。
动态内存分配
动态内存分配指代动态分配虚拟地址空间中堆的内存给相应变量。
因为动态内存分配不仅涉及分配内存，同样涉及释放内存，因此如何有效管理堆内存，以保证堆尽可能小，同时提供完整功能，这便需要认真设计动态内存分配器。
动态内存分配器将对内存视为一组不同大小的块集合进行维护 (类似下图)，其中每个块要么已分配给某个变量，要么处于空闲状态。处于空闲状态的块等待被分配给进程使用；处于已分配状态的块保持分配状态，直至其被程序自身释放 (此种分配器称为显式分配器)，或被垃圾回收器释放 (此种分配器称为隐式分配器)。
注意：实际计算机内部往往具有块大小约束及块对齐要求。
按照请求分配空闲块存在两种情况：1. 请求空间小于空闲块空间，且两者之差不足以构建一个空闲块，或者两者之差不满足块对齐要求，此时便存在内部空间浪费，此种称为 内部碎片。2. 请求空间小于等于所有空闲块空间之和，却大于任意单个空闲块空间，此时便存在外部空间浪费，此种称为 外部碎片。此两种情况会降低堆内存的利用效率，应当尽可能减少该种情况的发生。
显式分配器
我们首先介绍最简单的块组织方式 —— 隐式空闲链表，随后介绍更为高效的块组织方式 —— 显式空闲链表、分离的空闲链表。
隐式空闲链表
对于隐式空闲链表而言，其中块具有如下结构 (块首存放块大小和分配信息)：
注：如果设定块 8 字节对齐，那么块大小一定是 8 的倍数，因此只需高 29 位表征块大小即可，其余 3 位用于存放其他信息。
基于此种结构，我们很容易实现块的按序索引 (即当前块位置 + 块大小 = 下一块位置)，如此便构成隐式链表 (设定：如果某块大小为 0 且已分配，则表明其为隐式空闲链表的尾部。)：
注：实际实现之中，为满足对齐要求，堆开始处可能存放无用块。另外为简化后续的空闲块合并，往往存在隐式空闲链表的首部块。
基于此结构，容易实现块分配 (即基于首次适配或最佳适配等放置规则选择合适块，然后设置该块为分配块即可，可能需要视对齐要求和块大小限制进行分割块)、块回收 (直接设置该块为未分配即可)。然而，对于块合并而言，其具有一点困难：容易合并当前空闲块与后继空闲块，而无法快速合并前驱空闲块。为解决此问题，通常修改块结构如下：
显式空闲链表
隐式空闲链表具有一个大缺点，即需搜索全部堆块以寻找合适块进行分配。为解决此问题，显式空闲链表通过在空闲块内添加指向前驱和后继的空闲块索引，从而实现只需搜索所有空闲块，即可寻找合适块进行分配。此时，块结构如下：
基于此结构，容易实现块分配和块合并。而块分割或者块回收具有两种不同实现方式 (相比于后者而言，前者操作更快；然而，当采用首次适配进行块分配时，后者的内存利用率更高，且几近于最佳适配的内存利用率)：
基于后进先出 (LIFO) 维护空闲链表
当块分割或块回收后，直接将空闲块放置于链表首部，如此可实现常数操作。
按照地址顺序维护空闲链表
当块分割或块回收后，按空闲链表查找位于此位置之前的那个空闲块，并将其放置于该空闲块之后，如此实现需要搜索所有空闲块。
分离的空闲链表
显式空闲链表虽已改进块分配性能，然而它需要搜索全部空闲块。为进一步提高效率，分离的空闲链表被提出，它基于块大小将所有的空闲块分配至多个空闲链表，如此可将搜索范围缩至特定块大小范围的链表所含的空闲块。
当请求来临时，首先查找维护特定块大小范围的空闲链表，如果找到直接分配，否则查找比此特定块大小范围更高一级的空闲链表，找到直接分配，否则仍按此规则查找，直至不存在满足要求的空闲块，此时需要申请堆内存以构建满足要求的空闲块，然后分配即可。如果空闲块可分割的话，则将分割的空闲块放置相应的空闲链表即可。
注：针对分离的空闲链表采用首次适配策略，其内存利用率近乎于针对整个堆的最佳适配策略的内存利用率。另外，C 语言的 malloc 函数即是基于此实现动态分配器的。
隐式分配器
隐式分配器使用垃圾回收器自动回收堆存储过程中的不再使用的已分配块。此处简略说明垃圾回收器的基本原理。
垃圾回收器将内存视为一张有向可达图，其形式如图所示：
图中节点分为两类：根节点 (存放于栈、寄存器或全局变量内)、堆节点 (存放于堆中，对应于已分配块)。每个根节点指向一个堆节点，堆节点内部又存有其他堆节点的指针。当存在一条从某任意根节点出发并到达堆节点 p 的有向路径，则称堆节点 p 可达，反之称为不可达。
垃圾回收器的工作便是基于某种形式维护有向可达图，并适时回收堆中不可达的堆节点。