虚拟内存了, 到了CSAPP的最后三分之一了. 虚拟内存看了一下, 类似高速缓存是内存的映射, 虚拟内存也是一个映射的集合.
地址
虚拟内存和异常控制机制一样, 也是软硬结合的, 由硬件异常, 硬件地址翻译, 主存, 磁盘文件和内核软件的完美协作和交互组成. 为每个进程提供了一个大的, 一致的和私有的地址空间.
在日常使用中, 虚拟内存是不可见的, 自动工作的, 不需要应用程序员的干涉. 虚拟内存的特点有:
- 虚拟内存涉及计算机系统的所有层面
- 虚拟内存给了应用程序强大的能力
- 虚拟内存使用不当非常危险
既然可以把虚拟内存抽象为一个地址空间, 那么很显然虚拟内存也有地址. 同时物理内存也有地址. 二者的地址空间不一定相同. 有些计算机采用物理地址寻址, 即寻址线路直接连接内存. 现代计算机都采用虚拟地址寻址, CPU生成虚拟地址, 虚拟地址通过硬件地址翻译器翻译成物理地址, 再接入内存单元.
CPU的地址和翻译硬件, 叫做内存管理单元, 或者内存控制单元. CPU的翻译利用的是存放在主存中的查询表来动态翻译虚拟地址, 这个查询表由操作系统管理, 所以这是软硬一体的流程.
地址空间是一个从0到最大内存编号的地址, CSAPP里假设都是线性也就是连续的. 虚拟内存有虚拟内存空间, 物理地址则有物理地址空间. 关键要认识到:
主存的每一个字节, 都有一个来自虚拟地址空间的虚拟地址和来自物理地址空间的物理地址.
练习 9.1 完成下边的表格
| 虚拟地址位数 | 虚拟地址数 | 最大可能的虚拟地址 |
|---|---|---|
| 8 | 256 | 256-1 = 255 |
| 16 | 64K = 2的16次方 | 64K-1 |
| 32位 | 2的32次方 | 2的32次方-1 = 4G-1 |
| 48 | 256T = 2的48次方 | 256T-1 |
| 64 | 16E | 16E-1 |
做完之后发现, 这其实是N位计算机能够支持的最大虚拟内存地址, 也是虚拟内存的大小. 常用的32位机器可以有4GB的虚拟内存地址空间, 而64位机器可以有16E的虚拟内存地址空间.
虚拟内存的组织结构 – 页表
虚拟内存被组织成为一个存放在磁盘上的连续N个字节大小的单元组成的数组. 每个字节有唯一的虚拟地址, 就是数组的索引.
注意, 这里提到了存放在磁盘上. 而这些存放在磁盘上的内容, 被缓存在主存中. 就像高速缓存有缓存块一样, 主存到磁盘之间的传输, 也被分成一个一个块.
虚拟内存系统将虚拟内存分割成大小固定的块, 这个块叫做虚拟页(Virtual Page). 类似的, 物理内存也被分割为物理页(也叫页帧), 大小与虚拟页相同.
所以虚拟内存可以看成是一个虚拟页的集合, 这个虚拟页的集合分为三个不相交的子集:
- 未分配的页: 虚拟内存系统还未分配(或者创建)的页. 没有任何数据何其关联.
- 缓存的页: 已经缓存在物理内存中的已分配页
- 未缓存的页: 没有缓存在物理内存中的已分配页
虚拟页存储在磁盘上, 物理页缓存在DRAM中. 实际上高速缓存缓存了主存的内容, 而主存缓存了虚拟内存的内容. 虚拟内存则是存储在硬盘上的内容.
由于DRAM缓存不命中的开销很大, 所以虚拟内存的页一般都比较大, 不像高速缓存可能是几十个字节, 虚拟页一般是4K-2MB. DRAM是全相连的, 任何虚拟页都可以放在任何的物理页中.
DRAM缓存采取写回方式(设置一个标记, CPU写缓存的时候先检查标记, 如果标记是0就直接覆盖, 标记是1就先写内存, 再写缓存.这里的内存和缓存指的是两个级别的存储器, 并不特指硬件设备.)
和高速缓存一样, 虚拟内存系统必须判断一个虚拟页是不是缓存在DRAM的某个地方(就像CPU从内存读的时候, 可以判断这块内存是不是在缓存里). 如果虚拟页在DRAM缓存中, 则缓存命中. 如果不存在, 系统必须找到虚拟页在磁盘上的位置, 然后在物理内存中选择一个牺牲页, 将虚拟页从磁盘复制到DRAM中, 替换牺牲页.
这个功能软硬一体的, 开始说的存放在物理内存的, 供CPU翻译地址的查询表, 就是页表, 页表把虚拟页映射到物理页. 每次地址翻译硬件将虚拟地址翻译成物理地址的时候, 都会读取页表. 操作系统则负责维护页表的内容, 以及在磁盘和DRAM之间来回传送页.
页表实际上市一个数组, 其中的每一个元素叫做页表条目(Page Table Entry). 虚拟地址空间中的每个页在页表中的一个固定偏移量的位置处, 都有一个PTE. (这里好像高速缓存, 就是将虚拟缓存分成各个相等的块.)
PTE可以认为是由一个有效位, 外加一个地址字段组成的. 有效位表示这个页是不是已经缓存在DRAM中, 如果有效位被设置, 则地址字段表示DRAM中相应物理页的起始位置. 如果有效位没有设置, 就表示这个虚拟页还没有被分配, 则地址是空.
其实可以发现, 类似高速缓存, 虚拟页越大, 总共分的页数就越少, 则页表就越短. 页表的长度, 就是总的虚拟地址空间/页大小.
9.2 确定页表的长度
| n | P=2的p次方 | PTE数量 |
|---|---|---|
| 16 | 4K | 2e16/2e12 = 2e4 = 16 |
| 16 | 8K | 2e16/2e13 = 2e3 = 8 |
| 32 | 4K | 2e32/2e12 = 2e20 = 1M |
| 32 | 8K | 2e32/2e13 = 2e19 = 512K |
知道了页表, 就类似高速缓存一样, 有命中与未命中了. CPU要读一个虚拟内存地址的时候, 地址翻译硬件会将其翻译成一个索引来定位要读取的页. 然后去检查页面, 因为有效位是1, 所以就会到内存中去读取, 读取的地址就是页表中的地址.
在虚拟内存的习惯说法中, DRAM缓存不命中叫做缺页(page fault), 地址翻译硬件在检查页表的时候, 发现有效位没有被设置, 这个时候硬件会触发一个缺页异常, 然后调用内核中的缺页异常处理程序, 这个程序会选择一个牺牲页, 如果牺牲页被修改了, 内核就会将其写回磁盘. 然后将其替换掉. 替换掉之后, 还会修改牺牲页和载入页的页表条目.
完成缺页替换之后, 还记得上一章的异常处理中缺页的处理方式, 是重新执行指令. 这个时候再去检查页表, 就会发现被缓存了, 然后读取之就可以了, 一切就像没有发生过缺页一样.
除了关键的页, 页表, 缺页等术语之外, 还有一些虚拟内存方面的名词:
- 交换(swapping): 在磁盘和内存之间传送页
- 页面调度: 和交换是同一个意思
- 换入: 页从磁盘载入DRAM
- 换出: 页被从DRAM中弄走
- 按需页面调度: 一直等到有不命中发生的时候才调度页面
- 预测不命中: 尝试在不命中发生之前就调度页面
听上去预测不命中会高端一些, 然而所有现代系统使用的都是按需页面调度的方式.
管理内存和保护内存
虚拟内存简化了对内存的管理, 提供了一种保护内存的方法.
上一节学了基础的知识, 也就是以页表映射为核心, 将虚拟内存的内容在DRAM和磁盘间来回传送, 以满足程序的需要的基础过程.
实际上, 操作系统为每一个进程都提供了独立的页表, 因此每个进程看上去都会有独立的虚拟地址空间. 两个进程的虚拟地址即使相同, 映射的实际物理内存地址可以相同, 也可以不同.
这就为管理内存提供了深远的影响:
- 简化链接: 对于链接器来说, 并不需要知道实际的物理地址, 因为实际的物理地址因机器而已. 只需要知道虚拟地址即可, 所以就可以编译出位置无关的目标文件. 否则链接器就变成了针对不同内存大小要提供不同版本的软件了.
- 简化加载: 在加载器加载程序的时候, 同样也无需自己去排布各个段的地址, 只需要按照固定的逻辑分配即可, 而且在分配的时候, 也不会实际复制任何数据, 只有按需的时候才会加载页面即读入数据.
- 简化共享: 像之前我们编写的程序, 各个程序都需要系统调用, 需要将系统调用函数加载到所有程序的栈中吗? 有了虚拟内存, 显然不需要, 操作系统只需要将内核以及内核保留的一部分物理内存, 映射到每个进程的虚拟内存的同样一段地址上去. 所有的进程访问这些虚拟地址, 其实都是在访问同一个位置的物理内存.
- 简化内存分配: 如果需要分配额外内存, 只需要分配一个连续的虚拟内存页面, 然后映射到物理内存中同样数量的物理页面就可以了, 而不需要分配连续的物理内容, 这就让分配变得容易许多.
所谓保护内存, 就是让控制读写权限. 现实的PTE上还带有一些控制位, 用于表明该内存地址是否可以由用户状态的程序读写, 至少有三个位, SUP, READ, WRITE. 外加上有效位, 可以知道PTE还是有点复杂的.
如果CPU在执行指令的时候, 遇到这几个位不符合要求, CPU(其实是内存控制器)就会触发一个硬件异常, 然后将控制传递给内核中的异常处理程序. Linux在shell中将这种错误显示为segment fault. 所以看到这个错误, 就会知道是在访问内存的时候出了问题.
地址翻译机制
地址翻译的核心, 就是把CPU寻的虚拟内存地址翻译成物理内存地址, 然后将物理内存地址交给主存取出数据的过程.
CPU中有一个特殊的寄存器, 专门用来存储当前页表的地址. CPU寻找的虚拟地址包含两个部分, 一部分是虚拟页面偏移量(VPO), 一部分是虚拟页号(VPN, 也就是页表的索引号).
每个PTE中从前边的知识可以知道, 存放了当前PTE页对应的物理页号, 也就是对应页号的物理地址.
在开始翻译的时候, 内存控制单元根据虚拟页号, 到页表中找到对应的PTE ,然后拿出其中的物理页号, 将物理页号之后拼接上虚拟页面偏移量, 就得到了实际的物理地址.
由于物理页和虚拟页大小是相同的, 所以虚拟页面偏移量直接可以作用于物理页面. 通过这个翻译机制, 对于任何虚拟地址的寻址, 都可以通过页表对应到物理内存的某个页上. 在加上前边说的页表换算和缺页机制, 每个应用程序就拥有了一个独立的虚拟地址空间, 并且想从存储器读入什么就读入什么.
9.3 计算32位虚拟地址和24位物理内存地址在不同虚拟页大小下的数据
| P | VPN位数 | VPO位数 | PPN位数 | PPO位数 |
|---|---|---|---|---|
| 1KB | 页号就是虚拟地址除以页面大小, 所以2e32/2e10=2e22, 有 22 位 | 虚拟地址长度去掉页号, 就是偏移量, 所以偏移量有32-22 = 10 位 | 物理页号可以先计算出物理页面偏移量是10位, 所以物理页面有14位 | 物理页面偏移量=虚拟页面偏移量, 所以也是10位 |
| 2KB | 2e32/2e11 = 2e21, 有21位 | 32-21 = 11位 | 24-11 = 13位 | 11位 |
| 4KB | 32-12 = 20位 | 32-20 = 12位 | 12位 | 12位 |
| 8KB | 32-13 = 19位 | 13位 | 11位 | 13位 |
根据微软官方的介绍, 32位 windows 的页大小是4KB. 并且操作系统内核不使用硬件地址翻译.
知道了地址翻译的基本机制, 就可以来看看在现实中的地址翻译的几个特点:
- 结合高速缓存和虚拟内存. 大多数系统, 采用虚拟地址访问内存, 采用物理地址访问高速缓存.
- 利用TLB加速页表访问. 由于页表存放在内存中, 访问时间比访问高速缓存慢得多. 在CPU的内存控制器中, 包含一个针对页表条目的缓存, 称为翻译后备寄存器(TLB).
这个东西是一个小的高速缓存, 有很多行, 每一行保存有单个PTE组成的块. 其索引也类似高速缓存, 从页号中提取一部分用于组选择和行匹配. 当TLB命中的时候, MMU的速度就非常快. - 多级页表. 页表也是需要占用大小的, 现在的计算机普遍是64位寻址, 操作系统给的虚拟内存地址空间一般是48位, 按照之前说的 windows 的页是4KB, 则 页表 有 2e36个索引, 假如每个PTE有4字节, 也就是有2e38个字节的页表大小, 大概是64G. 常用的16G内存连页表都放不下. 如何解决这个问题, 在下一节单独讨论.
多级页表
在现实中, 并不是一个页表就存放了所有的页表数据. 实际的页表是分层次的. 这里分析一下CSAPP的例子:
虚拟内存有32位, 容量是4G. 每个页面是4KB大小, 每个PTE长度是4字节. 很显然, 如果只用一个页表, 页号有2e32/2e12 = 2e20 个页. 也就是一共有1024K个页.
现在已经分配了2K个页给代码和数据, 6K+1023个页也未分配, 然后还有一个1页给了用户栈. 则目前从开始的地方到用户栈, 一共有2+6+1 = 9K个页面. 容量是 9K * 4KB = 36M的空间. 其中代码和数据段的大小是 2K*4KB = 8M. 6K个空白页的大小是 6K * 4KB = 24M.
然后来用有层次的页表来分配. 首先一级页表将4GB内存分成1024个片(chunk), 每一个片是4MB. 这个时候可以知道, 我们上边涉及到的内存是36M, 因此一级页表的0-8索引里就可以对应这36M空间.
这个时候可以先把索引分配一下:
- 0 索引 对应8M代码和数据段中的第1个4M
- 1 索引 对应8M代码和数据段中的第2个4M
- 2 索引 对应24M未使用部分中的第1个4M
- 3 索引 对应24M未使用部分中的第2个4M
- 4 索引 对应24M未使用部分中的第3个4M
- 5 索引 对应24M未使用部分中的第4个4M
- 6 索引 对应24M未使用部分中的第5个4M
- 7 索引 对应24M未使用部分中的第6个4M
- 8 索引 对应最后1023个空白页+1个用户栈页, 总大小也是4M
可见, 只有0,1 和8对应的内存空间有被使用的部分, 而2-7是完全没有使用的. 在多级页表中, 完全没有使用到的内存空间对应的PTE就是空. 如果有部分被分配, PTE中会存放对应的二级页表的基址
.
二级页表中每个PTE映射一个4KB的虚拟内存页面, 4MB/4KB = 2e22/2e12 = 2e10, 也有1024个条目. 其中的每个条目就直接对应一个页了. 这里设计好的PTE也是4字节大小.
之前地址翻译的时候, 在页表中寻找页用的是VPN也就是页号作为索引. 在有了多级页表的时候, 很显然, 就不能只有一个VPO, 而是先使用一个一级VPO, 再使用二级VPO, 有几级页表就会有几次VPO. 最后取到PTE中的实际物理页表号.
所以 n 级页表下的虚拟地址, 其真正构成是 n 个 VPN + 1个VPO, MMU会用前n个VPN在n级页表中查找最终的物理页号, 然后和VPO拼起来作为物理地址送入内存.
回过头来看看这个多级页表有什么特点:
- 无需保存全部的页表, 这个例子里, 2-7的页表根本无需在内存中生成, 在需要的时候再生成, 可以有效节约空间
- 通过合理的编排大小, 可以看到, 一级页表有1024个条目, 每个4字节, 二级页表也有1024个条目, 每个4字节. 大小都一样. 而且每个页表都是4KB大小, 恰好是一个页的大小. 调入调出页表保证对齐页.
实际的TLB也是同时缓存多级页表的, 查询多级页表的速度也不算慢.
地址翻译示例
一些前提条件:
- 内存按单字节访问和寻址
- 虚拟地址长14位
- 物理地址长12位
- 页面大小是64字节
- TLB四路组相连, 能存16个条目
- L1 高速缓存是物理寻址, 直接映射, 行大小4字节, 一共16个组.
首先计算虚拟页号, 2e14/2e6 = 2e8, 即页号长8位, 即页表的长度是256个PTE. 偏移量是6位低地址, 页号是虚拟地址的高8位. 对应物理地址, 低6位是偏移量, 高6位是物理页号.
TLB利用虚拟页号来寻址, 由于TLB有四个组, 很显然需要将虚拟页号按4个区分, 则虚拟页号的低2位作为组, 剩下的高6位作为标记. 这是之前的高速缓存的做法.
真正的高速缓存则是用物理地址来寻址的, 因此由于行大小是4字节, 显然需要2位表示偏移, 然后是16组, 所以需要4位表示组索引. 剩下对应物理地址长度12 – 2 – 4 = 6就是标记长度.
然后CPU试图读0x03d4, 这个虚拟地址对应的14位长度是0x00001111010100, 这是一个虚拟地址, 先计算页号和偏移量, 显然虚拟页号是高8位 = 00001111 = 0x0F, 偏移量是低6位, 即010100 = 0x14.
之后根据之前的工作原理, 会先去TLB进行寻找. 此时0x0F的最低2位作为组, 会去寻找组0x3, 剩下的高六位000011 = 0x3作为标记, 结合3组中的标记3, 可以得到PPN= 0x0D = 001101, 有效位是1.
既然在TLB中找到了缓存的PPN也就是物理页号, 然后就将物理页号和偏移量结合起来, 得到 001101 010100 = 0x354, 这个就是对应的物理地址.
这其实已经完成了虚拟地址的翻译工作, 然后要寻物理地址了, 就要去高速缓存先看一下了. 此时可以知道, 偏移=00, 组索引是0101 = 5, 标记是001101 = 0d.
在高速缓存里找第5组, 0d标记, 得到有效位为1, 块0是36, 最后读出的结果就是0x36.
所以可见整体的地址翻译过程是:
- CPU寻虚拟地址
- MMU寻TLB缓存, 缓存命中则返回, 缓存不命中寻内存中页表并更新TLB.
- MMU拼出物理地址
- 用物理地址寻高速缓存
- 高速缓存命中则OK; 高速缓存不命中, 读取内存并更新高速缓存.
- 返回数据给CPU
练习9.4 继续翻译其他地址
虚拟地址是0x03d7.
- A 虚拟地址14位是 00 0011 1101 0111
- B 地址翻译:
参数 值 VPN 虚拟页号 0000 1111 = 0xF TLB索引 11 = 0x3 TLB标记 000011 = 0x3 TLB命中?(是/否) 命中, 组3标记3的位置存在数据0D 缺页?(是/否) 物理页号是0D, 页表中存在索引是0F的条目对应0D, 所以不缺页 PPN 0D - 物理地址是 0011 0101 0111
-
参数 值 字节偏移 11 = 0x3 缓存组索引 0x5 缓存标记 001101 = 0xd 缓存命中?(是/否) 是 返回的缓存字节 0x1D
之后的Intel Haswell i7的内存控制机制和之前基本上是一样的, 目前支持48位的虚拟地址和52位的物理地址空间, 页大小可以在启动的时候被配置成4KB或者4MB. Linux使用4KB的页.
i7采用4级页表, 高速缓存是物理寻址, TLB是虚拟内存寻址. 每级页表的中的PTE长度都是64个字节.
Linux虚拟内存系统
现在可以再来看一下内存结构图了. 通过这一章可以知道, 以前说的程序段从0x40000000开始, 还有链接中的那些地址, 其实都是虚拟内存地址.在栈底往上的部分, 是内核虚拟地址.
对于每个进程来说, 内核虚拟地址中的一部分是被映射到共享的物理页面, 其中存放着内核的一些系统调用函数的代码和共享的数据结构. 另外一部分则是每个进程都不相同, 记录着内核针对这个进程的栈, 进程的页表, 以及记录虚拟地址空间的各种数据结构.
