计算机组织与系统结构 虚拟存储器 Virtual Memory ( 第十九讲 ) 程旭 2012.12.24
容量访问时间成本 CPU 寄存器 100s Bytes <10s ns Cache K Bytes 10~100 ns $0.01~0.001/bit 主存 M Bytes 100ns-1us $0.01~0.001 磁盘 G Bytes 毫秒 10-3 ~10-4 美分 磁带无限秒 ~ 分 10-6 存储层次的级别 寄存器堆 Cache 存储器 磁盘 磁带 指令操作数 块 (Blocks) 页 (Pages) 文件 (Files) 分段传输单位 程序 / 编译器 1-8 字节 Cache 控制 8-128 字节 操作系统 512-4K 字节 较高级别 较快 用户 / 操作员 Mbytes 较大较低级别
存储所有我们已读 ( 写 ) 听 ( 说 ) 看的信息 人类数据类型 / 小时 / 天 (/4 年 ) / 一生阅读文字 ( 含少量图片 ) 200 K 2-10 M/G 60-300 G 以 120wpm 说 43 K 0.5 M/G 15 G 以 1KBps 说 3.6 M 40 M/G 1.2 T 50Kb/s POTS 的视频 22 M.25 G/T 25 T 200Kb/s VHS 质量的视频 90 M 1 G/T 100 T 4.3Mb/s HDTV/DVD 视频 1.8 G 20 G/T 1 P
一部小说 美国国会图书馆 ( 文字 ) 美国国会图书馆 ( 声音 + 电影 ) Kilo Mega Giga Tera Peta 1 封信 1 部电影 美国国会图书馆 ( 图像 ) 所有磁盘 Exa 所有相片 所有磁带 Zetta Yotta 现在的所有信息
本讲提纲 重温存储层次和 Cache 引论 虚拟存储器 页表和快表 (TLB) 保护 存储层次对计算机科学其他学科的影响
虚拟存储 提供一种理想中的非常非常大的存储器 许多工作所需存储器的总和大于实际的物理存储器 每个工作的地址空间大于实际的物理存储器 使得可利用的 ( 快速 昂贵 ) 的物理存储器得以很好地利用 简化存储器的管理 ( 当今, 使用虚拟存储技术的主要原因 ) 使用存储层次, 保持平均访问时间很低 至少包括两级存储层次 : 主存和二级存储 虚拟地址 程序员使用的地址 虚拟地址空间 上述地址的集合 存储器地址 物理存储器中存储字的地址, 也称为物理地址或实地址 ( Real address)
虚拟存储系统设计的基本问题 从二级存贮器向主存传输信息块的大小 某信息块的访问需要引入存储 M, 但是 M 已经装满, 那么 M 中的一些区域就必须释放, 为新的信息块腾出空间 替换策略 (replacement policy) M 中的哪个区域将安放新的信息块 放置策略 (placement policy ) 失效的信息项只有在出现页面失效 (fault) 时, 才从第二级存储器中取出 读取 / 装入策略 (fetch/load policy) reg cache mem disk frame pages 分页组织 虚拟和物理地址被划分为同等大小的信息块 页帧 (page frames) 页 (pages)
地址映射 V = {0, 1,..., n - 1} 虚拟地址空间 M = {0, 1,..., m - 1} 物理地址空间 n > m 映射 : V M U {0} 地址映射函数 MAP(a) = a 如果在虚拟地址 a 的数据出现在物理地址 a, 并且 a 在 M 中 = 0 如果在虚拟地址 a 的数据不出现在 M 中 处理器 a 名字空间 V 失效信息项故障缺页处理 a 地址变换机制 0 a' 主存 二级存储 物理地址 OS 完成这一传输
分页组织 物理地址 0 1024 7168 页帧 0 1 7 物理存储器 1K 1K 1K 地址变换映射 0 1024 页 0 1 1K 1K 映射单位 也是从虚拟存储器到物理存储器的传输单位 31744 31 1K 虚拟存储器 地址映射 10 虚拟地址 页号 偏移量 页表基址寄存器 到页表的索引 V 页表 访问权限 PA + 实际上, 经常采用串联方式 位于物理存储器的表 物理存储器地址
地址映射算法 If V = 1 then 该虚拟地址指示的所需页存放在主存中 else 该虚拟地址指示的所需页存放在第二级存储器中 访问权限 R = 只读, R/W = 读 / 写, X = 只可执行 If 访问的类别与指定的访问权限不相符, then 保护违例故障 (protection_violation_fault) If 没有设置有效位 (V)then 缺页 (page fault)
地址映射算法 保护故障 (Protection Fault) 访问权限违例 ( access rights violation): 向硬件 微码或软件故障处理机制发出自陷处理请求 缺页 (Page Fault): 所需页没有驻留在物理存储器中, 也将导致自陷, 通常还伴随着上下文切换 (context switch) 当从第二级存储中访取页面时, 当前进程挂起 例如,VAX 11/780 每个进程可以看到 4 G (2 32 字节 ) 的虚拟地址空间 1/2 用于用户区域 1/2 用于被所有进程共享的系统区域 页面大小为 512 字节
碎片和再分配 碎片 (Fragmentation) 是由于某种原因, 存储空间中的一些区域变得不可利用 再分配 (Relocation): 将程序或数据移动到地址空间中一个新的区域 ( 可能需要调整所有的指针 ) 外部碎片 (External Fragmentation): 数据块之间的剩余空间 内部碎片 (Internal Fragmentation): 程序大小通常并不是页面大小的整数倍, 最后一个页帧中就会出现 浪费 0 1. 已占用.. k-1
最佳页面大小 选择页面大小使得碎片最少 页面大小大 内部碎片变得严重 但是增加页面数量 / 名字空间 更大的页表 一般而论, 通常需要增加页面大小, 这是因为, 随着 RAM 价格下降, 存储器变得更大 处理器速度和磁盘速度之间的差距变大 编程人员需要越来越大的虚拟地址空间 当今, 大多数机器的页面大小为 4K 字节, 另外, 页面大小有继 续增加的趋势
碎片 ( 续 ) 页表碎片 (Table Fragmentation): 当页表非常大时, 就出现了页表碎片, 这是因为虚拟地址空间很大, 直接映射页表可能占据很大的存储空间 例如 : VAX 系统结构 注意 : 这意味着页表将需要 2 21 表项, 每个表项 4 字节长, 总共 8 M 字节 可供选择的方案 : 21 9 XX 页号 偏移量 00 用户进程的 P0 区域 01 用户进程的 P1 区域 10 系统名字空间 (1) 硬件相联映射 : 每个页帧需要一个表项 (O( M )), 而不是每个页一个表项 (O( N )) (2) 基于散列表的 软件 方案 ( 反向页表 :inverted page table) 页号 偏移量 是否出现访问权限页号物理地址 页表 相联存储或散列查找页号 ( 页号域 )
2 级页表 根页表 4 字节 第二级页表 物理地址 4 字节 物理地址 数据页 段 0 256 P0 1 K D0 4 K 段 1 物理地址... 物理地址...... P255 D1023 段 255 物理存储器中 256K 字节 在系统虚拟地址空间分配的 1 M 字节 在用户虚拟地址空间分配 2 8 8 2 2 10 12 x x x 2 = 2 38
页替换算法 就像 Cache 块替换算法一样! 最近最少使用 : 选择出最近最少使用的页面来替换 需要有关过去访问页面的信息, 非常难以实现 ( 将页表项根据从最近最多访问到最近最少访问的次序排序 ; 当一个页面被访问时, 将它移动到列表的头部 ; 于在列表尾部的页表项就是将被替换出的页表项 ) 性能很好, 遵从了局部性原则
页面替换 ( 续 ) 非最近使用 : 与每个页面相关联的是一个访问标志 : 访问标志 (reference flag) = 1 如果该页在最近的过去被访问过 = 0 否则 如果需要替换, 选择任意一个访问标志为 0 的页帧替换掉 该页是在最近的过去没有被访问过的页 非最近使用 (NRU) 替换策略的实现 : 页表表项 1 0 1 0 1 0 0 0 访问位 页表表项 最近替换指针 (lrp) 如果需要进行替换, 将 lrp 前移到下一个页表项 ( 与表的大小取模 ) 直到发现一个具有 0 位的页表项 ; 这就是要替换的目标 ; 在上述工作的同时, 将所有检查过的页表项的访问位置为 0 一种优化的策略是查找最近既没有被访问, 又 不脏 的页
按需调页和预取页面 访取策略 (Fetch Policy) 何时将该页换入存储器? 如果只有在缺页时才将页面调入, 那么这种策略就称为 按需调页 (demand paging) 另外一种选择方案是预取 (prefetching): 预测未来的访问, 在实际使用这些页面之前, 预先装入 + 减少了页面传输的开销 - 将移出已经在页帧中的页, 从而不利于缺页率 - 预测未来访问通常很困难 绝大多数系统只实现了按需调页, 而没有实现预测
虚拟地址和 Cache CPU VA PA miss Trans- Cache lation hit Main Memory data 需要一次额外的存储访问来将虚拟地址变换成物理地址 这使得 cache 访问的代价非常高, 而且这也是我们希望尽可能快得执行的 最内层循环 思考 : 为什么总是用物理地址来访问 cache? 虚拟地址 cache 有一个很难对付的问题! 同义问题 (synonym problem): 两个不同的虚拟地址可以映射到同一物理地址 => 两个不同的 cache 表项包含对同一物理地址的数据! 对于更新 : 必须更新所有具有同一物理地址的 cache 表项或者允许存储器不一致 确定上述情况需要大量的硬件, 特别是需要对物理地址标签进行相联查找以确定是否出现多次命中
快表 (TLB) 加速地址变换的一种方式是使用一种关于最近使用页表表项的特殊 cache 它有很多名字, 但最经常使用的名字是变换旁视缓冲器 (Translation Lookaside Buffer:TLB) 或快表! 虚拟地址物理地址脏位访问有效位访问方式 TLB 访问时间与 Cache 访问时间是可比的 ( 但要小一些 ) ( 也比主存访问时间要小得多 )
变换旁视缓冲器 就像其他的 cache, TLB 可以是全相联的 组相联的, 也可以是直接映射的 TLB 一般较小, 通常即使在高性能机器中也只有 128-256 个表项 这样就可以实现全相联查找 大多数中等性能的机器使用 n 路组相联的组成 使用 TLB 的地址变换 CPU hit VA PA miss TLB Cache Lookup miss Translation hit Main Memory 1/2 t data t 20 t
减少变换时间 具有 TLB 的机器可以进一步降低时钟周期数 / Cache 访问 可以将 Cache 访问与 TLB 访问重叠 由于使用虚拟地址中的高位来查找 TLB, 而用低位来作为访问 Cache 的索引, 因而上述策略可以工作
Cache 和 TLB 访问重叠 32 TLB 相联查找 index Cache 1 K 10 2 4 bytes 00 PA Hit/ Miss 20 12 page # disp PA Data Hit/ Miss IF cache 命中 AND (cache 标签 = 物理地址 ) THEN 将数据提交给 CPU ELSE IF [cache 失效 OR (cache 标签 = 物理地址 )] AND TLB 命中 THEN 用 TLB 中的物理地址来访问存储器 ELSE 做正常的虚拟地址变换 =
重叠 TLB 访问的问题 重叠的访问只能当用于对 cache 进行索引的地址位不会作为虚拟地址变换的结果而改变时, 才能正常工作 这通常只适用于小 cache 和大页面大小或者高 n 路组相联的大 cache 例如 : 假设 cache 的容量从 4K 增长到 8K, 而其他都不变 11 2 cache 索引 00 20 12 虚拟页号 偏移量 解决方案 : 变成 8K 字节的页面大小变成 2 路组相联 cache ( 仍然使用 10 位索引 ) 这一位被虚拟地址变换所改变, 但是 cache 查找时也需要 1K 10 2 路组相联 cache 4 4
分段 ( 参见 x86) 相对于分页 ( 通常与分页结合使用 ) 每个程序模块分配一段 ; 可能具有不同的大小 ; 段是物理存储器和 磁盘之间传输的基本单位 段号 偏移量 Present 访问方式段长物理始地址 BR 段表 物理地址 + 出现位 故障 : 段失效 (Present = 0) 溢出 (Displacement 超出了段长 ) 保护违例 ( 访问与段保护不相符 ) 基于段的寻址通常用于实现存储器的能力 (capabilities), 例如, 硬件支持复杂的保护机制
基于段的寻址方式缺点 : (1) 对可变大小的块进行存储分配 (2) 外部碎片 : 这种物理存储器分配可能导致所有可用的空间片都不足以再分配给任何一段 在运行时解决这一问题非常费时 段式和页式结合 : 段页式策略 虚拟地址 段号页号偏移量 IBM 中使用 : 4K 字节页面 16 x 1 M 字节或 64 x 64 K 字节段
虚拟存储器的历史 自从发明虚拟存储器至今, DRAM 已经增大了 64,000 倍 今天, 系统缺页率已经非常低 那么, 是否可以放弃虚拟存储呢?
结论一 虚拟存储是作为存储层次的另外一层发明的 当时的争论是 : 软件是否可以自动在许多程序之间管理 64KB 存储器? DRAM 容量的迅猛增长消除了这一争论 今天, 虚拟存储器可以使得多个进程共享同一存储, 而无需将所有进程交换到磁盘, 这时保护就非常重要 ( 多级 ) 页表将虚地址映射到物理地址 TLB 对于快速变换非常重要 TLB 失效对性能影响很大
结论二 算法理论和编译基于操作的数目 编译将消除一些操作, 并简化一些操作 : 整数加法 << 整数乘法 << 浮点加法 << 浮点乘法 高级流水线 => 这些操作将需要相同的时间 随着时钟频率增高和流水线加深, 指令将需要越来越少的时间, 但是 DRAM 的速度提高却低得多 今天, 执行时间是 ( 操作数,cache 失效 ) 的函数 考虑到 cache 的重要性, 这对下面主题意味着什么 : 编译器? 数据结构? 算法?