# 3.1.2 地址转换
上一节我们介绍了三种类型的地址，逻辑地址在程序中使用，物理地址在CPU与内存交互时使用，虚拟地址是逻辑地址到物理地址转换过程中的中间状态。CPU 使用一个专门的部件来进行地址转换，该部件叫着MMU(Memory Management Unit), MMU完成地址翻译的总体流程如下：
其中 Segmentation Unit 与 Paging Unit 是MMU 内部的独立部件。除了硬件支持之外，CPU还需要操作系统中的各种数据结构来辅助完成地址翻译与权限校验工作，本节我们将深入讨论这两步地址转换的各种细节。
#### 1. 转换逻辑地址
段（Segment）是逻辑地址的核心，对于每个段，系统都需要一个数据结构来描述其基本信息，例如基址、大小、权限、类型等，该结构叫着 [Segment Descriptor](https://en.wikipedia.org/wiki/Segment_descriptor), 一个 `Segment Descriptor` 长度为8字节，其格式为：
其中重要的字段包括：
* Base Address: 段基址，总共32位
* Limit: 段长度，总共20位
* G: Granularity, 表示段大小的单位，为0时单位为字节, 即段大小为 2^20 字节，总共1M; 为1 时单位为4kb, 段大小总共为4G
* DPL: Descriptor Privilege Level, 当前段的权限，0最高，3最低。Linux 中0 代表Kernel Mode, 3 代表User Mode
系统可以包含不同类型的段，因此也会有不同类型的Segment Descriptor, Linux 中用得比较多的段包括：
* Code Segment Descriptor, 该段包含程序代码
* Data Segment Descriptor, 该段用来保存程序数据
* Task State Segment Descriptor, 该段用来保存处理器的寄存器内容
* Local Descriptor Table Descriptor, 该段指向一个包含LDT的段，这种Segment Descriptor 只会出现在GDT中
当系统对内存段划分好了之后，需要一个表来保存所有的Segment Descriptor, 存放全局共享的Segment Descriptor的表叫着 Gobal Descriptor Table, 简称为GDT, 在多核系统中，每个CPU都会有一个GDT. 每个进程也可以根据自己的需求单独定义如何划分内存段，存放进程局部使用的Segment Descriptor的表叫着 Local Descriptor Table, 简称为LDT. GDT 与 LDT 的内容都在内存中，分别由一个寄存器指向两个表的基地址，这两个寄存器叫着 gdtr 与 ldtr.
我们知道逻辑地址由两部分组成，即：段+段内偏移，其中第一部分叫着 Descriptor Selector, 目的就是用来从GDT或者LDT中寻找目标 Segment Descriptor, 其构成如下：
整个 Descriptor Selector 有16 位，各字段意义如下：
* index: GDT 或 LDT 中的索引，GDT/LDT 用来保存 Segment Descriptor 的内存地址是连续的，因此我们可以将其看着是一个数组，因此Segment Selector可以通过索引查找目标Segment Descriptor
* TI: Table Indicator, 指定是从GDT(TI=0)还是LDT(TI=1)查找Segment Descriptor
* RPL: Requestor Privilege Level, 请求者的权限，MMU在做地址转换时需要将其与目标 Segment Descriptor 中的DPL做权限对比
综合上述知识，MMU已经可以完成逻辑地址到线性地址的翻译了，其工作流程如下：
1. 从逻辑地址中解析出Descriptor Selector
2. 通过Descriptor Selector 确定Descriptor Table 是GDT 还是LDT
3. 从目标Descriptor Table 找到对应的Segment Descriptor, 并作权限校验等工作
4. 将Segment Descriptor中的段基址加上逻辑地址中的偏移量，得出最终的线性地址
示意图如下：
在不考虑效率的情况下，我们已经达成目标了，但如果仔细检查上述步骤并结合程序执行的实际过程，我们可以发现如下情况：
1. 上述翻译步骤中，对每个逻辑地址都会解析一遍Descriptor Selector, 但一个程序所使用的段通常是有限的，而且在类型上有明确区分（例如代码段与数据段），因此同一个程序内，这部分信息的变化频率不会太高，对每个地址都进行解析有点太低效了
2. 对CPU而言，通过总线访问内存其实已经是比较昂贵的操作了，最快访问数据的方式是直接访问寄存器（Register），而上述步骤中，每次地址翻译我们都需要通过内存查找GDT或者LDT, 这也是一个低效的过程
为了提升效率，硬件设计者们在CPU中引入了专门的段寄存器来存放Segment Selector, 例如 cs, ds, ss 等，只有当段发生改变时，段寄存器中的内容才需要更新。除此之外，为了加速对 Segment Descriptor 的访问，CPU还为每个段寄存器配套提供了一个寄存器，该寄存器用来存放与段寄存器中的Segment Selector 相对应的Segment Descriptor, 每次当CPU 加载新的Segment Selector 到段寄存器中时，对应的Segemnt Descriptor 就会从内存中加载到该寄存器中，这样MMU在翻译整个逻辑地址时就都不需要访问内存了。
> 存放Segment Descriptor 的寄存器是不可编程（non-programmable）的，即程序设计者无法直接通过汇编指令使用这些寄存器。
#### 2.2. 转换虚拟地址
分页（Paging）是对分段（Segment）机制的拓展与深化，当开启分页功能时，物理内存被划分成了固定大小的连续区域，每个区域叫着一页（Page），页的大小可以配置，通常情况下是4kb, 此时我们还需要对线性地址做一次翻译，以便得到物理地址。
为了支持CPU对线性地址的翻译，OS需要采用相同的思路来对内存页进行管理，页是操作系统管理物理内存的基本单元，OS需要为每个页创建一个数据结构来对其各种信息进行封装，还需要一个页表（Page Table）来存放所有这些数据结构。总的来说，就是与Segment Descriptor与GDT/LDT对等的数据结构。但此时我们会遇到一个问题，系统对段的使用是按照种类来区分的，因此段的数量并不会太多，而系统对页的使用是按照大小来区分的，页的数量将会随着物理内存的增加而增加。按照默认情况下页大小为4kb来计算，一个4GB的物理内存将会被划分为1M(2^20)个物理页面，这样页表就太大了。为了解决这个问题，页表被拆分成了多个层级，中间的层级叫着页目录（Page Directory）。例如一个32位的线性地址的编码如下：
* Page Directory Index \
页目录中每条记录（entry）都指向一个页表，线性地址中有10位用于表示页目录索引，这样一个页目录可以存放2^10=1024个页表记录。页表记录（Page Directory Entry）中记录着相应页表的各种信息，其中页表基址是最重要的一项。
* Page Table Index \
页表中每条记录都指向一个物理页面（Physical Page），同样有10 位用于页表目录索引，因此一个页表也可以存放2^10=1024个页面记录。页面记录（Page Table Entry）中记录着相应物理页面的基本信息，例如页面基址，以及该物理页面是否已经被分配等。
* Page Offset \
由于每页的大小是4kb, 因此线性地址中最低位的12位用来表示页内偏移，用来在目标页中定位最终的物理地址。
每个进程都需要构建自己的页表，两级页表可以极大地减少页表对内存的需求。假设页表的每条记录需要4字节的空间，如果只采用一级页表，那么完整构建一个4GB 空间的页表就需要4MB的内存，不管进程实际上会使用多少内存，页表都需要这么大的空间；而当采用二级页表之后，一级的页目录只需要4kb, 二级的页表总共有2^10个，每个也需要4kb内存，但二级页表可以按需分配，不需要一次性全部初始化，这就显著地降低了对内存的实际需求。
页目录的基地址存放在[控制寄存器cr3](https://en.wikipedia.org/wiki/Control_register)中，MMU对线性地址的翻译流程如下：
1. 通过寄存器cr3找到页目录的基地址，从线性地址中解析出 Page Directory Index, 并在页目录中找到对应的页表条目
2. 从页表条目中找到二级页表的基地址，从线性地址中解析出 Page Table Index, 并在二级页表中找到对应的页面条目
3. 从页面条目中找到物理页面的基地址，从线性地址中解析出 Page Offset, 相加得出最终的物理地址
总体流程的示意图如下：
这里的例子只讲解了二级页表的原理，但这种对页面的拆分方式可以嵌套任意层，不管是[PAE(Physical Address Extension](https://en.wikipedia.org/wiki/Physical_Address_Extension)) 还是64位系统都采用了多级页表，这里不再展开。同理，页面大小的改变也不会改变对页表构建的方式，只是用于各级页面的位数将会不同。
页表的层级越多，MMU在翻译线性地址时需要访问内存的次数就越多，这对于效率是不友好的。Segmentation Unit 在翻译逻辑地址时通过增加寄存器的方式解决了该问题，但页表条目实在太多了，寄存器不是一个好的解决方案。CPU的硬件缓存（L1, L2, L3）理论上会有帮助，但那是通用的缓存空间，不是专门为Paging Unit设计的，为了加速对虚拟地址的翻译，CPU引入了专门的缓存设备TLB(Translation Lookaside Buffers), TLB 用来缓存虚拟地址到物理地址的映射，这样只有第一次翻译虚拟地址时，Paging Unit才需要访问内存中的页表，后续对于相同的虚拟地址，都可以直接从TLB中获取。每个CPU都有自己的TLB, 从这一点也可以看出，将进程迁移到其它CPU将失去所有TLB 中的缓存，降低进程执行的效率。由于每个进程都有自己的独立页表，所以频繁的进程切换也会导致TLB上的缓存失效，造成性能损失。
了解了分页机制的原理之后，我们回到起点来思考一个问题：为什么需要分页？我们可以尝试着思考如下几个场景：
* 按需分配物理内存 \
与段相比，页的粒度更小，而且大小固定，这为OS单独对物理内存进行管理提供了基础。CPU在翻译虚拟地址时，虽然到最后都会落到一个具体的物理页面上，但我们不需要在程序一启动时就为其分配物理内存，或者为其预留物理内存，而是可以将对物理内存的分配推迟到使用时再分配。这样就对系统的物理内存与虚拟地址空间进行了解耦，程序中只需要规划如何使用虚拟地址，而对应的实际物理内存位于何处由操作系统负责。
* 按需加载数据 \
前面我们只讨论了CPU如何从内存中存取数据，但内存并不是一个持久化设备，内存中的数据需要从其它设备中读取进来，通常情况下是磁盘。采用何种策略从磁盘加载数据对程序的行为会产生重大影响。一个自然的思路是程序执行时先将整个程序的所有数据加载到内存，但这种方式非常低效，不仅会显著增加程序的启动时间，而且程序可能在本次执行过程中并不需要所有的数据，例如用户启动一个程序之后又立马将其关闭，那么该程序中任何交互性的功能代码都不会被使用到；另一个思路是完全不做预加载，仅仅将内存当成一个缓存来使用，每次访问数据时如果内存中还没有的话就从磁盘获取，但这又会导致过多的磁盘I/O, 也不是最高效的利用磁盘的方式。
内存页的设计使得OS能够以合适的粒度来完成内存与磁盘之间的数据交换，OS可以每次从磁盘读取一页数据，或者向磁盘写入一页数据，这种整块整块地对数据的读取才是高效利用磁盘的方式。
* 模拟更大的物理内存 \
当虚拟地址空间大于实际物理内存时，如果程序设计时使用了全部的虚拟地址空间，那么势必会有多个虚拟页面会被映射到相同的物理页面上（[鸽巢原理](https://en.wikipedia.org/wiki/Pigeonhole_principle)），如何解决这种冲突呢？此时我们需要借助于磁盘这种二级存储设备来模拟出更大的物理内存，具体做法是将冲突物理页面上的内容换出到磁盘，等实际使用时再换入内存，例如如果虚拟页面A与B都映射到了物理页面K上，那么当程序使用A 时，如果此时物理页面K里面不是A 的内容，那么就将K 的内容换出到磁盘上，将A的内容换入，当程序使用B时同理。换出换入叫着 Swap Out/In, 这里不做深入讲解。
从系统的总体架构上来看，分页（Paging）的最大作用是引入了一个抽象层（Abstraction Layer），从而将物理内存与程序使用的地址空间彻底解耦。内存分配、释放、规整等本身是个非常复杂的问题，这样系统对物理内存的管理就完全推给了操作系统，线性地址所提供的地址空间完全变成了一个抽象概念，或者说是抽象的接口。