操作系统 | 内存管理之虚拟内存管理【思维导图版】

下面是程序锅在寒假期间根据《现代操作系统原理和实现》做的一个思维导图，完整、详细、清晰的文字版本后头会出，因为自己也想出整一套出来。

以下内容是由 XMind 根据上述思维导图的内容自动转换而来。

虚拟内存

Motivation

1.多个应用程序并发执行时，假如采用如下方式：运行 A 就允许 A 访问所有的物理内存资源；当切换到另一个应用程序 B 的时候，就将 A 的所有内存数据保存到存储设备中，将 B 的数据从存储设备加载到内存中。这种方式的弊端就是读写存储设备的速度太慢了。
2.假如采用如下方式：让每个应用程序使用物理内存的一部分，数据会一直驻留在内存中。虽然不用从存储设备中存储了，但是存在无法保证不同应用程序所使用的物理内存间的隔离型，而是无法保证应用程序可用的地址空间是连续被统一的，增加了程序编写及编译的复杂性

基本思想

在应用程序与物理内存之间加入一个新的抽象-虚拟内存

作用

1.应用程序是面向虚拟内存编写
2.应用程序运行时只能使用虚拟地址，CPU 负责将虚拟地址转换为物理地址，内核负责设置虚拟地址与物理地址之间的映射

优点

1.内核仅仅将应用程序实际使用的虚拟地址映射到物理地址，从而提高内存的利用率
2.由于映射，每个应用程序只能看到自己的虚拟地址空间所映射的物理内存，从而保证了不同应用程序之间的隔离性
3.每个应用程序的虚拟地址空间是统一的、连续的，降低了编程的复杂度

虚拟内存的设计目标

1.高效性：虚拟内存抽象不能在应用程序运行过程中造成明显的性能开销；虚拟内存抽象不应该占用过多的物理内存资源
2.安全性：虚拟内存抽象需要使不同应用程序的内存互相隔离，即一个应用程序只能访问自己的物理内存区域
3.透明性：虚拟内存抽象需要考虑对应用程序的透明性，使得应用程序开发者在编程时无须考虑虚拟内存抽象

虚拟内存功能

共享内存
- 允许同一物理页在不同的进程间共享，从而实现不同进程间的相互通信、传递数据。

基于共享内存，又衍生出了写时拷贝、内存去重。

写时拷贝
- 允许两个进程之间以只读的方式（页表项除了存储物理地址之外，还会存相关的权限位，只读的话那么其实就是清除可写位）共享同一段物理内存。一旦某个进程对该内存区域进行修改，就会触发缺页异常，内核会在物理内存中将缺页异常对应的物理页重新拷贝一份，并且新拷贝的物理页以可读可写的方式重新映射给触发异常的应用程序，然后再恢复应用程序的执行。

这里的缺页异常是由违反权限导致的，但是这里的缺页异常也还是会调用缺页异常处理函数。然后在函数中，内核会发现此次缺页异常是因为写了只读内存导致的，而且该内存区域又是被内核标记位了写时拷贝，因此内核采取的方式是拷贝一份物理页。
- 实例

	- 不同进程间以写时拷贝的方式映射相同的动态连接库
	- fork 的时候会先以写时拷贝的方式共享全部内存数据

内存去重
- 内核会定期地在内存中扫描具有相同内容的物理页，并找到映射到这些物理页的虚拟页，然后只保存一个物理页，并将虚拟页以写时拷贝的方式映射到这个物理页，然后释放其他物理页。
- 优缺点
  - 会对进程访存时延造成影响：因为访问一个被去重的虚拟页时会触发缺页异常，导致内存拷贝，进而影响性能
- 实例
  - Linux 的 KSM（Kernel Same-page Merging）
内存压缩
- 内存资源不足时，内核选择“最近不太会使用”的内存页，压缩其中的数据。当进程访问被压缩的数据时，内核会将其解压。
- 优缺点
  - 相比换入换出，可以迅速地腾出空闲内存空间，又能够很快地恢复被压缩的数据。
- 实例
  - Linux 的 zswap 机制

zswap 机制在内存中为换页过程提供了缓冲区，称为 zswap 区域。内核会将准备换出的内存数据进行压缩，然后将压缩后的内容写入 zswap 区域（实际还是内存）。之后，zswap 中的数据会被批量换出到磁盘。当被换出到 zswap 区域或者磁盘上的数据再次被访问时，该机制会将压缩的换入和解压。

这种方式的好处的就是让写到磁盘设备的操作被延迟地完成，从而进行更加高效的磁盘批量 IO，甚至避免磁盘 IO。即使触发了磁盘操作，但是写/读的数据量会明显减小（压缩了）。

大页（huge page）
- Motivation
  - 地址在翻译的时候每个内存页都需要占用一个 TLB 缓存项，因此 CPU 有限的 TLB 缓存项显得弥足珍贵。在内存页大小为 4KB 的情况下，随着，对内存的需求变大，CPU 中有限的 TLB 缓存项很难保证高 TLB 命中率。
- 基本思想
  - 大页的大小可以是 2MB 甚至是 1GB，使用大页可以大幅度减少 TLB 的占用量。
- 优缺点
  - 减少 TLB 缓存项的使用，从而提高 TLB 的命中率。
  - 减少页表的级数，提升页表查询的效率。
  - 假如整个大页使用不多，则会造成物理内存资源浪费
  - 增加内核管理内存的复杂度，导致相关的漏洞
