到目前为止，我们都假设地址很小，可以在物理内存中足够放下。现在我们需要放开这个假设，同时假设我们需要支持同时运行的巨大地址空间。因为对于现代的计算机来说，同时运行几个大型程序是很常见的事。另一方面，如果支持巨大内存的话，应用程序就不要担心内存不够的情况。
为了达到这个目的，我们需要借助物理内存更低一层的内存，就是磁盘。对于更大的地址空间来说，其中有部分是没有正在使用的，我们可以把这部分放到磁盘中。磁盘会比内存的空间大很多，但是它的缺点是更慢(如果它足够快的，我们就可以把它当成内存一样来使用了)。
对于现代计算机来说，基于闪存的固态硬盘(SSD)会比机械硬盘(磁盘)快很多，但依旧没有物理内存快。
交换空间
首先我们需要在磁盘中开辟一块空间，这块空间就是用来物理页的移入和移出。在操作系统中，这块空间被称为交换空间(swap space)，因为我们将物理内存中的页交换到其中，并在需要的时候又交换回去。同时，也意味着我们假设操作系统是以页大小为单位来读取或写入交换空间。因此，操作系统需要记住被交换出去页的硬盘地址(disk address)。
交换空间的大小是很关键的，它决定了系统在某一时刻能使用的最大内存页数。简单起见，现在假设它非常大。
通过一个简单的例子来理解，见下图，可以看到4页物理内存和一个8页的交换空间，这个例子中，3个进程(进程 0、进程 1 和进程 2)分别只有一部分物理页，另一部分在交换空间中，第4个进程(黑色块的进程3)的所有页都被交换到磁盘上，所以它目前没有在运行。
交换磁盘中有一块是空闲的。通过这个小例子其实就已经可以看到，使用交换空间可以让系统假装内存比实际的物理内存大。
存在位
因为现在我们在磁盘中多了一些空间，所以我们需要在系统中增加一些机制来支持从硬盘中交换页，为了简单起见，我们假设是硬件在管理TLB。
回想一下内存引用的时候会发生什么。正在运行的进程生成虚拟内存的引用(用来获取指令或者访问数据)，然后硬件会将其转为物理地址，再从物理内存中获取数据。
如果在 TLB 中找不到 VPN(即 TLB 未命中)，则硬件在内存中查找页表(使用页表基址寄存器)，并使用 VPN 查找该页的页表项(PTE)作为索引。如果页有效且存在于物理内存中，则硬件从 PTE 中获得 PFN，将其插入 TLB，并重试该指令，这次产生 TLB 命中。到现在为止还挺好。
因为现在允许页被交换到磁盘中，所以在命中PTE时，会发现这个页不在物理内存中，硬件(或操作系统，在软件管理TLB时)判断是否在内存中的方法是通过页表项中的一条新信息，即存在位(present bit)。如果存在位设置为1，则表示改页在物理内存中，如果不在的话，则会触发缺页错误(page fault)，通常这时候会交给操作系统去处理，操作系统会运行一段”页错误处理程序“代码，这在前面讲TLB的时候也讲过。
页错误
回想一下，在TLB未命中的情况下，我们有两种方式来处理，一种是硬件来管理TLB，一种是软件(操作系统)。而无论是哪种方式，当发生缺页错误的时候，都会交给操作系统来处理页错误，操作系统来决定错误处理程序(page-fault handler)做什么。即使是硬件管理TLB，它也信任操作系统来处理这个重要的任务
当触发页错误的时候，操作系统需要将该页交换到内存中。那么，问题来了：操作系统如何知道所需的页在哪儿？在许多系统中，页表项是记录这些信息的最佳位置。因此，操作系统可以根据PTE中的某些位来存储硬盘地址，这些位通常用来存PFN这样的数据。所以操作系统接收到页错误的时候，它会在PTE中取出硬盘地址，然后再对硬盘发起I/O请求，将页读到内存中。
当硬盘I/0完成后，会对CPU引脚发出一个中断信号，表示I/O已经完成了，接下来操作系统会更新页表，将这个页的存在位(present bit)标记位1，同时更新PTE的PFN字段。然后重试指令。下一次会先在TLB中查找，TLB中当然是未命中，然后再去查页表，这次在页表中就能够查到了，然后将其插入到TLB中(这一步也可以在处理页错误的时候就更新TLB)。最后的重试操作会在TLB中找到转换映射，从已转换的内存地址获取所需的数据或者指令。
这里值得注意的是，当I/O在运行时，进程是处于阻塞(blocked)状态。因此当页处理程序在开始工作时，操作系统会去调度其它可以执行的进程，因为I/O的操作是很耗时的。
页处理处理流程
当我们理解了这些后，现在就可以粗略地描绘内存访问的完整流程。也就是说，现在如果有人问你：”当程序对内存发起一次数据读取时发生了什么？“，我们应该对该流程中所有存在的可能性都有了很好的概念。
如下代码是MMU在做地址转换时做的事情，下列代码中可以发现，如果TLB未命中，则会发生3种情况
- 访问了一个无效页，硬件捕获了这个非法访问，抛出异常
if (PTE.Valid == False)，操作系统会执行对应的错误处理程序，可能会杀死这个进程。
- 该页存在(present)同时有效(valid)
(PTE.Present == True)，这种情况只需要更新TLB，然后重试即可。
- 该页被交换到了磁盘中，页错误处理程序需要运行，虽然这对进程来说是一个正常的页(毕竟是有效的)，但是它不在物理内存中。
如下还有一段代码，是操作系统在处理缺页错误时做的事情，它主要是为从硬盘中换入的页找到一个合适的物理帧，也比较好理解。
首先会先查找一个空的物理帧，如果没有空的物理帧，则需要等待替换算法运行完，它会送内存中踢出一些页，释放帧供这里使用。然后发起一次硬盘的I/O请求，将要换入的页读取到这个物理页中，随后更新PTE的一些标记，最后重试。
何时开始交换
到目前为止，我们都假设是在内存满了的时候才执行替换，然而实际的操作系统不会这么做，操作系统会给内存预留一小部分空闲的空间。
具体来说，操作系统会设置两个水位线，高水位线(Hight Watermark, HW)和低水位线(Low Watermark, LW)。原理是这样，当操作系统发现内存页低于几个页时(低水位线)，后台会有一个进程开始执行，当空闲的页达到高水位线时就进入休眠状态。这个后台进程有时会被称为交换守护进程(swap daemon)或页守护进程(page daemon)。
通过同时执行多个交换过程，我们可以进行一些性能优化。例如，许多系统会把多个要写入的页聚集(cluster)或分组(group)，同时写入到交换区间，从而提高硬盘的效率。这种合并操作会减少硬盘的寻道和旋转开销，从而提高性能。
而为了配合后台的分页进程。上述的页错误处理机制就需要进行修改，首先要先检查是否有空页(因为操作系统大多情况会给内存预留一部分空页)，如果没有空页的话，则唤醒分页进程，等分页进程把所需的页换进内存后再继续它的工作。
如何交换
接下来我们学习如何对内存进行交换。
缓存管理
在更深入的研究之前，我们先清楚我们需要解决的问题。我们主要是想让地址请求在前置的缓存都未命中时，那么在物理内存中就需要尽可能的命中。
如果我们知道程序在某个时间段内地址引用的缓存命中和未命中次数，我们就可以得到程序的平均内存访问时间(Average Memory Access Time, AMAT)。具体来说，可以通过以下公式来计算AMAT。
- 表示访问内存的成本 (memory)
- 表示访问磁盘的成本 (disk)
- 表示在物理内存中命中
- 表示在物理内存中未命中
和 的变化范围是，同时
假设现在有一个小的地址空间：4KB，每页256字节大小，一共16页(16*256 = 4096)。因此，虚拟地址的VPN是4位，偏移量是8位(此处心算即可得出)。
接着，程序发出了以下内存引用(即虚拟地址)：
0x000，0x100，0x200，0x300，0x400，0x500，0x600，0x700，0x800，0x900 这些虚拟地址访问的是地址空间前10页的每一页第一个字节(页号是每个虚拟地址的第一个十六进制数字)让我们再进一步假设，除了虚拟页3之后，其它的页都已经在物理内存中。因此我们的内存引用序列会得到以下行为：
命中，命中，命中，未命中，命中，命中，命中，命中，命中，命中。此时我们已经得到缓存的命中与未命中数，因此，命中率是()要计算AMAT，还需要知道访问内存的成本及访问磁盘的成本。这里，我们假设访问内存(TM)的成本约为100ns (100ns = 0.0001ms)，访问磁盘的成本为10ms，因此，我们把这些值代入公式如下：
因此计算可以得到0.00009 + 1ms = 1.00009，或约1ms。如果我们的命中率是99.99%()，结果是完全不同的：AMAT是，大约快了100倍。当命中率接近100时，AMAT接近100ns(因为物理内存的访问是100ns)
1s【秒】 = 1000ms【毫秒】1ms【毫秒】 = 1000μs【微秒】1μs【微秒】 = 1000ns【纳秒】1ns 【纳秒】= 1000ps【皮秒】
遗憾的是，在现代系统中，因为访问硬盘的成本很高，即使出现很小概率的未命中也会降低程序的平均内存访问时间。为了尽可能的避免这种情况，避免程序以磁盘的速度运行，我们可以为物理内存开发更智能的策略。
最优替换策略
我们先学习最优替换策略，目的是一会在学习其它策略时方便对比。这个最优(optimal)策略是Belady多年前开发的(这个策略之前叫做MIN)。最优策略可以做到总的未命中数量最少。Belady展示了一个简单的方法(遗憾的是，很难实现！)，它所做的就是替换内存中最远才会访问的页。
虽然最优策略非常不切实际，但是作为学习和研究还是有意义的。因为它可以用来和其它策略的命中率来作为参考。最优策略的命中率只有82%，也就是说，如果你写的一个策略达到了80%的命中率的话，其实已经很高了，基本上可以停止无谓的优化了。
最优策略的想法很简单：当要发生内存替换的时候，它会替换你在最长时间才会访问的页。也就是说，这个页相对其它页而言，是最不重要的。
我们用一个简单的例子来理解最优策略，假设缓存只能够缓存3个页，接着程序会按照如下顺序访问虚拟页
0，1，2，0，1，3，0，3，1，2，1。下表展示了最优策略的访问。访问 | 命中/未命中 | 踢出 | 导致缓存状态 |
0 | 未命中 | ㅤ | 0 |
1 | 未命中 | ㅤ | 0、1 |
2 | 未命中 | ㅤ | 0、1、2 |
0 | 命中 | ㅤ | 0、1、2 |
1 | 命中 | ㅤ | 0、1、2 |
3 | 未命中 | 2 | 0、1、3 |
0 | 命中 | ㅤ | 0、1、3 |
3 | 命中 | ㅤ | 0、1、3 |
1 | 命中 | ㅤ | 0、1、3 |
2 | 未命中 | 3 | 0、1、2 |
1 | 命中 | ㅤ | 0、1、2 |
可以看到，前3次的访问都是未命中的，因为缓存一开始是空的，这种也叫冷启动未命中(cold-start miss, 或强制未命中 compulasory miss)。
接着开始引用页0和页1，这时候就能够命中了，在表的最后一列也同时展示了缓存中的值。再接下来访问了页3，此时缓存已满，必须要执行内存替换！那么，问题来了，我们应该替换哪一页？
现在如果使用最优策略来进行检查，会发现程序随后就会访问页0，页3，页1，也就意味着页2是最长时间才会再次访问的。所以这里替换页2是最优的。
此时又会导致未迷命中接下来的3次访问都会命中缓存，随后程序开始访问页2，此时又会导致未命中。此时最优策略发现下一次访问的是页1，因此这里替换页0和页3都可以，在这个例子中我们可以看到把页3替换掉了。
接着，我们来计算一下缓存命中率：一共命中了6次，未命中5次，那么缓存命中率是或54.5%，如果再减去强制未命中(即忽略页的第一次未命中)的话，命中率是81.8%。
但是，最优策略最大的问题在于，未来的访问是无法预知的，我们没有办法为操作系统实现一个最优策略。因此，学习最优策略的主要原因是在于我们开发实际可用的策略时，可以将最优策略来进行比较，让我们知道我们开发的策略有多接近”完美“
缓存未命中的类型
- 强制性(compulsory miss)未命中(或冷启动未命中，cold-start miss)，这是对项目的第一次引用，缓存一开始空的。
- 容量未命中(capacity miss)，缓存空间已满，需要将缓存中的一个项踢出以将新的缓存引入。
- 冲突未命中(conflict miss)，这个未命中只会出现在硬件中，因为硬件缓存中对项的放置位置有限制，这是由于集合关联性(set-associativity)不会出现在操作系统的页面缓存中，因为这样的缓存总是完全关联的(fully-associative)，即对页面可以放置的内存位置没有限制。
FIFO策略
很多早期的操作系统为了尽可能的让系统复杂度降低，采用了这种非常简单的FIFO(先入先出)替换策略，当页进入系统时，简单地放入一个队列，当发生页替换时，只需要将最先加入队列的页进行替换既可，这个策略的优势在于实现起来很简单。
可以很明显的看到，这个策略没办法确定哪些页是重要的页，即一个页如果被多次访问，它也是有可能被替换出去
Belady的异常
Belady(最优策略的发明者)和他的同事在研究FIFO策略时发现了一个有意思的引用序列：
1，2，3，4，1，2，5，1，2，3，4，5。有趣的问题：当缓存的容量从3变成4的时候，缓存的命中率会增加还是下降呢？
一般来说，当缓存容量增加时，命中率也会相应的提高。但是这个例子中采用FIFO，命中率反而下降了！如果感兴趣的话可以计算一下。这种奇怪的现象被称为Belady的异常(Belady’s Anomaly)。
其它的一些策略，如LRU就不会有一个问题。因为LRU具有栈的特性(stack property)。对于这种性质的算法，大小为N+1(N表示原有的缓存大小)的缓存中包含了N缓存的内容。因此，当缓存增大时，缓存命中率至少可以保证不变，有可能提高。先进先出(FIFO)和随机(Random)等很显然没有栈特性，因此容易出现异常行为。随机策略
随机策略的想法是：当内存满了的时候，它会随机选择一个页来进行替换。这个策略实现起来也很简单，但是它在挑选替换页时不够智能。
随机策略的表现完全取决于运气，同一组内存引用序列，随机策略可能会比FIFO好很多，也可能会更差。
下图有一个10000次实验后随机策略的平均命中率，每次试验都有不同的随机内存引用序列。下图可以看出，有时候随机策略有40%的命中率，和FIFO的命中率差不太多，而有时候则会更糟，这完全取决于当时的运气
LRU(最近最少使用)
LRU(Least-Recently-Used, LRU)策略是根据页最近的访问时间来决定是否替换的，如果缓存空间中有3个页，则会将访问时间最久的那个页替换掉。因为根据时间局部性原理来说，如果程序在过去访问过某个页，则它很可能马上会继续访问。这个页就是比较重要的页，这个策略就可以解决FIFO和随机策略可能会替换掉重要页的问题。
与之一起出现的还有LFU(Least-Frequently-Used, LFU)策略，这个策略主要是根据空间局部性原理，即替换访问次数最少的页。
我们通过一个小例子来更好的理解LRU，下表即可体现。从表中可以看到当第一次发生缓存未命中的时候，LRU将页2踢出了，因为页0和1的访问时间是最近的(LRU是根据访问时间来决定提出哪个页)。在这个例子中，很显然LRU的决定是更加准确的。同时，在这个例子中，LRU的表现快赶上最优策略了。
访问 | 命中/未命中 | 踢出 | 导致缓存状态 |
0 | 未命中 | ㅤ | 0 |
1 | 未命中 | ㅤ | 0、1 |
2 | 未命中 | ㅤ | 0、1、2 |
0 | 命中 | ㅤ | 1、2、0 |
1 | 命中 | ㅤ | 2、0、1 |
3 | 未命中 | 2 | 0、1、3 |
0 | 命中 | ㅤ | 1、3、0 |
3 | 命中 | ㅤ | 1、0、3 |
1 | 命中 | ㅤ | 0、3、1 |
2 | 未命中 | 0 | 3、1、2 |
1 | 命中 | ㅤ | 3、2、1 |
当然，LRU也并不是完全没有缺点，偶发性，周期性的批量性访问时，LRU依旧可能会淘汰掉热点数据。
同时，与LRU,LFU相反的策略还有MFU(Most-Frequently-Used, 最经常使用策略)和MRU(Most-Recently-Used, 最近使用策略)，尽管这些策略在某些场景下表现良好，但是在大多数场景下的表现都不好，因为它们忽视了大多数程序都具有局部性的特点。
使用不同策略的工作负载示例
我们通过实际的内存访问来测试几个策略的实际工作表现。这个测试我们每次会访问100个页，当一次测试完成后会将缓存的大小增加1，缓存的大小从1-100变化。也就是说，一共进行了10000次页的访问。
无局部性程序负载测试
无局部性的程序意味着，每次的内存引用是随机的。下表是实际的表现，x轴表示缓存大小的变化，y轴表示每个缓存的命中率，其中OPT表示最优策略。
对于无局部性的程序来说，使用哪种策略几乎都没有任何影响
“80-20”负载测试
这个程序中80%内存引用都是在使用20%的页(热门页)。也就是说，100个页中，有20个页是频繁在访问的。
下图中是实际的表现，可以看到，尽管FIFO和随机策略表现都很好，但LRU的表现更为优秀。因为它会保持住比较热门的页。当一个页被访问时，很可能它马上会进行下一次访问。
当我们学习到这里的时候，不经会发出疑惑，LRU的命中率提升相对FIFO和随机策略真的重要吗？这个其实需要“视情况而定”。如果每次未命中的代价很大(很常见)，那么LRU的命中率提升是对性能有巨大的影响的，如果未命中的代价不是很大，则LRU的优势并不明显。
“循环顺序”负载
我们再来换个测试场景，这个测试我们每次只引用50个页，从0依次到49，然后循环重复访问。下图展示了各个策略的实际表现。
这种工作负载在许多应用程序(包括重要的商业应用，如数据库)中是很常见的，下表中体现了LRU和FIFO策略在这种负载下的最差和最好表现。当缓存大小小于50的时候，LRU和FIFO策略的命中率是0，当大于等于50的时候，LRU和FIFO策略的命中率是100%。
在这种循环顺序的工作负载下，这些较旧的页其实会比新加入进来的页更早发生访问。也就是说，如果缓存大小只有49页，那么循环50个页的工作负载也会导致0%的命中率。
我们也发现了另一个现象，在这个工作负载中，随机策略的表现不错，虽然它距离最优策略还有距离，但是至少达到了非零的命中率。可以看出随机策略也有一些不错的优点，即在特殊情况下依旧不会出现奇怪的结果。
实现LRU
通过以上策略的学习，我们可以发现，像LRU这种基于历史数据的算法在大多数情况下的表现都是最优。它比简单的FIFO和随机策略的优势是，不会踢掉重要的页。那么，我们该如何实现它呢？
以LRU为例，如果真的要实现它，我们在每次进行页访问时(取指令，加载指令，存储指令)，都需要更新一些信息，从而将该页移动到列表的最前面(即MRU侧)。与FIFO相比，FIFO的页列表只有在页被添加，或者被提出的时候才需要更新信息。为了记录哪些页是最久时间没有被使用的，系统必须对每次的内存引用都做一些记录工作。显然，如果不十分小心的话，这样的记录反而会对性能造成影响。
有一种方法可以加快速度，就是让硬件来承担一部分工作，硬件可以在每个页访问时更新内存中的时间字段(这个字段可以在每个进程的页表，也可以在内存的某个单独的数组中，每个物理页有一个)。因此，当页被访问时，硬件会去更新这个字段。然后，当发生页替换的时候，操作系统可以简单的扫描系统中所有页，将时间字段是最久的页找出将其踢出。
但是，随着系统中页的增长，对这些页进行一次完整的线性扫描的开销也是很大的。想象一下，一台32位的机器，一共有4GB内存，每个页是4KB，那么就有100w个页()，即使是现代CPU的速度，扫描这100w条数据都需要很长时间。
所以这就引起了一个新的问题：我们是否真的需要找到绝对最旧的页进行替换？因为真的实现一个完美LRU代价太高了，找到差不多最旧的页可以吗？
近似LRU
事实证明，答案是肯定的：从计算开销的角度上来看，近似LRU更为可行，实际上这也是许多现代操作系统的做法。
这个想法是需要硬件来增加一个使用位(use bit，有时被称为是引用位，reference bit)，这种做法在第一个支持分页的系统Atlas one-level store中实现。系统中的每个页有一个使用位，这个位会一直从0和1之间变化，这些位会被存在某个地方(例如页表中或者某个数组中)。每次页被引用时会将其标记为1。硬件不会去清除这个标记(即将其设置为0)，这由操作系统负责。
时钟算法(clock algorithm)
这个算法的思想是，系统中的所有页都放在一个循环列表中，时钟指针(clock hand)开始时指向某个特定的页(哪个页不重要)。
当发生页替换时，指针会检查当前指向页P的使用位是1还是0。如果是1，将表示这个页最近被使用，不能将其替换。然后将P的使用设置为0，时钟指针递增到下一页(P+1)。这个算法会持续找到使用位为0的页。也就是说，在最差的情况下，它只会完整的遍历一次列表。
下图有一个时钟算法的变种的行为，它虽然还不如完美的LRU命中率高，但是它比不考虑历史访问的方法好很多。
考虑脏位
刚刚我们的时钟算法没有考虑过内存中页如果有修改的情况。即如果页被修改(modified)并因此变脏(dirty)，那么如果将它踢出的话，还需要将其写回到磁盘中，这样的开销很昂贵。如果踢出一个没有被修改过的页，踢出就不需要成本，则不需要考虑将其写回到硬盘中的问题。这个小修改也是有Corbato提出的。因此，一些虚拟机系统都更倾向于踢出干净页，而不是脏页。
为了能够支持这种行为，硬件需要多增加一个脏位(dirty bit)。每次对页中的内容进行修改时都要同时修改这个脏位。
页载入和写回
操作系统在考虑将页从磁盘加载到内存时，有对应的页选择(page selection)策略(Denning为之命名)，它向操作系统提供了一些不同的选项。
页载入
大多数操作系统都是使用按需分页(demand paging)，这意味着操作系统只有在页被访问时才会将页加入到内存，”按需“即可。但是，操作系统可能会提前预判你即将会使用的页，从而提前载入。这种行为称为预取(prefetching)，只有在合理的成功机会下才会这么做。如代码页P被加入到内存，那么代码页P+1也很有可能会被访问，因此也该被载入内存。
写回
而在考虑如何将页写回到磁盘时，最简单的方式就是每次都写一个。但是操作系统一般不会立即去执行写入，而是会等待一些待完成的写入，然后批处理操作。
这种行为通常被称为聚集(chustering)写入，或者是分组写入(grouping)，这样做是因为磁盘驱动器的性质，执行单次大的写操作，会比很多小的写操作更高效。
抖动
当内存总是被频繁的超额请求时，这就出现了抖动(thrashing)现象，抖动会导致页会被频繁的换入换出。
一些早期的操作系统有一组相当复杂的机制来应对抖动。例如，给定一组进程，系统可以决定不允许部分进程，通过减少运行中的进程来减少工作集。这种方式叫做准入控制(adminssion control)，它表明，少做一些工作有时会比多做一些更好，这是我们在生活中以及现代操作系统中经常遇到的情况(令人遗憾)。
还有一些系统会采用更严格的方式来管理内存过载，如让内存超额请求时，某些版本的Linux会运行”内存不足的杀手程序(out-of-memory killer)”。
这个守护进程会选择一个内存密集型进程并杀死它，从而以不怎么委婉的方式减少内存。虽然这种方式减少了内存压力，但是可能带来一些问题，例如，如果它杀死了我们很多人都是使用的一个后端服务，那么会导致这个引用程序不可用。
小结
我们目前学习了很多页替换的策略，这些都是现代操作系统中的一部分。现代操作系统增加了对时钟算法等简单LRU近似值的一些调整。例如，扫描抗性(scan resistance)是很多现代算法的重要组成部分。它试图避免LRU的最坏情况行为，我们在循环工作负载中看到了这种情况。因此，页替换算法的发展还在继续。
但是，在大多数情况下，内存访问和磁盘访问时间的差异增加了，这些算法的重要性降低了。由于交换到磁盘中开销很大，因此频繁交换的成本很高。所以，避免频繁交换的最佳方案往往很简单：购买更多的内存。