一文看懂内存管理及TLB的基本原理

1.  概述

程序通常运行在虚拟内存空间，虚拟内存的大小由处理器位数决定。对于32位处理器，其地址范围是0~0xFFFF_FFFF，即4GB；对于64位处理器，其地址范围是0~0xFFFF_FFFF_FFFF_FFFF，这个范围就是程序能够产生的地址范围，其中的某个地址就称为虚拟地址。

和虚拟内存（virtual memory）相对应的是物理内存（physical memort），物理内存是现实世界中直接使用的存储器，其中的某个地址就是物理地址。物理内存的大小不能超过处理器最大可以寻址的空间。例如，32位处理器的物理内存（一般简称为内存）可以是256MB，即PM的范围是0~0xFFF_FFFF，也可以将物理内存增加到4GB，此时虚拟内存和物理内存的地址空间大小是相同的。

使用了虚拟地址，则处理器输出的地址就是虚拟地址，这个地址不会直接送到物理存储器中，而要先进行地址转换。负责地址转换的部件称为内存管理单元(Memory Manage Unit, MMU)，如下图。

使用虚拟存储器的系统

使用虚拟存储器不仅便于程序在处理器中运行，还给程序编写带来好处。在直接使用物理存储器的处理器中，如果要同时运行多个程序，需要为每个程序都分配一块地址空间，每个程序都需要在这个地址空间内运行，这样极大地限制了程序的编写，而且不能使处理器随便地运行程序。

通过操作系统动态地将每个程序的虚拟地址转化为物理地址，还可以实现程序的保护。即使两个程序使用了同一个虚拟地址，它们也会对应到不同的物理地址，因此可以保证每个程序的内容不会被其他程序随便改写。通过这种方式，还可以实现程序间的共享，例如操作系统内核提供了打印(printf)函数，第一个程序在地址A使用了printf，第二个程序在地址B使用了printf，操作系统在地址转换的时候，会将地址A和B转换为同样的物理地址，这个物理地址就是printf函数在物理存储器中的实际地址，这样就实现了程序的共享。虽然两个程序都用了printf，但没必要使printf占用物理内存的两个地方，因此，使用虚拟存储器不仅可以降低物理存储器的容量需求，还可以带来另外的好处：保护(protect)和共享(share)。

一个处理器要支持现代的操作系统，就必须支持虚拟存储器，它是操作系统里非常重要的内容。

2.  地址转换

目前最通用的虚拟内存是基于分页(page)的虚拟存储器。虚拟地址空间以页为单位划分，典型的页大小为4KB，相应的物理地址也进行同样大小的划分。由于历史原因，物理地址空间中不叫做页，而称为frame，它和页的大小必须相等。当程序开始运行时，会将当前需要的部分内容从硬盘中搬移到物理内存中，每次搬移的单位就是一个页的大小。由于只有在需要时才将一个页的内容放到物理内存中，这种方式就称为demand page，它使处理器可以运行比物理内存更大的程序。

对于一个虚拟地址，VA[11:0]表示页内的位置，称为page offset，VA剩余的部分用来表示哪个页，也称为VPN(Virtual Page Number)。相应的，物理地址的PA[11:0]表示frame内的位置，称为frame offset，而PA剩余的部分表示哪个frame，称为PFN(Physical Frame Number)。由于页和frame的大小一样，所以VA到PA的转换实际上就是VPN到PFN的转换，offset不需要变化。

2.1  单级页表

在使用虚拟内存的系统中，都是用一张表来存储虚拟地址到物理地址（实际上是VPN到PFN）的对应关系，这个表称为页表(Page Table，PT)，也称为转换表（translation table）。这个表一般放在物理内存中，使用虚拟地址来寻址，表格中被寻址到的内容就是该虚拟地址对应的物理地址。每个程序都有自己的页表，为了指示程序的页表在物理内存中的位置，处理器中一般会有一个页表寄存器(Page Table Register，PTR)，用来存放当前运行程序的页表在物理内存中的起始地址。每次操作系统将一个程序调入物理内存中执行时，会将寄存器PTR设置好。当然，这种机制可以工作的前提是页表位于物理内存中一片连续的地址空间内。

