Training

Size: px

Start display at page:

Download "Training"

敛暴索
7 years ago
Views:

1 计算机组织与系统结构虚拟存储器 Virtual Memory ( 第十九讲 ) 程旭

2 容量访问时间成本 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 控制字节操作系统 512-4K 字节较高级别较快用户 / 操作员 Mbytes 较大较低级别

3 存储所有我们已读 ( 写 ) 听 ( 说 ) 看的信息人类数据类型 / 小时 / 天 (/4 年 ) / 一生阅读文字 ( 含少量图片 ) 200 K 2-10 M/G 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

4 一部小说美国国会图书馆 ( 文字 ) 美国国会图书馆 ( 声音 + 电影 ) Kilo Mega Giga Tera Peta 1 封信 1 部电影美国国会图书馆 ( 图像 ) 所有磁盘 Exa 所有相片所有磁带 Zetta Yotta 现在的所有信息

5 本讲提纲重温存储层次和 Cache 引论虚拟存储器页表和快表 (TLB) 保护存储层次对计算机科学其他学科的影响

6 虚拟存储提供一种理想中的非常非常大的存储器许多工作所需存储器的总和大于实际的物理存储器每个工作的地址空间大于实际的物理存储器使得可利用的 ( 快速昂贵 ) 的物理存储器得以很好地利用简化存储器的管理 ( 当今, 使用虚拟存储技术的主要原因 ) 使用存储层次, 保持平均访问时间很低至少包括两级存储层次 : 主存和二级存储虚拟地址程序员使用的地址虚拟地址空间上述地址的集合存储器地址物理存储器中存储字的地址, 也称为物理地址或实地址 ( Real address)

