读懂操作系统之虚拟内存地址翻译原理分析篇（二）

前言

上一节我们整体概括通过MMU将虚拟地址翻译为物理地址的转换，这个过程都是按序就班的进行，一切都是基于已提前创建、分配虚拟页、物理页以及命中的前提，只是给和我一样没怎么系统学习操作系统的童鞋首先在脑海里有个大概的印象，本节我们从源头开始分析为程序创建进程到映射到主存上整个详细过程，本文将通过大量图解来分析原理，以便让各位能够完全理解地址翻译原理。若有叙述不当之处，还请批评指正。 

虚拟内存原理分析

如果没有系统学习现代操作系统，理论上我们会认为用户程序会将内存视为单个连续的内存空间，实际上可以将用户程序在内存中分布可以分散在页面的整个物理内存中。分页是一种内存管理方案，它允许进程的物理地址空间不连续。

物理内存划分：将物理内存划分为称为帧的固定大小的块（大小为2的幂，介于512字节和16 MB之间，必须跟踪所有空闲帧）

虚拟（逻辑）内存划分：将逻辑内存分成大小相同的块（称为页，每一块也是分为相同大小的页面）

若要运行大小为N页的程序，需要找到N个空闲帧并加载程序

地址翻译方案

通过常驻内存中的页表将虚拟地址翻译为物理地址， CPU生成的虚拟地址被划分为虚拟页号（用作页表索引，该页表包含物理内存中每个页的基地址）和虚拟页偏移量（与基址结合找到存储单元的物理存储地址）。对于给定的逻辑地址空间2^m和页面大小2ⁿ，如下：

分页内存管理方案本质就是通过MMU将CPU产生的虚拟地址通过中间媒介（页表）进行地址翻译，如下为简单翻译版本，一目了然。

上述我们学习了将逻辑地址（虚拟地址）划分为页号（注意：页号并不属于页表的一部分，页号不储存在主存）和页偏移量，到底是怎样借助页号和页偏移量进行翻译的呢？我们举个例子：假设如下一个32字节的物理内存，逻辑地址空间为16字节，说明逻辑地址有4位，而页帧偏移量为4个字节，因页帧偏移量和虚拟页偏移量相等，所以虚拟页偏移量也为4个字节即2位，所以页号为（4-2）= 2位即逻辑地址共有4页，如此假设和实际理论计算对等。地址翻译如下：

若CPU要找出逻辑地址为4的物理地址，通过上述我们知道逻辑地址为4在第1页且偏移量为0，然后去查找页表索引等于1的页帧号为6，因为物理地址 = （frame * pageSize）+ offset，所以逻辑地址4的物理地址=（6 * 4 bytes）+ 0 byte offset = 24。同理，比如如上逻辑地址为7在第1页，偏移量为3对应页表上的帧6，所以其物理地址为：（6 * 4 bytes）+ 3 byte offset = 27，这里需要注意的是物理地址的偏移量是相对这页的起始位置偏移。通过上述图解，我们反推根据逻辑地址和每页字节大小计算出其所在页和偏移量（下面根据虚拟地址计算虚拟页号和偏移量会用到），比如逻辑地址为7，因每页大小为4个字节，则所在页为（7 / 4） = 1，偏移量（7 mod / 4） = 3。

扩展页表条目（PTE）信息

现代计算机页表上的条目除了包含将虚拟地址翻译为虚拟地址的主要信息（有效位、页号）外，其中还包含如下其他信息（下面讲解页面置换算法会用到）：

保护位（Protection）：控制对指定虚拟页的访问是否可读、可写、可执行

引用位（Refrence）：为了近似实现LRU算法，帮助操作系统估算最近最少使用的页，当一页被访问时该位将被置位，操作系统定期将引用位清零，然后重新记录，这样就可以判定在这段特定时间内哪些页被访问过，通过检查引用位是否关闭，操作系统就可以从那些最近最少访问的页中选择一页

脏位（Modify）：当某一页被替换时，操作系统需要知道该页是否需要被复制写回，为了追踪读入主存中的页是否被写过，增加一个脏位，当页中任何字被写时就将这一位置位。如果操作系统选择替换某一页，脏位指明了把该页所占用的主存让给另一页之前，是否需要将该页写回磁盘，因此，一个被修改的页通常被称为脏页。

TLB缓存页表

上一节我们讲过CPU产生逻辑地址后通过MMU转换为物理地址时，每次都要访问页表，访问缓存和主存的时间相差上百个时钟周期，所以为了提高查找性能则使用TLB，我们可认为TLB是实现页表最好的方式，本质上是缓存页表。在没有TLB作为缓存时，我们使用页号（VPN）作为索引去页表上查找物理页号，引入TLB后，将页号划分为TLBT（TLB标记）和TLBI（TLB索引）只是做了一下转换而已，TLBI占2位，剩余的位就是TLBT。下面会通过一个实际例子来讲解如何结合TLBT和TLBI在TLB上查找。

