分段与分页

## 1 分段

### 1.1 原理

1. 在分段机制下，操作系统**以段**（一段连续的物理内存）**的形式管理/分配物理内存**。
2. **应用程序的虚拟地址空间由若干个不同大小的段组成**，比如代码段、数据段等，**当CPU访问虚拟地址空间中某一个段的时候**，**MMU会通过查询段表得到该段对应的物理内存区域**。
3. 具体来说，虚拟地址由两部分构成：
   1. 第一个部分表示**段号**，**标识着该虚拟地址属于整个虚拟地址空间中的哪一个段**。
   2. 第二个部分表示**段内地址**（段内偏移），**即相对于该段起始地址的偏移量**。
4. **段表存储着一个虚拟地址空间中每一个分段的信息**，其中包括**段起始地址**（对应于物理内存中段的起始物理地址）和**段长**。
5. 在**翻译虚拟地址**的过程中，MMU首先**通过段表基址寄存器找到段表的位置**，**结合待翻译虚拟地址中的段号**，**可以在段表中定位到对应段的信息**（步骤一），然后**取出该段的起始地址**（物理地址），**加上待翻译虚拟地址中的段内地址**（偏移量），**就能够得到最终的物理地址**（步骤二），段表中还存有段长信息，用于检查虚拟地址是否超出合法范围。
   ![](https://notebook.ricear.com/media/202206/2022-06-30_214045_626206.png)

### 1.2 存在的问题

1. 在分段机制下，不仅虚拟内存空间被划分成不同的段，**物理内存也以段为单位进行分配**。
2. **在虚拟地址空间中**，**相邻的段所对应的物理内存中的段可以不相邻**，因此，操作系统能够实现**物理内存资源的离散分配**，但是，这种段式分配方式**容易导致在物理内源上出现外部碎片**，即**在段与段之间留下碎片**（不足以映射给虚拟地址空间中的段），从而造成**物理内存资源利用率的降低**。

> - 如果一共有6GB的物理内存，目前被划分成4段进行分配，第一段为0 ~ 2GB，第二段为2 ~ 3GB，第三段为3 ~ 5GB，第四段为5 ~ 6GB。
   > - 如果第二段和第四段被释放，然后又需要分配一个2GB的段，虽然此时空闲的物理内存总量为2GB，但因为这2GB内存不连续，因此分配还是会失败。
   >

> Intel公司在8086处理器上开始引入分段机制，然后在80286处理器上使用分段机制来支持虚拟内存，在后期的处理器上尤其在x86_64架构之后，基于分页机制的虚拟内存已成为主流（不过出于向前兼容的考虑，硬件仍然支持分段机制）。
   >

## 2 分页

### 2.1 原理

1. 分页机制的基本思想是**将应用程序的虚拟地址空间划分成连续的**、**等长的虚拟页**（显著区别于分段机制下不同长度的段），同时**物理内存也被划分成连续的**、**等长的物理页**。
2. **虚拟页和物理页的页长固定且相等**，**从而使得操作系统能够很方便地为每个应用程序构造页表**，**即虚拟页到物理页的映射关系表**。
3. 逻辑上，该机制下的虚拟地址也由两个部分组成：
   1. 第一部分标识着**虚拟地址的虚拟页号**。
   2. 第二部分标识着**虚拟地址的页内偏移量**。
4. 在具体的地址翻译过程中，MMU首先**解析得到虚拟地址中的虚拟页号**，并**通过虚拟页号去该应用程序的页表**（页表起始地址存放在**页表基地址寄存器**中）**中找到对应条目**，然后**取出条目中存储的物理页号**，最后**用该物理页号对应的物理页起始地址加上虚拟地址中的页内偏移量得到最终的物理地址**。
   ![](https://notebook.ricear.com/media/202206/2022-06-30_221529_777622.png)

### 2.2 优点

1. 在分页机制下，**应用程序虚拟地址空间中的任意虚拟页可以被映射到物理内存中的任意物理页上**，因此操作系统**也能实现物理内存资源的离散分配**。
2. **分页机制按照固定页大小分配物理内存**，**使得物理内存资源易于管理**，**可有效避免分段机制中外部碎片的问题**。

### 2.3 多级页表

#### 2.3.1 为什么需要多级页表

1. 前面我们提到页表是分页机制中的关键部分，负责记录虚拟页到物理页的映射关系，操作系统负责对页表进行配置，如果使用一张简单的单级页表来记录映射关系，那么对于64位的虚拟地址空间，假设页的大小为4KB，页表中的每一项大小为8字节（主要用于存储物理地址），那么一张页表的大小就是$\frac{2^{64}}{4KB} \times 8字节$，即33554432GB。
2. 为**压缩页表大小**操作系统引入了**多级结构的页表**，用来满足虚拟内存在**空间高效性**方面的要求，和简单的单级页表类似，使用多级页表（假设有$k$级）的时候，一个虚拟地址中依然包括**虚拟页号**和**页内偏移量**，其中**虚拟页号将被进一步地划分成**$k$**个部分**（$虚拟页号_0、虚拟页号_1、...、虚拟页号_i，0 \le i \lt k$），$虚拟页号_t$**对应于该虚拟地址在第**$i$**级页表中的索引**。
3. **当任意一级页表中的某一个条目为空时**，**该条目对应的下一级页表不需要存在**，以此类推，**接下来的页表同样不需要存在**，因此，多级页表的设计**极大地减少了页表占用的空间大小**，换句话说，**多级页表允许在整个页表结构中出现空洞**，而**单级页表则需要每一项都实际存在**，因为在实际应用中，**应用程序的虚拟地址空间中的绝大部分是处于未分配状态的**，所以**多级页表可以部分创建**，从而能够**极大地节约所占空间**。
   > 为什么单级页表中的每一项都需要存在？
   >
   > 1. **单级页表可以看成以虚拟地址的虚拟页号作为索引的数组**，**整个数组的起始地址**（物理地址）**存储在页表基地址寄存器中**，**翻译某个虚拟地址即根据其虚拟页号找到对应的数组项**，**因此整个页表必须在物理内存中连续**，**其中没有被用到的数组项也需要预留着**（也就是说不能出现空洞）。
   >

#### 2.3.2 具体实例

1. 下面将结合AArch64体系结构下的多级页表的具体实现来进行阐述，该体系下的虚拟地址有64位，其中**低48位参与地址翻译**，**页表级数为4级**，**虚拟页大小为4KB**。
2. 在以上设置下，物理内存被划分为连续的、4KB大小的物理页，一个虚拟地址可以映射对应一个物理页，正因为页的大小是4KB，所以虚拟地址的**低12位**（$2^{12} = 4KB$）**对应于页内偏移量**。
3. 整个页表的起始地址（物理地址）存储在一个特殊的寄存器中，对于包括Linux在内的主流操作系统上的用户地址空间来说，这个**页表基地址寄存器是TTBR0_EL1**。
4. **第0级**（页表）**有且仅有一个页表页**，**页表基地址寄存器存储的就是该页的物理地址**，**其余每一级页表拥有若干个离散的页表页**，**每一个页表页也占用物理内存中的一个物理页**（4KB）。
5. **每个页表项占用8个字节**，**用于存储物理地址和相应的访问权限**，故一个页表页包含512个页表项（$\frac{4KB}{8} = 512$），由于512项对应于9位（$2^9 = 512$），因此**虚拟地址中对应于每一级页表的索引都是9位**。
6. 具体来说，一个64位的虚拟地址在逻辑上被划分成如下几个部分：
   1. 第63至48位：全为0或者全为1（硬件要求），通常操作系统的额选择是，应用程序使用的虚拟地址的这些位都是0，同时也意味着应用程序的虚拟地址空间大小可以达到$2^{48}$个字节。
   2. 第47至39位：这9位作为该虚拟地址在第0级页表中的索引值，对应于下图中的$虚拟页号_0$。
   3. 第38位至30位：这9位作为该虚拟地址在第1级页表中的索引值，对应于下图中的$虚拟页号_1$。
   4. 第29位至21位：这9位作为该虚拟地址在第2级页表中的索引值，对应于下图中的$虚拟页号_2$。
   5. 第20位至12位：这9位作为该虚拟地址在第3级页表中的索引值，对应于下图中的$虚拟页号_3$。
   6. 第11至0位：由于页的大小是4KB，所以低12位代表页内偏移量。
      ![](https://notebook.ricear.com/media/202207/2022-07-01_215356_575096.png)
7. 当MMU翻译一个虚拟地址的时候：
   1. **首先根据页表基地址寄存器中的物理地址找到第0级页表**。
   2. **然后将虚拟地址的虚拟页号0作为页表项索引**，**读取第0级页表页中的相应页表项**，**该页表项中存储着下一级**（第1级）**页表页的物理地址**，**MMU按照类似的方式将虚拟地址的**$虚拟页号_1$**作为页表项索引**，**继续读取第1级页表页中的相应页表项**。
   3. **往下类推**，**MMU将在一个第3级页表页中的页表项里面找到该虚拟地址对应的物理页号**，**再结合虚拟地址中的页内偏移量即可获得最终的物理地址**。
8. 这样的4级页表结构**允许页表内存在空洞**，操作系统可以**在虚拟地址被应用程序使用之后再分配并填写**，在这里我们举一个极端的例子来说明多级页表在内存占用方面的优势：
   1. 假设整个应用程序的虚拟地址空间中只有两个虚拟页被使用，分别对应于最低和最高的两个虚拟地址。
   2. 在使用4级页表后，整个页表实际上只需要1个0级页表页、2个1级页表页、2个2级页表页、2个3级页表页，合计7个页表页（即整个页表中大部分都是空洞），仅仅占用28KB的物理内存空间，远小于单级页表的大小。

#### 2.3.3 存在的问题

1. 多级页表结构虽然能够**显著地压缩页表大小**，但是**会导致地址翻译时长的增加**（时间换空间的权衡），具体来说，多级页表结构使得MMU在翻译虚拟地址的过程中需要**依次查找多个页表页中的页表项**，**一次地址翻译可能会导致多次物理内存访问**。

### 2.4 TLB

#### 2.4.1 原理

![](https://notebook.ricear.com/media/202207/2022-07-03_164649_006526.png)

1. 为了**减少地址翻译的访存次数**，MMU引入了**转址旁路缓存**（Translation Lookaside Buffer, TLB）部件来**加速地址翻译的过程**。
2. TLB**缓存了虚拟页号到物理页号的映射关系**：
   1. 我们可以把TLB简化成**存储着键值对的哈希表**，其中**键是虚拟页号**，**值是物理页号**。
   2. MMU会先**把虚拟页号作为键去查询TLB中的缓存项**，**若找到则可直接获得对应的物理页号而无须再查询页表**。
   3. 我们称**通过TLB能够直接完成地址翻译的过程为TLB命中**（TLB hit），反之，为**TLB未命中**（TLB miss）。
3. 一般来说，TLB硬件采用**分层的架构**（类似于CPU缓存），分为**L1**和**L2**两层，其中**L1又分为数据TLB和指令TLB**，分别用于**缓存数据和指令的地址翻译**；**L2不区分数据和指令**（也存在分离的设计）。
4. 作为CPU内部的硬件部件，TLB的**体积**实际上是**极小**的，这也就意味着其**缓存项的数量是极其有限的**，例如，在树莓派4使用的AArch64 Cortex-A72 CPU中，每个CPU核心只有约一千条TLB缓存项。
5. 由于TLB缓存项的数量有限，需要有效地加以利用，才能保证尽量高的TLB命中率，在主流的AArch64和x86_64体系架构下，**TLB在地址翻译过程中是由硬件**（MMU）**进行管理的**：
   1. **硬件规定了页表基地址的位置以及页表的内部结构**，**操作系统只需按照硬件的规范来构造和配置页表**。
   2. **当TLB未命中时**，**硬件将通过页表基地址查询页表**，**找到对应的页表项**，**并且将翻译结果填写到TLB中**；**若TLB已满**，**则根据硬件预定的策略替换掉某一项**；**之后若需再次翻译同样的虚拟页号**，**硬件就可以迅速地从TLB中直接找到对应的物理页号**（TLB命中）。

> 为什么硬件仅仅采用简单的TLB管理方式，就能够在大多数情况下获得较高的TLB命中率？
>
> - 因为[局部性](https://notebook.ricear.com/project-26/doc-345)起了重要作用，具体来说，**应用程序在运行过程中访问内存的模式具有时间局部性和空间局部性**，前者指的是**被访问过一次的内存位置在未来通常会被多次访问**，后者指的是**如果一个内存位置被访问**，**那么其附近的内存位置通常在未来也会被访问**。
> - **TLB中的一条缓存项对应着一个内存页**，**由于内存访问的时空局部性**，**TLB缓存项在将来很可能会被多次查询**，**即发生TLB命中的可能性较大**。

#### 2.4.2 刷新

1. TLB的引入带来了一个新的挑战，即**如何保证TLB中内容与当前页表内容的一致性**：
   1. 例如两个应用程序$A$和$B$使用了同样的虚拟地址$VA$，但是对应于不同的物理地址$PA_1$和$PA_2$。
   2. 在应用程序$A$访问$VA$时，TLB会缓存$VA$到$PA_1$的翻译，在切换到应用程序$B$运行后，尽管操作系统更新了CPU使用的页表基地址，但是当$B$访问$VA$时，CPU如果依然从TLB中寻找$VA$的翻译，则会导致应用程序$B$的$VA$也被翻译成$PA_1$，进而产生访存的错误。
   3. 这个问题产生的根本原因在于**页表已经发生了变化**，而**TLB却没有做相应的更新**，由于**TLB是使用虚拟地址进行查询的**，所以**操作系统在进行页表切换**（应用程序切换）**的时候需要主动刷新TLB**。
2. **若操作系统在切换应用程序的过程中刷新TLB**，**那么应用程序开始执行**（被切换到）**的时候总是会发生TLB未命中的情况**，**进而不可避免地造成性能损失**，**可以使用一种为TLB缓存项打上标签的方式来避免应用程序切换过程中TLB刷新的开销**：
   1. 以AArch64体系结构为例，他提供了**ASID**（Address Space IDentifier）功能（x86_64上对应的功能称为PCID，Process Context IDentifier）。
   2. 具体来说，操作系统可以**为不同的应用程序分配不同的ASID作为应用程序的身份标签**，再**将这个标签写入应用程序的页表基地址寄存器中的空闲位**（如TTBR0_EL1的高16位）。
   3. 同时，**TLB中的缓存项也会包含ASID这个标签**，从而**使得TLB中属于不同应用程序的缓存项可以被区分开**，因此，**在切换页表的过程中**，**操作系统不再需要清空TLB中的缓存项**。
3. 不过，在修改页表内容之后，操作系统还是**需要主动刷新TLB以保证TLB缓存和页表项内容一致**，在AArch64体系结构中提供了多种不同粒度的刷新TLB的指令，包括**刷新全部TLB**、**刷新指定ASID的TLB**、**刷新指定虚拟地址的TLB**等，操作系统**可以根据不同场景选用合适的指令**，**最小化TLB刷新的开销**，**以获得更好的性能**。

## 参考文献

1. 《现代操作系统：原理与实现》