- 实例
  - AArch64 中，L2 页表项中存在一个特殊的位（第一位），它标志着这个页表项中存储的物理地址是指向 L3 页表页还是指向一个大小为 2MB 的大页（该位为 0）；同样，L1 页表项的第 1 位是 0，则表示该物理地址直接指向一个大小为 1GB 的大页。可以利用硬件提供的大页支持，在虚拟内存中直接以 2MB 或者 1GB 进行地址映射。

AArch64 中还可以通过 TCR_EL1 寄存器设置最小页大小，如 4KB、16KB、64KB。当最小页为 16KB、64KB 的时候，L2 页表项指向的大页为 32MB、512MB（在 ARMv8.0 上，最小页为 16KB、64 KB 时，只有 L2 页表项支持大页功能）。
- Linux 提供了透明大页机制，能够自动将一个进程中连续 4KB 内存页合并为 2MB 的内存页。

缺页异常与换页

换页机制
- 当物理内存不够的时候，操作系统应该可以把若干物理页的内容写到类似磁盘中，然后这些物理页就可以被回收继续使用了。
- 换入/换出
预取机制
- 由于换页过程中会涉及耗时的磁盘操作，所以操作系统往往会引入预取机制进行优化。

基本想法就是：在发生换入操作时，预测哪些页即将被访问，那么将这些页一并换入物理内存，从而减少缺页异常的次数。

缺页异常
- 当应用程序访问已分配但未映射到物理内存的虚拟页时，就会触发缺页异常。此时 CPU 会运行缺页异常处理函数（page fault handler），该函数会找到一个空闲物理页（可能也会通过换页的方式），将磁盘上的数据加载到物理页中。

其实访问未分配的虚拟页时也会触发异常，那么内核是判断这个虚拟页在不在虚拟地址空间对应的 VMA（虚拟内存区域）中来区分是未分配还是已分配但未映射的。如果在 VMA 中，那么则是后者，否则是前者。
- 实例

	- x86-64 体系结构上，缺页异常会触发 13 号异常，并且访问出错的虚拟地址会存放在 CR2 寄存器中。
	- AArch64 中缺页异常是与其他一些用户态同步异常共用一个异常号（8号同步异常），内核会根据 ESR（Error Syndrome Register）寄存器中存储的信息来判断发生的异常是否为缺页异常，如果是则从 FAR_EL1 寄存器中取出发生异常的虚拟地址。

页替换策略
- 目标
  - 猜测哪些页应该被换出，从而最小化缺页异常带来的性能损害。
- MIN 策略/OPT策略
  - 选择未来不会被访问的页，或者在最长时间内不会再访问的页。

该策略是理论最优，实际场景中很难实现。往往作为一个标准，衡量其他页替换策略的优劣。

- FIFO策略

	- 优先选择最先换入的页进行换出
	- 优缺点

		- 直观且开销低，但是在实际使用中表现不佳

- Second Chance 策略

	- FIFO 策略的一种改进版本，由于考虑了页的访问信息，所以一般情况下会由于 FIFO。

同样维护一个先进先出的队列，用于记录换入物理内存的物理页号，但是还要给物理页号维护一个访问标志位。假如要访问的页号在队列中了，就将其访问标志位置上。当选择要换出的内存页时，会先查看队头的页号，如果没有被置上那就直接换出；假如被置上了，那就取消标志位，然后将其挪到队尾。

- LRU 策略

	- 选择最久未被访问的页换出，基于的出发点是：过去频繁访问的页很有可能在后续也会被频繁访问。

- MRU 策略

	- 选择最近访问的内存页换出，基于的假设是：程序不会反复地访问相同的地址。

- 时钟算法策略

	- 与 Second Chance 策略类似，就是换入的物理内存页号排成一个时钟形状，该时钟有一个针臂，指向换入内存的页号的后一个。同时，也会给每一个页号一个标志位。每次需要换出页号时，该算法就从针臂所指的页号开始检查，如果当前页号的标志位没有置上，则将该页换出；如果已经被置上了，那么就将标志位清空，并且针臂顺时针移到下一个页号，如此重复，直到找到一个访问位没有被置上的页号。
	- 优缺点

		- 相比 Second Chance 省略了队头移到队尾的操作，时钟算法会更加高效一点

- 工作集模型

	- Motivation：避免颠簸现象的发生（颠簸现象是指选择的替换策略与实际的工作负载不同，结果导致页被换出又被换入）
	- 基本思想

		- 优先将非工作集中的页换出

	- 基本策略

		- 一个应用程序在时刻 t 的工作集 W 为它在时间区间 [t-x,t] 使用的内存页集合，也被视为它在未来（下一段 x 时间内）会访问的内存集合。
		- 跟踪工作集的常用方法是工作集时钟算法：操作系统设置一个定时器，每经过固定的时间间隔，一个设置好的工作集跟踪函数就会被调用。

首先，每个内存页都有两个状态：上次使用时间和访问位，都是被初始化为 0。
CPU 硬件会在程序访问某个页的时候自动将对应的访问位设置为 1。
当函数被调用时，会检查内存页的状态，如果访问位是 1，也就说此次时间间隔内该页被访问过了，函数就会把当前系统时间赋值给该内存页的上次使用时间。如果访问位为 0，函数会计算该页的年龄（即当前系统时间-该页的上次使用时间）超过预设的时间 x，则它不在属于该工作集。检查完之后，会将访问位重新设置为 0。