TLB作为页表的缓存，用于存放映射到页帧中的那些项，TLB包含了页表中虚拟页到页帧映射的一个子集，因为将其作为缓存，所以额外还存在如上一个标记区域（TLBT），换句话说页表不同于TLB并不是作为缓存，所以并不需要标记区域，再加上如上额外的PTE扩展信息，所以TLB的存储结构如下：

TLB缺失

接下来我们开始进入TLB缺失环节，我们假设虚拟地址有14位，物理地址有16位，每页大小有64个字节，那么虚拟地址空间和物理地址空间如下图所示

因为每页大小为64字节即（2⁶），同时虚拟页偏移量和页帧偏移量相等，所以虚拟页偏移量和页帧偏移量都为6位，那么将虚拟地址空间和物理地址空间划分为对应的页号和页偏移量则如下图所示：

接下来则是将虚拟页号划分为TLBT和TLBI，因为TLB包含16个条目且4路关联，那么说明有S =（16 / 4）= 4组，那么TLBI占位 =  log_{2^{S = 2}}，剩余的则是TLBT = （8 - 2） = 6位，如下图所示

现在我们对虚拟地址和物理地址都有了完整的划分，现在假设TLB和页表状态存储结构分别如下图

假设现在CPU产生一个虚拟地址（0x0334），首先我们需要将其转换为虚拟页号（VPN），因每个页面大小为64字节，所以计算方式如下代码

var xvpn = Convert.ToInt32("0x334", 16);
var vpn = xvpn / 64; //vpn = 12
var vpo = xvpn % 64; //vpo = 52

上述计算出VPN等于12，然后将其对应虚拟地址上的VPN和VPO用二进制表示，分别如下图所示

而存储在TLB和页表上的状态都是16进制，所以上述VPN = 12₁₀ = 0x0C₁₆和VPO = 52₁₀ = 0x34₁₆，到此已经划分完VPN和VPO，接下来则是将VPN划分为TLBT和TLBI，由上述我们已经知道TLBT和TLBI在VPN中所占位数，所以如下图所示

由上我们可得出TLBT = 3₁₀ = 0x03₁₆，而TLBI = 0，有了TLBT（0x03）和TLBI（0）再去查找TLB状态表，如下红色标记

由上图我们发现此时标志无效而且物理页号也没有，此时发生TLB缺失，于是通过MMU将虚拟地址得到的VPN去页表中查找

此时我们看到在页表中也缺失，所以这里将发生缺页异常。TLB缺失分为如下两种情况

页在主存（页表）中，只需要创建缺失的TLB表项

页不在主存（页表）中，需要将控制权交给操作系统来解决缺页 

TLB缺失既可以通过软件处理也可以通过硬件处理，比如MIPS、Alpha通过软件处理TLB缺失，x86、ARM通过硬件处理TLB缺失，两种处理方式在性能差别上很小，无论哪一种方式需要执行的基本操作都是一样的。理论上来讲，在进程分配页帧时会将对应页帧更新到页表上，但是上述情况并未在主存页表中说明在页帧列表中没有空闲的页帧，所以这是TLB缺失中真正的缺页情况，此时将触发缺页异常，控制权交给操作系统内核中的缺页异常处理程序，操作系统知道了引起缺页的虚拟地址，操作系统必须完成以下3个步骤：【1】使用虚拟地址查找页表项，并在磁盘上找到被访问的页的位置【2】选择替换一个物理页，如果该选中的页被修改过，需要在把新的虚拟页装入之前将这个物理页写回磁盘，这一过程称为页面置换【3】启动读操作，将被访问的页从磁盘上取回到所选择的物理页的位置上【4】重新执行引发缺页的那条指令。因为第3个步骤需要耗费数百万个时钟周期，如果第2个步骤中被替换的物理页已被重写过，那么同样也会花费这么长时间，因此操作系统会选择另外一个进程在处理器上执行直到磁盘访问结束，所以前3个步骤执行所耗费的时间比较长，最后重新执行缺页指令。若在页表中找到了页帧号（即页在主存中），那说明TLB缺失只是一次转换缺失，在这种情况下，CPU只需要将页表项装载到TLB并且重新访问来进行缺失处理。

页面置换算法

为了解决缺页情况，所以必须实现页面置换作为请求调页的基础，这里我们介绍常见的几种置换算法，分别是Optional or MIN algorithm、FIFO(First-In-First-Out)、Clock、LRU(Least Recently Used)，针对各个算法，现假设有（1、2、3、4、1、2、5、1、2、3、4、5）12个引用串，4个空闲页帧。

FIFO（先进先出）

