1. 虚拟内存介绍

我们知道系统中的所有进程都是共享CPU和主存资源，但这样就会存在一个问题，这么多进程怎么知道主存上的一块内存是已分配给了其它进程还是空闲状态。所有我们需要一种机制来专门负责操作系统上内存资源的管理，而虚拟内存就充当这样一个角色。

虚拟内存是操作系统提供的一种内存管理技术，是对主存的一种抽象。由硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。

虚拟内存提供了三个重要的能力：

1. 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。
2. 它为每个进程提供了一致的地址空间（如每个进程的地址空间都是[0, 4G]），从而简化内存管理。
3. 它保护了每个进程的地址空间不被其他进程破坏：1）每个进程只能使用它已分配的内存，否则会出现“段错误”；2）页表为每块虚拟内存指定了访问权限，如果权限不对会出现“保护错误”；3）CPU引用不在主存上的虚拟页会触发缺页中断，中断处理程序会把主存中牺牲也换出到磁盘中。

2. 虚拟寻址

CPU 直接访问内存的方式就是使用物理地址，我们把这种方式称为物理寻址 (physical addressing)，然而，现代处理器使用的是一种称为虚拟寻址 (virtual addressing) 的寻址形式，使用虚拟寻址， CPU 通过生成一个虚拟地址 (Virtual Address, VA) 来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址 个虚拟地址转换为物理地址的任务叫做地址翻译 (address translation) 。地址翻译需要 CPU 硬件和操作系统之间的紧密合作。 CPU 芯片上叫做内存管理单元 (Memory Management Unit,MMU) 的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

3. 虚拟地址空间

虚拟地址和物理地址是一样，是一个非负整数的地址空间集合{0, 1, 2, …, N - 1}，这个地址空间集合就是虚拟地址空间(virtual address space)。一个地址空间的大小是由表示最大地址所需要的位数来描述的。例如，一个包含 N =$2^n$个地址的虚拟地址空间就叫做一个n位地址空间，由此可知一个32位的系统最多支持 $2^{32}$= 4GB大小地址。

虚拟页：

同时我们要知道**虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。**每字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存在主存中。

操作系统把虚拟内存划分成一个个大小固定的虚拟页(Virtual Page, VP)，类似地，物理内存被分割大小固定且相等的物理页 (Physical Page, PP) 也被称为页帧 或页框(page fram )。页面大小可以使用sysconf(_SC_PAGESIZE)查看。

对于虚拟机往往会有下面三种状态：

• 未分配：系统还未分配（或者创建）的页。未分配的块没占用任何数据和它们相关联，因此也就不占用任何磁盘空间。
• 已缓存：当前已缓存在物理内存（主存）中的已分配页。
• 未缓存：未缓存在物理内存中的已分配虚拟页。

如下图，虚拟页0，3还没有被分配，因此在磁盘上还不存在。虚拟页1，4和6 被缓存在物理内存中。页2、5和7已经被分配了，但是当前并未缓存在主存中。

3. 页表

页表就是一个**页表条目 **(Page Table Entry,PTE) 的数组，用来记录虚拟地址和物理地址之间的映射关系。每次将虚拟地址时转换为物理地址时都会读取页表。页表的内容由操作系统负责维护。

虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个页表条目（PTE），每个PTE都记录一个有效位（表示该页是否缓存在主存中）、虚拟页在物理页中的起始地址和页表的访问权限（READ、WRITE、SUP）等等信息。

4. 地址翻译

上面介绍的都是地址翻译的基础知识，下面介绍系统是如何实现虚拟地址到物理地址之间转换的。

前面我们介绍了虚拟页面分为三种状态：未分配、已缓存和未缓存，其中如果CPU引用到了未缓存的虚拟页，而该页在主存中并未分配，这种情况我们称为缓存不命中（不命中的虚拟页会有缺页中断处理程序帮忙处理，处理完后的虚拟页会变成已缓存状态），相反如果虚拟页存在缓存中也就是已缓存的虚拟，CPU访问时我们可以说缓存命中。而对于命中和不命中地址翻译流程如下：

缓存命中：

注：VA ：虚拟地址， PTEA: 页表条目地址，PTE: 页表条目，PA: 物理地址