下图表示如何使用PTR从物理内存中定位到一个页表，并使用虚拟地址来寻址页表，从而找到对应的物理地址。其实，使用PTR和虚拟地址来寻址，相当于用它们两个共同组成一个地址，来寻址物理内存。

图中每个页的大小是4K，使用PTR和虚拟地址共同来寻址，找到对应的表项(entry)，当表项对应的valid为1时，表示这个虚拟地址所在的4KB空间已经被OS映射到物理内存中，可以直接从物理内存中找到这个虚拟地址对应的数据。这时访问当前页内任意的地址，就是访问物理内存中被映射的那个4KB的空间了。如果被寻址的表项的valid是0，表示这个虚拟地址对应的4KB空间还没有被操作系统映射到物理内存，此时就产生Page Fault类型的异常，需要操作系统从更下一级的存储器(例如硬盘或闪存)将这个页对应的4KB内容搬移到物理内存。

通过页表进行地址转换

图中使用了32位的虚拟地址，页表在物理内存中的起始地址用PTR来指示。虚拟地址的寻址空间是2^32字节，即4GB；物理地址的寻址空间是2^30字节，即1GB。在页表中的一个表项(entry)能够映射4KB的大小，为了能映射整个4GB的空间，需要表项的个数应该是4GB/4KB=1M，也就是2^20，因此需要20位来寻址。也就是说32位的虚拟地址分成两部分，低12bit用来寻址一个页内的内容，高20bit用来寻址哪个页，因此真正寻址页表只需要VPN就够了。从页表中找到的内容也不是整个物理地址，而只是PFN。

需要注意，页表的结构不同于cache，页表中包括了所有VPN的映射关系，所以可以直接用VPN对页表进行寻址，而不需要使用Tag。

可以采用很多方法来减少一个进程的页表对于存储空间的需求，最常用的是多级页表(Hierarchical Page Table)，可以减少页表对于物理存储空间的占用，而且非常容易使用硬件实现。与之对应，本节所讲述的页表称为单级页表(Single Page Table)，也称为线性页表(Linear Page Table)。

2.2  多级页表

将一个4MB的线性页表划分为若干个更小的页表，称它们为子页表，处理器在执行进程的时候，不需要一下子把整个线性页表都放入物理内存中，而是根据需求逐步地放入这些子页表。而且，这些子页表不需要占用连续的物理内存空间。也就是说，相邻的子页表可以放在物理内存中不连续的位置，这样也提高了物理内存的利用效率。但是，由于所有的子页表是不连续地放在物理内存中，所以依旧需要一个表，来记录每个子页表在物理内存中存储的位置，称这个表格为第一级页表（Level1 Page Table），而那些子页表为第二级页表（Level2 Page Table）。

两级页表

这样，要得到一个虚拟地址对应的数据，先访问第一级页表，得到第二级页表的基地址，再去第二级页表得到对应的物理地址，然后就可以在物理内存中取出相应的数据。

例如，对于一个32位虚拟地址、页大小为4KB的系统，如果采用线性页表，则页表中表项个数为2^20，将其等分为2^10等份，每个等份就是一个第二级页表，共有1024个第二级页表，对应着第一级页表的1024个表项。也就是说，第一级页表需要10位地址来进行寻址。每个二级页表中，表项个数为1024，也需要10位地址来寻址。

下图中，一个页表中的表项简称为PTE，当操作系统创建一个进程时，就在物理内存中为这个进程找到一个连续的4KB空间，存在这个进程的第一级页表，并且将第一级页表在物理内存中起始地址放到PTR寄存器中，在ARM是TTB寄存器，X86是CR3寄存器等。随着这个进程的进行，操作系统会逐步在物理内存中创建第二级页表，每次创建一个第二级页表，操作系统就要将它的起始地址放到第一级页表对应的表项中。

使用两级页表进行地址转换

在很多硬件实现Page Table Walk的处理器中，都采用了多级页表的结构。Page Table Walk是指当发生TLB缺失时，需要从页表中找到对应的映射关系并将其写回到TLB的过程。

