深入分析虚拟内存

Posted on | In | Visitors:

概述

物理寻址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址，第一个字节的地址为0，第二个为1，以此类推。CPU访问内存最自然的方式就是使用物理地址，这种寻址方式即物理寻址。当CPU执行加载指令时，生成一个物理地址，通过内存总线将其送给主存。主存取出对应位置的内容返回给CPU，CPU将其放到一个寄存器里。

虚拟寻址

使用虚拟寻址，CPU通过生成一个虚拟地址（VA）来访问主存，这个虚拟地址在被送到内存之前先被转换成对应的物理地址。将一个虚拟地址转换为物理地址的任务称为地址翻译。执行这个任务的是一个位于CPU芯片上的叫做内存管理单元（MMU）的硬件，它利用存放在主存中的查询表（页表）来动态的翻译虚拟地址，该表的内容由操作系统管理。
概念上讲，虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每个字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的（部分）内容被缓存到主存中。和其他缓存一样，虚拟内存被划分为固定大小的虚拟页，大小为P字节，物理内存也被划分为固定大小的物理页（也称为页帧），大小也是P字节。在任意时刻，虚拟页面都有以下三种状态的一种：

  • 未分配的
    系统还没有分配的页。未分配的块没有任何数据和它们相关联，也就不占用磁盘空间，也就不能访问。
  • 已缓存的
    当前已缓存到物理内存中的已经分配了的页。
  • 未缓存的
    未缓存到物理内存的已经分配了的页（存在磁盘上，访问时会产生缺页中断）。

    页表

    同任何缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在主存中的某个地方。如果是，还需确定这个虚拟页存放在哪个物理页中。如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个牺牲页被替换。
    页表就是一种将虚拟页映射到物理页的存于物理内存中的一种数据结构，它是若干页表项（PTE）的集合，虚拟地址空间中的每个页在页表中固定偏移量处都有一个页表项。每次MMU将一个虚拟地址转换为物理地址时都要读取页表。
    现在假设每个PTE是由一个有效位和一个n位地址字段组成（真正的页表项比这要复杂）。有效位表明该地址字段是否被缓存到物理内存中，如果设置了有效位（已缓存），则表明这个物理页中缓存了该虚拟页，地址字段就表示物理内存中相应的物理页的起始地址；如果没有设置有效位（未分配），则用一个空地址表示这个虚拟页还没有分配；否则（未缓存），这个地址就指向该虚拟页所在的磁盘上的起始位置。

    比如该图中VP1 2 4 7已缓存，VP3 6 未缓存，VP0 5未分配。

工作集

尽管在整个运行过程中程序引用的不同页面的总数可能超过物理内存的大小，但是局部性原则保证了在任意时刻，程序将趋于在一个较小的活动页面集合上工作，这个集合叫做工作集，初始将工作集页面调度到内存中后，接下来对这个工作集的引用将导致命中，不会产生额外的磁盘流量。但是如果工作集的大小超过了物理内存的大小，此时页面将不断的换进换出，发生抖动，占据CPU资源，程序运行变慢。

分析

为什么要有虚拟内存的存在？

因为需要运行的程序太大太多，而内存空间又太小，不可能把所有程序都调入内存中工作。虚拟内存就是来解决这个问题的。

它是什么？怎么工作的？

每个程序都会被分配一个自己的虚拟地址空间，这些空间被分割成多个块，每个块称为一页，每一页有连续的地址范围，这些页被映射到物理内存，但并不是所有的页都必须在内存中程序才能运行。当程序引用到一部分在物理内存中的地址空间时，由MMU进行映射转换；当引用到一部分不在物理内存中的地址空间时，操作系统负责将该页面调入内存，重新执行失败的指令。

再谈MMU的地址翻译


CPU中的一个控制寄存器——页表基址寄存器指向当前页表。n位的虚拟地址包含两个部分：一个p位的虚拟页面偏移（VPO）和一个n-p位的虚拟页号（VPN），MMU以VPN为索引来选择适当的PTE，将PTE中的物理页号（PPN）和虚拟地址中的VPO串联起来，即得到了相应的物理地址（因为VPN和PPN都是P字节的，故物理页面偏移PPO和VPO是相同的）。
(PA：物理地址。PTEA：页表条目地址。PTE：页表条目。VA：虚拟地址)
当页面命中时，CPU执行以下步骤：

  1. 处理器生成一个虚拟地址，把它传给MMU。
  2. MMU生成PTE地址，并从高速缓存/主存请求得到它
  3. 高速缓存/主存向MMU返回PTE
  4. MMU构造物理地址，并把它传给高速缓存/主存
  5. 高速缓存/主存返回所请求的数据字给处理器


当页面未命中时，CPU执行以下步骤：

1到3步与命中相同

  1. PTE的有效位是0，触发一次异常，传递CPU中的控制到操作系统内核执行缺页异常处理程序
  2. 缺页处理程序确定出物理内存中的牺牲页，如果该页面已经修改，则将其换出到磁盘。
  3. 缺页处理程序调入新的页面，并更新内存中的PTE。
  4. 缺页处理程序返回到原来的进程，重新执行刚导致缺页的指令 。命中后将数据取出，返回给CPU。

可见，每次CPU产生一个虚拟地址，MMU都要查询一次PTE，即从内存中取一次数据，访问内存其实是比较慢的，大约需要几百个周期。可以将一些PTE表项缓存到高速缓存SRAM中，称为翻译后备缓冲器（TLB）。
TLB是一个小的，虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块，每次访问只需要1到2个周期。
当TLB命中时：

  1. CPU产生一个虚拟地址
  2. MMU从TLB中取出相应PTE
  3. MMU将这个虚拟地址翻译成一个物理地址，并将其发送到高速缓存/主存中。
  4. 高速缓存/主存将所需数据返回给CPU。

当TLB不命中时，MMU必须从内存页表中取出相应的PTE，并将其拷贝到TLB中覆盖一个原有块，然后执行和命中时相同的3.4步

4.多级页表引入

当有一个32位的地址空间、4KB的页面大小、每个PTE占4个字节，这个时候意味着需要2^32 \ 2^12 = 1M个页表项需要存于内存中，时时刻刻占4M内存，显然不切实际，（何况64位）。此时就要用到多级页表。

多级页表的思想抽象的说就是加法换乘法。针对上述情况，设置两级页表，一级页表中有1024个PTE，每个PTE存储一个二级页表的地址。每个二级页表中有1024个PTE，每个PTE映射一个4KB的虚拟内存页面。

这种方法从两方面减小了内存需求：

  1. 如果一级页表中一个PTE全是空的，那么相应的二级页表就不会存在。实际中也是如此，比如4G内存，实际上大部分都没有分配。
  2. 只有一级页表才总是在内存中；虚拟内存系统可以在需要时进行创建，换进，换出二级页表，只有最经常使用的部分二级页表会在内存中，这也大大减少了内存的压力。

可以这样想，一本书表示一个虚拟内存，书的目录代表页表，如果书非常厚，那么导致的结果就是目录项很多，目录也非常厚，此时的多级页表就类似与给目录加了一个目录。

参考资料：
《深入理解计算机系统 3th》（CSAPP） 第9章
《现代操作系统 3th》（MOS）第3章