本文将介绍操作系统对内存的虚拟化。

一、内存虚拟化的目标

• 透明：操作系统虚拟内存，应该让运行的程序不可见，程序应该认为自己拥有完整的、物理的内存空间
• 效率：操作系统应该用更少的时间、空间消耗实现虚拟化
• 保护：操作系统应该确保各个进程的内存空间不会相互影响

二、地址转换

1. 什么是地址转换？

地址转换，又被称为基于硬件的地址转换。

利用地址转换，硬件对每次内存访问进行处理，进程进行内存访问时指定 “它所认为的地址”，由操作系统将指令中的虚拟地址转换为物理地址。

2. 硬件支持

具体来说，每个 CPU 需要两个硬件寄存器：

• 基址寄存器：用于记录物理地址起始位置
• 界限寄存器：用于记录可用空间范围

对于每一个访问内存的指令，CPU 会通过基址寄存器将虚拟地址转换为物理地址，并通过界限寄存器避免进程访问额外的内存空间

3. 操作系统支持

操作系统应该做的事情有：

• 在进程创建时，为进程分配对应的内存空间

• 在进程终止时，回收内存

• 在进程切换时，操作系统必须保存和恢复两个硬件寄存器（基址寄存器、界限寄存器）

  每个 CPU 只有两个硬件寄存器，因此应该在进程切换时，将两个寄存器中记录的内容切换

• 提供异常处理程序，在程序视图越界访问内存时，进行异常处理

三、分段

1. 问题说明

当进程需要空间时，如果简单地将一整块空间直接完整划分给它使用，将可能出现以下问题：

• 内存空间可能有大量的闲置，导致物理资源的浪费
• 每次分配内存时，都需要一片完整的内存空间，分配所需较大

2. 分段的含义

将进程所需的内存空间按照逻辑划分为若干类型。

典型的三种类型：代码、栈、堆

每种类型在物理内存中均有着各自的一片内存空间。

每种类型均有一对硬件寄存器。

当需要为进程分配内存空间时，分别分配各个类型的内存空间。

四、空闲空间管理

1. 底层机制

(1) 空闲列表

操作系统会维护一个空闲列表，说明内存中的所有空闲空间。

(2) 分割

如果所需的空间小于 “空闲空间块” 的大小，则 “空闲空间块” 将被分割走一部分，变为更小的 “空闲空间块”。

(3) 合并

空间被归还时，如果该空间与 “空闲空间块” 相邻，则 “空闲空间块” 会与该空间合并，变成更大的 “空闲空间块”。

(4) 已分配空间大小的记录

程序在释放已分配空间时，通常不会手动指定空间大小，只用将空间对应的指针交给 free() 即可。

因此，操作系统需要自己记住已分配空间的大小。

操作系统通常会在分配空间的同时额外分配一个区域，该区域在被分配空间之前，被称为头块，其中存储着被分配空间的大小。

2. 基本策略

(1) 最优匹配

遍历整个空闲列表，找到所有大于等于请求大小的空闲块，返回其中最小的一个。

(2) 最差匹配

找到最大的空闲块，将其分割，一部分满足请求，一部分继续作为空闲块。

(3) 首次匹配

找到一块足够大的空闲块，将其分割，一部分满足请求，一部分继续作为空闲块。

(4) 下次匹配

不同于首次匹配每次都从空闲列表头开始查找，下次匹配会额外维护一个指针，该指针指向上一次查找结束的位置，下次便可以从指针处开始查找。

通过这种方式，避免了每次都从空闲列表的头部开始查找。

3. 其它策略

(1) 分离空闲列表

增加一个独立的列表，用于管理几种固定大小的、经常被申请的内存空间。将固定大小的、频繁的请求都交由分离空闲列表处理，其它大小的请求再由更通用的内存分配程序处理。

(2) 伙伴系统

该方法用于简化合并操作。

将内存空间递归地二分，当块被释放时，只需要递归地检查并合并块的伙伴（二叉树兄弟结点），就可以将空闲内存空间合并。

五、分页

1. 什么是分页？

为了便于空间管理，将内存空间划分为若干物理块，同时将进程所需空间划分为若干页，块与页的大小相同，可以将进程的任一页放置在任一物理块中。