使用这种多级页表结构，每一级的页表都需要存储在物理内存中，因此要得到一个虚拟地址对应的数据，需要多次访问物理内存。显然，这个过程消耗的时间是很长。对于一个二级页表，需要访问两次物理内存，才能得到虚拟地址对应的物理地址，然后还需要访问一次物理内存得到数据，因此要得到虚拟地址对应的数据，共需要访问三次物理内存。

使用虚拟存储器的优点总结：

让每个程序都有独立的地址空间。

引入虚拟地址到物理地址的映射，为物理内存的管理带来方便，可以更灵活地对其进行分配和释放，在虚拟内存上连续的地址空间可以映射到物理内存上不连续的空间。

在处理器中如果存在多个进程，为这些进程分配的物理内存之和可能大于实际可用的物理内存，虚拟存储器的管理使得这种情况下各个进程仍能够正常运行，此时为各个进程分配的只是虚拟存储器的页，这些页可能存在物理内存中，也可能临时存在于更下一级的硬盘中，在硬盘中这部分空间被称为swap空间。当物理内存不够用时，将物理内存中一些不常用的页保存到硬盘上的swap空间。因此处理器等效可以使用的物理内存的总量是物理内存的大小 + 硬盘中swap空间的大小。

利用虚拟存储器，可以管理每一个页的访问权限。从硬件角度，单纯的物理内存本身不具有各种权限的属性，它的任何地址都可以被读写，而操作系统则要求在物理内存中实现不同的访问权限。例如一个进程的代码段（text）一般不能被修改，而数据段（data）一般可读可写。这些权限的管理通过页表来实现，在页表中设置每个页的属性，操作系统和MMU可以控制每个页的访问权限。

3.  TLB和Cache

3.1  TLB的设计

3.1.1  概述

对两级页表来说，需要访问两次物理内存才可以得到虚拟地址对应的物理地址（一次访问第一级页表，另一次访问第二级页表），而物理内存的运行速度相对于处理器是很慢的。此时可以借鉴Cache的设计理念，使用一个速度比较快的缓存，将页表中最近使用的PTE缓存下来，因为它们在以后可能继续使用，尤其对于取指令来说，考虑到程序本身的串行性，会顺序地从一个页内取指令，将PTE缓存起来能够加快一个页内4KB内容的地址转换速度。

由于历史原因，缓存PTE的部件一般不叫Cache，而叫TLB (Translation Lookaside buffer)，在TLB中存储了页表中最近使用过的PTE。本质上，TLB就是页表的Cache。但是TLB不同于一般的cache，它只有时间相关性(Temporal Locality)，也就是现在访问的页，很有可能在以后继续被访问。至于空间相关性(Spatial Locality)，TLB没有明显的规律，因为在一个页内有很多情况，都可能使程序跳转到其他不相邻的页中取指令或数据，也就是说，虽然当前在访问一个页，但未必会访问它相邻的页。

TLB本质上是Cache，有三种组织方法：直接相连（direct mapped）、组相连（set associative）和全相连（fully associative）。现代的处理器，很多都采用两级TLB，第一级TLB分为指令TLB(I-TLB)和数据TLB(D-TLB)，一般采用全相连的方式；第二级TLB是指令和数据共享，一般采用组相连的方式，这种设计方法和多级Cache一样。

TLB是页表的Cache，所以TLB的内容完全来自于页表，下图为一个全相连的TLB，从处理器送出的虚拟地址首先送到TLB中进行查找，如果TLB对应的内容是有效的（即valid位为1），则表示TLB命中，可以直接使用从TLB得到的物理地址来寻址物理内存；如果TLB缺失（即valid位为0），那么需要访问物理内存中的页表，此时有如下两种情况：

(1) 在页表中找到的PTE是有效的，即这个虚拟地址所属的页存在于物理内存中，那么就可以直接从页表中找到对应的物理地址，使用它来寻址物理内存从而得到需要的数据，同时将页表中的这个PTE写回到TLB中，供以后使用。

(2) 在页表中找到的PTE是无效的，即这个虚拟地址所属的页不在物理内存中，造成这种现象的原因很多，例如这个页在以前没有被使用过，或者这个页已经被交换到了硬盘中等，此时就应该产生Page Fault类型的异常，通知操作系统来处理这个情况，操作系统需要从硬盘中将相应的页搬移到物理内存中，将它在物理内存中的首地址放到页表内对应的PTE中，并将这个PTE的内容写到TLB中。

