1. 管理内存
内存（RAM）是计算机中一种需要认真管理的资源。虽然当前内存的存储容量在飞速的增长，但程序的大小的增长速度却比内存容量增长的还要快得多。所以合理利用内存资源是一个迫在眉睫的问题。
经过多年的探索，人们提出了分层存储器体系（memory hierarchy）的概念，在这个体系中，有只有若干兆（MB）的、昂贵的、速度可以比肩CPU的寄存器，也有数千兆（GB）的、价格和速度都适中的内存，同样有数兆兆（TB）的低速廉价的硬盘。操作系统的工作是将这个分层存储体系抽象成一个有用的模型并管理这个抽象模型。
操作系统中管理分层存储体系的内存的部分叫做存储管理器（memory manager）。它的任务是高效的管理内存，即记录哪些内存正在被使用，哪些内存是空闲的，在进程需要的时候为其分配内存，在进程使用完后释放内存。
历史的发展过程中存储管理器的管理方案不是一成不变的，下面首先从最简单的管理方案开始，逐步介绍到更为缜密的方案。
2. 无存储器抽象
2.1. 最简单的无存储器抽象
最简单的存储器抽象就是没有抽象，即每一个程序都直接访问物理内存。不过这种无存储器抽象仅活跃于遥远的历史中（20世纪80年代之前）。
那个时候对于一个程序员来说，呈现在眼前的就是最直接的物理内存：从0到某个上限的地址集合。这种情况下很难同时运行两个以上的程序，因为一个程序很容易就访问到了另一个程序用到的内存，这样通常会导致另一个程序的崩溃。
按照这种方式组织系统的时候，通常同一时间只有一个程序在运行。当用户输入一个命令之后，操作系统将这个程序从硬盘加载到内存上并执行，运行完成后打印输出并等待下一条命令，键入下一条命令后操作系统把新程序加载到内存并覆盖上一个程序。
在无存储器模型下实现并行的一个可能的方法是使用线程，因为线程的设计之初就假设了同一个进程内的所有线程共享同一内存映像，恰好符合无存储器模型的特点。不过人们通常希望并行执行的是毫不相关的程序，这就不是线程的强项了，并且使用无存储器模型的早期电脑可能实现线程抽象都是个问题。
2.2. 无存储器抽象的情况下运行多个程序
在没有存储器抽象的情况下，同时运行多个程序也是有可能的。操作系统只需要把当前内存中的所有内容保存到硬盘上，再加载另一个程序到内存中就可以了，等到想运行上一个程序的时候再把硬盘中保存的内容重新加载到内存中即可。同一时间保证只有一个程序在运行就不会发生冲突。这就是交换的思想。
同样有某些技术可以不借用交换的思想就实现多个程序同时运行。IBM 360的早期模型是这样解决的：内存被划分为2KB的块，每个块都分配有一个四位的保护键来表示这个块现在是属于哪个程序的。PSW（Program Status Word，程序状态字）中保存了当前进程的一个四位码，每个程序只能访问保护键和自己的四位码相同的内存块。如果某个程序试图访问保护键与自己的四位码不同的内存块，操作系统就能很容易的捕获到，从而及时阻止这一行为。
但这个方法有一个严重的漏洞，如上图所示。现有两个程序即图a和图b，它们各自需要占用内存16KB，一个灰色一个白色表示这些内存块具有不同的保护键，即暂时属于不同的程序。程序a一开始0地址处的指令是跳转到地址24，而程序b的0地址处的指令是跳转到地址28，这看起来没什么问题。当这两个程序被同时加载到内存中时，假设如图c所示，程序a在下，程序b在上面紧挨着存储。这时候程序a运行起来后还是没什么问题，但等到程序b开始运行问题就大了，程序b直接跳到地址28处，而此时地址28属于程序a，所以操作系统捕捉到后直接报错导致程序b崩溃。
这里的关键问题是两个程序都直接使用了物理地址，而这正是需要避免的。我们希望每个程序都使用私有的本地地址来对内存寻址，而本地地址又能自动的转换成物理地址。之后的历史发展逐渐满足了这一要求。先来看看IBM 360是怎么解决这个问题的，它使用了静态重定位技术来改善这个问题。即当一个程序例如程序b被加载到了 16384 的位置上，加载的时候操作系统会自动给程序中的每个地址加上常数 16384。静态重定向机制理论上是可行的，但这不是一种通用的解决方案，因为这会拖慢程序的加载速度，并且它需要可执行程序提供额外的信息表示程序中的哪些数据需要加上这个常数而哪些不用，因为操作系统可能无法区分程序中哪些是地址哪些是普通的数据。
最后，历史的发展并不是将所有旧的东西都颠覆掉，而是取其精华剔其糟粕。虽然无存储器抽象在大型计算机、小型计算机、台式计算机上已经销声匿迹了，但在嵌入式系统和智能卡系统中还是很常见的。现在，如收音机、洗衣机或微波炉这样的设备都已经由软件（ROM形式）来控制了，在这些情况下软件都还是使用直接访问物理地址的方式来运行的。这能够正常运行的原因是，这些设备上运行的程序都是事先确定的，写死在了ROM上，这样一切的地址访问都是可控的，不用担心访问非法的内存。
3. 一种存储器抽象：地址空间
总之，直接将物理内存暴露给进程是一件很危险的事情。第一，程序可以（恶意的）自由访问其他程序甚至是操作系统的内存，从而做某些破坏（除非使用某些额外的保护方案，如IBM 360的保护键模式）。第二，使用这种模型，想要同时运行多个程序是很困难的，尤其是还需要解决地址的重定位问题。因此，我们需要其他办法。
3.1. 地址空间
要使多个程序同时处于内存并且不受影响，有两个必须要解决的问题：保护和重定位。上一小节介绍的IBM 360通过保护键模式解决了保护的问题，而重定位问题被静态重定向技术解决了，但这是一个缓慢且复杂的技术。
一个更好的方法是创造一个新的存储器抽象：地址空间。就像进程的引进就创造了一类抽象的CPU以运行程序一样，地址空间为程序创造了一种抽象的内存。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有各自独立的地址空间（除非某些需要共享某一内存区域的特殊场景）。
这个技术的难点在于如何使每个进程的地址空间各自独立，即一个程序中的地址28和另一个程序的地址28代表的是不同的物理内存地址。下面是一个简单的解决方案，但是随着历史的推进，操作系统有了更复杂而且更好的解决方案。
基址寄存器与界限寄存器
这个简单的解决方法是动态重定向，对应于更早的静态重定向，这种方法同样简单的把每个进程的地址空间映射到物理内存的不同部分。具体的实现细节是，每个CPU配置两个特殊的硬件寄存器，通常叫做基址寄存器和界限寄存器。当时用这种方法的时候，程序装载到内存中的连续空闲位置并且无需事先重定位。考虑下面这个熟悉的图，两个程序被相邻的加载到内存中，当运行处于下方的程序的时候，基址寄存器中填入程序的起始物理地址，对于下面的例子即地址0，而界限寄存器中填入起始物理地址加程序的长度即地址16380。而当运行位于上方的程序的时候基址寄存器填入地址16384，界限寄存器填入地址32764。
3.2. 交换技术
交换技术为了解决什么问题
如果物理内存足够大，上面所介绍的实现多个程序同时运行的多种技术可能勉强能用。但事与愿违，现代windows、OSX或者Linux仅仅在完成引导后都会启动50~100个进程，有的在后台等待email，有的等待可能的网络连接，而典型的用户程序 Photoshop 仅一启动就能轻易的占据500MB内存，开始处理图像后轻易能占据数GB内存。因此，像上面的方法中把所有进程一直保存在内存中需要耗费巨大的内存，如果内存不够，就没办法同时运行。
有两种解决内存超载的技术。最简单的是交换（Swapping）技术，即把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当它们不运行的时候就不占用内存（尽管其中的一些进程会被周期性的唤醒以完成相关工作，然后又进入睡眠状态）。另一种策略是虚拟内存（virtual memory），该策略甚至可以使程序只有一部分调入内存的情况下运行。下面先介绍交换技术。
交换系统的操作如上图所示。开始的时候内存中只有进程A。之后创建进程B和C或者将它们从磁盘上换入内存。第四张图表示将进程A换入磁盘，然后将进程D换入内存。最终再把进程B换入磁盘，把进程A换回内存。由于A的位置发生变化，所以它换入的时候要重新进行静态重定位或者在程序运行期间（多数是这种情况）通过硬件对其地址进行动态重定位。
交换技术的弊端
交换在内存中产生了多个空闲区（hole，也即空洞），即上图中的阴影部分。可以想象如果内存中存在很多进程并且经过足够长的时间后，内存中可能会出现大量的小空洞，这些小空洞加起来表示内存还有相当一部分空间是空闲的，但此时却无法加载任何一个相对较大的进程，这就降低了内存的使用率。解决这一问题的一个可能的措施是把所有进程向下移动，使得所有小空洞合并成为一个大空洞，这种技术称为内存紧缩（memory compaction）。但通常不进行这一操作，因为搬运如此大量的内存空间需要耗费相当多的CPU时间。
还有一个需要考虑的问题，即进程创建或者换入的时候为其分配多大的内存。我们知道很多程序设计语言允许在堆上动态的申请空间，如果该进程在内存中与一个空闲区相邻，那么可以把空闲区分配给该进程供其增长。但如果周围都紧挨着其他进程，那么就需要把该进程换到另一个更大的空闲区以便继续运行，这可能比较难以实现并且要耗费大量移动数据的时间。
一种解决上述问题的方式是为每一个进程分配一些冗余的空间，这样就可以保证该进程在只需要一些额外内存的情况下可以免去繁琐的内存搬移。
3.3. 空闲内存管理
在动态分配内存时，操作系统必须对其进行管理。一般而言，有两种方法跟踪内存使用情况：位图和空闲区链表。而Linux系统可能还是用了一些特定的内存分配器（如伙伴分配器和slab分配器）。
使用位图管理内存
使用位图时，内存可能被划分成小到几个字节大到几千个字节的分配单元。每个分配单元对应位图中的一位，0表示空闲，1表示占用（或者相反）。如下图所示，图a是一块内存，图b是这块内存对应的位图：
分配单元的大小是一个重要的设计因素。分配单元越小，位图所需空间越大。然而即使分配单元只有4字节即32位，也能算出位图只需要物理内存的1/32的大小。而分配单元更大则位图所需空间就越小。但若进程的大小不是分配单元的整数倍，则最后一个分配单元中就会有些比特被浪费掉。
位图提供了一种简单的，可以利用一块固定大小的空间就来记录管理内存的方法。但这种方法的主要问题在于，当要载入一个占k个分配单元的程序的时候，操作系统需要在位图中寻找有k个连续0的串，而这是一种费时的操作。
使用链表管理内存
另一种记录内存使用的方法是，维护一个记录已分配内存段和空闲内存段的链表。其中链表的一个节点可能包含一个进程，或者包含两个进程间的一块内存区。如下图所示：
链表的每个节点都包含以下域：空闲区（H）或进程（P）的指示标志，起始地址，长度和指向下一节点的指针。
在图示例子中，段链表是按照地址升序排列的，其好处是进程终止或者被换出链表的时候的更新非常直接。一个要终止的进程在段链表中通常有两个邻居，那么终止的时候就可能会有如下四种情景。
这几种情况下需要对段链表进行一些合并操作，所以使用双向链表可能会更加方便。当按照地址升序来存储段链表时，有几种算法可以用来为一个进程分配内存：
- 首次适配算法（first fit）：这是一种最简单的查找空闲区的算法。操作系统沿着段链表顺序查找，直到遇到一块足以容纳新程序的空闲区，并将这块空闲区分割成两个部分，一个分配给进程，一个划分成新的空闲区。这是一种速度很快的算法。
- 下次适配算法（next fit）：下次适配算法与首次适配算法很像，只不过每次找到空闲区的时候都记录下当前的位置，当下次寻找空闲区的时候会从记录位置开始寻找而不是再从头开始寻找。
- 最佳适配算法（best fit）：最佳适配算法搜索整个段链表，找到一块能容纳新程序的最小的空闲内存分配给新程序。最佳适配算法尝试寻找一块最适合的空闲区，而不是拆分一个可能日后会用到的大空闲区。
最佳适配算法由于每次都需要遍历整个链表，所以效率更低，而且同样让人意外的是，最佳适配算法比首次适配算法浪费更多的内存，因为最佳适配算法每次都会产生一个很小的空闲区，而相比之下首次适配算法产生的空闲区可能更大。见招拆招，人们又想出了最差适配算法（worst fit），即总是分配最大的空闲区，但仿真软件表示这也不是一种好的方法。
还可以将空闲区和进程分离成两条不同的链表，然后让空闲区链表按照空间大小有序排列，这样查找空闲区的速度就可以加快，但同时终止程序释放内存时的合并速度又会变慢。
最后一种分配算法称为快速适配算法（quick fit），它为那些常用大小的空闲区维护单独的链表。例如，所有大小为4K的空闲区组成一条链表，所有大小为8K的空闲区组成一条链表，依此类推。这种方法寻找一块指定大小的空闲区的速度非常快，但缺点同样明显，在进程终止后合并空闲区成了一个耗时的大麻烦。
4. 虚拟内存
尽管基址寄存器和界限寄存器可以用于创建地址空间的抽象，但还有另一个问题需要解决，即管理软件的膨胀。这也是上面介绍的交换技术所要解决的问题。但交换技术并不是一个有吸引力的解决方案，因为一个典型的SATA硬盘的峰值传输率只有每秒几百兆，这意味着需要好几秒才能换出一个1GB的程序。
程序大于内存的问题早在计算机发展初期就出现了，20世纪60年代所采用的解决方案是：把程序分割成许多片段，每个片段称为一个覆盖（overlay）。程序开始运行后首先加载覆盖管理模块，之后覆盖管理模块载入覆盖0，覆盖0执行完成后通知覆盖管理模块载入覆盖1，覆盖1可能紧挨覆盖0存储或者是直接覆盖覆盖0（内存不够的情况下）。其他不用的覆盖存放在硬盘上，在需要的时候由操作系统换入换出。
可以看出这是一种程序模块化的设计思路，虽然由操作系统自动执行换入或换出，但是要求程序员必须把程序分割成多个片段（覆盖），这可能非常耗时并且易于出错。
所幸没过多久就有人想到一个方法，把全部工作都交给计算机去做。
这种方法称为虚拟内存（virtual memory）。虚拟内存的基本思想是，每个程序拥有自己的地址空间，这个空间被分成多个块，每一块称作一页或页面（page）。每一页有连续的地址范围。每个页都被映射到物理内存上，但并不是所有页都必须在内存中才能运行程序。当程序引用到一部分在物理内存上的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存上的地址空间时，由操作系统负责将缺失的部分装入物理内存并且重新执行失败的指令。
虚拟内存技术很适合多道程序设计系统，因为一个程序在等待片段读入内存的时候，可以把CPU交给另一个程序使用。
4.1. 分页
什么是分页
大部分虚拟内存系统都使用了一种称为分页（paging）的技术。在任何一台计算机上，程序都引用一组内存地址。例如程序执行指令MOV REG, 1000时，它把地址为1000的内存单元的内容复制到REG中。
由程序引用的地址称为虚拟地址（virtual address），它们构成了虚拟地址空间（virtual address space）。在没有虚拟内存的机器上，系统直接将虚拟地址送到地址总线上。而在使用了虚拟内存的情况下，虚拟地址不是被送到内存总线上，而是被送到内存管理单元（Memory Management Unit，MMU），MMU负责把虚拟地址映射为物理内存地址，如下图所示:
下图说明了这种映射是如何工作的：
如图，现有一个需要内存64K的程序，但物理内存仅有32K，在任一时间仅有部分虚拟页面会映射在物理内存上，而磁盘上必须一直保留有整个64K程序的副本供需要时调入内存。
虚拟地址空间按照固定大小划分成被称为页面（page）的若干单元，在物理内存中对应的单元称为页框。RAM和磁盘的交换总是以整个页面为单元进行的。很多操作系统和CPU支持不同大小的页面混合使用，例如，x86-64架构的处理器支持4KB、2MB和1GB大小的页面，因此可以将一组4KB大小的页面用于用户程序，将一个1GB大小的页面用于内核程序。
分页如何工作
在上图的例子中，如果试图访问虚拟地址0，例如执行下面的命令MOV REG, 0地址0会被送到MMU上，MMU看到虚拟地址0落在页面0（0K ~ 4K）上，根据映射结果，这一页面对应的是页框2（8K ~ 12K），因此MMU将虚拟地址0变成物理地址8192，并把地址8192送到地址线上。同样若程序访问一个在页面内有偏移的虚拟地址，MMU在转换的时候同样会加上偏移量。
而图中有的页面上有一个叉号，表示这个分页当前并不在物理内存上。在实际的硬件中，用一个在/不在的标志位（present / absent bit）记录页面是否存映射在物理内存上。当程序访问了一个没有映射的页面的时候，MMU注意到，于是使CPU陷入到操作系统，这个陷阱称为缺页中断或缺页错误（page fault）。操作系统找一个很少使用的页框并将其加载到磁盘上，换入请求的页框，修改映射关系，然后重新启动引起陷阱的指令。
下图展示了MMU内部如何将一个虚拟地址映射到物理地址上：
假如当前机器的地址线宽度为16位。MMU输入一个虚拟地址8196，即二进制 0010 0000 0000 0100，这个16位的虚拟地址被分成4位的页号和12位的页内偏移，之所以是12位的页内偏移是因为12位二进制刚好能表示一个页面的大小4K。而4位的页号表示总共可以记录16条页信息。
MMU中的映射表称为页表（page table）（事实上页表一般并不存储在MMU内部，而是存储在内存中，MMU中只有一个指向内存中页表位置的寄存器，参见后面的加速分页部分），虚拟地址的4位页号作为页表的索引，以此得出页号对应的页框号，如果页表中该项的在/不在位为1，则将页框号复制到输出寄存器的高三位，再加上输入虚拟地址中的低12位页内偏移。如此就构成了15位的物理地址，输出寄存器的值随即被送入地址总线。这也展现了如何将一个16位的虚拟地址映射成15位的物理地址。
4.2. 页表
作为一种简单的情况，虚拟地址被分成4位的虚拟页号和12位的页内偏移。当然3位或者5位的虚拟页号也可能存在，这就对应于不同的页内偏移位数，即对应于不同的页面大小。
通过虚拟页号作为页表的索引，以找到对应的页框号，从数学上来说页表就是一个函数，输入虚拟页号输出页框号。
页表项的结构
上图是一个典型的页表项的结构。
其中最重要的当属页框号，毕竟页面映射的目的就是找到页框号。其次是在/不在位，这决定了是否需要发起一个缺页中断来映射一个处于磁盘上的页面。
保护（protection）位指出了一个页面允许什么类型的访问，最简单的保护只需要1位，分别表示读写/只读。更普遍的做法是用三位，分别表示是否启用读、写、执行操作。
为了记录页面的使用情况，引入了修改（modified）位和访问（referenced）位。当一个页面被写入了后自动设置修改位，这在重新分配页框的时候非常有用，如果修改位为1则需要把这个在内存中修改过的页面写回磁盘中以供下一次读入，如果修改位为0则直接覆盖这一内存中的页面即可，因为其在磁盘中的副本还是有效的。
无论是读还是写，系统都会将对应页表项的访问位置1表示这一页面正在被访问。这在发生缺页中断的时候操作系统选择置换的页面的时候很有用，因为置换掉已经不使用了的页面更符合常理。
最后，虚拟内存的本质就是用来创造一个对物理内存抽象——地址空间。虚拟内存的原理是将虚拟地址空间分解成页，并将每一页映射到物理内存的页框上，或者暂时不映射（留存在硬盘上）。
4.3. 加速分页、针对大内存的页表
了解了分页的基本原理后，进一步思考分页存在的两个问题：
- 虚拟地址到物理地址的映射必须非常快
- 如果虚拟地址空间很大，则页表也会很大
第一个问题是因为每次访问内存都需要经过页表的转换，所有的指令和数据都来自内存，所以执行每个指令访问一到两次页表是很常见的。由于页表存在于内存中，所以必须想办法加快访问页表的速度使得访问页表不会是执行一条指令的速度瓶颈。
第二个问题同样很严峻，上面的讨论举例的是16位的地址线，如果页面大小为4K，则只需要16条页表项。但现代计算机至少使用32位的虚拟地址，而且64位甚至更加普遍。假设页面大小为4KB，32位的地址空间将近有100万页，而64位的地址空间所需的表数目为100万的2^32倍，无异于天文数字。而且要注意，每个进程都有其独立的页表，因为他们有各自独立的虚拟地址空间。
于是对大页表的快速访问成为构建计算机的主要瓶颈。最简单的解决方法是在MMU中保存一个公用页表，每次运行一个进程的时候，都把这个进程在内存中的页表副本拷贝到MMU中的公用页表里，覆盖上一次的页表，这样当这个进程访问内存的时候MMU会直接在内部完成映射而不用访问内存中的页表。但不足之处是每次切换进程的时候都要重新拷贝页表，会拉低性能。
另一种极端是所有页表都只存储在内存中，MMU中只存储一个指向页表起始位置的寄存器。这样就没有解决上面所说的映射慢的问题。
转换检测缓冲区
经过多年的观察，人们发现大多数程序总是对少量的内存进行多次访问，而不是反过来。因此只有很少的页表需要被反复读取，其他页表很少被访问。
于是人们想到，在MMU中设置一个小型的硬件设备，里面的内容类似于页表项。这种设备称为转换检测缓冲区（Translation Lookaside Buffer，TLB），有时又称为相联存储器（associate memory）或快表。如下图所示:
可以看到里面的内容几乎和页表一一对应，因为转换检测缓冲区就相当于存储在MMU中的高速页表。
现在看一下TLB是如何工作的。将一个虚拟地址送入MMU中进行转换的时候，硬件首先对比虚拟地址的虚拟页号和TLB中的虚拟页面号是否能匹配上。如果发现了一个匹配项并且保护位不冲突，则将页框号直接取出，如果保护位冲突则报错。如果没有匹配则继续正常到内存中的页表中查找。找到需要的页表项后，从TLB中淘汰一个表项，然后用新找到的表项替换它。
多级页表
TLB加快了虚拟地址到物理地址的转换。而另一个问题是如何处理巨大的虚拟地址空间。
第一种方法是采用多级页表。一个简单的例子如下图所示：
图a表示32位的虚拟地址被分成了10位的PT1域，10位的PT2域和12位的偏移量。因为偏移量为12位，即页面大小4KB，共2^20个页面。
引入多级页表的原因是避免把全部页表一直保存在内存中。特别是那些从不需要的页表就不应该保留。为了印证这个说法，思考一个最简单的加法程序，可能只需要寥寥几条指令，但如果按照前面的说法，需要2^20个页表项来表示程序的地址空间，而事实上4GB的虚拟地址空间中只有很少一部分有数据，也就是说2^20个页表项中有相当大一部分页表项的在/不在位都是0，因为甚至这部分虚拟地址空间就不指向一段实际的数据，而程序正常情况下也不可能去访问这些页表项，所以就导致一个页表占用超大空间但利用率极低。多级页表如何解决这个问题呢？就是把2^20个页表项“分离”。
现在来看多级页表如何工作。首先图里的例子中，有两级页表，即顶级页表和二级页表。虚拟地址PT1域的10位就表示了顶级页表1024个页表项的下标，而顶级页表中的每个页表项又指向了一个1024项的二级页表，PT2域中的10位就表示二级页表的下标，而每个二级页表项就表示一个4K的页面（页表项中就有需要的页框号），这样算回去，一个顶级页表项就表示了4MB的页面，1024个顶级页表想刚好表示4GB的虚拟地址空间。
图中顶级页表的白色页表项表示该项对应的4MB的虚拟地址有实际的数据，而灰色表示没有实际的数据，即无需指向二级页表，而在/不在位为0。如果映射虚拟地址的时候，首先找到的顶级页表项的在/不在位就是0的话，操作系统意识到程序想访问一个根本不存在数据的区域，则可能会直接给程序发出信号杀死进程。
这样，虽然一个进程的虚拟空间有4GB，但我实际只需要4个有1024个页表项的页表就能表示虚拟地址空间，而不需要一个多达2^20个页表项的页表。
二级页表可以扩展为三级页表、四级页表以应对更大的虚拟地址空间。
倒排页表
针对页表过大这个问题，另一种解决方案是倒排页表（inverted page table）。在这种设计中，实际内存的每一个页框对应一个表项，而不是每一个虚拟页面对应一个表项。例如，对于64位虚拟地址，4KB的页大小，4GB的RAM，一个倒排页表仅需要 2^20 个表项。因为只有 2^20 个页框。
虽然倒排页表可能节省很大的空间，但他也有很大的不足：即虚拟地址到物理地址的转换会非常麻烦，因为不能使用下标直接索引页表项了。取而代之的是，它必须搜索整个倒排页表来查找某一个表项。
走出这种两难局面的方法是混合使用TLB和哈希表。TLB用法和前面介绍的一样，将一组最近使用过的页表项放在MMU内部以减少访问内存的次数。而哈希表在这里同样很有用，通过哈希虚拟地址来建立哈希表，而所有具有相同散列值的页表项被链接在一起。如果哈希表条目数和物理页面数一样多，则哈希表的冲突链的平均长度将会是一个表项的长度，这可以大大提升映射速度。而一旦一个新的页框被找到，也可以将之加载到TLB中。
倒排页表在64位机器中很常见，因为在64位机器中即使使用了大页面，还是需要相当多的页表项。如上图，共需2^52个页表项。但如果使用了倒排页表，页表项的数目就不会随着地址位数的增长而起飞了~~~
5. 页面置换算法
当发生缺页中断的时候，操作系统必须在内存中选择一个页面将其换出内存，以便为即将换入的页面腾出空间。如果要换出的页面在驻留内存期间被修改过，还需要把它写回磁盘上的副本。如果没有修改过，说明磁盘上的副本是最新的，那么直接让调入的页面覆盖被淘汰的页面就行了。
发生缺页中断时，虽然可以随机选取一个页面进行淘汰，但如果每次都淘汰的是最不常使用的页面会提升系统的性能。如果一个被频繁使用的页面被置换出内存，那么很可能马上又要被置换回来，这将带来不必要的开销。于是人们从理论和实践两个方面对页面置换算法进行了深入的研究。这里介绍几个最重要的算法。
事实上，页面置换问题在计算机设计的其他领域也同样会发生。因为只要使用了缓存思想的地方，都会面临的一个问题就是缓存满了怎么办，无非就是这里的置换问题。
下面要讨论的所有页面置换算法都有一个问题，当需要从内存中换出某个页面时，它是否只能是缺页进程自己的页面？也就是说能否保留自己的所有页面而将其他进程的页面换出。如果不行的话，就可以有效的将每一个进程控制在一定的页面数目内，反之则不然。
5.1. 最优页面置换算法
很容易就能想到最好的页面置换算法，但此算法不可能实现。。。
该算法概括如下，在缺页中断发生时，内存中已经有了一些页面，而这些页面有的只要再执行10个指令就会访问到，而有的页面还得再执行1000条指令后才会访问到，每个页面可以用还需多少条指令才能访问到做一个标记。最优页面置换算法应该优先置换标记最大的页面，即让这个被置换的页面所导致的缺页中断来临的越晚越好。也即上面所说的，置换掉最不常使用的页面。
这个算法唯一的问题就是无法实现。当缺页中断发生的时候，操作系统无法知道各页面下一次将在什么时候被访问。也就不可能找出所谓的标记最大的页面。
5.2. 最近未使用页面置换算法
为了能让操作系统便于记录一些有效信息，在大部分有虚拟内存的计算机中，系统为每一个页面设置了两个状态位。当页面被访问（读或写）的时候设置R位，当页面被写入（修改）的时候设置M位。这些包含在页面项中。再用一下上面的图：
可以用这两个状态位来实现一个简单的页面置换算法：当启动一个进程的时候，它的所有页面的两个位都被操作系统设置为0，R被定期的（比如在每次时钟中断时）清零，以代表虽然之前某个时间该页被访问了，但已经过了足够长的时间，可以认为该页是短时间内没有访问过的了。而之所以M位不能清零是因为置换页面的时候，操作系统需要根据页面的M位来判断是否需要把该页写回磁盘。
当发生缺页中断的时候，操作系统检查所有页面的R和M位，并将之分成四类：
- 第0类，没有被访问，没有被修改
- 第1类，没有被访问，已经被修改
- 第2类，已经被访问，没有被修改
- 第3类，已经被访问，已经被修改
注意第1类完全有可能出现，即第3类过了一个时钟中断后R位被清零就成了第1类。
NRU（Not Recently Used，最近未使用）算法从类编号最小的类中随机选取一个页面进行置换。这个算法的一个隐含的观点是，一个短时间内没有被访问但是被修改了的页面比短时间内访问过了但没有被修改的页面更需要被置换。
5.3. 先进先出页面置换算法
另一种开销较小的页面置换算法是FIFO（First-In First-Out，先进先出）算法。
即操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面接在链表尾，最早进入的当然就会在表头。当发生缺页中断的时候，淘汰链表头的页面并把新的页面接在链表尾部。
纯粹的FIFO可能并不讨喜，因为可能一个使用非常频繁的页面一直在链表中，直到有一天它被淘汰了，又得很快再置换回来。
5.4. 第二次机会页面置换算法
FIFO算法可能会把经常使用的页面置换出去，于是对该算法做一个简单的修改：检查最老页面的R位，如果R位为0，则说明这个页面又老又很少被使用，则将该页面置换出去。如果R位为1，则首先将R位清零，然后把这个页面放在链表尾部，好像这是一个新置换进来的页面一样，之后对新的表头页面重复上述步骤。
这个算法称为第二次机会（second chance）算法。
5.5. 时钟页面置换算法
尽管第二次页面置换算法相对来说已经比较合理了，但它经常需要在链表中移动节点，既降低了效率又不是很必要。一个更好的办法是把所有页面都保存在一个类似钟面的环形链表中，而表针指向最老的页面。
当发生缺页中断的时候，首先检查表针指向的页面的R位，如果为0，则淘汰该页面并把新页面插入这个位置，之后让表针前移一个位置。如果为1，则将R位清零0，然后让表针前移一个位置重复上述步骤。
5.6. 最近最少使用页面置换算法
对最优页面置换算法的一个很好的近似是基于如下的观察：在前面几条指令中频繁使用的页面很可能在后面后面的几条指令中被再次使用。反过来说，已经很久没使用过的页面很有可能在未来一段时间内继续不被使用。这个思想提出了一个可实现的算法：在缺页中断发生的时候，置换未使用时间最长的页面。这个策略称为LRU（Least Recently Used，最近最少使用）页面置换算法。
虽然LRU在理论上是可行的，但代价很高。为了完全实现LRU，需要在内存中维护一个所有页面的链表，并且根据最近使用的次数来对链表进行排序。而每次发生缺页中断的时候都要更新一次链表，这很耗时间。
然而，还是有一些用特殊硬件实现LRU的方法。首先考虑一个最简单的方法，假设有一个硬件保有一个64位的计数器，它在每条指令执行完后自动加1，每个页表项都必须要有一个对应的存储64位数值的字段。每次访问内存后，就将被访问的页面的64位字段更新为计数器的值。一旦发生缺页中断，就检查所有页表项中，64位字段最小的页面进行置换。该页面就是最近使用的最不频繁的页面。
5.7. 用软件模拟LRU
事实上上面所说的硬件很少有机器实现了。因此，需要一种用软件模拟LRU的方案。一种可能的方案是NFU（Not Frequently Used，最不常使用）算法。该算法将每个页面与一个软件计数器相关联，每一次时钟中断时，将每个页面的R位（0/1）加到它自己的计数器上，之后将R清零。可以看出这个计数器大致上跟踪了所有页面被访问的频繁程度。发生缺页中断的时候，置换计数器最小的页面。
NFU最大的问题在于从不忘记，这也是为什么叫最不常使用算法而不是最近最不常使用算法的原因。假设某段时间某一页面被频繁使用，于是它的计数器有一个很高的值，但过了一段时间后，这一页面已经很少被使用了，但由于之前的积累，再发生置换的时候几乎不会选取这个页面作为淘汰的对象，这就有可能导致淘汰最近有用的页面而保留已经无用的页面。
幸运的是只需要对NFU做一个简单的修改就能让它很好的模拟LRU，即，在R位被加进计数器之前先把计数器右移一位；其次，将R位加到计数器的最左端而不是最右端。
修改之后的算法称为老化（aging）算法。下图表现了它的工作过程：
现有0~5共6个页面，初始情况下6各页面的计数器都是0。在第一次时钟中断的时候，每个页面的R位分别为1、0、1、0、1、1，于是将计数器右移后在最左端加上R位后各个页面的计数器变成了第一列的情景。剩下几列依此类推。
可以看出，老化算法相当于在NFU的基础上加上了权重的思想，最近一次时钟中断内的访问具有最高的权重，而以前的访问的权重随着时间的推移逐渐降低。
