虚拟内存详解

目录

一、虚拟内存概念

二、物理地址和虚拟地址

三、虚拟内存作为缓存的工具

1、虚拟页

 2、页表

3、缺页

四、地址翻译

五、高速缓存与虚拟内存结合

1、利用TLB加速地址翻译

2、多级页表

一、虚拟内存概念

虚拟内存时硬件异常、硬件地址翻译、主存、磁盘文件以及内核软件的完美交互。它为每个进程提供了私有的地址空间。虚拟内存提供了三个重要的能力：

1）它将主存看成是存储在磁盘文件上的地址空间的高速缓存，在主存中只保存活动区域,并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。

2）它为每个进程提供了致的地址空间，从而简化了内存管理。

3）它保护每个进程的地址空间不被破坏。

虚拟内存是危险的，每次应用程序引用一个变量、间接引用一个指针，或者调用一个诸如melloc这样的动态分配程序时，它就会和虚拟内存发生交互。

二、物理地址和虚拟地址

计算机的主存被组织成一个由M个连续个字节大小的单元组成的数组，每字节都有一个唯一的物理地址，CPU访问内存最自然的方式就是使用物理地址，这种方式成为物理寻址，如下图所示：

早期的PC使用物理寻址，而且诸如数字信号处理器、嵌人式微控制器以及Cray超级计算机这样的系统仍然继续使用这种寻址方式。然而，现代处理器使用的是一种称为虚拟寻址(virtual addressing)的寻址形式，如下所示：

使用虚拟寻址，CPU通过生成一个虛拟地址(Virtual Address， VA)来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译(address translation)。 就像异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。CPU芯片上叫做内存管理单元(Memory Management Unit,MMU)的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

地址空间是一个非负整数地址的有序集合。如果地址空间中的整数是连续的，那么我们说它是一个线性地址空间。space)。在一个带虚拟内存的系统中，CPU从一个有N=2"个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间。一个地址空间的大小是由表示最大地址所需要的位数来描述的。例如，一个包含N=2的n次方虚拟地址空间就叫做一个n位地址空间。一个系统还有一个物理地址空间(physicaladdressspace)，对应于系统中物理内存的M个字节。地址空间区分了数据对象本身和它的属性。一个数据对象可以对应几个相互独立的地址，每个地址都选自不同的地址空间，这就是虚拟内存的基本思想。主存中的每个字节都有一个选自虚拟地址空间的地址和物理地址空间的地址。虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组每字节都有一个唯一的虚拟地址，作为到数组的索引。

三、虚拟内存作为缓存的工具

1、虚拟页

VM系统通过将虚拟内存分割为称为虚拟页(Virtual Page，VP)的大小固定的块来处理磁盘和主存之间的传输问题。每个虚拟页的大小为P=2的p次方字节。类似地，物理内存被分割为物理页(Physical Page. PP)，大小也为P字节(物理页也 被称为页帧(page frame))。 在任意时刻，虛拟页面的集合都分为三个不相交的子集:

●未分配的: VM系统还未分配(或者创建)的页。未分配的块没有任何数据和它们相 关联，因此也就不占用任何磁盘空间。

●缓存的:当前已缓存在物理内存中的已分配页。

●未缓存的:未缓存在物理内存中的已分配页。

下图的示例展示了一个有8个虚拟页的小虚拟内存。虚拟页0和3还没有被分配，虚拟页1、4、6已经被分配并缓存在主存中，2、5、7被分配未被缓存在主存中。

 2、页表

用DRAM缓存来表示虚拟系统缓存，它在主存中缓存虚拟页。（CASPP书中所用的术语）DRAM缓存是全相联的，即虚拟页可以放在任何物理页中当发生不命中时采用了比存储器更为精细的替换算法，并且DRAM缓存总是使用写回而不是直写。

同任何缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在DRAM中的某个地方。如果是，系统还必须确定这个虚拟页存放在哪个物理页中。如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到DRAM中，替换这个牺牲页。这些功能是由软硬件联合提供的，包括操作系统软件、MMU(内存管理单元)中的地 址翻译硬件和一个存放在物理内存中叫做页表(page table)的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。为了方便我们将假设每个PTE是由一个有效位(valid bit)和一个n位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在DRAM中。如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那 么一个空地址表示这个虚拟页还未被分配。否则，这个地址就指向该虚拟页在 磁盘上的起始位置。下图展示了一个页表的基本组织结构。页表就是一个页表条目（Page Table Entry, PTE)的数组。

 图中的示例展示了一个有8个虚拟页和4个物理页的系统的页表。四个虚拟页(VP1、VP2、VP4和VP7)当前被缓存在DRAM中。两个页 (VP0和VP 5)还未被分配，而剩下的页(VP3和VP6)已经被分配了，但是当前还未被缓存。图中有一个要点要注意，因为DRAM缓存是全相联的，所以任意物理页都可以包含任意虚拟页。