TLB的内容

图中，因为TLB采用了全相连的方式，所以相比页表，多了一个Tag的项，它保存了虚拟地址的VPN，用来对TLB进行匹配查找，TLB中其它的项完全来自于页表，每当发生TLB缺失时，将PTE从页表中搬移到TLB内。

现代处理器都支持大小可变的页，由操作系统来管理。根据不同应用特点选用不同大小的页，可以最大限度利用TLB中有限的空间，同时又不至于在页内产生更多的碎片。为了支持这种特性，在TLB中需要相应的位进行管理，例如MIPS处理器的TLB中，有一个12位的Pagemask项，它用来指示当前被映射的页的大小。

采用不同大小的页，在寻址TLB时，进行的地址比较也是不同的，对于1MB大小的页，只需要将VA[31:20]作为Tag，参与地址比较就可以了，虚拟地址剩余的20位将用来寻址页的内部。不仅如此，对TLB的寻址还受到其他内容的影响，例如ASID和Global位。

3.1.2  TLB缺失

当一个虚拟地址查找TLB，发现需要的内容不在其中时，就发生了TLB缺失(miss)，由于TLB本身的容量很小，所以TLB缺失发生的频率比较高，很多情况下都可以发生TLB缺失，主要有以下几种：

(1) 虚拟地址对应的页不在物理内存中，此时页表中没有对应的PTE，而TLB是页表的cache，自然TLB中也不可能有。

(2) 虚拟地址对应的页在物理内存中，因此页表中有对应的PTE，但这个PTE还没有放到TLB中，这种情况也经常发生，毕竟TLB的内容远小于页表。

(3) 虚拟地址对应的页在物理内存中，因此页表中有对应的PTE，这个PTE也曾存在于TLB中，但后来被替换出去了，现在这个页又重新使用了，此时这个PTE就存在于页表中，但不在TLB内。

其实，（2）和（3）两种情况是在说同一件事情，即虚拟地址和物理地址的映射关系存在于页表中，而不存在于TLB中，此时只需要从页表中就可以找到这个映射关系，因此它们的处理时间比情况（1）要短。

解决TLB缺失的本质就是要从页表中找到对应的映射关系，并将其写回到TLB内，这个过程称为Page Table Walk，可以使用硬件状态机来完成，也可以使用软件来做，它们各有优缺点，各自工作流程如下：

(1) 软件实现Page Table Walk。软件实现可以保证最大的灵活性，但一般也需要硬件配合，来减少工作量。一旦发现TLB缺失，硬件把产生TLB缺失的虚拟地址保存到一个特殊寄存器中，同时产生一个TLB缺失类型的异常，在异常处理程序中，软件使用保存在特殊寄存器当中的虚拟地址去寻址物理内存中的页表，找到对应的PTE，并写回到TLB中，很显然，处理器需要支持直接操作TLB的指令，如写TLB指令和读TLB指令等。对于超标量处理器，对异常处理时，会将流水线中所有的指令抹掉，这样会产生一些性能上缺失，但可以实现灵活的TLB替换算法，MIPS和Alpha处理器一般采用这种方法。

(2) 硬件实现Page Table Walk。硬件实现一般由MMU完成。TLB缺失时，MMU自动使用当前的虚拟地址去寻址物理内存中的页表，多级页表的最大优点就是容易使用硬件进行查找，只需要使用一个状态机逐级进行查找就可以，如果从页表中找到的PTE是有效的，那么将它写回到TLB，这个过程全部由硬件自动完成。如果MMU发现查找到的PTE是无效的，那么就只能产生Page Fault类型的异常，由操作系统来处理整个情况。使用硬件处理TLB缺失更适合超标量处理器，它不需要打断流水线，因此性能会好一点，但是需要操作系统保证页表已经在物理内存中建立好了，并且操作系统需要将页表的基地址预先写到处理器内部的寄存器中(例如PTR)，这样才能保证硬件可以正确地寻址页表，ARM、PowerPC和x86处理器都采用这种方法。