该算法记录了每个页面记录调到内存的时间，当必须置换页面时，将选择最旧的页面，请注意，并不需要记录调入页面的确切时间，可以通过创建一个队列实现此目的。具体过程太过简单，这里就不再细讲，此时将发生10次缺页错误，我们可计算出缺页率为（10/12）= 83%。如下：

OPT or MIN(最优)

最优置换算法找出最长时间没有使用的页，具有最低缺页率，可以用作离线分析方法，但是难以实现。此时将发生6次缺页错误，我们可计算出缺页率为（6/12）= 50%。如下：

LRU（最近最少使用）

FIFO算法使用的是页面调入内存的时间，OPT算法使用的是页面将来使用的时间，而LRU算法采用置换最长时间没有的页，该算法将每个页面与它上次使用的时间关联起来，当需要置换页面时，LRU选择最长时间没有使用的页面，该算法很难实现。此时将发生8次缺页错误，我们可计算出缺页率为（8/12）= 67%。如下：

启动和切换进程

上述我们只是从已经将程序加载到内存中所创建的进程角度来分析如何将虚拟地址翻译为物理地址，由于操作系统负责管理内存，因此必须了解物理内存的分配详细信息，分配了哪些页帧、每个页帧分配个哪个进程的哪个页面，哪些页帧可用，总共有多少帧，对此我们还一无所知。将用户程序加载到虚拟内存中的进程后为其划分对应的虚拟页，假设如下划分了4个虚拟页，操作系统在跟踪的页帧列表找出空闲（操作系统分配帧算法，这里暂不讨论）的页帧分配给虚拟页，然后操作系统再启动进程。如下图：

如上节所述页表保存在主存中，当调度进程时通过页表基址寄存器（PTBR）指向激活的指定进程页表， 当然也会加载另外一个寄存器（程序计数器，PC），所以每个数据或指令访问需要进行两次主存访问，一次是页表，另一次则是用于数据或指令。

当进程希望以受限的方式共享信息时，操作系统必须对其进行协助，这是因为访问另外一个进程的信息需要改变访问进程的页表，写访问位可以用来把共享限制为只读，并且和页表中其他位一样，该位只能被操作系统所修改。为了允许另一进程，设为P1，去读属于进程P2的一页，P2就要请求操作系统在P1地址空间中为一个虚拟页生成页表项，指向P2想要共享的物理页。如果P2要求操作系统可以使用写保护位以防止P1对数据进行改写，由于只有TLB缺失才会访问页表，任何决定页对的访问权限不仅要包含在页表中，还要包含在TLB中。当操作系统决定从进程P1切换到P2时，我们称之为上下文切换，它必须保证P2不能P1的页表，否则不利于数据保护，若没有TLB，只需要把页表基址寄存器指向P2的页表而不是P1就够了，如果有TLB，我们必须在其中清除属于P1的表项，不仅仅是为了保护P1的数据，而且是为了迫使TLB装入P2的表项。如果进程切换的频率很高，那么这一举措效率将会很低。例如，在操作系统切回P1之前，P2可能只装入了很少的TLB表项，但是，P1随后发现它所有的表项都不见了，因此不得不通过TLB缺失来重新加载这些表项，产生这个问题的原因在于进程P1和P2使用同一虚拟地址空间，并且我们必须清除TLB以防止地址混淆。另一种常见的方法则是增加进程标识符和任务标识符来扩展虚拟地址空间，比如FastMATH就有8位地址空间标识域（ASID），这个标识域标识了当前正在运行的进程，当进程切换时，它保存在由操作系统装入的寄存器中，进程标识符与TLB的标记部分相连接，因此只有在页号和进程标识符相匹配时，TLB才会发生命中，如此一来，除非特殊情况，我们就不需要清除TLB。 说了怎么多除了保护机制外，当我们切换进程时主要需要做哪些工作呢（即从一个进程控制块（Process Control Block，PCB）切换到另一个进程块，后续会深入讲解操作系统线程和进程）？

切换页表到当前PCB

页表基址寄存器指向当前页表

清除TLB，并将当前页表项装载到TLB（按需加载，进程访问哪些页才将对应页表项加载到TLB）

留个作业

若TLB中的PTE条目达到上限即满时，不难想象理论上会替换现有条目，那么采取替换的策略或机制是怎样的呢？

总结

基于上一节内容我们详细讲解了将虚拟地址翻译为物理地址的具体过程、进程页帧分配、页面置换算法，在讲解TLB缺失时并未涉及高速缓存，TLB和高速缓存将在下一节作为详解。关于虚拟内存内容通过一两篇文章根本讲解不清楚，比如还有减少页表容量方式、TLB和高速缓存关系、Intel和Linux虚拟内存系统等等。我尽量通过图解方式来带给大家较好的理解体验，能够更好的消化和吸收虚拟内存。