3、缺页

页命中：如上图图一所示，当CPU要读包含在虚拟页VP2中的虚拟内存中的一个字时，地址翻译硬件将虚拟地址作为一个索引来定位PTE2，并从内存中读取它，因为设置了有效位，那么地址翻译硬件就知道VP2是缓存在内存中了，所以他会使用PTE中的物理内存地址（该地址指向PP1中缓存页的起始地址）来构造出这个字的物理地址，这就是页命中。如下图；

 缺页：在虚拟内存的习惯说法中，DRAM缓存不命中称为缺页(page fault)。上图展示了 在缺页之前我们的示例页表的状态。CPU引用了VP3中的一个字，VP3并未缓存在DRAM中。地址翻译硬件从内存中读取PTE3，从有效位推断出VP3未被缓存，并且触 发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页， 在此例中就是存放在PP3中的VP4。如果VP 4已经被修改了，那么内核就会将它复制回磁盘。无论哪种情况，内核都会修改VP 4的页表条目，反映出VP 4不再缓存在主存中 这一事实。接下来，内核从磁盘复制VP3到内存中的PP3，更新PTE 3，随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在，VP3已经缓存在主存中了，那么页命中也能由地址翻译硬件正常处理了，下图展示了在缺页之后我们的示例页表的状态。

 在虚拟内存的习惯说法中，块（主存与CPU之间还存在着高速缓存，高速缓存和主存之间的交换单元被成为块）被称为页。在磁盘和内存之间传送页的活动叫做交换(swapping)或者页面调度(paging)。页从磁盘换入(或者页面调入)DRAM和从DRAM换出(或者页面调出)磁盘。一直等待，直到最后时刻，也就是当有不命中发生时，才换入页面的这种策略称为按需页面调度(demand paging)。也可以采用其他的方法，例如尝试着预测不命中，在页面实际被引用之前就换入页面。然而，所有现代系统都使用的是按需页面调度的方式。操作系统分配新的虚拟内存页面时，会在磁盘上创建空间并更新DRAM中的PTE表。尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存总的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面(active page)集合上工作，这个集合叫做工作集( working set)或者常驻集合(resident set)。在初始开销，也就是将工作集页面调度到内存中之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。

到目前为止，我们都假设有一个单独的页表，将一个虚拟地址空间映射到物理地址空间。实际上，操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。

虚拟内存还使得容易向内存中加载可执行文件和共享对象文件，简化加载。要把目标文件中.text和.data节加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页，把它们标记为无效的(即未被缓存的)，将页表条目指向目标文件中适当的位置。有趣的是，加载器从不从磁盘到内存实际复制任何数据。在每个页初次被引用时，要么是CPU取指令时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页。将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作内存映射(mem-ory mapping)。

一般而言，每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程共享的。在这种情况中，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。

然而，在一些情况中，还是需要进程来共享代码和数据。例如，每个进程必须调用相同的操作系统内核代码，而每个C程序都会调用C标准库中的程序，比如printf。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和C标准库的副本，如下图所示：

当一个运行在用户进程中的程序需要额外的堆空间时，操作系统就分配k个连续的虚拟内存页面，并将它们映射到物理内存中任意位置的k个任意的物理页面，页面可以随机分散在物理内存中。

每次CPU生成一个地址时，地址翻译硬件都会读一个PTE，所以通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单，下图展示了大致的思想：

 在这个示例中，每个PTE中已经添加了三个许可位。SUP位表示进程是否必须运行在内核(超级用户)模式下才能访问该页。运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些SUP为0的页面。READ位和WRITE位控制对页面的读和写访问。如果进程i运行在用户模式下，那么它有读VP0和读写VP1的权限。然而,不允许它访问VP2。如果一条指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell一般将这种异常报告为“段错误(segmenta-tion fault)”。

四、地址翻译