• 第一步：处理器生成一个虚拟地址，并把它传送给 MMU。
• 第二步：MMU 生成 PTE 地址，并从高速缓存/主存请求得到它。
• 第三步：高速缓存/主存向 MMU 返回 PTE。
• 第四步：MMU 构造物理地址， 并把它传送给高速缓存/主存。
• 第五步：高速缓存/主存返回所请求的数据字给处理器。

缓存不命中：

• 第一步到第三步：和缓存命中流程的第一步到第三步相同。
• 第四步：PTE 中的有效位是零，主存中未存储虚拟页，这时MMU 会触发了一次缺页异常，传递 CPU中的控制到操作系统内核中的缺页异常处理程序。
• 第五步：缺页处理程序会先确定出物理内存中的牺牲页，如果这个页面内容和磁盘内容一致（说明页面内容不是脏数据），则把它换出到缺页对应磁盘位置。
• 第六步：缺页处理程序页面调入新的页面，并更新内存中的 PTE。
• 第七步：缺页处理程序返回到原来的进程，再次执行导致缺页的指令。 CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，在 MMU 执行了图中剩余步骤之后，主存就会将所请求字返回给处理器。

5. TLB加速地址翻译

在MMU中包含了一个PTE的小的缓存，称为**翻译后备缓冲器 **(Tranlation Lookaside Buffer, TLB)，TLB是一个小的虚拟寻址缓存保存着PTE，当地址翻译时如果TLB命中则可以直接获取到物理内存地址，如果不命中则需要多执行一步去访问高速缓存/主存中的PTE，从中获取到物理地址。因为MMU位于芯片上，所以如果TLB命中的话会大大加快地址翻译速度。

以下是TLB命中时地址翻译过程：

• 第1步：CPU 产生一个虚拟地址。
• 第2步和第3步： MMU从TLB 中取出相应的 PTE。
• 第4步： MMU 将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。
• 第5步：高速缓存/主存将所请求的数据字返回给 CPU。

当TLB 不命中时，MMU 必须从高速缓存/主存中取出相应的 PTE。新取出的 PTE 存放在 TLB 中，可能会覆盖—个已经存在的条目。

6. 多级页表

前面提到的都是一个单独的页表来进行地址翻译，对于这样的页表在一个32位的地址空间，4KB的页面和一个4字节的PTE，即使引用程序只引用了很小部分的虚拟内存，但是任然需要一个4MB （ 4 *$2^{32}$/ 4KB）页表驻留在内存中。对于64位的系统来说将变得更加复杂。

所以采用了多级页表的形式，比如，一级页表的每个PTE负责映射虚拟地址空间中一个 4MB 的片（chunk），每个片又都由1024个连续的页面组成；二级页表中的每个PTE负责映射一个4KB 的虚拟内存页面。

这么做的有两个好处：

1）如果一级页表中的 PTE 是空的，那么二级页表就不会存在，这样可以节约大部分内存。

2）只有一级页表才要总是在主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表；这就减少了主存的压力；只有最经常使用的二级页表才要缓存在主存中。

7. 页面置换算法

在磁盘和内存之间传送页的活动叫做交换 (swapping) 或者页面调度(paging) 。页从磁盘换入主存叫页面调入 ，从主存换出到磁盘叫页面调出 ，都是相对主存而言。

当系统物理内存用完时，页面就会在主存和磁盘之间频繁调入和调出，程序性能会出现明显的抖动，如果系统内存使用量超过了系统物理内存加交换空间的总大小那么系统程序将会阻塞。由此也可知道程序的最大虚拟内存空间 = 物理内存+交换空间。

当发生缺页中断时，虽然可以随机地选择一个页面来置换，但是如果每次都选择不常使用的页面会提升系统的性能。如果一个被频繁使用的页面被置换出内存，很可能它在很短时间内又要被调入内存，这会带来不必要的开销。人们已经从理论和实践两个方面研究出了很多算法，目前页面算法有下面几个：

1. 最优页面置换算法
2. 最近未使用页面置换算法
3. 先进先出页面置换算法
4. 第二次机会页面置换算法
5. 时钟页面置换算法
6. 最近最少使用页面置换算法
7. 用软件模拟LRU
8. 工作集页面置换算法
9. 工作集时钟页面置换算法

具体算法原理见《现代操作系统》第3.4节。

本文主要参考书籍《深入理解计算机系统》。