3.1.3  TLB的写入

当一个页从硬盘搬移到物理内存之后，操作系统需要知道这个页中的内容在物理内存中是否被改变过。如果没有被改变过，当这个页需要被替换时可以直接进行覆盖，因为总能从硬盘中找到这个页的备份；如果这个页的内容在物理内存中被修改过(例如store指令的地址落在了这个页内)，那么在硬盘中存储的页就过时了，在物理内存中的这个页要被替换时，需要先将它从物理内存中写回到硬盘，因此需要在页表中，对每个被修改的页加以标记，称为脏状态位(dirty)，当物理内存中的一个页要被替换时，首先检查它在页表中对应PTE的脏状态位，如果为1，需要先将这个页写回到硬盘，然后才能将其覆盖。

使用TLB作为页表的缓存之后，处理器送出的虛拟地址会首先访问TLB，如果命中，那么可以直接从TLB中得到物理地址，不需要再访问页表。执行load/store指令都会使 TLB中对应的“使用位use”变为 1，表示这个页中的某些数据最近被访问过；如果是 store指令，还会使脏状态位dirty也变为1，表示这个页中的某些数据被改变了。但如果采用写回(Write Back)的TLB，那么使用位use和脏状态位dirty改变的信息并不会马上从TLB中写回到页表，只有等到TLB中的一个表项要被替换的时候，才会将它对应的信息写回到页表中，这会给操作系统进行页表替换带来问题，因为页表中记录的状态位(use和dirty)可能是过时的。一种比较容易的解决办法就是操作系统在Page Fault发生时，首先将TLB中的内容写回到页表，然后就可以根据页表中的信息进行后续处理了。

实际上，操作系统完全可以认为被TLB记录的所有页都是需要被使用的，这些页在物理内存中不能够被替换。操作系统可以使用一些办法来记录页表中哪些PTE被放到了TLB中来实现。

如果在系统中使用了D-Cache，那么物理内存中每个页的最新内容都可能存在D-Cache中，要将这个页的内容写回到硬盘，首先需要确认D-Cache中是否保留着这个页的数据。因此在进行页表替换时，操作系统就必须有能力从D-Cache中找出这个页的内容，并将其写回到物理内存中。

3.1.4  对TLB进行控制

如果由于某些原因导致一个页的映射关系在页表中不存在了，那么它在TLB中也不应该存在，而操作系统在一些情况下，会把某些页的映射关系从页表中抹掉，例如：

(1) 当一个进程结束时，这个进程的指令(code)、数据(data)和堆栈(stack)所占据的页表就需要变为无效，这样就释放了这个进程占据的物理内存空间。但是，此时在I-TLB中可能存在这个进程的程序对应的PTE，在D-TLB中可能还存在着这个进程的数据和堆栈的PTE，此时需要将I-TLB和D-TLB中和这个进程相关的所有内容置为无效，如果没有使用ASID，最简单的做法就是将I-TLB和D-TLB中的全部内容都置为无效，这样保证新的进程可以使用一个干净的TLB；如果实现了ASID，只需将这个进程对应的内容在TLB中置为无效就可以了。

(2) 当一个进程占用的物理内存过大时，操作系统可能会将这个进程中的一部分不经常使用页写回到硬盘中，这些页在页表中对应的映射关系也应该置为无效，此时也需要将I-TLB和D-TLB中对应的内容置为无效，但是，一般操作系统会尽量避免将存在于TLB中的页置为无效，因为这些页在以后很可能会被继续使用。

因此，抽象出来，对TLB的管理需要包括的内容有如下几点：

能够将I-TLB和D-TLB的所有表项(entry)置为无效；

能够将I-TLB和D-TLB中某个ASID对应的所有表项置为无效；

能够将I-TLB和D-TLB中某个VPN对应的表项置为无效；

不同的处理器有着不同的方法来对TLB进行管理。在ARM处理器中，使用系统控制协处理器(ARM称之为CP15)中的寄存器对TLB进行控制，因此处理器只需要使用访问协处理器的指令(MCR和MRC)来向CP15中对应的寄存器写入相应的值，就可以对TLB进行操作。