地址翻译是一个N元素的虚拟地址空间中的元素和一个M元素的物理地址空间中元素之间的映射。下图展示了MMU如何利用页表来实现这种映射。CPU中的一个控制寄存器，页表基址寄存器(Page Table Base Register，PTBR)指向当前页表。n位的虚拟地址包含两个部分:一个p位的虚拟页面偏移（Virtual Page Offset，VPO)和一个(n一p位的虚拟页号( Virtual Page Number,VPN)

,MMU利用VPN来选择适当的PTE。例如，VPN 0选择PTE 0,VPN 1选择PTE1，以此类推。将页表条目中物理页号(Physical Page Number，PPN)和虚拟地址中的 VPO串联起来，就得到相应的物理地址。注意，因为物理和虚拟页面都是Р字节的，所以物理页面偏移(Physical Page Offset，PPO)和 VPO是相同的。

页命中步骤如下图a： 

●第1步:处理器生成一个虚拟地址，并把它传送给MMU。

●第2步:MMU生成PTE地址，并从高速缓存/主存请求得到它。

●第3步:高速缓存/主存向 MMU返回PTE。

●第4步:MMU构造物理地址，并把它传送给高速缓存/主存。

●第5步:高速缓存/主存返回所请求的数据字给处理器。

缺页步骤： 

●第1步到第3步:和页命中中的第1步到第3步相同。

●第4步:PTE中的有效位是零，所以MMU触发了一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。

●第5步:缺页处理程序确定物理内存中的牺牲页，如果这个页面已经被修改，则把它换出到磁盘。

●第6步:缺页处理程序页面调人新的页面，并更新内存中的PTE。

●第7步:缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU将引起缺页的虚拟地址重新发送给MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，在MMU执行了上图b中的步骤之后，主存就会将所请求字返回给处理器。

页命中完全由硬件来处理，而缺页则由硬件和操作系统来完成。

五、高速缓存与虚拟内存结合

在任何既使用虚拟内存又使用SRAM高速缓存的系统中，都有应该使用虚拟地址还是使用物理地址来访问SRAM高速缓存的问题。大多数系统是选择物理寻址的。使用物理寻址，多个进程同时在高速缓存中有存储块扣共享来自相同虚拟页面的块成为很简单的事情。而且，高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。下图展示了一个物理寻址的高速缓存如何和虚拟内存结合：

1、利用TLB加速地址翻译

 许多系统在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器(Translation Lookaside Buffer，TLB)。TLB是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块TLB通常有高度的相联度。如下图所示：用于行匹配的标记TLBT和用于组选择的索引TLBI是从虚拟页号vpn中提取出来的。

如果TLB有T=2的t次方个组，那么TLB索引(TLBI)是由VPN的t个最低位组成的，而TLB标记(TLBT)是由VPN中剩余的位组成的。结合了TLB的地址翻译步骤可以变为:

●第1步:CPU产生一个虚拟地址。

●第2步和第3步:MMU从TLB中取出相应的PTE。

第4步:MMU将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。

●第5步:高速缓存/主存将所请求的数据字返回给CPU。

当TLB不命中时，MMU必须从L1缓存中取出相应的PTE，如下图b）所示。新取出的PTE存放在TLB中，可能会覆盖一个已经存在的条目。 

2、多级页表

 假设有一个32位的地址空间、4KB的页面和一个4字节的PTE，那么即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个4MB的页表驻留在内存中。对于地址空间为64位的系统来说，问题将变得更复杂，用来压缩页表的常用方法是使用层次结构的页表。假设32位虚拟地址空间被分为4KB的页，而每个页表条目都是4字节。还假设在这一时刻，虚拟地址空间有如下形式:内存的前2K个页面分配给了代码和数据，接下来的6K个页面还未分配，再接下来的1023个页面也未分配，接下来的1个页面分配给了用户栈。下图展示了我们如何为这个虚拟地址空间构造一个两级的页表层次结构。

一级页表中的每个PTE负责映射虚拟地址空间中一个4MB的片(chunk)，这里每一片都是由1024个连续的页面组成的。比如，PTE0映射第一片，PTE1映射接下来的一片，以此类推。假设地址空间是4GB，1024个PTE已经足够覆盖整个空间了。 如果片i中的每个页面都未被分配，那么一级PTEi就为空。例如，图中片2~7是未被分配的。然而，如果在片i中至少有一个页是分配了的，那么一级PTEi就指向一个二级页表的基址。例如，图中片0、1和8的所有或者部分已被分配，所以它们的一级PTE就指向二级页表。

二级页表中的每个PTE都负责映射一个4KB的虚拟内存页面，就像我们查看只有一级的页表一样。注意，使用4字节的PTE，个一级和二级页表都是4KB字节，这刚好和一个页面的大小是一样的。 这种方法从两个方面减少了内存要求。

第一：如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在。这代表着一种巨大的潜在节约，因为对于一个典型的程序，4GB的虚拟地址空间的大部分都会是未分配的。

第二：在主存中，虚拟内存系统可以在需要时创建、页面调人或调出二级页表，这就减少了主存的压力;只有最经常使用的二级页表才需要缓存在主存中。 下图描述了使用k级页表层次结构的地址翻译。虚拟地址被划分成为k个VPN和1个VPO。每个VPNi都是一个到第i级页表的索引，其中1≤i≤k。第j级页表中的每个PTE，1≤j≤h一1，都指向第j+1级的某个页表的基址。第k级页表中的每个PTE包含某个物理页面的PPN，或者一个磁盘块的地址。为了构造物理地址，在能够确定PPN之前，MMU必须访问k个PTE，对于只有一级的页表结构，PPO和VPO是相同的。