为了记录每个进程的各个页放置到哪个块中，操作系统通常会为每个进程设置一个页表，用于保存页的映射信息。

为了使进程能够访问到实际的地址，操作系统会在进程访问内存时做地址转换。

2. 页表的性能问题

如果引入分页机制，可能会带来较高的性能开销。

首先，要将内存划分为若干个块；其次，需要通过页表记录这些块的映射信息；最后，每次进行内存访问时，都需要额外访问页表（以进行地址转换）。

3. 页表的性能问题解决方案 - TLB

(1) 什么是 TLB？

TLB，translation-lookaside buffer，地址转接旁路缓冲存储器，又名地址转换缓存。TLB 是一个硬件，它是对地址映射关系的缓存。

(2) TLB 如何工作？

对每次内存访问，硬件会先检查 TLB 中是否有期望的地址映射关系，如果有，快速取出，否则，访问页表，取出信息并更新 TLB。

(3) 进程切换时的 TLB 处理

每个进程都有各自的一个页表，用于存储该进程的地址映射关系，因此，在进程切换时，TLB 也应该做相应的处理。

常见的两种处理方法是：

• 在进程切换时，清空 TLB
• 为 TLB 增加一个进程标识符，使其能够区分不同进程的地址映射关系

(4) TLB 的数据淘汰

与其它缓存相同，TLB 也存在空间大小限制，并且常会使用 LRU 策略进行数据淘汰。

4. 页表的存储问题

页表可以非常大，因为一个进程可以需要很大的空间，这些空间将被划分为 “巨量” 的页，这些映射关系都需要保存在页表中，将会导致页表的空间占用也十分大。

5. 页表的存储问题解决方案

(1) 更大的页

将页划分得更大，映射关系就可以变少，从而页表便可以缩小。

这一方法存在一个致命问题：更大的页会导致更多的内存浪费。

(2) 分段 + 分页

不再只会进程提供一个页表，而是为每个逻辑段分别提供一个页表。这种方式可以更好地节约内存，避免分配空间的闲置。

这一方法存在的问题是：分段要求程序对内存的使用也符合规范，这是不现实的。

(3) 多级页表

不再以一个占用一块完整空间的数组存储映射关系，而是采用类似 “索引” 的方式，维护一个树形结构，从而可以将映射关系离散、分别存储在内存的各个地方。

(4) 反向页表

反向页表是对空间的极致节省。

页表不再是每个进程一个，而是所有进程共用一个，其中的项表明哪个进程在使用这个物理页、哪个虚拟页映射到这个物理页。

(5) 交换至磁盘

允许系统在内存压力较大时，将页表中的一部分交换到磁盘。

六、模拟出更大空间

1. 为什么要模拟出更大空间？

考虑这样一个情况，同时有多个用到大量内存的进程在运行，以至于将所有 “虚拟内存” 都放入 “物理内存” 中已经不可行了，此时便需要引入额外的机制来模拟一个更大的内存空间，营造出都放在内存中的假象。

2. 交换空间

交换空间，swap space，是操作系统在磁盘中开辟的专门用于与内存做交换的空间。操作系统会将页交换到其中，又在需要的时候交换出去。

3. 存在位和页错误

操作系统会在页表项中增设一个存在位，用于表示该页是否存在于内存之中。

当进行内存访问时，如果发现页表存在位为 false，则视为发生了页错误，应该从硬盘中交换页。

页错误并不是错误，可以理解为页未命中

4. 合适进行交换？

操作系统通常不会等到内存已满后才执行交换，而是更倾向于主动预留一部分空闲内存。

绝大多数操作系统会这样做：

设置高水位和低水位；当可用内存小于低水位时，交换程序开始运行，直至可用内存大于高水位。

5. 将什么页交换出内存？

(1) FIFO

先进先出，以队列形式管理内存中的页，并在需要淘汰页时淘汰最先进入队列的页。

(2) 随机

在需要淘汰页时，随机选择一个页，淘汰。

(3) LRU

按照最近最少使用原则，将最近最不常用的页淘汰。

(4) 近似 LRU

操作系统通常会采用这个方法，不再要求完美的 LRU，而是淘汰相对近的相对不常用的页。

参考

• 操作系统导论