虚拟存储系统设计的基本问题从二级存贮器向主存传输信息块的大小某信息块的访问需要引入存储 M, 但是 M 已经装满, 那么 M 中的一些区域就必须释放, 为新的信息块腾出空间替换策略 (replacement policy) M 中的哪个区域将安放新的信息块放置策略 (placement

7 虚拟存储系统设计的基本问题从二级存贮器向主存传输信息块的大小某信息块的访问需要引入存储 M, 但是 M 已经装满, 那么 M 中的一些区域就必须释放, 为新的信息块腾出空间替换策略 (replacement policy) M 中的哪个区域将安放新的信息块放置策略 (placement policy ) 失效的信息项只有在出现页面失效 (fault) 时, 才从第二级存储器中取出读取 / 装入策略 (fetch/load policy) reg cache mem disk frame pages 分页组织虚拟和物理地址被划分为同等大小的信息块页帧 (page frames) 页 (pages)

8 地址映射 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 完成这一传输

9 分页组织物理地址页帧物理存储器 1K 1K 1K 地址变换映射页 0 1 1K 1K 映射单位也是从虚拟存储器到物理存储器的传输单位 K 虚拟存储器地址映射 10 虚拟地址页号偏移量页表基址寄存器到页表的索引 V 页表访问权限 PA + 实际上, 经常采用串联方式位于物理存储器的表物理存储器地址

10 地址映射算法 If V = 1 then 该虚拟地址指示的所需页存放在主存中 else 该虚拟地址指示的所需页存放在第二级存储器中访问权限 R = 只读, R/W = 读 / 写, X = 只可执行 If 访问的类别与指定的访问权限不相符, then 保护违例故障 (protection_violation_fault) If 没有设置有效位 (V)then 缺页 (page fault)

11 地址映射算法保护故障 (Protection Fault) 访问权限违例 ( access rights violation): 向硬件微码或软件故障处理机制发出自陷处理请求缺页 (Page Fault): 所需页没有驻留在物理存储器中, 也将导致自陷, 通常还伴随着上下文切换 (context switch) 当从第二级存储中访取页面时, 当前进程挂起例如,VAX 11/780 每个进程可以看到 4 G (2 32 字节 ) 的虚拟地址空间 1/2 用于用户区域 1/2 用于被所有进程共享的系统区域页面大小为 512 字节

12 碎片和再分配碎片 (Fragmentation) 是由于某种原因, 存储空间中的一些区域变得不可利用再分配 (Relocation): 将程序或数据移动到地址空间中一个新的区域 ( 可能需要调整所有的指针 ) 外部碎片 (External Fragmentation): 数据块之间的剩余空间内部碎片 (Internal Fragmentation): 程序大小通常并不是页面大小的整数倍, 最后一个页帧中就会出现浪费 0 1. 已占用.. k-1

13 最佳页面大小选择页面大小使得碎片最少页面大小大内部碎片变得严重但是增加页面数量 / 名字空间更大的页表一般而论, 通常需要增加页面大小, 这是因为, 随着 RAM 价格下降, 存储器变得更大处理器速度和磁盘速度之间的差距变大编程人员需要越来越大的虚拟地址空间当今, 大多数机器的页面大小为 4K 字节, 另外, 页面大小有继续增加的趋势

14 碎片 ( 续 ) 页表碎片 (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) 页号偏移量是否出现访问权限页号物理地址页表相联存储或散列查找页号 ( 页号域 )

15 2 级页表根页表 4 字节第二级页表物理地址 4 字节物理地址数据页段 P0 1 K D0 4 K 段 1 物理地址... 物理地址 P255 D1023 段 255 物理存储器中 256K 字节在系统虚拟地址空间分配的 1 M 字节在用户虚拟地址空间分配 x x x 2 = 2 38

16 页替换算法就像 Cache 块替换算法一样! 最近最少使用 : 选择出最近最少使用的页面来替换需要有关过去访问页面的信息, 非常难以实现 ( 将页表项根据从最近最多访问到最近最少访问的次序排序 ; 当一个页面被访问时, 将它移动到列表的头部 ; 于在列表尾部的页表项就是将被替换出的页表项 ) 性能很好, 遵从了局部性原则

17 页面替换 ( 续 ) 非最近使用 : 与每个页面相关联的是一个访问标志 : 访问标志 (reference flag) = 1 如果该页在最近的过去被访问过 = 0 否则如果需要替换, 选择任意一个访问标志为 0 的页帧替换掉该页是在最近的过去没有被访问过的页非最近使用 (NRU) 替换策略的实现 : 页表表项访问位页表表项最近替换指针 (lrp) 如果需要进行替换, 将 lrp 前移到下一个页表项 ( 与表的大小取模 ) 直到发现一个具有 0 位的页表项 ; 这就是要替换的目标 ; 在上述工作的同时, 将所有检查过的页表项的访问位置为 0 一种优化的策略是查找最近既没有被访问, 又不脏的页

18 按需调页和预取页面访取策略 (Fetch Policy) 何时将该页换入存储器? 如果只有在缺页时才将页面调入, 那么这种策略就称为按需调页 (demand paging) 另外一种选择方案是预取 (prefetching): 预测未来的访问, 在实际使用这些页面之前, 预先装入 + 减少了页面传输的开销 - 将移出已经在页帧中的页, 从而不利于缺页率 - 预测未来访问通常很困难绝大多数系统只实现了按需调页, 而没有实现预测

19 虚拟地址和 Cache CPU VA PA miss Trans- Cache lation hit Main Memory data 需要一次额外的存储访问来将虚拟地址变换成物理地址这使得 cache 访问的代价非常高, 而且这也是我们希望尽可能快得执行的最内层循环思考 : 为什么总是用物理地址来访问 cache? 虚拟地址 cache 有一个很难对付的问题! 同义问题 (synonym problem): 两个不同的虚拟地址可以映射到同一物理地址 => 两个不同的 cache 表项包含对同一物理地址的数据! 对于更新 : 必须更新所有具有同一物理地址的 cache 表项或者允许存储器不一致确定上述情况需要大量的硬件, 特别是需要对物理地址标签进行相联查找以确定是否出现多次命中

20 快表 (TLB) 加速地址变换的一种方式是使用一种关于最近使用页表表项的特殊 cache 它有很多名字, 但最经常使用的名字是变换旁视缓冲器 (Translation Lookaside Buffer:TLB) 或快表! 虚拟地址物理地址脏位访问有效位访问方式 TLB 访问时间与 Cache 访问时间是可比的 ( 但要小一些 ) ( 也比主存访问时间要小得多 )

21 变换旁视缓冲器就像其他的 cache, TLB 可以是全相联的组相联的, 也可以是直接映射的 TLB 一般较小, 通常即使在高性能机器中也只有个表项这样就可以实现全相联查找大多数中等性能的机器使用 n 路组相联的组成使用 TLB 的地址变换 CPU hit VA PA miss TLB Cache Lookup miss Translation hit Main Memory 1/2 t data t 20 t

22 减少变换时间具有 TLB 的机器可以进一步降低时钟周期数 / Cache 访问可以将 Cache 访问与 TLB 访问重叠由于使用虚拟地址中的高位来查找 TLB, 而用低位来作为访问 Cache 的索引, 因而上述策略可以工作

23 Cache 和 TLB 访问重叠 32 TLB 相联查找 index Cache 1 K bytes 00 PA Hit/ Miss page # disp PA Data Hit/ Miss IF cache 命中 AND (cache 标签 = 物理地址 ) THEN 将数据提交给 CPU ELSE IF [cache 失效 OR (cache 标签 = 物理地址 )] AND TLB 命中 THEN 用 TLB 中的物理地址来访问存储器 ELSE 做正常的虚拟地址变换 =

24 重叠 TLB 访问的问题重叠的访问只能当用于对 cache 进行索引的地址位不会作为虚拟地址变换的结果而改变时, 才能正常工作这通常只适用于小 cache 和大页面大小或者高 n 路组相联的大 cache 例如 : 假设 cache 的容量从 4K 增长到 8K, 而其他都不变 11 2 cache 索引虚拟页号偏移量解决方案 : 变成 8K 字节的页面大小变成 2 路组相联 cache ( 仍然使用 10 位索引 ) 这一位被虚拟地址变换所改变, 但是 cache 查找时也需要 1K 10 2 路组相联 cache 4 4

25 分段 ( 参见 x86) 相对于分页 ( 通常与分页结合使用 ) 每个程序模块分配一段 ; 可能具有不同的大小 ; 段是物理存储器和磁盘之间传输的基本单位段号偏移量 Present 访问方式段长物理始地址 BR 段表物理地址 + 出现位故障 : 段失效 (Present = 0) 溢出 (Displacement 超出了段长 ) 保护违例 ( 访问与段保护不相符 ) 基于段的寻址通常用于实现存储器的能力 (capabilities), 例如, 硬件支持复杂的保护机制

26 基于段的寻址方式缺点 : (1) 对可变大小的块进行存储分配 (2) 外部碎片 : 这种物理存储器分配可能导致所有可用的空间片都不足以再分配给任何一段在运行时解决这一问题非常费时段式和页式结合 : 段页式策略虚拟地址段号页号偏移量 IBM 中使用 : 4K 字节页面 16 x 1 M 字节或 64 x 64 K 字节段

27 虚拟存储器的历史自从发明虚拟存储器至今, DRAM 已经增大了 64,000 倍今天, 系统缺页率已经非常低那么, 是否可以放弃虚拟存储呢?

28 结论一虚拟存储是作为存储层次的另外一层发明的当时的争论是 : 软件是否可以自动在许多程序之间管理 64KB 存储器? DRAM 容量的迅猛增长消除了这一争论今天, 虚拟存储器可以使得多个进程共享同一存储, 而无需将所有进程交换到磁盘, 这时保护就非常重要 ( 多级 ) 页表将虚地址映射到物理地址 TLB 对于快速变换非常重要 TLB 失效对性能影响很大

29 结论二算法理论和编译基于操作的数目编译将消除一些操作, 并简化一些操作 : 整数加法 << 整数乘法 << 浮点加法 << 浮点乘法高级流水线 => 这些操作将需要相同的时间随着时钟频率增高和流水线加深, 指令将需要越来越少的时间, 但是 DRAM 的速度提高却低得多今天, 执行时间是 ( 操作数,cache 失效 ) 的函数考虑到 cache 的重要性, 这对下面主题意味着什么 : 编译器? 数据结构? 算法?

Microsoft PowerPoint - chx06_org19_memoryhierarchy.ppt

Microsoft PowerPoint - chx06_org19_memoryhierarchy.ppt 计算机组织与系统结构虚拟存储器 Virtual Memory ( 第十九讲 ) 程旭 2006.6.1 局部性原理访问的可能性局部性原理 : 0 地址空间 2 程序在一定的时间段内通常只会访问地址空间较小的部分例如 :10% 的代码将耗费 90% 的程序执行时间两种不同类型的局部性 : 时间局部性 (Temporal Locality): 如果一个信息项正在被访问, 那么在近期她很可能还会被再次访问