起因
之前我们学习到，我们通过将虚拟内存和物理内存进行分段，分成代码段，堆段，栈段等。但是通过将内存进行分段同时也带来了外部碎片的问题，因为将其分割成不同大小时空间就已经开始碎片化(fragmented)了。随着时间的推移，分配程序会变得更加困难。
为了解决这个问题，演变出了另一种解决方案，通过将虚拟内存进行分页，即将内存分割成固定大小的单元，每个单元称为一虚拟页(Virtual Page Number, VPN)。
而在物理内存中，将其每一个单元称为页帧(Paeg rame)，每个页帧都对应相应的虚拟内存页。
基本实现
有一个很简单的示例可以理解分页是怎么实现且工作的。假设现在有一个
64字节的小空间，这个小空间被划分成了4个16字节(16*4 = 64)的虚拟页。而物理内存假设有
128字节，在这个例子中，物理页和虚拟页的大小是对应的，也是16字节1页，物理内存被划分成8个页帧，虚拟内存的4个虚拟页被分配到这个物理内存中，如下图所示
我们知道，操作系统会为每个进程创建一个页表，记录虚拟地址对应的物理地址，对于我们这个例子来说，这个进程的页表就有4个条目:
(虚拟页0 → 物理页帧3)，(虚拟页1 → 物理页帧7)，(虚拟页2 → 物理页帧5)，(虚拟页3 → 物理页帧2)
接下来我们来进行虚拟地址到物理地址的转换，为了更好理解转换的过程，我们首先需要理解，对于我们这个例子来说，虚拟空间只有64字节，用6个2进制位就足够表示(), 也就是说，虚拟地址(virtual address)是6个二进制位的。如下图所示
紧接着，我们需要对这个地址进行拆分，将它拆分成虚拟页号(virtual page numb, VPN)和页内偏移量(offset)。
我们例子中，每个页的大小是16字节，16字节用4个2进制位()就可以表示完整了，那么剩下的2位可以用来表示虚拟页号
在我们理解了上述前提后，此时假设我们需要来进行一次地址操作
这里
“21”就是虚拟地址，转换成二进制就是“01 0101”，对于这个地址，将它拆分成虚拟页号和偏移量后是如下图形式的
这样拆分后，我们可以计算出虚拟页号是
“01” 也就是十进制的1，表示虚拟页号是第1页，偏移量是 0101，表示偏移量是5。此时我们可以去检查这个进程的页表，来将这个虚拟地址转换成真实地址，可以发现虚拟页号第1页被映射到了物理帧号(physical frame number, PFN)的7(有时候也比称为物理页号 physical page number, PPN)。
物理帧号7的二进制形式是
111，那么MMU(内存管理单元 Memory Manage Unit)在做地址转换的时候就会用这个PFN去替换(把01替换成111)VPN，而偏移量不需要做任何改变，因为偏移量只是告诉页面具体的哪个字节是我们需要的，而经过转换后这个地址最终变成了 111 0101(十进制 117)，这个位置就是准确的物理地址。
当我们学习到这里时，我们就可以询问关于分页的一些基本问题。如这些页表在哪里储存？页表中的典型内容是什么？页表有多大？分页是否会让操作系统变的更慢？
页表
页表的存在就是用来记录进程的虚拟页(VPN)对应物理页(PFN)，刚刚我们例子的物理地址和虚拟地址都比较小，假想一个32位的操作系统，它的地址是32位的，然后每个虚拟页都有4KB的大小。那么对于这么大的内存来说，它的VPN就有20位，偏移量有12位( = 4096bit = 4KB)。
一个20位的VPN意味着，操作系统需要为每个进程保存(1048576, 一百多万)个条目。假设每个页表条目(PTE)需要4个字节，那么一个进程的页表就需要4MB(1048576 * 4 /1024 = 4096), 4MB的内存。如果有100个进程，那就需要400MB的内存了。很显然，这个内存占用空间是巨大的，所以页表并没有存在MMU中，而是会被操作系统存在物理内存中。
页表中究竟有什么
页表除了我们刚刚说说的虚拟页号(VPN)，还有其它一些信息。
- 有效位(valid bit): 表示转换的地址是否有效，在程序刚开始运行的时候，代码和堆会在地址空间的一端，而栈在另一端，那么中间还未使用的位置都会被标记成无效(invalid)。如果进程尝试访问这区间的内存，操作系统可能会kill掉这个进程。将未使用的页面标记成无效，可以无需为这些页面分配物理帧，从而大量的节省内存。
- 保护位(protection bit): 表示页是否可读，写或执行。
- 存在位(present bit): 表示页是否在物理内存还是磁盘上(即它被交换到磁盘中，swapped out)
- 脏位(dirty bit): 表示页是否有进行过修改，如果有进行过修改，则它在写回的时候需要将数据进行更新。
- 参考位(reference bit): 表示这个页是否被访问过，这在页面替换(page replacement)的时候是很关键的信息。
如下有一副x86架构的示例页表项。它包含一个存在位(P)，确定是否允许写入该页面的读/写位(R/W)确定用户模式进程是否可以访问该页面的用户/超级用户位 (U/S)，有几位(PWT、PCD、PAT 和 G)确定硬件缓存如何为这些页面工作，一个访问位(A)和一个脏位(D)，最后是页帧号(PFN)本身。
分页：也很慢
经过到现在的学习，我们已经知道了，一个程序的页表是很大的，而经过实践，人们也发现了它会让速度有所变慢。
来看一个简单的例子，这里我们只分析对地址
“21”的使用，而不关心这个地址具体的数据是啥样的。对于我们来说，我们其实已经知道了，
21 对应的物理地址其实就是117，上述我们已经讨论过了。那么对于操作系统来说，它是怎么知道的呢，首先它要取找到这个进程的页表，现在我们假设一个页表基址寄存器(page-table base register)包含了页表的起始位置的物理地址，那么为了找到
21这个地址的页表项(PTE)，硬件会做以下操作对于我们的例子来说VPN_MASK(掩码)的值就是
110000，这个掩码的作用就是为了取VPN(高2位，因为虚拟地址一共分了4页)，而清空其它位; SHIFT被设置成4(偏移量是4位)，右移4位，这样就可以得到VPN了。
再深入一点，如地址21(二进制 010101), 按位与(都是1才为1) VPN_MASK(110000)之后得到 010000，然后再右移4位，得到了01，对应的就是虚拟页1。然后再用这个值作为页表基址寄存器指向PTE数组的索引。这个物理地址所在的物理帧是7。现在知道了这个物理地址，那么硬件现在就好办了，接下来它只需要取出偏移量，然后对物理帧号进行拼接(物理帧号 按位或 偏移量)，就可以拿到确切的位置了，
这lia行的意思就是先取出偏移量，这里的OFFSET_MASK是
0011111(因为要取偏移量(低4位)，所以要清空高2位)，得到offset是(000101)。 然后用物理帧号拼接上偏移量，这里的PFN是7，二进制是
111。PFN_SHIFT应该是4(因为左移运算是在2进制数后面补0，而偏移地址是4位)，所以将PFN左移4位得到的结果就是111 0000然后用这个数按位或offset(按位或只要遇到1就是1)拼接上偏移量，所以最终的物理地址是111 0101，完整的代码应该是如下所示现在可以看到，在对内存进行引用的时候会带来两个问题，
- 页表本身占用了很多内存。
- 在对内存进行引用的时候运行会很慢，因为每次对内存进行引用都需要执行上述的代码操作对物理内存直接进行访问是很慢的，这一点在学习存储器体系架构的时候已经学习过了。
TLB
为了让地址转换更快(这次多级页表中效果更为明显)，操作系统常常需要硬件的帮助，转译后备缓冲器(Translation Lookaside Buffer，TLB)，在国内被翻译为页表缓存、转址旁路缓存，它的作用是为了做页表的缓存(cache)，因为页表是被放在物理内存中的，如果每次虚拟地址转换物理地址都需要进行一次内存访问，那么就会变得很慢，而TLB的作用就是缓存页表的条目，如果TLB中包含所需的条目，那么TLB就可以直接进行返回。
TLB具有一定数目的空间槽，里面的每一个条目都会记录虚拟地址到物理地址的映射关系，它类似于一个hash表结构。key是虚拟地址，value是物理地址。如果TLB能够命中的话，则可以以非常快的速度匹配结果。
以下有一个TLB的大体框架，说明了硬件如何处理虚拟地址转换
TLB其实就是页表的缓存，如果能够在TLB中命中缓存，那么开销则不会很大，如果未命中的话，则需要执行一次额外的内存访问:
- 容量：12 - 4,096 分页表条目
- 命中时间：0.5 - 1 时钟周期
- 不命中代价：10 - 30 时钟周期
- 不命中率: 0.01% - 3%
示例：访问数组
为了弄清楚TLB的操作，我们来看一个简单的虚拟地址追踪，看看他是怎么处理的。
我们有一个256位的小虚拟地址空间，256一共需要8个二进制位来表示，其中4位是VPN，和4位的偏移量，然后这个地址空间的页大小是
16bit。假设我们有一个数组，这个数组一共有10项，数组的每一项都是一个4字节大小。它起始地址位于虚拟地址100的位置。
如下图所示，一共有
16bit * 16 = 256bit大小的地址空间，这个数组位于第6页，偏移量为4的位置，因为100/16=6.25, 1/0.25=4, 所以得到第6页的偏移量为4的位置。
现在考虑一个简单的循环代码
简单起见，这里只考虑对数组的访问(忽略i和sum的引用，以及指令本身)，当访问第一个数组(
a[0])时，看到是虚拟地址100，硬件会从中取出VPN(VPN=6)接着会去TLB中查看是否已经存在有效映射，因为这里是程序第一次访问该数组，所以TLB未命中。接下来访问
a[1]，这次TLB可以命中了！因为在访问a[0]的时候未命中，就会将一整页的转换缓存下来，因此a[1]能够命中，接下来继续访问a[2]，将继续命中，因为它们属于同一页。可惜随后继续访问
a[3]的时候TLB会未命中，但是接下来几项(a[4]-a[6])都会命中，因为它们属于同一页。最后，访问
a[7]的时候又会TLB未命中，系统又会去查找页表，看这个虚拟页在物理内存的位置，然后相应的更新TLB，最后两次访问(a[8]-a[9])都会命中。现在来总结一下对这个数组的10次访问对TLB的行为表现：未命中、命中、命中、未命 中、命中、命中、命中、未命中、命中、命中。可以得到命中率(hit rate)为70%。虽然这不是很高，因为我们希望命中率接近100%。
这里也同时需要注意页大小对这个示例的影响，如果这个页大小翻一倍(32字节，而不是16字节)，那么未命中的会更少，典型的页大小是4KB，这种情况下，密集的，基于数组的访问会让TLB表现很好，每页的访问只会遇到一次不命中。
关于TLB性能还有一点，如果在这次循环后不久，又对这个数组发生了访问，这次我们可以看到更好的结果，假设TLB足够大，那它就能缓存所需的转换映射, 就可以让10次访问全部命中！因为这种是属于空间局部性(temporal locality)，即短时间内对内存项的再次引用，所以TLB的命中率会高很多。所以，如果一个程序的时间局部性和空间局部性(spatial locality)良好的话，那么TLB的命中率就会很高。
时间局部性和空间局部性在csapp中有介绍 这里我们可能会有疑惑，既然缓存有这么多优势，那为什么不直接把这个缓存做的更大呢，把所有的数据都装下去呢。 这里我们需要注意，我们遇到了最基本的定理，如果想要缓存尽可能的快，那么它就必须小，因为光速和其它物理限制会起作用。那就意味着，更大的缓存注定会更慢，所以无法达到目的。因此我们只能用小而快的缓存，那么要解决的问题就是如何把缓存利用好来更好的提升性能。
如何处理TLB未命中的情况
处理TLB未命中有硬件和软件(操作系统)两个方案。以前的硬件有复杂的指令集(Complex-Instruction Set Computer, CISC)，搞硬件的那些人不相信搞操作系统的人。所以是硬件在全权处理TLB的未命中。
硬件知道页表在物理内存的的位置(通过页表基址寄存器，page-table base register PTBR)，那么发生TLB未命中的时候，硬件就通过
PTBR找到该进程的页表，然后遍历这个页表，找到正确的PTE(页表项)，然后拿出转换映射，更新PTE, 并且重试该指令。x86架构就是通过这种”旧”体系结构用硬件来管理TLB的，它采用固定的多级页表(multi-level page table)，然后由CR3寄存器来指向当前页表。现代化的体系架构(如 MIPS R10k，Sun公司的SPARC v9，都是精简指令集，Reduced-Instruction Set Computed, RISC)，它们都是有软件管理TLB(software-managed TLB)。当TLB未命中时，硬件系统会抛一个异常(如下代码最后一行)，这里会暂停当前的指令流，然后将特权级提升至内核模式，跳转到陷阱处理程序(trap handler)。这个陷阱处理程序是一段代码，它就是来处理TLB未命中的，它也会遍历去查找页表中的转换映射，然后用特别的”特权”指令更新TLB，然后从陷阱返回。然后硬件会重试该指令
这里在处理TLB未命中代码时，操作系统需要注意在调用陷阱处理程序时可能导致的无限递归。有很多解决方案，如可以把TLB的陷阱处理程序直接放在物理内存中(它不需要做任何映射(unmapped)，也不经过地址转换)。或者可以在TLB中保留一些项，记录陷阱处理程序的地址，这样的话，每次需要调用陷阱处理程序时候总是可以在TLB中命中。
软件(操作系统)来处理TLB未命中的方式会很灵活，操作系统可以用任意结构来实现页表，不需要改变硬件。另一方面是更简单，如上述代码，在TLB未命中时，硬件只需要抛出异常，不需要做其它额外的操作，剩下的事情交给操作系统就OK了。
TLB中的内容
典型的TLB会有32项，64项或者128项，因为这足够小，所以是全相联的(fully associative)。同时，在查找的时候硬件会并行的去查找TLB，当找到期望的转换映射时，一条TLB可能会像如下所示
VPN | PFN | 其它位 |
其它位可能包含有效(valid)位，表示该项是否有效的地址转换。还有保护(protection)位，表示这页是否拥有访问权限，如代码页是可读和可执行，堆页是可读和可写。还有地址空间标识符(address-space identifier, ASID)，脏位(dirty bit)等。
TLB和CPU缓存的并行查找
有一种常见优化是，当对于给定一个虚拟地址，如果TLB和CPU缓存都使用相同的地址索引方式（如二进制的前几位高地址是页号索引，低地址是页内偏移，页内偏移在转换的过程中是不会改变的）。CPU会同时对TLB和CPU缓存同时进行查找，而不用先执行完一个，再进行另一个。
两者都会同时进行查找，而在TLB命中后，它会将找到的页号发送给CPU缓存，CPU缓存会再次进行比对，以确定是否命中。这种TLB和CPU缓存的并行查找可以减少访存过程的延迟，提高系统的性能。
上下文切换时对TLB的处理
当进程发生切换时，可能TLB会遇到一些问题。因为TLB的映射只是对当前进程有用的，当进程发生了个改变，如果依旧去读取TLB中的数据，那很显然会读取到错误的数据。
为了解决问题，可以在进程发生切换时。简单地直接清空(flush)TLB，即把TLB中所有的项有效位(valid bit)都置为0。但是这也会导致新的问题，即每次上下文切换都需要清空TLB，那么每次新进程访问数据和代码的时候都会导致TLB未命中。如果操作系统频繁的切换进程，这种开销会很大。
还有另一种方案，即通过
ASID来区分进程，ASID通常比进程的PID位数少(PID一般是32位，ASID一般是8位)。来看一下这个例子, 下面例子中就出现了两个进程中的10VPN映射到了不同的物理地址，那么硬件就是通过
ASID来区分属于哪个进程。VPN | PFN | 有效位 | 保护位 | ASID |
10 | 101 | 1 | rwx | 1 |
- | - | - | 0 | - |
10 | 170 | 1 | rwx | 2 |
- | - | - | 0 | - |
当然，还有另外一种情况，就是不同的
VPN映射到了相同的PFN，如下例，这种就是多个进程在共享相同的物理页(如代码段的页，以二进制或者共享库的方式)，这种方式减少了物理页的使用，可以减少内存使用的压力。VPN | PFN | 有效位 | 保护位 | ASID |
10 | 101 | 1 | r-x | 1 |
- | - | 0 | - | - |
50 | 101 | 1 | r-x | 2 |
- | - | 0 | - | - |
TLB替换策略
所有缓存都要考虑缓存替换，对于TLB来说，当插入一个新项时，该替换(replace)哪一个旧项呢？
- 一种很常见的策略是采用最近最少使用(least-recently-used, LRU)的项进行替换，会替换最久时间没有使用的项。LRU会尽量利用内存引用流的局部性，意味着最近使用次数最少的项可能是最好的候选项。
- 还有一种典型的策略是随机(random)策略，即随机替换一项出去，这个策略很简单，而且可以避免一种极端场景。
如TLB只能存放
n页，但是一个程序频繁的访问n+1页，如果依旧采用LRU策略，就会导致最久没使用的项被替换，但是接下来，这个程序马上就会使用它。这样的话LRU策略可能就会导致TLB的表现极差，每次都会未命中，但是如果采用随机策略的话，这里表现就会好很多（龙芯F2的TLB就是用的这种策略，以及L1和L2缓存）
龙芯 2F 处理器在 TLB 缺失的时候采用随机替换的策略来选择要被替换的 TLB表项。 一级 Cache 和二级 Cache 均采用随机替换算法。 https://scc.ustc.edu.cn/zlsc/lxwycj/200910/W020100308600774636332.pdf
实际系统的TLB表项
这个例子来自MIPS R4000，它是一个RISC指令集的架构的微处理器。下图是一个稍微简化的MIPS
TLB项
MIPS R4000支持32位的地址空间，页大小是
4KB。所以在典型的虚拟地址中，预期会看到20位的VPN和12位的偏移量。但是上图中的VPN只有19位，这是因为用户空间只占地址空间的一半(是的一半)，剩下一半留给内核。
MIPS TLB还有其它的一些位，比如全局位(Global, G)，表示这个位是否全局进程共享的，如果这个位设置成1，那么就会忽略ASID。
还有ASID位，它是8位大小，用来区分进程空间的(这里有个问题，最大可以表示256，那么超过256怎么办?)。
还有3个一致性位(Coherence, C)，决定硬件如何缓存该页；脏位(Dirty Bit, D)，表示该页是否写入新数据；有效位(Valid Bit, V)，表示这个页的映射是否有效映射。还有图中没展示的
page mask字段。MIPS TLB一般有32项或者64项，大多数是给用户进程使用的， 少部分条目是留给操作系统使用的。操作系统可以设置一个寄存器，然后告诉硬件为自己保留多少TLB槽。这些保留的TLB槽，操作系统会做一些关键的代码转换，如TLB未命中的处理程序地址。下图有一个龙芯2f处理器的TLB操作处理，可供参考：
因为MIPS TLB是通过软件来管理的。所以操作系统提供了一些更新TLB的指令，如下表所示，这些指令都是特权指令。用户程序不可随意修改TLB中的内容。
巧合的是龙芯2F处理器中也是使用下表一样的指令来处理的。
指令 | 作用 |
TLBP | 查找执行的转换映射是否在TLB中 |
TLBR | 读取TLB中的某个条目到指定的寄存器 |
TLBWI | 替换TLB中指定的某个项中的内容 |
TLBWR | 替换TLB中随机某个项中的内容 |
TLB几个值得注意的问题
在多核心CPU下，如何保证缓存？
现代的CPU因为都是多核心的CPU，每个CPU都会有自己的缓存(TLB, L1, L2缓存)，这点在
CSAPP中的9.7.1中可以体现。那么如何保证一个进程在执行的过程中一直是在一个核心上运行的，而不会被调度到其它核心呢，答案是可以通过CPU亲和性来实现，这将会让程序只在其中一个核心上运行。ASID超过大小怎么办？
ASID和进程的PID肯定是不一样的，ASID会比PID少很多，一般是8位或者16位，也就是说只能表示256或者65536个进程，我们以256举例，如果ASID超过了256需要怎么办，在Linux中，如果超过了这个大小，那么就会flush整个TLB，然后重新分配ASID。参考资料
- 龙芯2f的处理器手册，里面写了比较详细的设计
- Intel 64 and IA-32 Architectures Software Developer’s Manuals
