虚拟内存
尽管基址寄存器和变址寄存器用来创建地址空间的抽象，但是这有一个其他的问题需要解决：管理软件的膨胀(managing bloatware)。虽然内存的大小增长迅速，但是软件的大小增长的要比内存还要快。在 1980 年的时候，许多大学用一台 4 MB 的 VAX 计算机运行分时操作系统，供十几个用户同时运行。现在微软公司推荐的 64 位 Windows 8 系统至少需要 2 GB 内存，而许多多媒体的潮流则进一步推动了对内存的需求。
这一发展的结果是，需要运行的程序往往大到内存无法容纳，而且必然需要系统能够支持多个程序同时运行，即使内存可以满足其中单独一个程序的需求，但是从总体上来看内存仍然满足不了日益增长的软件的需求（感觉和xxx和xxx 的矛盾很相似）。而交换技术并不是一个很有效的方案，在一些中小应用程序尚可使用交换，如果应用程序过大，难道还要每次交换几 GB 的内存？这显然是不合适的，一个典型的 SATA 磁盘的峰值传输速度高达几百兆/秒，这意味着需要好几秒才能换出或者换入一个 1 GB 的程序。
SATA（Serial ATA）硬盘，又称串口硬盘，是未来 PC 机硬盘的趋势，已基本取代了传统的 PATA 硬盘。
那么还有没有一种有效的方式来应对呢？有，那就是使用 虚拟内存(virtual memory)，虚拟内存的基本思想是，每个程序都有自己的地址空间，这个地址空间被划分为多个称为页面(page)的块。每一页都是连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，硬件会立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
在某种意义上来说，虚拟地址是对基址寄存器和变址寄存器的一种概述。8088 有分离的基址寄存器（但不是变址寄存器）用于放入 text 和 data 。
使用虚拟内存，可以将整个地址空间以很小的单位映射到物理内存中，而不是仅仅针对 text 和 data 区进行重定位。下面我们会探讨虚拟内存是如何实现的。
虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中，当一个程序等待它的一部分读入内存时，可以把 CPU 交给另一个进程使用。
分页
大部分使用虚拟内存的系统中都会使用一种 分页(paging) 技术。在任何一台计算机上，程序会引用使用一组内存地址。当程序执行
MOV REG,1000
这条指令时，它会把内存地址为 1000 的内存单元的内容复制到 REG 中（或者相反，这取决于计算机）。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。
这些程序生成的地址被称为 虚拟地址(virtual addresses) 并形成虚拟地址空间(virtual address space)，在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存中线上，读写操作都使用同样地址的物理内存。 在使用虚拟内存时，虚拟地址不会直接发送到内存总线上 。相反，会使用 MMU(Memory Management Unit) 内存管理单元把 虚拟地址映射为物理内存地址 ，像下图这样
下面这幅图展示了这种映射是如何工作的
页表给出虚拟地址与物理内存地址之间的映射关系。每一页起始于 4096 的倍数位置，结束于 4095 的位置，所以 4K 到 8K 实际为 4096 - 8191 ，8K - 12K 就是 8192 - 12287
在这个例子中，我们可能有一个 16 位地址的计算机，地址从 0 - 64 K - 1，这些是虚拟地址。然而只有 32 KB 的物理地址。所以虽然可以编写 64 KB 的程序，但是程序无法全部调入内存运行，在磁盘上必须有一个最多 64 KB 的程序核心映像的完整副本，以保证程序片段在需要时被调入内存。
存在映射的页如何映射
虚拟地址空间由固定大小的单元组成，这种固定大小的单元称为 页(pages)。而相对的，物理内存中也有固定大小的物理单元，称为 页框(page frames)。页和页框的大小一样。在上面这个例子中，页的大小为 4KB ，但是实际的使用过程中页的大小范围可能是 512 字节 - 1G 字节的大小。对应于 64 KB 的虚拟地址空间和 32 KB 的物理内存，可得到 16 个虚拟页面和 8 个页框。RAM 和磁盘之间的交换总是以整个页为单元进行交换的。
程序试图访问地址时，例如执行下面这条指令
MOV REG, 0
会将虚拟地址 0 送到 MMU。MMU 看到虚拟地址落在页面 0 （0 - 4095），根据其映射结果，这一页面对应的页框 2 （8192 - 12287），因此 MMU 把地址变换为 8192 ，并把地址 8192 送到总线上。内存对 MMU 一无所知，它只看到一个对 8192 地址的读写请求并执行它。MMU 从而有效的把所有虚拟地址 0 - 4095 映射到了 8192 - 12287 的物理地址。同样的，指令
MOV REG, 8192
也被有效的转换为
MOV REG, 24576
虚拟地址 8192（在虚拟页 2 中）被映射到物理地址 24576（在物理页框 6 中）上。
通过恰当的设置 MMU，可以把 16 个虚拟页面映射到 8 个页框中的任何一个。但是这并没有解决虚拟地址空间比物理内存大的问题。
上图中有 8 个物理页框，于是只有 8 个虚拟页被映射到了物理内存中，在上图中用 X 号表示的其他页面没有被映射。在实际的硬件中，会使用一个 在/不在(Present/absent bit)位记录页面在内存中的实际存在情况。
未映射的页如何映射
当程序访问一个未映射的页面，如执行指令
MOV REG, 32780
将会发生什么情况呢？虚拟页面 8 （从 32768 开始）的第 12 个字节所对应的物理地址是什么？MMU 注意到该页面没有被映射（在图中用 X 号表示），于是 CPU 会陷入(trap)到操作系统中。这个陷入称为 缺页中断(page fault) 或者是 缺页错误。操作系统会选择一个很少使用的页并把它的内容写入磁盘（如果它不在磁盘上）。随后把需要访问的页面读到刚才回收的页框中，修改映射关系，然后重新启动引起陷入的指令。有点不太好理解，举个例子来看一下。
例如，如果操作系统决定放弃页框 1，那么它将把虚拟机页面 8 装入物理地址 4096，并对 MMU 映射做两处修改。首先，它要将虚拟页中的 1 表项标记为未映射，使以后任何对虚拟地址 4096 - 8191 的访问都将导致陷入。随后把虚拟页面 8 的表项的叉号改为 1，因此在引起陷阱的指令重新启动时，它将把虚拟地址 32780 映射为物理地址（4096 + 12）。
下面查看一下 MMU 的内部构造以便了解它们是如何工作的，以及了解为什么我们选用的页大小都是 2 的整数次幂。下图我们可以看到一个虚拟地址的例子
虚拟地址 8196 （二进制 0010000000000100）用上面的页表映射图所示的 MMU 映射机制进行映射，输入的 16 位虚拟地址被分为 4 位的页号和 12 位的偏移量。4 位的页号可以表示 16 个页面，12 位的偏移可以为一页内的全部 4096 个字节。
可用页号作为页表(page table) 的索引，以得出对应于该虚拟页面的页框号。如果在/不在位则是 0 ，则引起一个操作系统陷入。如果该位是 1，则将在页表中查到的页框号复制到输出寄存器的高 3 位中，再加上输入虚拟地址中的低 12 位偏移量。如此就构成了 15 位的物理地址。输出寄存器的内容随即被作为物理地址送到总线。
页表
在上面这个简单的例子中，虚拟地址到物理地址的映射可以总结如下：虚拟地址被分为虚拟页号（高位部分）和偏移量（低位部分）。例如，对于 16 位地址和 4 KB 的页面大小，高 4 位可以指定 16 个虚拟页面中的一页，而低 12 位接着确定了所选页面中的偏移量（0-4095）。
虚拟页号可作为页表的索引用来找到虚拟页中的内容。由页表项可以找到页框号（如果有的话）。然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成物理地址。
因此，页表的目的是把虚拟页映射到页框中。从数学上说，页表是一个函数，它的参数是虚拟页号，结果是物理页框号。
通过这个函数可以把虚拟地址中的虚拟页转换为页框，从而形成物理地址。
页表项的结构
下面我们探讨一下页表项的具体结构，上面你知道了页表项的大致构成，是由页框号和在/不在位构成的，现在我们来具体探讨一下页表项的构成
页表项的结构是与机器相关的，但是不同机器上的页表项大致相同。上面是一个页表项的构成，不同计算机的页表项可能不同，但是一般来说都是 32 位的。页表项中最重要的字段就是页框号(Page frame number)。毕竟，页表到页框最重要的一步操作就是要把此值映射过去。下一个比较重要的就是在/不在位，如果此位上的值是 1，那么页表项是有效的并且能够被使用。如果此值是 0 的话，则表示该页表项对应的虚拟页面不在内存中，访问该页面会引起一个缺页异常(page fault)。
保护位(Protection) 告诉我们哪一种访问是允许的，啥意思呢？最简单的表示形式是这个域只有一位， 0 表示可读可写，1 表示的是只读 。
修改位(Modified) 和 访问位(Referenced) 会跟踪页面的使用情况。当一个页面被写入时，硬件会自动的设置修改位。修改位在页面重新分配页框时很有用。如果一个页面已经被修改过（即它是 脏 的），则必须把它写回磁盘。如果一个页面没有被修改过（即它是 干净的），那么重新分配时这个页框会被直接丢弃，因为磁盘上的副本仍然是有效的。这个位有时也叫做 脏位(dirty bit)，因为它反映了页面的状态。
访问位(Referenced) 在页面被访问时被设置，不管是读还是写。这个值能够帮助操作系统在发生缺页中断时选择要淘汰的页。不再使用的页要比正在使用的页更适合被淘汰。这个位在后面要讨论的页面置换算法中作用很大。
最后一位用于禁止该页面被高速缓存，这个功能对于映射到设备寄存器还是内存中起到了关键作用。通过这一位可以禁用高速缓存。具有独立的 I/O 空间而不是用内存映射 I/O 的机器来说，并不需要这一位。
在深入讨论下面问题之前，需要强调一下：虚拟内存本质上是用来创造一个地址空间的抽象，可以把它理解成为进程是对 CPU 的抽象，虚拟内存的实现，本质是将虚拟地址空间分解成页，并将每一项映射到物理内存的某个页框。因为我们的重点是如何管理这个虚拟内存的抽象。
加速分页过程
到现在我们已经虚拟内存(virtual memory) 和 分页(paging) 的基础，现在我们可以把目光放在具体的实现上面了。在任何带有分页的系统中，都会需要面临下面这两个主要问题：
- 虚拟地址到物理地址的映射速度必须要快
- 如果虚拟地址空间足够大，那么页表也会足够大
第一个问题是 由于每次访问内存都需要进行虚拟地址到物理地址的映射 ，所有的指令最终都来自于内存，并且很多指令也会访问内存中的操作数。
操作数：操作数是计算机指令中的一个组成部分，它规定了指令中进行数字运算的量 。操作数指出指令执行的操作所需要数据的来源。操作数是汇编指令的一个字段。比如，MOV、ADD 等。
因此，每条指令可能会多次访问页表，如果执行一条指令需要 1 ns，那么页表查询需要在 0.2 ns 之内完成，以避免映射成为一个主要性能瓶颈。
第二个问题是所有的现代操作系统都会使用至少 32 位的虚拟地址，并且 64 位正在变得越来越普遍。假设页大小为 4 KB，32 位的地址空间将近有 100 万页，而 64 位地址空间简直多到无法想象。
对大而且快速的页映射的需要成为构建计算机的一个非常重要的约束。就像上面页表中的图一样， 每一个表项对应一个虚拟页面，虚拟页号作为索引 。在启动一个进程时，操作系统会把保存在内存中进程页表读副本放入寄存器中。
最后一句话是不是不好理解？还记得页表是什么吗？它是虚拟地址到内存地址的映射页表。页表是虚拟地址转换的关键组成部分，它是访问内存中数据所必需的。在进程启动时，执行很多次虚拟地址到物理地址的转换，会把物理地址的副本从内存中读入到寄存器中，再执行这一转换过程。
所以，在进程的运行过程中，不必再为页表而访问内存。使用这种方法的优势是简单而且映射过程中不需要访问内存。缺点是 页表太大时，代价高昂，而且每次上下文切换的时候都必须装载整个页表，这样会造成性能的降低。鉴于此，我们讨论一下加速分页机制和处理大的虚拟地址空间的实现方案
转换检测缓冲区
我们首先先来一起探讨一下加速分页的问题。大部分优化方案都是从内存中的页表开始的。这种设计对效率有着巨大的影响。考虑一下，例如，假设一条 1 字节的指令要把一个寄存器中的数据复制到另一个寄存器。在不分页的情况下，这条指令只访问一次内存，即从内存取出指令。有了分页机制后，会因为要访问页表而需要更多的内存访问。由于执行速度通常被 CPU 从内存中取指令和数据的速度所限制，这样的话，两次访问才能实现一次的访问效果，所以内存访问的性能会下降一半。在这种情况下，根本不会采用分页机制。
什么是 1 字节的指令？我们以 8085 微处理器为例来说明一下，在 8085 微处理中，一共有 3 种字节指令，它们分别是
1-byte(1 字节)、2-byte(2 字节)、3-byte(3 字节)，我们分别来说一下1-byte：1 字节的操作数和操作码共同以 1 字节表示；操作数是内部寄存器，并被编码到指令中；指令需要一个存储位置来将单个寄存器存储在存储位置中。没有操作数的指令也是 1-byte 指令。
例如：MOV B,C 、LDAX B、NOP、HLT（这块不明白的读者可以自行查阅）
2-byte: 2 字节包括：第一个字节指定的操作码；第二个字节指定操作数；指令需要两个存储器位置才能存储在存储器中。
例如 MVI B, 26 H、IN 56 H
3-byte: 在 3 字节指令中，第一个字节指定操作码；后面两个字节指定 16 位的地址；第二个字节保存
低位地址；第三个字节保存高位地址。指令需要三个存储器位置才能将单个字节存储在存储器中。例如 LDA 2050 H、JMP 2085 H
大多数程序总是对少量页面进行多次访问，而不是对大量页面进行少量访问。因此，只有很少的页面能够被再次访问，而其他的页表项很少被访问。
页表项一般也被称为
Page Table Entry(PTE)。
基于这种设想，提出了一种方案，即从硬件方面来解决这个问题，为计算机设置一个小型的硬件设备，能够将虚拟地址直接映射到物理地址，而不必再访问页表。这种设备被称为转换检测缓冲区(Translation Lookaside Buffer, TLB)，有时又被称为 相联存储器(associate memory) 。
| 有效位 | 虚拟页面号 | 修改位 | 保护位 | 页框号 |
|---|---|---|---|---|
| 1 | 140 | 1 | RW | 31 |
| 1 | 20 | 0 | RX | 38 |
| 1 | 130 | 1 | RW | 29 |
| 1 | 129 | 1 | RW | 62 |
| 1 | 19 | 0 | RX | 50 |
| 1 | 21 | 0 | RX | 45 |
| 1 | 860 | 1 | RW | 14 |
| 1 | 861 | 1 | RW | 75 |
TLB 加速分页
TLB 通常位于 MMU 中，包含少量的表项，每个表项都记录了页面的相关信息，除了虚拟页号外，其他表项都和页表是一一对应的
是不是你到现在还是有点不理解什么是 TLB，TLB 其实就是一种内存缓存，用于减少访问内存所需要的时间，它就是 MMU 的一部分，TLB 会将虚拟地址到物理地址的转换存储起来，通常可以称为地址翻译缓存(address-translation cache)。TLB 通常位于 CPU 和 CPU 缓存之间，它与 CPU 缓存是不同的缓存级别。下面我们来看一下 TLB 是如何工作的。
当一个 MMU 中的虚拟地址需要进行转换时，硬件首先检查虚拟页号与 TLB 中所有表项进行并行匹配，判断虚拟页是否在 TLB 中。如果找到了有效匹配项，并且要进行的访问操作没有违反保护位的话，则将页框号直接从 TLB 中取出而不用再直接访问页表。如果虚拟页在 TLB 中但是违反了保护位的权限的话（比如只允许读但是是一个写指令），则会生成一个保护错误(protection fault) 返回。
上面探讨的是虚拟地址在 TLB 中的情况，那么如果虚拟地址不再 TLB 中该怎么办？如果 MMU 检测到没有有效的匹配项，就会进行正常的页表查找，然后从 TLB 中逐出一个表项然后把从页表中找到的项放在 TLB 中。当一个表项被从 TLB 中清除出，将修改位复制到内存中页表项，除了访问位之外，其他位保持不变。当页表项从页表装入 TLB 中时，所有的值都来自于内存。
软件 TLB 管理
直到现在，我们假设每台电脑都有可以被硬件识别的页表，外加一个 TLB。在这个设计中，TLB 管理和处理 TLB 错误完全由硬件来完成。仅仅当页面不在内存中时，才会发生操作系统的陷入(trap)。
在以前，我们上面的假设通常是正确的。但是，许多现代的 RISC 机器，包括 SPARC、MIPS 和 HP PA，几乎所有的页面管理都是在软件中完成的。
精简指令集计算机或 RISC 是一种计算机指令集，它使计算机的微处理器的每条指令（CPI）周期比复杂指令集计算机（CISC）少
在这些计算机上，TLB 条目由操作系统显示加载。当发生 TLB 访问丢失时， 不再是由 MMU 到页表中查找并取出需要的页表项，而是生成一个 TLB 失效并将问题交给操作系统解决 。操作系统必须找到该页，把它从 TLB 中移除（移除页表中的一项），然后把新找到的页放在 TLB 中，最后再执行先前出错的指令。然而，所有这些操作都必须通过少量指令完成，因为 TLB 丢失的发生率要比出错率高很多。
无论是用硬件还是用软件来处理 TLB 失效，常见的方式都是找到页表并执行索引操作以定位到将要访问的页面，在软件中进行搜索的问题是保存页表的页可能不在 TLB 中，这将在处理过程中导致其他 TLB 错误。改善方法是可以在内存中的固定位置维护一个大的 TLB 表项的高速缓存来减少 TLB 失效。通过首先检查软件的高速缓存，操作系统 能够有效的减少 TLB 失效问题。
TLB 软件管理会有两种 TLB 失效问题，当一个页访问在内存中而不在 TLB 中时，将产生 软失效(soft miss)，那么此时要做的就是把页表更新到 TLB 中（我们上面探讨的过程），而不会产生磁盘 I/O，处理仅仅需要一些机器指令在几纳秒的时间内完成。然而，当页本身不在内存中时，将会产生硬失效(hard miss)，那么此时就需要从磁盘中进行页表提取，硬失效的处理时间通常是软失效的百万倍。在页表结构中查找映射的过程称为 页表遍历(page table walk)。
上面的这两种情况都是理想情况下出现的现象，但是在实际应用过程中情况会更加复杂，未命中的情况可能既不是硬失效又不是软失效。一些未命中可能更软或更硬（偷笑）。比如，如果页表遍历的过程中没有找到所需要的页，那么此时会出现三种情况：
- 所需的页面就在内存中，但是却没有记录在进程的页表中，这种情况可能是由其他进程从磁盘掉入内存，这种情况只需要把页正确映射就可以了，而不需要在从硬盘调入，这是一种软失效，称为
次要缺页错误(minor page fault)。 - 基于上述情况，如果需要从硬盘直接调入页面，这就是
严重缺页错误(major page falut)。 - 还有一种情况是，程序可能访问了一个非法地址，根本无需向 TLB 中增加映射。此时，操作系统会报告一个
段错误(segmentation fault)来终止程序。只有第三种缺页属于程序错误，其他缺页情况都会被硬件或操作系统以降低程序性能为代价来修复
针对大内存的页表
还记得我们讨论的是什么问题吗？（捂脸），可能讨论的太多你有所不知道了，我再提醒你一下，上面加速分页过程讨论的是 虚拟地址到物理地址的映射速度必须要快 的问题，还有一个问题是 如果虚拟地址空间足够大，那么页表也会足够大 的问题，如何处理巨大的虚拟地址空间，下面展开我们的讨论。
多级页表
第一种方案是使用多级页表(multi)，下面是一个例子
32 位的虚拟地址被划分为 10 位的 PT1 域，10 位的 PT2 域，还有 12 位的 Offset 域。因为偏移量是 12 位，所以页面大小是 4KB，公有 2^20 次方个页面。
引入多级页表的原因是避免把全部页表一直保存在内存中。不需要的页表就不应该保留 。
多级页表是一种分页方案，它由两个或多个层次的分页表组成，也称为分层分页。级别1（level 1）页面表的条目是指向级别 2（level 2） 页面表的指针，级别2页面表的条目是指向级别 3（level 3） 页面表的指针，依此类推。最后一级页表存储的是实际的信息。
下面是一个二级页表的工作过程
在最左边是顶级页表，它有 1024 个表项，对应于 10 位的 PT1 域。当一个虚拟地址被送到 MMU 时，MMU 首先提取 PT1 域并把该值作为访问顶级页表的索引。因为整个 4 GB （即 32 位）虚拟地址已经按 4 KB 大小分块，所以顶级页表中的 1024 个表项的每一个都表示 4M 的块地址范围。
由索引顶级页表得到的表项中含有二级页表的地址或页框号。顶级页表的表项 0 指向程序正文的页表，表项 1 指向含有数据的页表，表项 1023 指向堆栈的页表，其他的项（用阴影表示）表示没有使用。现在把 PT2 域作为访问选定的二级页表的索引，以便找到虚拟页面的对应页框号。
倒排页表
针对分页层级结构中不断增加的替代方法是使用 倒排页表(inverted page tables)。采用这种解决方案的有 PowerPC、UltraSPARC 和 Itanium。在这种设计中，实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项。
虽然倒排页表节省了大量的空间，但是它也有自己的缺陷：那就是从虚拟地址到物理地址的转换会变得很困难。当进程 n 访问虚拟页面 p 时，硬件不能再通过把 p 当作指向页表的一个索引来查找物理页。而是必须搜索整个倒排表来查找某个表项。另外，搜索必须对每一个内存访问操作都执行一次，而不是在发生缺页中断时执行。
解决这一问题的方式时使用 TLB。当发生 TLB 失效时，需要用软件搜索整个倒排页表。一个可行的方式是建立一个散列表，用虚拟地址来散列。当前所有内存中的具有相同散列值的虚拟页面被链接在一起。如下图所示
如果散列表中的槽数与机器中物理页面数一样多，那么散列表的冲突链的长度将会是 1 个表项的长度，这将会大大提高映射速度。一旦页框被找到，新的（虚拟页号，物理页框号）就会被装在到 TLB 中。
刊误
P115 页，两条线位置画反，根据下面的描述很容易误导他人，望修正。
文章参考：
https://en.wikipedia.org/wiki/Page_replacement_algorithm
http://faculty.salina.k-state.edu/tim/ossg/Memory/virt_mem/page_replace.html
https://www.geeksforgeeks.org/page-replacement-algorithms-in-operating-systems/
https://www.geeksforgeeks.org/multilevel-paging-in-operating-system/
https://en.wikipedia.org/wiki/Translation_lookaside_buffer
https://electricalvoice.com/instruction-word-size-8085-microprocessor/
https://en.wikipedia.org/wiki/Page_table
https://www.javatpoint.com/os-page-table
https://baike.baidu.com/item/内存/103614?fr=aladdin
https://baike.baidu.com/item/数据段/5136260?fromtitle=data segment&fromid=18082638&fr=aladdin
https://blog.csdn.net/One_L_Star/article/details/81901186
《现代操作系统》第四版
《Modern Operation System》fourth
