<4D F736F F F696E74202D20B5DACBC4D5C220B4E6B4A2C6F7B2E3B4CEBDE1B9B92E707074>

Transcription

1 Ch4: Memory Hierarchy 存储器层次结构 第一讲基本概念和主存储器第二讲高速缓冲存储器 (Cache) 第三讲虚拟存储器 (Virtual Memory) 1

2 第一讲基本概念和主存储器 主要内容 信息的存储 传送 处理单位的含义 记忆单元 / 编址单位 / 存储单位 / 传输单位 / 机器字长 存储器分类 可按存取方式 / 易失性 / 可更改性 / 元器件 / 功能来分 半导体存储器随机访问存储器 SRAM 的原理和特点 DRAM 的原理和特点 RAM 芯片组织 如何由记忆单元构成存储阵列 如何读写存储阵列中的信息 如何由芯片构成存储器 提高存储器速度的措施 : 芯片内采用行缓存, 同行内数据直接从缓存中取 采用多模块存储器, 多个存储器交叉存取 引入 Cache( 下一讲的主要内容 ) memory.2

3 回顾 : 存储器基本术语 记忆单元 ( 存储基元 / 存储元 / 位元 ) (Cell) 具有两种稳态的能够表示二进制数码 0 和 1 的物理器件存储单元 / 编址单位 (Addressing Unit) 主存中具有相同地址的那些位构成一个存储单元, 也称为一个编址单位存储体 / 存储矩阵 / 存储阵列 (Bank) 所有存储单元构成一个存储阵列编址方式 (Addressing Mode) 对存储体中各存储单元进行编号的方式 按字节编址 ( 基本上现代计算机都按字节编址 ) 按字编址 ( 早期有机器按字编址 ) 存储器地址寄存器 (Memory Address Register - MAR) 用于存放主存单元地址的寄存器 存储器数据寄存器 ( Memory Data Register-MDR(MBR) ) 用于存放主存单元中的数据的寄存器 memory.3

4 机器字长 回顾 : 存储器基本术语 运算器中参加运算的寄存器的位数, 即 : 数据通路的宽度 存储字 存储芯片中的一个读写单位, 一般等于芯片的数据线宽度 ( 注 : 最好存储器按机器字长组织成一个 自然 单位 它的长度一般应等于一个数或指令的位数 但很多机器的数据和指令都是变长的 ) 编址单位 一个存储单元的位数 现在都按字节编址, 即编址单位为 8 位 传输单位 对主存而言, 指一次从主存读出或写入的数的位数, 它可以不等于存储字的长度, 也可不等于编址单位 对外存而言, 数据通常按块传输, 传输单位为块 ( 例如 :386/486 等, 其编址单位为字节, 字长为 32 位, 单字位数为 16 位, 但传输单位可以是 8/16/24/32 位 ) memory.4

5 依据不同的特性有多种分类方法 (1) 按工作性质 / 存取方式分类 回顾 : 存储器分类 随机存取存储器 Random Access Memory (RAM) 每个单元的读写时间一样, 且与各单元所在位置无关 如 : 内存 ( 注 : 原意主要强调地址译码时间相同 现在的 DRAM 芯片采用行缓冲, 因而可能因为位置不同而使访问时间有所差别 ) 顺序存取存储器 Sequential Access Memory (SAM) 数据按顺序从存储载体的始端读出或写入, 因而存取时间的长短与信息所在位置有关 例如 : 磁带 直接存取存储器 Direct Access Memory(DAM) 利用一个共享读写机制, 直接定位到要读写的数据块, 在读写某个数据块时按顺序进行 例如 : 磁盘 相联存储器 Associate Memory or Content Addressed Memory (CAM) 按内容检索到存储位置进行读写 例如 : 快表 memory.5

6 回顾 : 存储器分类 (2) 按存储介质分类 半导体存储器 : 双极型, 静态 MOS 型, 动态 MOS 型 磁表面存储器 : 磁盘 (Disk) 磁带 (Tape) 光存储器 :CD,CD-ROM,DVD (3) 按信息的可更改性分类 读写存储器 (Read / Write Memory): 可读可写 只读存储器 (Read Only Memory): 只能读不能写 (4) 按断电后信息的可保存性分类 非易失 ( 不挥发 ) 性存储器 (Nonvolatile Memory) 信息可一直保留, 不需电源维持 ( 如 :ROM 磁表面存储器 光存储器等) 易失 ( 挥发 ) 性存储器 (Volatile Memory) 电源关闭时信息自动丢失 ( 如 :RAM Cache 等 ) memory.6

7 回顾 : 存储器分类 (5) 按功能 / 容量 / 速度 / 所在位置分类 寄存器 (Register) 封装在 CPU 内, 用于存放当前正在执行的指令和使用的数据 用触发器实现, 速度快, 容量小 ( 几十个 ) 高速缓存 (Cache) 位于 CPU 内部或附近, 用来存放当前要执行的局部程序段和数据 用 SRAM 实现, 速度可与 CPU 匹配, 容量小 ( 几 MB) 内存储器 MM( 主存储器 Main (Primary) Memory) 位于 CPU 之外, 用来存放已被启动的程序及所用的数据 用 DRAM 实现, 速度较快, 容量较大 ( 几 GB) 外存储器 AM ( 辅助存储器 Auxiliary / Secondary Storage) 位于主机之外, 用来存放暂不运行的程序 数据或存档文件 用磁表面或光存储器实现, 容量大而速度慢 memory.7

8 回顾 : 内存与外存的关系及比较 该任务的程序和数据从外存成批传到内存 5 任务完成后, 将处理得到的全部结果成批传送到外存以长久保存 指令 1 指令 2 指令 k 指令 n 数据 2 数据 m 外存储器 ( 简称外存或辅存 ) 存取速度慢 成本低 容量很大 不与 CPU 直接连接, 程序运行时, 外存中的程序及相关数据须先传送到内存, 然后才能被 CPU 使用 属于非易失性存储器 (Nonvolatile), 用于长久存放系统中几乎所有的信息 程序数据 1 数据1 任务启动时, 执行 CPU 2CPU 从内存中逐条存读取该程序的指令及 3 逐条执行相关的数据储指令, 按指令要求完成器外存储器对数据的运 4 将指令的运算处理算和处理结果送回内存保存 内存储器 ( 简称内存或主存 ) 存取速度快 成本高 容量相对较小时存放正在运行的程序和数据内 直接与 CPU 连接,CPU( 指令 ) 可以对内存中的指令及数据进行读 写操作 属于易失性存储器 (volatile), 用于临 memory.8

9 地址寄存器地址译码器问题 : 主存中存放的是什么信息?CPU 何时会访问主存? 读 / 写的数据 MDR 主存地址 MAR CPU 读 / 写控制信号 数据线 (64 位 ) 地址线 (36 位 ) 控制线 iii 读写控制电路 MM 记忆单元iii 存储单元地址 存储内容 主存是 CPU 可直接访问的存储器, 用于存放供 CPU 处理的指令和数据 性能指标 : 以字节为单位进行连续编址, 每个存储单元为 1 个字节 (8 个二进位 ) 存储容量 : 主存储器中所包含的存储单元的总数 ( 单位 :MB 或 GB) 存取时间 T A : 从 CPU 送出内存单元的地址码开始, 到主存读出数据并送到 CPU( 或者是把 CPU 数据写入主存 ) 所需要的时间 ( 单位 :ns,1 ns = 10-9 s) 存储周期 T MC : 连读两次访问存储器所需的最小时间间隔, 它应等于存取时间加上下一存取开始前所要求的附加时间, 因此,T MC 比 T A 大 ( 因为存储器由于读出放大器 驱动电路等都有一段稳定恢复时间, 所以读出后不能立即进行下一次访问 )

10 时间 存储容量 ( 或带宽 ) 的单位 memory.10 Notations and Conventions for Numbers H P CPrefix Appendix1: Abbreviation Notations Meaning and Conventions Numeric for Numbers Value Amill m One thousandth 10-3 micro µ One millionth nano n One billionth pico p One trillionth 10 1femto f One quadrillionth atta a One quintillionth kilo K (or k) Thousand 10 or mega M Million 10 or 2 giga G Billion or 2 tera T Trillion or 2 peta P Quadrillion or 2 exa E Quintillion or 2 61

11 回顾 : 内存储器的分类及应用 内存由半导体存储器芯片组成, 芯片有多种类型 : 半导体存储器 随机存取存储器 (RAM) 静态随机存取存储器 SRAM 动态随机存取存储器 DRAM ( 用作 Cache 存储器 ) 每个存储单元 (cell) 由 6 个晶体管组成 只要加上电源, 信息就能一直保持 对电器干扰相对不很敏感 比 DRAM 更快, 也更贵 ( 用作主存储器 ) 每个存储单元由 1 个电容和 1 个晶体管组成. 每隔一段时间必须刷新一次 对电器干扰比较敏感 比 SRAM 慢, 但便宜 只读存储器 (ROM) 不可在线改写内容的 ROM 快擦除存储器 (Flash ROM) ( 用作 BIOS 存储器 ) ( 图形卡 硬盘控制器 ) memory.11

12 回顾 : 六管静态 MOS 管电路 位线 D 6 管静态 NMOS 记忆单元 位线 D U DD V 2 V 4 V 5 Q V 1 V 3 Q V 6 位线 D 位线 D 行选线 字线 X 存储单元 存储单元 信息存储原理 : 看作带时钟的 RS 触发器 写入时 : - 位线上是被写入的二进位信息 0 或 1 - 置字线为 1 - 存储单元 ( 触发器 ) 按位线的状态设置成 0 或 1 memory.12 I / O V 7 V 8 列选线 Y I / O SRAM 中数据保存在一对正负反馈门电路中, 只要供电, 数据就一直保持, 所以不是破环性读出, 也不需要重写数据来保持数据不变 即 : 无需刷新! 读出时 : - 置 2 个位线为高电平 - 置字线为 1 - 根据存储单元的状态改变位线的输出电平

13 回顾 : 记忆单元的基本原理 动态单管 MOS 记忆单元电路 构造和表示 : 数据记忆在电容 C S 上,T 为门控管, 控制数据的进出 其栅极接读 / 写选择线 ( 字线 ), 漏和源分别接数据线 ( 位线 ) 和记忆电容 C S 数据 1 或 0 以电容 C S 上电荷量的有无来判别 读写原理 : 在选择 ( 字 ) 线上加高电平, 使 T 管导通 写 0 时, 在数据线上加低电平, 使 C S 上电荷对数据线放电 ; 写 1 时, 在数据线上加高电平, 使数据线对 C S 充电 ; 读出时, 在数据线上有一读出电压 它与 C S 上电荷量成正比 优点 : 电路元件少, 功耗小, 集成度高, 所以被广泛应用于大容量存储器中 缺点 : 速度慢 是破坏性读出 ( 读后状态被改变, 需读后再生 ) 需定时刷新 DRAM 的一个重要特点是, 数据以电荷的形式保存在电容中, 电容的放电使得电荷通常只能维持几个毫秒左右, 相当于 1M 个时钟周期左右, 因此要定期进行刷新 ( 读出后重新写回 ), 按行进行 ( 所有芯片中的同一行一起进行 ), 刷新操作所需时间通常只占 1%~2% 左右 字线 位线 接地 memory.13

14 回顾 : 半导体 RAM 的组织 记忆单元 (Cell) 存储器芯片 (Chip) 内存条 ( 存储器模块 ) 存储器芯片 : 存储体 + 外围电路 ( 地址译码和读写控制 ) 存储体 (Memory Bank): 由记忆单元 ( 位元 ) 构成的存储阵列 记忆单元的组织 : 字线 W 选择线 ( 字线 ) 位元 位元 位线 S 0 位线 S 1 数据线 ( 位线 ) 读写控制 R/W 读写控制 R/W Din Dout Din Dout memory.14

15 地址驱动线 回顾 : 字片式存储体阵列组织 X 向译码器 一维地址译码系统 假定有 m 位地址, 则地址译码驱动 ( 选择 ) 线的条数为多少? 有 2 m 条! 一般 SRAM 为字片式芯片, 只在单方向上译码, 同时读出一条字线上的所有位! memory.15

16 回顾 : 位片式存储体阵列组织 memory.16 假定有 m 位地址, 其地址译码驱动 ( 选择 ) 线的条数为多少? 有 2 m/2+1 位片式可在字方向和位方向扩充, 需要有片选信号!

17 回顾 : 位片式芯片框图 memory.17

18 位扩展为芯片位数的 16 倍 字扩展为芯片字数的 4 倍 问题 : 共几位地址? 几位选片, 几位片内选址? 编址单位是多少? 共 12 位地址, 高两位用来选片, 低 10 位用于片内选址, 编址单位为 16 位 memory.18

19 举例 :TMS4116 动态 MOS 存储器芯片 总体性能 : 存储容量 :16K x 1 位 7 根地址线复用 (2x7=14) 芯片引脚 芯片框图 地址缓冲器和地址译码器 存储阵列 读出再生放大器 基本时序 读写操作定时由 4116 芯片构成 64K 字 X16 位的存储器 问题 :CPU 送出的地址有几位? 送到 4116 芯片的地址有几位? CPU 送出的地址位数由主存空间大小决定 ; 送 4116 有 14 位地址 问题 :7 个地址引脚何时送行地址? 何时送列地址? RAS 有效时送行地址 CAS 有效时送列地址 memory.19 问题 :WE 的含义是什么? WE 低时写操作, 高时读操作

20 memory.20

21 ST0 结束时, 清除地址缓存器中的信息 memory.21

22 ST1 或 ST4 有效所存行或列地址信息 7 个地址缓存器的输出分别接到地址译码器的 7 个输入每个输入可能 Ai 或 Ai, 共多少种组合? 128 种组合! 行向和列向共 256 个译码器! memory.22

23 每个译码器输出连到一根行线或列线上 memory.23

24 memory.24

25 memory.25

26 memory.26

27 IN memory.27

28 举例 : 典型的 16M 位 DRAM(4Mx4) 16M 位 =4Mb x 4=2048 x 2048 x 4=2 11 x2 11 x4 (1) 地址线 :11 根分时复用, 由 RAS 和 CAS 提供控制时序 (2) 存储字是 4 位, 需四个位平面, 对相同行 列交叉点的四个位一起读 / 写 (3) 内部结构框图 问题 : 为什么每出现新一代存储器芯片, 容量至少提高到 4 倍? 行地址和列地址分时复用, 每出现新一代存储器芯片, 至少要增加一根地址线每加一根地址线, 则行地址和列地址各增加一位, 所以行数和列数各增加一倍 因而容量至少提高到 4 倍 SKIP memory.28

29 所有 DRAM 芯片同时刷新, 由刷新计数器自动计数, 按行刷新 ( 只产生行地址 ), 对 CPU 透明 举例 : 典型的 16M 位 DRAM(4Mx4) 问题 : 刷新计数器的位数是几位? 读 / 写行地址和刷新行地址被送到一个多路选择器, 由内部控制电路选择哪个地址被送到行译码器 四个位平面 BACK memory.29

30 DRAM 芯片的刷新 刷新周期 : 从上次对整个存储器刷新结束到下次对整个存储器全部刷新一遍为止的时间间隔, 为电容数据有效保存期的上限 (64ms) 有三种刷新方式 : 集中式 分散式 异步刷新 1 集中刷新 : 前一段时间正常读 / 写, 后一段时间停止读 / 写, 集中逐行刷新 特点 : 集中刷新时间长, 不能正常读 / 写 ( 死区 ), 很少使用 2 分散刷新 : 一个存储周期分为两段 : 前一段用于正常读 / 写操作, 后一段用于刷新操作 特点 : 不存在死区, 但每个存储周期加长 很少使用 3 异步刷新 : 结合上述两种方式 以 4096 行为例, 在 64ms 时间内必须轮流对每一行刷新一次, 即每隔 64ms/4096=15.625μs 刷新一行 特点 : 结合前两种, 效率高, 用得较多 memory.30

31 CPU 与存储器之间的通信方式 CPU 和主存之间有同步和异步两种通信方式 异步方式 ( 读操作 ) 过程 ( 需握手信号 ) CPU 送地址到地址线, 主存译码 CPU 发读命令, 然后等待存储器发回 完成 信号 主存接收到读命令后, 读数据送至数据线, 然后发 完成 信号给 CPU CPU 接收到 完成 信号, 从数据线取数写操作过程类似 同步方式的特点 CPU 和主存在同一个时钟信号控制下工作, 不需要应答信号 ( 如 完成 ) 主存总是在确定的时间内准备好数据,CPU 送出地址和读命令后, 总是在确定的几个时钟周期后去取数据 存储器芯片必须支持同步方式 memory.31

32 SDRAM 是同步存储芯片 每步操作都在系统时钟控制下进行 确定的等待时间 ( 读命令开始到数据线有效的时间,CAS 潜伏期 )CL, 例如 CL=2 clks 突发传送 BL=1/2/4/8 多体 ( 缓冲器 ) 交叉存取 利用总线时钟上升沿与下降沿同步传送 SDRAM 芯片技术 存储单元阵列 数据总线 DDR SDRAM 存储单元阵列 memory.32 数据总线 DDR2 SDRAM DDR3: 一个时钟内传送 8 个数据

33 特点 : 只读存储器和 Flash 存储器 信息只能读不能写 非破坏性读出, 无需再生 也以随机存取方式工作 信息用特殊方式写入, 一经写入, 就可长久保存, 不受断电影响 故是非易失性存储器 用途 : 用来存放一些固定程序 如监控程序 启动程序等 只要一接通电源, 这些程序就能自动地运行 ; 可作为控制存储器, 存放微程序 还可作为函数发生器和代码转换器 在输入 / 出设备中, 被用作字符发生器, 汉字库等 在嵌入式设备中用来存放固化的程序 memory.33

34 回顾 : 只读存储器 (Read Only Memory) MROM: 腌膜只读存储器 (Mask ROM) PROM: 可编程只读存储器 (Programmable ROM) EPROM: 可擦除可编程只读存储器 (Erasable PROM) EEPROM (E 2 PROM) : 电可擦除可编程只读存储器 (Electrically EPROM) flash memory: 闪存 闪存的读取速度与 DRAM 相近, 是磁盘的 100 倍左右 ; 写数据 ( 快擦 - 编程 ) 则与硬盘相近 (a) 0 状态 (b) 1 状态 (a) 编程 : 写 0 (b) 擦除 : 写 1 (a) 读 0 (b) 读 1 控制栅加足够正电压时, 浮空栅储存大量负电荷, 为 0 控制栅不加正电压时, 浮空栅少带或不带负电荷, 为 1 memory.34 有三种操作 : 编程 读取 擦除 最初都是 1; 编程 : 写 0; 擦除 : 写 1 读出 : 控制栅加正电压, 若为 0, 则读出电路检测不到电流 ; 若为 1, 则检测到电流

35 存储器芯片的扩展 字扩展 位数不变 扩充容量例如, 用 16K 8 位芯片扩展成 64K 8 位存储器, 需几个芯片? 地址范围各是多少? 字方向扩展 4 倍, 即 4 个芯片 FFFH, FFFH, 8000-BFFFH, C000- FFFFH 地址共 16 位, 高两位由外部译码器译码生成 4 个输出, 分别连到 4 个片选信号, 片内地址有 14 位 地址线 读 / 写控制线等对应相接, 片选信号则分别与外部译码器各个译码输出端相连位扩展 字数不变, 位数扩展例如, 用 位芯片构成 4K 8 位存储器, 需几个芯片? 地址范围各是多少? 位方向扩展 8 倍, 字方向无需扩展 即 8 个芯片, 地址范围都一样 :000-FFFH 地址共 12 位, 全部作为片内地址 芯片的地址线及读 / 写控制线对应相接, 而数据线单独引出, 没有外部译码器字位同时扩展 字和位同时扩展例如, 用 16K 4 位芯片构成 64K 8 位存储器, 需几个芯片, 地址范围各是多少? 字向 4 倍 位向 2 倍,8 个芯片 FFFH, FFFH, 8000-BFFFH, C000- FFFFH 地址线 读 / 写控制线等对应相接, 片选信号则分别与外部译码器各个译码输出端相连 有两种容量扩展方式 : 交叉编址和连续编址 memory.35

36 举例 :128MB 的 DRAM 存储器 问题 : 芯片内地址是否连续? 不连续, 是交叉编址方式! 可同时读写所有芯片 地址 A 问题 : 如果高位地址用作片选, 则情况如何? DRAM 行 bits ( 行地址 i, 列地址 j) bits bits bits bits bits DRAM 0 bits 8-15 bits 0-7 总容量 128 MB 由 8 片 DRAM 芯片构成 每片 16Mx8 bits 行地址 列地址各 12 位为什么呢? 每 1 行共 4096 列 (8 位 / 列 ) 选中某一行并读出之后再由列地址选择其中的一列 (8 个二进位 ) 送出 连续编址, 不可同时读写多个芯片 memory 问题 : 地址范围? 存储器地址位数 27 位, 片内地址 24 位, 与高 24 位存储器地址相同 范围 : FFFFFFH 主存储器地址 A 处的 64-bit 数据 最多读 64 位 0 存储控制器 : 行 列地址为 (i,j) 的 8 个单元 低 3 位地址的作用是什么? 确定 8 个字节中的哪个, 用来进行片选

37 举例 :SPARCstation 20 s Memory Module SPARCstation 20 Memory Controller SIMM Slot 0 SIMM Slot 1 SIMM Slot 2 SIMM Slot 3 SIMM Slot 4 SIMM Slot 5 SIMM Slot 6 SIMM Slot 7 Memory Bus 存储器总线的宽度为 128 位 DRAM SIMM DRAM DRAM DRAM DRAM DRAM DRAM DRAM DRAM DRAM DRAM 每个内存条最多能同时读出 128 位数据 memory.37 每次访存操作总是在某一个内存条内进行!

38 举例 :SPARCstation 20 s Memory Module one memory module ( 内存条 ) Smallest: 4 MB = 16x 2Mb DRAM chips, 8 KB of Page Mode SRAM Biggest: 64 MB = 32x 16Mb chips, 16 KB of Page Mode SRAM 每个芯片有 512 行 x512 列, 并有 8 个位平面每次读 / 写各芯片内同行同列的 8 位, 共 16x8=128 位 问题 : 行缓冲数据的地址有何特点? 一定在同行中, 故行地址相同! 512 rows 512 cols DRAM Chip 0 256K x 8 = 2 Mb 8 bits DRAM Chip SRAM bits<127:0> 256K x 8 = 2 Mb One page 行缓冲 memory SRAM Memory Bus<127:0> bits<7:0> 16 个芯片的行缓冲可以缓存 16x512x8 位数据当 CPU 访问一块连续的内存区 ( 即 : 行地址相同 ) 时, 可直接从行缓冲读取, 行缓冲用 SRAM 实现, 速度极快! Cache 行读要求从内存读一块连续区, 给定一个首地址, 采用突发传输方式

39 PC 机主存储器的物理结构 主存储器由若干内存条组成 内存条的组成 : 把若干片 DRAM 芯片焊装在一小条印制电路板上制成 内存条必须插在主板上的内存条插槽中才能使用 目前流行的是 DDR 和 DDR2 内存条 : 均采用双列直插式, 其触点分布在内存条的两面 DDR 条有 184 个引脚,DDR2 有 240 个引脚 PC 机主板中一般都配备有 2 个或 4 个 DIMM 插槽 memory.39

40 存储器芯片和 CPU 的连接 通过总线连接 地址线的连接 CPU 地址线决定了整个主存空间的寻址范围, 故比存储芯片地址引脚线多 若进行连续编址扩展, 则将 CPU 地址线的低位和存储芯片地址线相连, 高位部分用作字扩展时的片选信号的译码 ; 交叉编址扩展则相反 数据线的连接 CPU 数据线数决定了一次可读写的最大数据宽度, 故比存储芯片数据引脚线多, 通常将 CPU 数据线连到多个进行位扩展的芯片中, 使扩展后的位数与 CPU 数据线数相等 控制线的连接 如果 CPU 读 / 写命令线和存储芯片的读 / 写控制线都是一根, 且电平信号一致, 则可直接相连 若 CPU 读 / 写命令线分开, 则需要分别进行连接 ROM 区和 RAM 区的划分 主存空间包括 ROM 和 RAM 区 ROM 区用来存放 BIOS 等系统程序等, 选用 ROM 芯片构造 ;RAM 区用来存放用户程序, 选用 RAM 芯片构造 选择存储芯片的类型和数量时, 必须先确定好 ROM 区和 RAM 区的地址范围 memory.40

41 举例 :CPU 和主存的连接 CPU 地址线 A15~A0, 数据线 D7~D0,WR 为读 / 写信号,MREQ 为访存请求信号 0000H~3FFFH 为系统程序区,4000H~FFFFH 为用户程序区 用 8K 4 位 ROM 芯片和 16K 8 位 RAM 芯片构成该存储器, 要求说明地址译码方案, 并将 ROM 芯片 RAM 芯片与 CPU 连接 ROM 芯片的片选信号解 : 因为 0000H~3FFFH 为系统程序区,ROM 区高两位总是 00, 低 14 位为全译码 由最高三位确定 ROM 区大小为 : 位 =16K 8 位 =16KB RAM 芯片的片选信 ROM 芯片数为 :16K 8 位 / 8K 4 位 = 2 2 = 8, 字方向扩展 2 倍, 位方向扩展 2 倍号由最高两位确定 ROM 芯片内地址位数为 13 位, 连到 CPU 低 13 位地址线 A12~A0 问题 : 是交叉还是因为 4000H~FFFFH 为用户程序区,RAM 区高两位是 , 低 14 位为全译码 连续编址方案? RAM 区大小为 : 位 =3 16K 8 位 = 48KB 高位地址译码作 RAM 芯片数为 :48K 8 位 / 16K 8 位 = 3 1 = 3, 字方向上扩展 3 倍, 位方向上不扩展 为片选信号, 故 RAM 芯片内地址位数为 14 位, 连到 CPU 低 14 位地址线 A13~A0 是连续编址! 问题 : 为什么 WR 不连到 ROM 芯片上? 因为 ROM 芯片只能读, 不能写, 只要选中就是读, 无需读写信号 11X 01X 问题 :MREQ 信号的作用是什么? 为有效 ( 低电平 ) 时, 表示选中主存读写 memory.41 片选信号 CS 是哪一个?

42 回顾 : 存储器与 CPU 速度差距愈来愈大 100,000,000 10,000,000 1,000, ,000 ns 10,000 1, Disk seek time DRAM access time SRAM access time CPU cycle time 由于 CPU 工作速度很快, 内存速度比较慢 ( 差 1~2 个数量级 ), 从内存取数或向内存写数时,CPU 往往需要等待 memory.42 从上图可以看出什么? DRAM 硬盘与 CPU 之间的速度差距愈来愈大! 解决内存访问速度慢的措施有三个 : 提高主存芯片本身的速度 采用多模块存储器技术 在主存和 CPU 之间加入 Cache

43 提高 DRAM 存储器速度的措施 之一 : 采用芯片内部行缓冲, 以提高芯片本身的速度反复多次使用芯片内部缓冲器中的内容, 不需每次都重复进行 行访问 DDR SDRAM (Double data-rate synchronous DRAM) 和 DDR2 SDRAM 时钟频率内部频率传输频率 =100MHz =100MHz =200MHz 时钟频率内部频率传输频率 =100MHz =200MHz =400MHz 存储单元阵列 数据总线 存储单元阵列 数据总线 DDR SDRAM DDR2 SDRAM memory.43

44 提高 DRAM 存储器速度的措施 之二 : 多模块技术 2 个 4 个或多个存储器同时工作 memory.44

45 加快访存速度措施之二 : 多模块存储器 多体存储器和多模块存储器 多体存储器 由若干个小体组成共用地址寄存器 MAR 和数据寄存器 MDR 不能提高数据访问速度 双口存储器 通常作为双口 RAM 或指令预取部件两套独立的读 / 写控制电路 地址缓存 地址译码及地址线和数据线能同时进行两个数据的读 / 写 多模块存储器 也包含多个小体每个体有其自己的 MAR MDR 和读写电路可独立组成一个存储模块能提高数据访问速度 根据不同的编址方式可分为连续编址和交叉编址 memory.45

46 连续编址多模块存储器 按高位地址划分模块 程序从某个单元开始访问后, 继续在同一模块访问, 完毕后才跳到下一个 地址在同一模块内连续编号, 称 连续编址 例如 : 一个模块执行程序, 另一个模块实现 DMA 访问, 可提高存储器总的吞吐量 为什么能提高吞吐量? 使多个模块并行存取! 第 0 模块第 1 模块第 7 模块 memory.46

47 交叉编址多模块存储器 程序从某个单元开始访问后, 总是在所有模块间交替进行 按低位地址划分模块 地址在不同模块之间交叉编号, 称 交叉编址 memory.47 第 0 模块第 1 模块第 2 模块第 3 模块 为什么能提高吞吐量? 使多个模块交叉存取! 每隔 1/4 周期在数据总线上得到一个信息, 使主存吞吐量提高 4 倍! 在存储地址 相关 或出现 转移 时, 并行性被破坏

48 Increasing Bandwidth Interleaving( 交叉 ) Access Pattern without Interleaving: CPU Memory D1 available Start Access for D1 Start Access for D2 Memory Bank 0 Access Pattern with Interleaving: CPU Memory Bank 1 Memory Bank 2 Access Bank 0 Access Bank 1 Access Bank 2 Access Bank 3 We can Access Bank 0 again Memory Bank 3 memory.48

49 第一讲小结 信息的存储 传送 处理单位 记忆单元 / 编址单位 / 存储单位 / 传输单位 / 机器字长 存储器分类 可按存取方式 / 易失性 / 可更改性 / 元器件 / 功能来分 半导体存储器随机访问存储器 SRAM : 速度快, 容量小, 可做快速小容量存储器 DRAM: 速度慢, 容量大, 用作主存 RAM 芯片组织 : 存储阵列 : 按行 列排, 分别由行地址和列地址指出位置 地址译码器 : 分行 列地址译码器 读写逻辑 : 可控制多个位平面的同一位数据一起读 / 写 提高存储器速度的措施 : 芯片内采用行缓存, 行内数据直接从缓存中取 采用多模块存储器, 多个存储器交叉存取 引入 Cache( 下一讲的主要内容 ) memory.49

50 第二讲高速缓冲存储器 (Cache) 主要内容 什么是程序访问的局部化特性 具有 Cache 机制的 CPU 的基本访存过程 Cache 和主存之间的映射方式 直接映射 / 全相联映射 / 组相联映射 cache 容量和块大小的选择 Cache 替换算法 cache-friendly 的程序 Cache 的写策略 Write Back 和 Write Through Cache 失靶处理 Cache 性能评估 memory.50

51 What we want in a memory 到目前为止, 已经了解到有以下几种存储器 : Register,SRAM,DRAM, Hard Disk,Magnetic Tape and Optical Disk 1KB 1MB 1GB 100GB 100GB 1ns 2ns 10ns 10ms 1ns 问题 : 你认为哪一种最适合做计算机的存储器呢? 单独用某一种存储器, 都不能满足我们的需要! 考虑结合各种存储器的特点, 采用分层存储器结构来构建计算机的存储体系! memory.51

52 计算机中存储器的层次结构 典型存取时间 1 ns(0.5~1cycle) 寄存器 典型容量 <1KB 2 ns(1~3cycle) cache 存储器 1MB 10 ns(10~100cycle) 主存储器 (RAM 和 ROM) 内存储器 256MB-1GB 10 ms (10~100cycle) 外存储器 ( 软盘 硬盘 光盘 ) 外存储器 40GB-200GB 10 s 后备存储器 ( 磁带库 光盘库 ) 10TB-100TB 分析 : 速度越快, 成本较高 为提高性能 / 价格, 各存储器组成一个层状塔式结构, 取长补短, 协调工作 工作过程 : 1)CPU 运行时, 需要的操作数大部分来自寄存器 2) 如需要从 ( 向 ) 存储器中取 ( 存 ) 数据时, 先访问 cache, 如在, 取自 cache 3) 如操作数不在 cache, 则访问 RAM, 如在 RAM 中, 则取自 RAM 4) 如操作数不在 RAM, 则访问硬盘, 操作数从硬盘中读出 RAM cache memory.52

53 五层金字塔形分层系统从上到下的特点 : 1, 每位价格降低 2, 容量增大 3, 存取时间增大 4, 访问频度降低 回顾 : 传统存储器分级体系结构 传统结构 Traditional Memory Hierarchy memory.53

54 开辟一部分内存区, 用作 Disk Cache, 用于存放将被送到磁盘上的数据 现代存储器分级体系结构 引入 Disk Cache 的好处 : (1) 写盘时按 簇 进行, 以避免频繁地小块数据写盘 (2) 有些中间结果数据 在写回盘之前可被快速地再次使用 memory.54 Contemporary Memory Hierarchy ( 现代结构 )

55 层次化存储器结构 (Memory Hierarchy) To CPU From CPU Upper Level Memory Block X Lower Level Memory Block Y 数据总是在相邻两层之间复制传送 Upper Level: 上层更靠 CPU Smaller, faster, and uses more expensive technology Lower Level: 下层更远离 CPU Bigger, slower, and uses less expensive technology Block: 最小传送单位是一个定长块, 互为副本 问题 : 为什么这种层次化结构是有效的? 主要是基于 程序访问局部化 特点! memory.55 时间局部性 (Temporal Locality) 含义 : 刚被访问过的单元很可能不久又被访问做法 : 让最近被访问过的信息保留在靠近 CPU 的存储器中空间局部性 (Spatial Locality) 含义 : 刚被访问过的单元的邻近单元很可能不久被访问做法 : 将刚被访问过的单元的邻近单元调到靠近 CPU 的存储器中

56 加快访存速度措施之三 : 引入 Cache 大量典型程序的运行情况分析结果表明 在较短时间间隔内, 程序产生的地址往往集中在存储器的一个很小范围内 这种现象称为程序访问的局部性 程序具有访问局部性特征的原因 指令 : 指令按序存放, 地址连续, 循环程序段或子程序段重复执行 数据 : 连续存放, 数组元素重复 按序访问 程序访问局部性分为空间局部性和时间局部性 基于程序访问的局部性使访存要求能快速得到响应 在 CPU 和主存之间设置一个快速小容量的存储器, 其中总是存放最活跃 ( 被频繁访问 ) 的程序块和数据, 由于程序访问的局部性特征, 大多数情况下,CPU 能直接从这个高速缓存中取得指令和数据, 而不必访问主存 这个高速缓存就是位于主存和 CPU 之间的 Cache! SKIP memory.56

57 Typical Memory Reference Patterns memory.57 下面用一个例子来说明!

58 程序的局部性原理举例 1 memory.58 高级语言源程序 对应的汇编语言程序 sum = 0; for (i = 0; i < n; i++) sum += a[i]; *v = sum; I0: sum <-- 0 I1: ap <-- A A 是数组 a 的起始地址 I2: i <-- 0 I3: if (i >= n) goto done I4: loop: t <-- (ap) 数组元素 a[i] 的值 I5: sum <-- sum + t 累计在 sum 中 I6: ap <-- ap + 4 计算下 1 个数组元素的地址 I7: i <-- i + 1 I8: if (i < n) goto loop I9: done: V <-- sum 累计结果保存至地址 v 问题 : 指令和数据的时间局部性和空间局部性各自体现在哪里? 指令 : 0x0FC(I0) 0x108(I3) 0x10C(I4) 0x11C(I8) 0x120(I9) 若 n 足够大, 在一段时间内就一直在局部区 N 次域内执行指令, 故循环内指令的时间局部性好 ; 按顺序执行, 故程序的空间局部性好! 数据 : 只有数组在主存中 :0x400 0x404 0x408 0x40C 0x7A4 数组元素按顺序存放, 也按顺序访问, 所以, 空间局部性好 ; 每个数组元素都被访问 1 次, 所以没有时间局部性 每条指令 4 个字节 ; 每个数组元素 4 字节 指令和数组元素在内存中均连续存放 sum, ap,i, t 均为通用寄存器 ;A,V 为内存地址 主存的布局 : 0x0FC 0x100 0x104 0x108 0x10C 0x110 0x114 0x400 0x404 0x408 0x40C 0x410 0x414 0x7A4 BACK I0 I1 I2 I3 I4 I5 I6 a[0] a[1] a[2] a[3] a[4] a[5] 指令A 数据V

59 memory.59 程序的局部性原理举例 2 以下程序 A 和 B 中, 哪一个对数组 A 引用的空间局部性更好? 时间局部性呢? 变量 sum 的空间局部性和时间局部性如何? 对于指令来说,for 循环体的空间局部性和时间局部性如何? 程序段 A: int sumarrayrows(int A[M][N]) { int i, j, sum=0; for (i=0; i<m, i++) for (j=0; j<n, j++) sum+=a[i][j]; return sum; } 程序段 B: int sumarraycols(int A[M][N]) { int i, j, sum=0; for (j=0; j<n, j++) for (i=0; i<m, i++) sum+=a[i][j]; return sum; } 假定数组在存储器中按行优先顺序存放 M=N=2048 时主存的布局 : 0x0FC 0x100 for 循环体 0x17C 0x180 0x184 0x400 0x404 0xc00 0xc04 I1 I2 I33 I34 I35 A[0][0] A[0][1] A[0][2047] A[1][0] A[1][1] A sum 指令数据

60 memory.60 程序段 A: int i, j, sum=0; for (i=0; i<2048, i++) for (j=0; j<2048, j++) sum+=a[i][j]; return sum; 程序的局部性原理举例 2 0x0FC 0x100 for 循环体 0x17C 0x180 0x184 0x400 0x404 程序段 A 的时间局部性和空间局部性分析 (1) 数组 A: 访问顺序为 A[0][0], A[0][1],, A[0][2047]; A[1][0], A[1][1],,A[1][2047]; 与存放顺序一致, 故空间局部性好! 因为每个 A[i][j] 都只被访问一次, 所以时间局部性差! (2) 变量 sum: 单个变量不考虑空间局部性 ; 每次循环都要访问 sum, 所以其时间局部性较好! (3) for 循环体 : 循环体内指令按序连续存放, 所以空间局部性好! 循环体被连续重复执行 2048x2048 次, 所以时间局部性好! 0xc00 0xc04 I1 I2 I33 I34 I35 A[0][0] A[0][1] A[0][2047] A[1][0] A[1][1] A sum 实际上优化的编译器使循环中的 sum 分配在寄存器中, 最后才写回存储器! 指令数据

61 memory.61 程序段 B: int i, j, sum=0; for (j=0; j<2048, j++) for (i=0; i<2048, i++) sum+=a[i][j]; return sum; } 程序的局部性原理举例 2 0x0FC 0x100 for 循环体 0x17C 0x180 0x184 0x400 0x404 程序段 B 的时间局部性和空间局部性分析 (1) 数组 A: 访问顺序为 A[0][0], A[1][0],, A[2047][0]; A[0][1], A[1][1],,A[2047][1]; 与存放顺序不一致, 每次跳过 2048 个单元, 若交换单位小于 2KB, 则没有空间局部性! ( 时间局部性差, 同程序 A) (2) 变量 sum:( 同程序 A ) (3) for 循环体 :( 同程序 A) 0xc00 0xc04 I1 I2 I33 I34 I35 A[0][0] A[0][1] A[0][2047] A[1][0] A[1][1] 实际运行结果 (2GHz Intel Pentium 4): 程序 A:59,393,288 时钟周期程序 B:1,277,877,876 时钟周期 程序 A 比程序 B 快 21.5 倍!! A sum 指令数据

62 Cache( 高速缓存 ) 是什么样的? Cache 是一种小容量高速缓冲存储器, 它由 SRAM 组成 Cache 直接制作在 CPU 芯片内, 速度几乎与 CPU 一样快 程序运行时,CPU 使用的一部分数据 / 指令会预先成批拷贝在 Cache 中,Cache 的内容是主存储器中部分内容的映象 当 CPU 需要从内存读 ( 写 ) 数据或指令时, 先检查 Cache, 若有, 就直接从 Cache 中读取, 而不用访问主存储器 问题 : 要实现 Cache 机制需要解决哪些问题? 如何分块? 主存块和 Cache 之间如何映射? Cache 已满时, 怎么办? 写数据时怎样保证 Cache 和 MM 的一致性? 给出的主存地址怎样转换为 Cache 地址? 数据访问过程 : 主存储器 10 4 Cache 存储器 主存中的部分信息拷贝在 Cache 存储器中 主存分成若干大小相同的块, 称为主存块 (Block),Cache 也被分成相同大小的块, 称为 Cache 行 (line) 或槽 (Slot) Cache 对程序员 ( 编译器 ) 是否透明? 为什么? 是透明的, 程序员 ( 编译器 ) 在编写 / 生成低级语言程序时无需了解 Cache 是否存在或如何设置 memory.62 但是, 对 Cache 深入了解有助于编写出高效的程序!

63 Cache 的操作过程 问题 : 什么情况下, CPU 产生访存要求? 在执行指令过程中, 会取指令和读写数据! 如果被访问的信息不在 cache 中, 称为缺失或失靶 (miss) 缺失处理 如果被访问的信息在 cache 中, 称为命中 (hit) memory.63

64 Cache 映射 (Cache Mapping) 什么是 Cache 的映射功能? 把访问的局部主存区域取到 Cache 中时, 该放到 Cache 的何处? Cache 槽比主存块少, 多个主存块映射到一个 Cache 槽中 如何进行映射? 把主存划分成大小相等的主存块 (Block) Cache 中存放一个主存块的对应单位称为槽 (Slot) 或行 (line) 或块 (Block) 将主存块和 Cache 槽按照以下三种方式进行映射 直接 (Direct): 每个主存块映射到 Cache 的固定槽中 全相联 (Full Associate): 每个主存块映射到 Cache 的任意槽中 组相联 (Set Associate): 每个主存块映射到 Cache 的固定组中的任意槽中 memory.64

65 The Simplest Cache: Direct Mapped Cache Direct Mapped Cache( 直接映射 Cache) 把主存的每一块映射到一个固定的 Cache 槽 ( 行 ) 也称模映射 (Module Mapping) 映射关系为 : Cache 槽号 = 主存块号 mod Cache 槽数举例 :4=100 mod 16 ( 假定 Cache 共有 16 槽 ) ( 说明 : 主存第 100 块应映射到 Cache 的第 4 槽中 ) 特点 : 容易实现, 命中时间短 无需考虑淘汰 ( 替换 ) 问题 但不够灵活,Cache 存储空间得不到充分利用, 命中率低例如, 需将主存第 0 块与第 16 块同时复制到 Cache 中时, 由于它们都只能复制到 Cache 第 0 槽, 即使 Cache 其它槽空闲, 也有一个主存块不能写入 Cache 这样就会产生频繁的 Cache 装入 memory.65 SKIP

66 直接映射 Cache 组织示意图 假定 : 数据在主存和 Cache 之间按块传送的单位为 512 字 Cache 大小 :2 13 字 =8K 字 =16 槽 x 512 字 / 槽 主存大小 : 2 20 字 =1024K 字 =2048 块 x 512 字 / 块 0220CH Cache 标记 (tag) 指出对应槽取自哪个主存块群 主存 tag 指出对应地址位于哪个块群举例 : 假定 Cache 为空, 如何对 0220CH 单元进行访问? B 第 1 块群中的 0001 块 ( 即第 17 块 ) 中第 12 个单元!

67 Cache Organization: Cache Tag and Cache Index 假定主存地址为 32 位, 按字节编址 假定 Cache 是块大小为 1B 的直接映射 Cache Cache Index: The lower N bits of the memory address Cache Tag: The upper (32 - N) bits of the memory address 31 N 0 Cache Tag Example: 0x50 Cache Index Ex: 0x03 Valid Bit Cache tag 2 = 否? 2 N Cache Data Bytes Byte 0 Byte 1 Byte =1 否? 1 0x50 Byte 3 3 : : : N Byte 2-1 N 2-1 memory.67 利用了时间局部性 : 某字节不久又可能被用 没有利用空间局部性 : 某字节的邻近字节不久可能也被用, 但没有被调到 Cache ( 每次调入的一块信息只有一个字节!) 发生冲突概率增大, 因为块小使映射到同一个 Cache 行的主存块增加可以通过增大块的大小来利用空间局部性

68 Ex2: 1 KB Direct Mapped Cache with 32 B Blocks For a 2 N byte cache (N=10 in this example): The uppermost (32 - N) address bits are always the Cache Tag The lowest M address bits are the Byte Select (Block Size = 2 M ) Suppose Block size is 32B, M= Cache Tag Example: 0x50 Cache Index Byte Select Ex: 0x01 Ex: 0x00 2 Valid Bit 3 1 : Cache Tag 0x50 : Cache Data Byte 31 Byte 63 : : Byte 1 Byte 33 : 4 Byte 0 Byte Byte 1023 : Byte memory.68

69 Ex3: 64 KB Direct Mapped Cache with 16B Blocks 假定主存和 Cache 之间采用直接映射方式, 块大小为 16B Cache 的数据区容量为 64KB, 主存地址为 32 位, 按字节编址 要求 : 说明主存地址如何划分, 访存过程的硬件实现 Memory Address 31 0 Byte Hit V Tag 16 tag 2 Index Byte offset 1 5 Block offset 128 data Mux Word 4K Entries memory.69 = Mux Data 问题 :Cache 有多少行? 容量多大? 共 (64K / 16)= 4K 行 容量 4Kx(1+16)+64Kx8=580Kbits=72.5KB, 数据占 64KB / 72.5KB = 88.3%

70 如何计算 Cache 的容量? Consider a cache with 64 Blocks and a block size of 16 bytes. What block number does byte address 1200 map to? 答 : 地址 1200 对应存放在第 11 槽 因为 : [1200/16=75] module 64 = 11 How many total bits are required for a directed mapped cache with 16K Entries of data and 1-word blocks, assuming a 32-bit address? (Cache : 直接映射方式 16K 项数据 块大小为 1 个 32 位字 32 位地址 ) 答 :Cache 的存储布局如下 : Cache 共有 16K x 4B= 64KB 数据 所以,Cache 的大小为 :2 14 (32 + ( )+1) = = 784 Kbits 若块大小为 4 个字呢? 2 14 ( ( )+1) = = 2288 Kbits 若块大小为 2 m 个字呢? 2 14 (2 m 32 + ( m)+1) memory.70

71 全相联映射 Cache 组织示意图 各主存块可装到 Cache 任一槽 Slot( 行 Line 或项 Entry) 中 称为全映射或全相联映射 假定 : 数据在主存和 Cache 之间块传送的单位为 512 字 Cache 大小 :2 13 字 =8K 字 =16 槽 x 512 字 / 槽 主存大小 : 2 20 字 =1024K 字 =2048 块 x 512 字 / 块 Cache 标记 (tag) 指出对应槽取自哪个主存块 主存 tag 指出对应地址位于哪个主存块两个标记相等时, 说明要找的地址在对应槽中 比较所有标记都不等, 则缺失 举例 : 假定 Cache 为空, 如何对 01E0CH 单元进行访问? B 是第 15 块中的第 12 个单元! 可映射到任意 cache 槽中

72 举例 :Fully Associative Fully Associative Cache 无需 Cache 索引, 为什么? 因为同时比较所有 Cache 项的标志 By definition: Conflict Miss = 0 ( 全相联映射没有冲突失靶, 因为只要有空闲 Cache 块, 都不会发生冲突 ) Example: 32bits memory address, 32 B blocks. 比较器位数多长? we need N 27-bit comparators 31 4 Cache Tag (27 bits long) Byte Select Ex: 0x01 Cache Tag Valid Bit Cache Data = Byte 31 = Byte 63 = = = : : : : : : Byte 1 Byte 33 0 Byte 0 Byte 32 memory.72

73 memory.73 比直接映射灵活, 命中率高 采用相联存取技术 ( 按内容访问 ), 实现复杂 速度慢 Cache 标志位数增加, 比较逻辑成本随之增加 不适合大容量 Cache

74 组相联映射 (Set Associative) 组相联映射结合直接映射和全相联映射的特点 将 Cache 所有槽分组, 把主存块映射到 Cache 固定组的任一槽中 也即 : 组间模映射 组内全映射 映射关系为 : Cache 组号 = 主存块号 mod Cache 组数举例 : 假定 Cache 划分为 :8K 字 =8 组 x2 槽 / 组 x512 字 / 槽 4=100 mod 8 ( 主存第 100 块应映射到 Cache 的第 4 组的任意槽中 ) 特点 : 结合了直接映射和全相联映射的优点 当 Cache 的组数为 1 时, 则变为相联映射 ; 当每组只有一个槽时, 则变为直接映射 每组两个槽 ( 称为 2 路组相联 ) 较常用 一般每组 4 个槽以上的情况很少用 在较大容量的 L2 Cahce 和 L3 Cahce 中使用 4- 路以上 memory.74

75 组相联映射的 Cache 组织图 假定 : 数据在主存和 Cache 之间按块传送的单位为 512 字 Cache 大小 :2 13 字 =8K 字 =16 槽 x 512 字 / 槽 =8 组 x2 槽 / 组 x512 字 / 槽 主存大小 : 2 20 字 =1024K 字 =2048 块 x 512 字 / 块 memory.75 Cache 标记 (tag) 指出对应槽取自哪个主存组群 主存 tag 指出对应地址位于哪个主存组群中两个标记相等时, 说明要找的地址在对应槽中 举例 : 假定 Cache 为空, 如何对 0120CH 单元进行访问? B 是第 1 组群中的 001 块 ( 即第 9 块 ) 中第 12 个单元 所以, 映射到第一组中 将主存地址标记和固定 Cache 组中每个 Cache 标记进行比较

76 Valid 例 1:A Two-way Set Associative Cache N-way set associative N entries for each Cache Index ( 每个 Cache 组有 N 槽 or 行 ) N 个直接映射的行并行操作 Example: Two-way set associative cache Cache Index 选择其中的一个 Cache 行集合 (2 行 ) 对这个集合中的两个 Cache 行的 Tag 并行进行比较 根据比较结果确定信息在哪个行, 或不在 Cache 中 Cache Tag : : : Cache Index Cache Data Cache Data Cache Block 0 Cache Block 0 1 : Cache Tag Valid : : Adr Tag 2 Compare 5 Sel 1 1 Sel 0 Mux Compare memory.76 3 Hit OR 4 Cache Block 3

77 例 2:A N-way Set Associative Cache memory.77

78 Disadvantage of Set Associative Cache N-way Set Associative Cache 相对于 Direct Mapped Cache: 比较器的个数为 :N:1 需要额外的 MUX 延时 数据在判断是否命中后才被得到, 而直接映射可 投机 预取在直接映射中, 可认为总是命中, 所以可先把数据取来, 若失靶则再恢复 Valid Cache Tag Cache Data Cache Block 0 : : : Cache Index Cache Data Cache Block 0 : Cache Tag Valid : : Adr Tag Compare Sel1 1 Mux 0 Sel0 Compare OR memory.78 Hit Cache Block

79 三种映射方式总结 memory.79

80 命中率 失靶率 失靶损失 Hit: 要访问的信息在 Cache 中 Hit Rate( 命中率 ): 在 Cache 中的概率 Hit Time ( 命中时间 ) : 在 Cache 中的访问时间, 包括 : Time to determine hit/miss + Cache access time ( 即 : 判断时间 +Cache 访问 ) Miss: 要找的信息不在 Cache 中 Miss Rate ( 缺失率 ) = 1 - (Hit Rate) Miss Penalty ( 缺失损失 ): 访问一个主存块所花时间 Hit Time << Miss Penalty (Why?) memory.80

81 Average access time( 平均访问时间 ) 要提高平均访问速度, 必须提高命中率! memory.81 Cache 对程序员是透明的 : 程序不用管信息在主存还是在 Cache! 完全由硬件完成在主存和 Cache 之间的信息交换

82 看看命中率对平均访问时间的影响 设平均访问时间 T : T = HT C + (1 - H)(T C + T M ) = T C + (1 - H)T M 例 1. 若命中率 H=0.85, Tc=1 ns, T M =20ns, 则平均访问时间 T 为多少? 答 : T = 4ns 例 2. 若命中率 H 提高到 0.95, 则结果又如何? 答 : T = 2ns 例 3. 若命中率为 0.99 呢? 答 : T = 1.2ns 访问速度与命中率的关系非常大! memory.82

83 三种映射方式 高速缓存的失靶率和关联度 直接映射 : 唯一映射 ( 只有一个可能的位置 ) 全相联映射 : 任意映射 ( 每个位置都可能 ) N- 路组相联映射 :N- 路映射 ( 有 N 个可能的位置 ) 什么叫关联度? 一个主存块映射到 Cache 中时, 可能存放的位置个数 直接映射 : 关联度最低, 为 1 全相联映射 : 关联度最高, 为 Cache 行数 N- 路组相联映射 : 关联度居中, 为 N 关联度和 miss rate 有什么关系呢? 和命中时间的关系呢? 直观上, 你的结论是什么?( Cache 大小和块大小一定时 ) 失靶率 : 直接映射最高, 全相联映射最低 命中时间 : 直接映射最小, 全相联映射最大 用例子来说明 memory.83

84 关联度示例 关联度为多少? 2 关联度为多少? 1 关联度为多少? 4 memory.84 关联度为多少? 8 BACK

85 例子 :Cache 缺失和关联度 设有三个大小相等的 Cache, 都有四行, 每行一个字 Cache1: 全相联 Cache2: 2- 路组相联 Cache3: 直接映射 按以下主存块地址顺序访问, 其缺失次数各为多少? 右边三种情况各对应哪种 Cache? 直接映射 2 路组相联全相联 Cache 块号 = 主存块号 mod 4 Cache 组号 = 主存块号 mod 2 全相联的缺失率最低直接映射最高! 相联度高, 则缺失率低 memory.85

86 关联度与标记位大小 主存地址 32 位, 块大小为 16 字节,Cache 总大小为 4K 块, 问 : 标志位的总位数是多少? 块内地址占几位? 4 位 直接映射方式下 : 相当于每组 1 块, 共 4K 组标志占 =16 位总位数占 4Kx16=64K 位 关联度增加一倍 (2-way) 每组 2 块, 共 2K 组标志占 =17 位总位数占 4Kx17=68K 位 关联度增加 2 倍 (4-way) 每组 4 块, 共 1K 组标志占 =18 位总位数占 4Kx18=72K 位 memory.86 如何只取其中某字节? 全相联时 : 整个为 1 组, 每组 4K 块标志占 32-4=28 位总位数占 4Kx28=112K 位

87 The Need to Replace! ( 何时需要替换?) Direct Mapped Cache: 映射唯一, 无需考虑替换, 毫无选择地用新信息替换老信息 N-way Set Associative Cache: 每个主存数据有 N 个 Cache 槽可选择, 需考虑替换 Fully Associative Cache: 每个主存数据可存放到 Cache 任意槽中, 需考虑替换结论 : 若 Cache miss in a N-way Set Associative or Fully Associative Cache, 则可能需要替换 其过程为 : 从主存取出一个新块 选择一个有映射关系的空 Cache 槽 对应的 Cache 槽已被占满而需要调入新的主存块时, 必须考虑从 cache 槽中调出一个主存块 memory.87

88 替换 (Replacement) 算法 问题举例 : 组相联映射时, 假定第 0 组的两个槽分别被主存第 0 和 8 块占满, 此时若需调入主存第 16 块, 根据映射关系, 它只能放到 Cache 第一组, 因此, 第一组中必须调出一块, 那么调出哪一块呢? 这就是淘汰策略问题, 也称替换算法 常用替换算法有 : 先进先出 FIFO (first-in-first-out) 最近最少用 LRU ( least-recently used) 最不经常用 LFU ( least-frequently used) 随机替换算法 (Random) 等等这里的替换策略和后面的虚拟存储器所用的替换策略类似, 将是以后操作系统课程的重要内容, 本课程只做简单介绍 有兴趣的同学可以自学 memory.88

89 ( 自学 ) 替换算法 - 先进先出 (FIFO) 总是把最先进入的那一块淘汰掉 例 : 假定主存中的 5 块 {1,2,3,4,5} 同时映射到 Cache 同一组中, 对于同一地址流, 考察 3 槽 / 组 4 槽 / 组的情况 3 行 / 组 4 行 / 组 * 1* 1* 4 4 4* * 5* 2 2 2* 1 1 1* 1* 1* * * 4 4 1* 1* 1* 1* 1* 1* * * * * 3 3 3* * * 由此可见,FIFO 不是一种堆栈算法, 即命中率并不随组的增大而提高 memory.89

90 ( 自学 ) 替换算法 - 最近最少用 (LRU) 总是把最近最少用的那一块淘汰掉 例 : 假定主存中的 5 块 {1,2,3,4,5} 同时映射到 Cache 同一组中, 对于同一地址流, 考察 3 槽 / 组 4 槽 / 组 5 槽 / 组的情况 3 行 / 组 4 行 / 组 5 行 / 组 memory.90

91 ( 自学 ) 替换算法 - 最近最少用 是一种堆栈算法, 它的命中率随组的增大而提高 当分块局部化范围 ( 即 : 某段时间集中访问的存储区 ) 超过了 Cache 存储容量时, 命中率变得很低 极端情况下, 假设地址流是 1,2,3,4,1 2,3,4,1,, 而 Cache 每组只有 3 槽, 那么, 不管是 FIFO, 还是 LRU 算法, 其命中率都为 0 这种现象称为颠簸 (Thrashing / PingPong) 该算法具体实现时, 并不是通过移动块来实现的, 而是通过给每槽设定一个计数器, 根据计数值来记录这些主存块的使用情况 这个计数值称为 LRU 位 具体实现 memory.91

92 memory.92 ( 自学 ) 替换算法 - 最近最少用 计数器变化规则 : 每组 4 槽时, 计数器有 2 位 计数值越小则说明越被常用 命中时, 被访问的槽的计数器置 0, 比其低的计数器加 1, 其余不变 未命中且该组未满时, 新槽计数器置为 0, 其余全加 1 未命中且该组已满时, 计数值为 3 的那一槽中的主存块被淘汰, 新槽计数器置为 0, 其余加

93 最不经常用 (LFU) 算法 : 替换掉 Cache 中引用次数最少的块 LFU 也用与每个槽相关的计数器来实现 ( 这种算法与 LRU 有点类似, 但不完全相同 ) 随机算法 : ( 自学 ) 替换算法 - 其他算法 随机地从候选的槽中选取一个淘汰, 与使用情况无关 ( 模拟试验表明, 随机替换算法在性能上只稍逊于基于使用情况的算法 而且代价低!) memory.93

94 有效位 (Valid Bit) 装入新块时使 V=1 开机或复位时使 V=0 第一次被替换时使 V=1 通过使 V=0 冲刷 Cache memory.94

95 举例 假定计算机系统有一个容量为 32Kx16 位的主存, 且有一个 4K 字的 4 路组相联 Cache, 主存和 Cache 之间的数据交换块的大小为 64 字 假定 Cache 开始为空, 处理器顺序地从存储单元 中取数, 一共重复 10 次 设 Cache 比主存快 10 倍 采用 LRU 算法 试分析 Cache 的结构和主存地址的划分 说明采用 Cache 后速度提高了多少? 采用 MRU 算法后呢? 答 : 假定主存按字编址 每字 16 位 主存 :32K 字 =512 块 x 64 字 / 块 Cache:4K 字 =16 组 x 4 槽 / 组 x 64 字 / 槽 主存地址划分为 : 标志位 组号 字号 /64=68, 所以处理器的访问过程是对前 68 块连续访问 10 次 memory.95

96 举例 第 0 行第 1 行第 2 行第 3 行 第 0 组 0/64/48 16/0/64 32/16 48/32 第 1 组 1/65/49 17/1/65 33/17 49/33 第 2 组 2/66/50 18/2/66 34/18 50/34 第 3 组 3/67/51 19/3/67 35/19 51/35 第 4 组 第 15 组 LRU 算法 : 第一次循环, 对于每一块只有第一字未命中, 其余都命中 ; 以后 9 次循环, 有 20 块的第一字未命中, 其余都命中. 所以, 命中率 p 为 ( x20)/43520=99.43% 速度提高 :tm/ta=tm/(tc+(1-p)tm)=10/(1+10x(1-p))=9.5 倍 memory.96

97 举例 0 槽 1 槽 2 槽 3 槽 0 组 0/16/32/48 16/32/48/64 32/48/64/0 48/64/0/16 1 组 1/17/33/49 17/33/49/65 33/49/65/1 49/65/1/17 2 组 2/18/34/50 18/34/50/66 34/50/66/2 50/66/2/18 3 组 3/19/35/52 19/35/51/67 35/51/67/3 51/67/3/19 4 组 组 15 组 MRU 算法 : 第一次 68 字未命中 ; 第 2,3,4,6,7,8,10 次各有 4 字未命中 ; 第 5,9 次各有 8 字未命中 ; 其余都命中. 所以, 命中率 p 为 ( x4-2 x8)/43520=99.74% 速度提高 :tm/ta=tm/(tc+(1-p)tm)=10/(1+10x(1-p))=9.77 倍 memory.97

98 写策略 (Cache 一致性问题 ) 为何要保持在 Cache 和主存中数据的一致? 因为 Cache 中的内容是主存块副本, 当对 Cache 中的内容进行更新时, 就存在 Cache 和主存如何保持一致的问题 以下情况也会出现 Cache 一致性问题 当多个设备都允许访问主存时例如 :I/O 设备可直接读写内存时, 如果 Cache 中的内容被修改, 则 I/O 设备读出的对应主存单元的内容无效 ; 若 I/O 设备修改了主存单元的内容, 则对应 Cache 槽中的内容无效 当多个 CPU 都带有各自的 Cache 而共享主存时某个 CPU 修改了自身 Cache 中的内容, 则对应的主存单元和其他 CPU 中对应的 Cache 槽的内容都变为无效 有两种情况 写命中 (Write Hit): 要写的单元已经在 Cache 中 写不命中 (Write Miss): 要写的单元不在 Cache 中 memory.98

99 基本的 Cache 处理算法 写分配方式 memory.99

100 Write Policy: Write Through versus Write Back memory.100 处理 Cache 读比 Cache 写更容易, 指令 Cache 比数据 Cache 容易设计 对于写命中, 有 Two options Write Through ( 通过式写 写直达 直写 ) 同时写 Cache 和主存单元 What!!! How can this be? Memory is too slow(>100cycles)? 10% 的存储指令使 CPI 增加到 : x10%=11 使用写缓冲 (Write Buffer) Write Back ( 一次性写 写回 回写 ) 在失靶时一次写回 Cache 块, 每块有个修改位 ( dirty bit- 脏位 ) 大大降低主存带宽需求, 控制可能很复杂对于写不命中, 有 Two options Write Allocate ( 写分配 ) 将主存块装入 Cache, 然后更新相应单元 试图利用空间局部性, 但每次都要从主存读一个块 Not Write Allocate ( 非写分配 ) 直接写主存单元, 不装入主存块到 Cache SKIP 直写 Cache 可用非写分配或写分配为什么? 写回 Cache 通常用写分配

101 Write Through 中的 Write Buffer Processor Cache DRAM Write Buffer Memory Controller 在 Cache 和 Memory 之间加一个 Write Buffer Processor: 同时写数据到 Cache 和 Write Buffer Memory controller: 将缓冲内容写主存 Write buffer ( 写缓冲 ) 是一个 FIFO 队列 一般有 4 项 在存数频率 <<DRAM 写 ( 周期 ) 频率情况下, 效果好 最棘手的问题 Store frequency > 1 / DRAM write cycle( 频繁写 ) 时, 使 Write buffer 饱和 ( 溢出 ), 会发生阻塞 memory.101

102 Write Buffer Saturation( 写缓冲饱和 ) Processor Cache DRAM Write Buffer 发生写缓冲饱和的可能性 The CPU Cycle Time < DRAM Write Cycle Time ( 客观上如此 ) Store frequency >> 1/ DRAM write cycle( 又发生频繁写 ) 即 : 如果 CPU 时钟宽度远远小于 DRAM 写周期, 并且一段时间内发生大量的写操作, 则不管写缓冲多大, 都会发生写缓冲溢出 ( 饱和 ) 如何解决写缓冲饱和? 加一个二级 Cache Processor Cache L2 Cache DRAM Write Buffer 使用 Write Back 方式的 Cache BACK memory.102

103 写策略 (Cache 一致性问题 ) 问题 1: 以下算法描述的是哪种写策略? Write Through Write Allocate! 问题 2: 如果用非写分配, 则如何修改算法? memory.103 BACK

104 写策略 2:Write Back 算法 问题 : 以下算法描述的是哪种写策略? Write Back Write Allocate! memory.104

105 写策略 2:Write Back 中的修改 ( 脏 ) 位 BACK memory.105

106 Cache 性能评估与改善 CPU 时间 :CPU 执行时间 + 等待内存访问时间 即 : CPU 时间 =(CPU 执行时钟数 +Cache 缺失引起阻塞的时钟数 )X 时钟周期 Cache 缺失引起阻塞的时钟数 = 读操作阻塞时钟数 + 写操作阻塞时钟数 读操作阻塞时钟数 =( 读的次数 / 程序 ) x 读缺失率 x 读缺失损失 写操作的情况较复杂 : 回写 (write back): 替换时, 需要一次性回写一个块, 故会产生一些附加回写阻塞写操作阻塞时钟数 =( 写次数 / 程序 ) x 写缺失率 x 写缺失损失 + 回写阻塞 直写 (write through): 包括写失靶和 write buffer 阻塞两部分写操作阻塞时钟数 =( 写次数 / 程序 ) x 写缺失率 x 写缺失损失 + 写缓冲阻塞 假定回写阻塞或写缓冲阻塞可以忽略不计, 则可将读和写综合考虑 : 内存阻塞时钟数 =( 访存次数 / 程序 ) x 缺失率 x 缺失损失 内存阻塞时钟数 =( 指令条数 / 程序 ) x ( 缺失数 / 指令 ) x 缺失损失 memory.106

107 举例 : 失靶带来的损失到底多大? 设 Code Cache 的缺失率为 2%,Data Cache 的缺失率为 4% 假定一个处理器在没有任何存储器阻塞时的 CPI 为 2,miss penalty 为 100 个时钟 如果用 SPECint2000 来衡量, 则使用完全没有缺失的完美 Cache, 处理器的速度会快多少? 分析过程如下 : 指令的缺失时钟数为 :Ix2%x100=2.0xI SPECint2000 的访存指令 (Load 和 Store) 频度为 :36%, 所以数据的缺失时钟数为 :Ix36%x4%x100=1.44xI 指令和数据总的缺失时钟数为 :2xI+1.44xI=3.44I, 也即 : 平均每条指令要有 3.44 个时钟处在存储器阻塞状态因此, 因为存储器阻塞而使得 CPI 数增大到 =5.44. 故 : CPU time with stalls CPU time with perfect cache = IxCPIstallxClock cycle IxCPIperfectxClock cycle = 如果 Cache 不发生缺失, 则处理器速度会快 2.72 倍 memory.107

108 举例 : 处理器速度提高而存储器不变时的情况 例 1: 假定上例中 CPI 减为 1, 时钟宽度不变, 则 : 因为存储器阻塞而使得 CPI 数增大到 =4.44. 故 : CPU time with stalls IxCPIstallxClock cycle = CPU time with perfect cache IxCPIperfectxClock cycle 由此可知 : 存储器阻塞所花时间占整个执行时间的比例从 : 3.44 / 5.44=63% 上升到 3.44 / 4.44=77% 结论 :CPI 越小,Cache 阻塞的影响越大 例 2: 假定上例中时钟频率加倍, CPI 不变, 则 : = 主存速度不太可能改变, 故绝对时间不变, 所以 miss 损失为 200 个时钟 每条指令发生的总缺失时钟数为 :(2%x200)+36%x(4%x200)=6.88 故 : 存储器阻塞使得 CPI 数增大到 =8.88 时钟快的机器的性能 IxCPIstallofslow xclock cycle = = 5.44 = 1.23 时钟慢的机器的性能 IxCPIstalloffast xclock cycle/2 8.88/2 memory.108 由此可知 : 时钟快的机器的性能只是较慢时钟机器的 1.2 倍 如果没有 Cache 缺失的话, 应该是 2 倍! 结论 :CPU 时钟频率越高,Cache 缺失损失就越大 上述两个例子说明 : 处理器性能越高, 高速缓存的性能就越重要!

109 Cache 大小 Block 大小和失靶率的关系 Cache 性能由缺失率确定, 而缺失率与 Cache 大小 Block 大小 Cache 级数等有关 memory.109 Cache 大小 :Cache 越大,Miss 率越低, 但成本越高! Block 大小 :Block 大小与 Cache 大小有关, 且不能太大, 也不能太小!

110 Block Size Tradeoff ( 块大小的选择 ) 块大能很好利用 spatial locality, BUT: 块大, 则需花更多时间读块, 缺失损失变大 块大, 则 Cache 项变少, 缺失率上升 Average Access Time: = Hit Time x (1 - Miss Rate) + Miss Penalty x Miss Rate Miss Penalty Miss Rate Exploits Spatial Locality Average Access Time Fewer blocks: compromises temporal locality Increased Miss Penalty & Miss Rate Block Size Block Size Block Size 所以, 块大小必须适中! memory.110

111 系统中的 Cache 数目 刚引入 Cache 技术时只有一个 Cache 近年来多 Cache 系统成为主流 多 Cache 系统中, 主要有两个考虑因素 : [1] 单级 / 多级片内 (On-chip)Cache: 将 Cache 和 CPU 作在一个芯片上外部 (Off-chip)Cache: 不做在 CPU 内而是独立设置一个 Cache 单级 Cache: 只用一个片内 Cache 多级 Cache: 同时使用 L1 Cache 和 L2 Cache, 有些高端系统甚至有 L3 Cache L1 Cache 更靠近 CPU, 其速度比 L2 快, 其容量比 L2 大 [2] 联合 / 分立分立 : 指数据和指令分开存放在各自的数据和指令 Cache 中一般 L1 Cache 都是分立 Cache, 为什么? L1 Cache 的命中时间比命中率更重要! 为什么? 联合 : 指数据和指令都放在一个 Cache 中一般 L2 Cache 都是联合 Cache, 为什么? L2 Cache 的命中率比命中时间更重要! 为什么? memory.111

112 多核处理器中的多级 Cache memory.112

113 多级 cache 的性能 采用 L2 Cache 的系统, 其缺失损失的计算如下 : 若 L2 Cache 包含所请求信息, 则缺失损失为 L2 Cache 的访问时间 否则, 要访问主存, 并取到 L1 Cache 和 L2 Cache( 缺失损失更大 ) 例子 : 有一处理器的 CPI 为 1, 所有访问能在 L1 Cache 中命中, 时钟频率为 5GHz 假定访问一次主存的时间为 100ns, 包括所有的缺失处理 设平均每条指令在 L1 Cache 中的缺失率为 2%, 若增加一个 L2 Cache, 访问时间为 5ns, 而且容量大到使全局缺失率减为 0.5%, 问处理器速率提高了多少? 解 : 如果只有一级 Cache, 则缺失只有一种 : 即 :L1 缺失 ( 访问主存 ), 其缺失损失为 :100nsx5GHz=500 个时钟 CPI=1+500x2%=11.0 如果有二级 Cache, 则有两种缺失 : 即 :L1 缺失 ( 访问 L2 Cache):5nsx5GHz=25 个时钟 L2 缺失 ( 访问主存 ):500 个时钟 CPI=1+25x2%+500x0.5%=4.0 因此, 二者的性能比为 11.0/4.0=2.8 倍 memory.113

114 设计支持 Cache 的存储器系统 指令执行过程中, 发生 Cache 缺失时, 必须到 DRAM 中取数据或指令 在 DRAM 和 Cache 之间传输的单位是 Block 问题 : 怎样的存储器组织使得 Block 传输最快 (miss penalty 最小 ) 呢? 存储器访问过程 : 发送地址到内存 :1 个总线时钟访问内存的初始化时间 :10 个总线时钟从总线上传送一个字 :1 个总线时钟假定一个 Block 有 4 个字, 则缺失损失各为多少时钟? 4x(1+10+1)=48 memory.114 Two-word: 2x(1+10+1)=24 Four-word: =12 Interleaved four banks one-word: 1+1x10+4x1=15

115 复习 :SPARCstation 20 s Memory Module one memory module ( 内存条 ) 页模式 : 一行为一页 ( 块 ) Smallest: 4 MB = 16x 2Mb DRAM chips, 8 KB of Page Mode SRAM Biggest: 64 MB = 32x 16Mb chips, 16 KB of Page Mode SRAM 每个芯片有 512 行 x512 列, 并有 8 个位平面每次读 / 写各芯片内同行同列的 8 位, 共 16x8=128 位 DRAM Chip cols DRAM Chip 0 256K x 8 = 2 Mb One page 512 rows 256K x 8 = 2 Mb 8 bits SRAM bits<127:0> SRAM Memory Bus<127:0> 行缓冲 bits<7:0> 16 个芯片的行缓冲可以缓存 16x512x8 位数据 memory.115 当 CPU 访问一块连续的内存区 ( 即 : 行地址相同 ) 时, 可直接从行缓冲读取, 行缓冲用 SRAM 实现, 速度极快! Cache 行读要求从内存读一块连续区, 给定一个首地址, 采用突发传输方式

116 地址 A 复习 :128MB 的 DRAM 存储器 DRAM 行 bits 芯片容量 : 16MB=4096X4096X8 位 ( 行地址 i, 列地址 j) bits bits bits bits bits DRAM 0 bits 主存储器地址 A 处的 64-bit 数据 64-bit 双字 bits 总容量 =128 MB 由 8 片 DRAM 芯片构成 每片 16Mx8 bits 行地址 列地址各 12 位 每 1 行共 4096 列 (8 位 / 列 ) 选中某一行并读出之后再由列地址选择其中的一列 (8 个二进位 ) 送出在主存和 CPU 之间传送的是一个 Cache 行 一个 Cache 行通常位于同一个行缓冲中, 第一次访存时间长, 以后很快 存储控制器 : 行 列地址为 (i,j) 的 8 个单元 memory.116

117 实例 : 奔腾机的 Cache 组织 主存 :4GB=2 20 x 2 7 块 x 2 5 B/ 块 Cache:8KB=128 组 x2 槽 / 组 x32b/ 槽 替换算法 : 采用 LRU, 每组有一位 LRU 位, 用于记录该组 2 个槽的使用情况 可以这样规定 : 该位为 0, 则下次将淘汰第 0 槽 该位为 1, 则下次淘汰第 1 槽 写策略 : 默认方式为一次性写 (Write Back), 也可动态设置为通过式写 (Write Through) Cache 一致性 : 支持 MESI 协议 ( 在 计算机系统结构 课程详细介绍 ) memory.117

118 采用 12 级流水线结构指令 Cache 和数据 Cache 分开所以控制信号各自分开产生 实例 : 内置 FastMATH 处理器 FastMATH 处理器是 MIPS 结构的嵌入式微处理器 Hit V Tag 18 tag 31 Memory Address 2 Index Byte offset data 各 Cache 有 : (16KB / 64B) 项 Byte 5 Block offset Mux Word 256 Entries = 3 Mux 32 4 Data 写操作比读操作复杂! 处理器提供了写通过和写回两种方式, 由 OS 决定采用何种策略 SPEC2000int 的指令 数据和综合缺失率分别为 :0.4%, 11.4%, 3.2% memory.118

119 实例 :Pentium 4 的 cache 存储器 前端总线 总线接口部件 预取控制逻辑 64 位, 时钟频率 指令 cache 及指令预取部件 Pentium 4 中有 3 个 cache 存储器, 分成两级 : 一级 cache 数据缓存 (L1 数据 cache),8kb 指令缓存, 8KB 二级缓存 (L2 cache), 容量为 256 KB~2MB L2 cache (48GB/s) 256 位, 时钟频率 L1 数据 cache(8kb) memory.119

120 缓存在现代计算机中无处不在 问题 : 缓存技术可以应用在哪些方面? 例如 : 问题 : 缓存技术的实现手段和目的各是什么? 将大容量慢速存储器中当前刚用过的局部数据复制或暂存在小容量快速存储器中, 由于信息访问的局部性特点, 可提高总体访问效率 memory.120

121 第二讲小结 引入 Cache 的基础是程序访问的局部化特性 时间局部性和空间局部性 引入 Cache 减少了对内存的访问,CPU 能在快速的 Cache 中得到信息 Cache 和主存之间的映射方式 直接映射 ( 模映射 ): 地址 = 标志 cache 行索引 块内地址 全相联映射 ( 全映射 ): 地址 = 标志 块内地址 组相联映射 ( 组间模映射, 组内全映射 ): 地址 = 标志 cache 组索引 块内地址 如何提高 cache 的命中率? 增大 cache 容量, 适中的块大小 采用多级 cache 技术 (2 级或 3 级等 ) 采用快速查找算法, 并采用并行判定是否命中 不能命中时, 采用有效的算法将读入的内容替换 cache 中暂时不使用的内容 编译器优化目标程序 程序员写出 cache-friendly 的程序 Cache 的写策略 Write Back 和 Write Through memory.121

122 第三讲虚拟存储器 主要内容 存储管理技术的发展过程 虚拟存储器的基本概念按需调页虚拟地址空间 虚拟存储器方式三种方式 : 页式 段式 段页式逻辑地址 -- 物理地址的转换页表缺页处理 替换策略 快表 存储保护地址越界检查存取权限检查 memory.122

123 存储器资源的管理由操作系统来实现 操作系统 (OS) 通过合理地管理 调度计算机的硬件资源, 使其高效被利用 存储器作为一种空间资源也由 OS 来管理 CPU 执行的程序总是在操作系统和用户程序之间切换 主存中同时要存储 OS 和用户程序 磁盘中也要存储 OS 和用户程序 CPU 执行指令时, 涉及到存储器操作, 因此,CPU 中专门有一个存储器管理部件 MMU (Memory Management Unit) 协助 OS 完成存储器访问 memory.123 OS 为 进程 分配存储器资源, 所以, 先了解一下进程的概念

124 复习 : 一个典型程序的转换处理过程 经典的 hello.c C- 源程序 1 #include <stdio.h> 2 3 int main() 4 { 5 printf("hello, world\n"); 6 } 程序的功能是 : 输出 hello,world hello.c 的 ASCII 文本表示 # i n c l u d e <sp> < s t d i o h > \n \n i n t <sp> m a i n ( ) \n { \n <sp> <sp> <sp> <sp> p r i n t f ( " h e l l o, <sp> w o r l d \ n " ) ; \n } 不能, 需要转换为机器语言代码! 即 : 编译 计算机能够直接识别 hello.c 源程序吗? memory.124

125 复习 :Hello 程序的执行过程 Unix 系统启动可执行程序 hello 的 shell 命令行 : unix>./hello hello, world unix> [Enter] Hello 程序被启动后, 计算机的动作过程如下 : 1. Shell 程序读取字符串./hello 中各字符到寄存器, 然后存放到主存 ; 2. Enter 键输入后,shell 调用驻留在内存的 加载器 程序, 由加载器根据主存中的字符串 hello 到磁盘上找到特定的 hello 目标文件, 将其包含的指令代码和数据 ( hello, world\n ) 从磁盘读到主存 ; 3. 处理器从 hello 主程序的指令代码开始执行 ; 4. Hello 程序将 hello, world\n 串中的字节从主存读到寄存器, 再从寄存器输出到显示器上 memory.125

126 复习 :Hello 程序的数据流动过程 Red:shell 命令行处理 Blue: 可执行文件加载 Cyan:hello 程序执行过程 hello hello,world/n hello hello,world/n Hello 可执行文件 问题 :hello 程序何时被装入? 谁来装入? 被谁启动? 每次是否被装到相同的地方? Hello 程序是否知道还有其他程序在同时运行? 是否直接访问硬件资源? memory.126

127 操作系统在程序执行过程中的作用 在 Hello 程序执行过程中,Hello 程序本身没有直接访问键盘 显示器 磁盘和主存储器这些硬件资源, 而是依靠操作系统提供的服务来间接访问 例如, 调用 printf 函数访问硬件 操作系统是在应用程序和硬件之间插入的一个中间软件层 操作系统的两个主要的作用 : 硬件资源管理, 以达到以下两个目的 : 统筹安排和调度硬件资源, 以防止硬件资源被用户程序滥用 对于广泛使用的复杂低级设备, 为用户程序提供一个简单一致的使用接口 为用户使用系统提供一个操作接口 操作系统通过三个基本的抽象概念 ( 进程 虚拟存储器 文件 ) 实现硬件资源管理 文件 (files) 是对 I/O 设备的抽象表示 虚拟存储器 (Virtual Memory) 是对主存和磁盘 I/O 的抽象表示 进程 (processes) 是对处理器 主存和 I/O 设备的抽象表示 memory.127

128 进程 (processes) Hello 程序运行时,Hello 程序会以为 ( 错觉 ): 所有系统资源都被自己独占使用 处理器始终在执行本程序的一条条指令 进程是操作系统对运行程序的一种抽象 unix>./hello hello, world unix> [Enter] 一个系统上可以同时运行很多进程, 但每个进程都好像自己是独占使用系统 实际上, 操作系统让处理器交替执行很多进程中的指令 操作系统实现交替指令执行的机制称为 上下文切换 (context switching) 进程的上下文 指进程运行所需的所有状态信息, 例如 :PC 寄存器堆的当前值 主存的内容 段 / 页表 系统中有一套状态单元存放当前运行进程的上下文 上下文切换过程 ( 任何时刻, 系统中只有一个进程正在运行 ) 上下文切换指把正在运行的进程换下, 换一个新进程到处理器执行, 上下文切换时, 必须保存换下进程的上下文, 恢复换上进程的上下文 memory.128 开始,Shell 进程等待命令行输入输入 Hello 后 Shell 进行系统调用 OS 保存 shell 上下文, 创建并换入 hello 进程 Hello 进程中止时, 进行系统调用 OS 恢复 shell 进程上下文, 并换入 shell 进程 由于在一个进程的整个生命周期中, 有不同进程在处理器交替运行, 所以运行时间很难准确 重复测量

129 存储器管理 (Memory Management) 早期采用单道程序, 系统的主存中包含 : 操作系统 ( 常驻监控程序 ) 正在执行的一个用户程序 所以无需进行存储管理, 即使有也很简单 现在都采用多道程序, 系统的存储器中包含 : 操作系统 若干个用户程序如果在存储器中进程数很少, 则由于进程花费很多时间来等待 I/O, 常使处理机处于空闲状态 因此, 存储器需要进行合理分配, 尽可能让更多进程进入存储器 在多道程序系统中, 存储器的 用户 部分须进一步划分以适应多个进程 划分的任务由 OS 动态执行, 这被称为存储器管理 (memory management) memory.129

130 Memory Management Schema 使系统中尽量多地存储用户程序的解决办法有 : (1) 扩大主存 ( 程序越来越长 主存贵, 不是根本办法 ) (2) 采用交换 (Exchange) 方式和覆盖 (Overlap) 技术存储器中无处于就绪状态的进程 ( 例如 : 某一时刻所有进程都在等待 I/O) 时, 处理器将一些进程调出写回到磁盘, 然后 OS 再调入其他进程执行, 或新的作业直接覆盖老作业的存储区 分区 (Partitioning) 和分页 (Paging) 是交换的两种实现方式 交换 和 覆盖 技术的缺点 : 对程序员不透明 空间利用率差 (3) 虚拟存储器 (Virtual Memory) 类似上述分页方式, 但不是把所有页面一起调到主存, 而是采用 按需调页 Demand Paging, 在外存和主存间以固定页面进行调度 虚拟存储器方式下, 引入了虚拟地址空间的概念 SKIP memory.130

131 简单分区 (Partitioning) 主存分配 : 操作系统 : 固定 用户区 : 分区 简单分区方案 : 使用长度不等的固定长分区 (fixed-size partition) 当一个进程调入主存时, 分配给它一个能容纳它的最小的分区 例如, 对于需 196K 的进程可分配 256K 的分区 简单分区方式的缺点 : 因为是固定长度的分区, 故可能会浪费主存空间 多数情况下, 进程对分区大小的需求不可能和提供的分区大小一样 memory.131 问题 : 如何生成物理地址? 可以采用更有效的可变长分区的方式!

132 可变长分区 (Partitioning) 更有效的方式 ---- 可变长分区 (variable-length partition) 分配的分区大小与进程所需大小一样 特点 : 开始较好, 但到最后在存储器中会有许多小空块出现 时间越长, 存储器中的碎片就会越来越多, 因而存储器的利用率下降 更有效的方式是分页! memory.132

133 基本思想 : memory.133 分页 (Paging) 把内存分成固定长且比较小的存储块, 每个进程也被划分成固定长的程序块 程序块 ( 页 /page) 可装到存储器可用的存储块 ( 页框 /page frame) 中 无需用连续页框来存放一个进程 操作系统为每个进程生成一个页表 通过页表 (page table) 实现逻辑地址向物理地址转换 (Address Mapping ) 逻辑地址 (Logical Address): 程序中的指令所用的地址 物理地址 (physical 或 Memory Address): 存放指令或数据的实际内存地址 问题 : 是否需要将一个进程的全部都装入到内存? 根据程序访问的局部性可知 : 可以仅把当前活跃的浪费的空间最多是最后一页的部分! 页面调入主存, 其余留在磁盘上! 采用 按需调页 / Demand Paging 方式对主存进行分配! BACK

134 虚拟存储系统的基本概念 虚拟存储技术的引入用来解决一对矛盾 memory.134 一方面, 由于技术和成本等原因, 主存容量受到限制 另一方面, 系统程序和应用程序要求主存容量越来越大 虚拟存储技术的实质 程序员在比实际主存空间大得多的逻辑地址空间中编写程序 程序执行时, 把当前需要的程序段和相应的数据块调入主存, 其他暂不用的部分存放在磁盘上 指令执行时, 通过硬件将逻辑地址 ( 也称虚拟地址或虚地址 ) 转化为物理地址 ( 也称主存地址或实地址 ) 在发生程序或数据访问失效时, 由操作系统进行主存和磁盘之间的信息交换 虚拟存储器机制由硬件与操作系统共同协作实现, 涉及到操作系统中的许多概念, 如进程 进程的上下文切换 存储器分配 虚拟地址空间 缺页处理等 下面先介绍操作系统中一些有关概念

135 虚拟存储技术的实质 虚拟 ( 逻辑 ) 空间 用户程序 1 编程空间 虚拟 ( 逻辑 ) 空间 用户程序 k 编程空间 全部装入 页表 通过页表建立虚拟空间和物理空间的映射! 仅装入当前所需的代码和数据 用户程序 1 磁盘物理空间 用户程序 2 主存物理空间 用户程序 k 操作系统程序 用户程序 k 片段 用户程序 1 片段 用户程序 2 片段 发生缺页时, 调入新页 memory.135 BACK

136 虚拟地址空间 虚存为每个进程提供了一个假象 memory.136 好像每个进程都独占使用主存, 并且主存空间极大 虚存是主存和磁盘 I/O 设备的抽象 OS 使每个进程看到的存储空间都一致, 称为虚拟 ( 逻辑 ) 地址空间 Linux 操作系统的虚拟地址空间 ( 其他 Unix 系统的设计类此 ) 内核 (Kernel) 用户栈 (User Stack) 共享库 (Shared Libraries) 堆 (heap) 可读写数据 (Read/Write Data) 只读数据 (Read-only Data) 代码 (Code) 问题 : 加载时是否真正从磁盘调入信息到主存? 实际上不会从磁盘调入, 只是将代码和数据按 组块 与虚拟空间建立对应关系, 称为 映射 例如,hello 程序被加载器装入时, 首先创建其虚拟地址空间 ( 也称为存储器映像 ), 然后可执行文件的相关内容 复制 到代码段和数据段, 然后跳转到程序入口

137 MIPS 程序和数据的存储器分配 每个 MIPS 程序都按如下规定进行存储器分配 每个可执行文件都按如下规定给出代码和数据的地址 堆栈在高地址区, 从高到低增长 过程调用时, 生成当前 栈帧, 返回后退回当前栈帧 程序的动态数据 ( 如 :C 中的 malloc 申请区域 链表 ) 在堆 (heap) 中从低向高进行存放和释放 (free 时 ) 栈区位于堆栈高端, 堆区位于堆栈低端, 静态数据区上方 全局指针 $gp 固定设为 0x , 其 16 位偏移量的访问范围为 0x 到 0x1000 ffff 静态数据区从固定的 0x 处开始存放程序代码从固定的 0x 处开始存放故 PC 的初始值为 0x memory.137 这就是每个进程的虚拟 ( 逻辑 ) 地址空间!

138 虚拟存储器管理 实现虚拟存储器管理, 需考虑 : 块大小 ( 在虚拟存储器中 块 被称为 页 / Page ) 应多大? 主存与辅存的空间如何分区管理? 程序块 / 存储块之间如何映像? 逻辑地址和物理地址如何转换, 转换速度如何提高? 主存与辅存之间如何进行内容调换 ( 与 Cache 所用策略相似 )? 页表如何实现, 页表项中要记录哪些信息? 如何加快访问页表的速度? 如果要找的内容不在主存, 怎么办? 如何保护进程各自的存储区不被其他进程访问? 有三种虚拟存储器实现方式 : 分页式 分段式 段页式 memory.138

139 分页式系统 缺页的代价是什么? 读磁盘 ( 需花几百万个时钟周期!) 物理存储器和虚拟地址空间都被划分成大小物相等的页面磁盘和主存之间按页面为单位交换信息指令中给出的虚拟 ( 逻辑 ) 地址由虚页号和页内偏移量组成每个页表项记录对应虚页的情况 Valid 为 0 说明 miss ( 称为 page fault / 缺页 ) CPU 执行指令时, 首先需要将逻辑地址转换为主存的物理地址地址转换由 CPU 中的 MMU 实现 memory.139 Virtual page No. Valid Page table Physical page or Disk address 有些系统采用双表结构 : 主存页地址和磁盘页地址分开 Physical memory Disk storage 和 Cache 相比 : 页大小比 Cache 中 Block 大得多!32KB~64KB 采用全相联映射!Why? 通过软件来处理 缺页! Why? 采用 Write Back 写策略! Why?

140 页表结构 memory.140 每个进程有一个页表 典型页表中有装入位 修改 (Dirt) 位 替换控制位 访问权限位 禁止缓存位 实页号 页表项数由进程大小决定 页表在主存中的首址记录在页表基址寄存器中 必须解决页表占空间过大的问题 (1) 页表可能很大, 为了让一个进程具有很大的虚拟编程空间, 系统必须允许页表的项数足够多例如 : 在 VAX 系统中, 每个进程能拥有高达 2 31 =2G 字节的虚拟存储器, 按 512 字节 / 页进行分页, 则每个进程最多可达 2 22 个页表项 显然, 这么大的页表全部放在主存中是不适合的 (2) 系统中有许多进程, 每个进程有一个页表 解决页表过大的方法 一级页表 : 动态扩充, 限制大小 一级页表 : 分两个独立的段 二级或多级页表 : 一级为段 二级为页 将页表分页, 当前使用的页的页表项所在页表在内存, 其他在外存, 页表也要调进调出 反向 ( 倒置 ) 页表

141 倒置页表 (inverted page table) 结构 好处 : 页表的大小由页框数确定, 而不是由虚拟页数确定, 缩小了页表大小 虚页号用散列 (hash) 函数映射到散列表中 溢出 时, 由其链找到下项, 该项中页框号为所需虚页对应主存页框号 每项是一个指针, 指向倒置页表中的某项 页表项中记录有该虚页对应的主存页框号 memory.141

142 逻辑地址转换为物理地址的过程 PA Memory frame K 1K 1K 逻辑地址转换为物理地址过程 : Addr Trans MAP VA Virtual Memory page K 1K 1K unit of mapping also unit of transfer from virtual to physical memory memory VA page no. disp Page Table Base Reg index into page table V Page Table Access Rights PF# table located in physical memory + 当 V=0 时, 发生缺页当读写操作不符合 Access Right 时, 发生保护违例 actually, concatenation( 串联 ) is more likely frame no. disp PA

143 信息访问中可能出现的异常情况 可能有两种异常情况 : 1) 缺页 ( page fault) 产生条件 : 当 Valid( 有效位 / 装入位 ) 为 0 时相应处理 : 从磁盘中读信息到内存, 若内存没有空间, 则还要从内存选择一页替换到磁盘上, 替换算法类似于 Cache, 采用回写法, 页面淘汰时, 根据 dirty 位确定是否要写磁盘异常处理结束后 : 当前指令的执行被阻塞, 当前进程被挂起, 处理结束后回到原指令继续执行 2) 保护违例 ( protection_violation_fault ) 产生条件 : 当 Access Rights ( 存取权限 ) 与所指定的具体操作不相符时相应处理 : 在屏幕上显示 内存保护错 信息异常处理结束后 : 当前指令的执行被阻塞, 当前进程被终止 Access Rights ( 存取权限 ) 可能的取值有哪些? R = Read-only, R/W = read/write, X = execute only memory.143

144 TLBs --- Making Address Translation Fast 问题 : 一次内存引用要访问几次内存? 0 / 1 / 2 / 3 次? 把经常要查的页表项放到 Cache 中, 这种在 Cache 中的页表项组成的页表称为 Translation Lookaside Buffer or TLB( 快表 ) TLB 全相联时, 则没有 index, 只有 Tag, 虚页号需与每个 Tag 比 ; 若组相联时, 则虚页号高位为 Tag, 低位为 index, 用作组索引 Virtual Address Physical Address Dirty Ref Valid Access (tag+index) 虚页号分成 tag+index 对应物理页框号 memory.144 virtual page # 先由虚页号到 TLB 中找 若 TLB 中的 V=0 或 Tag VA, 则页表中找 若页表中的 V=0, 则缺页, 到磁盘中找 valid tag 页表 TLB page frame # 引入 TLB 的目减少到内存查页的是什么? 表的次数! Physical memory Disk storage 页表中需要 Tag 吗? 为什么?

145 Translation Look-Aside Buffers Miss1: TLB 中没有 VA Miss2: 页面不在主存 Miss3: PA 在主存中, 但不在 Cache 中 CPU CU VA TLB miss1 页表 PA hit1 Cache hit3 miss3 Main Memory miss1>>miss2, Why? miss2 hit2 因为 TLB 中的项比主存中的页数少得多! Page fault 可以用硬件也可以用软件来处理 TLB 失靶 (miss1) memory.145 1/2 t Miss1 的处理 : 查内存页表, 若发生 hit2, 则将页表项装入 TLB 中, 并进行地址转换 ; 否则 缺页, 引起相应的异常处理 大多用全相联 : 命中率高, 因为小, 故成本不高采用随机替换策略 : 降低替换算法的开销采用回写策略 : 减少访问内存的次数 t 20 t TLB 的一些典型指标 : TLB 大小 :16~512 项块大小 :1~2 项 ( 每个表项 4-8B) 命中时间 :0.5~1 个时钟周期失靶损失 :10~100 个时钟周期命中率 :90~99%

146 举例 : 三种不同缺失的组合 三种不同缺失 :TLB 缺失 Cache 缺失 缺页 三种缺失的组合情况的可能性分析 可能,TLB 命中则页表一定命中, 但实际上不会查页表可能,TLB 缺失但页表可能命中, 信息在主存, 就可能在 Cache 可能,TLB 缺失但页表可能命中, 信息在主存, 但可能不在 Cache 可能,TLB 缺失页表可能缺失, 信息不在主存, 一定也不在 Cache 不可能, 页表缺失, 说明信息不在主存,TLB 中一定没有该页表项同上不可能, 页表缺失, 说明信息不在主存,Cache 中一定也没有该信息最好的情况应该是 hit hit hit, 此时, 访问主存几次? 不需要访问主存! 以上组合中, 最好的情况是什么? hit hit miss 和 miss hit hit 只需访问主存 1 次以上组合中, 最坏的情况是什么? miss miss miss 需访问磁盘 并访存至少 2 次介于最坏和最好之间的是什么? miss hit miss 不需访问磁盘 但访存至少 2 次 memory.146

147 举例 : 内置 FastMATH TLB 页大小 4KB, 虚拟地址为 32 位, 则虚页号位数为多少? 32-12=20 位 地址转换 VA->PA 根据 PA 访问 cache 或主存 memory.147

148 虚拟地址 TLB 缺页处理 页表 物理地址 命中 cache 主存 缺失

149 CPU 访存过程 memory.149

150 分页式和分段式的比较 分页系统的特点 优点 : 实现简单, 开销少 因为只有进程的最后一个零头 ( 内部碎片 ) 不能利用, 故浪费很小 缺点 : 由于页不是逻辑上独立的实体, 因此可能会出现如 一条指令跨页 等问题, 使处理 管理 保护和共享等都不方便分段系统的实现 程序员或 OS 将程序模块或数据模块分配给不同的主存段, 一个大程序有多个代码段和多个数据段构成, 是按照程序的逻辑结构划分而成的多个相对独立的部分 ( 例如, 过程 子程序 数据表 阵列等 ) 段通常带有段名或基地址, 便于编写程序 编译器优化和操作系统调度管理 段可作为独立逻辑单位被其他程序调用, 以形成段间连接, 产生规模较大的程序 分段系统将主存空间按实际程序中的段来划分, 每个段在主存中的位置记录在段表中, 并附以 段长 项 段表本身也是主存中的一个可再定位段 因为段本身是程序的逻辑结构所决定的一些独立部分, 因而分段对程序员来说是不透明的 ( 而分页对程序员来说是透明的 ) memory.150

151 段式虚拟存储器的地址映像 物理地址 = 段起始地址 + 段内偏移量 Faults ( 异常情况 ): 缺段 ( 段不存在 ): 装入位 = 0 地址出界 : 偏移量超出最大段长保护违例 : 访问操作不符合访问方式指定的类型 memory.151

152 段式虚拟存储器的地址变换图 memory.152

153 分段式系统的特点 分段式和段页式的比较 优点 : 段的分界与程序的自然分界对应, 故段具逻辑独立性, 易于编译 管理 修改和保护, 便于多道程序共享 ; 某些类型的段 ( 堆栈 队列 ) 具有动态可变长度, 允许自由调度以有效利用主存空间 缺点 : 段长各不相同, 起 终点不定, 变化很大, 给主存分配带来麻烦, 且易在段间留下许多空余的零碎空间, 不好利用, 造成浪费 ( 例如 : 一个长段调出后, 调进一个短段就会造成碎区 ) 段页式系统基本思想 段 页式结合 程序按模块分段, 段内再分页, 进入主存仍以页为基本单位 逻辑地址由段地址 页地址和偏移量三个字段构成 用段表和页表 ( 每段一个 ) 进行两级定位管理 根据段地址到段表中查阅与该段相应的页表指针, 转向页表, 然后根据页地址从页表中查到该页在主存中的页框地址, 由此再访问到页内某数据 memory.153

154 段页式虚拟存储器的地址变换 memory.154

155 ( 自学 )Pentium 处理器的寻址方式 操作数的来源 : 立即数 ( 立即寻址 ): 直接来自指令 寄存器 ( 寄存器寻址 ): 来自 32 位 / 16 位 / 8 位通用寄存器 存储单元 ( 其他寻址 ): 需进行地址转换逻辑地址 => 线性地址 LA ( => 内存地址 ) 分段分页 指令中的信息 : (1) 段寄存器 SR( 隐含或显式给出 ) (2) 8/16/32 位偏移量 A ( 显式给出 ) (2) 基址寄存器 B ( 明显给出, 任意通用寄存器皆可 ) (3) 变址寄存器 I ( 明显给出, 除 ESP 外的任意通用寄存器皆可 ) 有比例变址和非比例变址 比例变址时要乘以比例因子 S (1:8 位 / 2:16 位 / 4:32 位 / 8:64 位 ) memory.155

156 寻址方式 ( 自学 ) Pentium 处理器寻址方式 算法 立即 ( 地址码 A 本身为操作数 ) 寄存器 ( 通用寄存器的内容为操作数 ) 偏移量 ( 地址码 A 给出 8/16/32 位偏移量 ) 基址 ( 地址码 B 给出基址器编号 ) 基址带偏移量 ( 一维表访问 ) 比例变址带偏移量 ( 一维表访问 ) 基址带变址和偏移量 ( 二维表访问 ) 基址带比例变址和偏移量 ( 二维表访问 ) 相对 ( 给出下一指令的地址, 转移控制 ) 操作数 =A 操作数 =(R) LA=(SR)+A LA=(SR)+(B) LA=(SR)+(B)+A LA=(SR)+ (I)xS+A LA=(SR)+(B)+(I) +A LA=(SR)+(B)+(I)xS+A 转移地址 =(PC)+A memory.156

157 ( 自学 )Pentium 处理器的存储器寻址 段寄存器 基址寄存器 线性地址空间 SS 变址寄存器 CS 段选择符 段表项 ( 段描述符 ) + x 比例因子 1/2/4/8 偏移量 8/16/32 位 基址 段限 存取权段限 有效地址 + 线性地址 基地址 memory.157

158 存储保护的基本概念 什么是存储保护? 为避免主存中多道程序相互干扰, 防止某程序出错而破坏其他程序的正确性, 或某程序不合法地访问其他程序或数据区, 应对每个程序进行存储保护 操作系统程序和用户程序都需要保护 以下情况发生存储保护错 地址越界 ( 转换得到的物理地址不属于可访问范围 ) 访问重定位 键保护 环保护 访问越权 ( 访问操作与所拥有的访问权限不符 ) 页表中设定权限 访问属性的设定 数据段可指定 R/W 或 RO; 程序段可指定 R/E 或 RO 最基本的保护措施 : 规定各道程序只能访问属于自己所在的存储区和共享区 对于属自己存储区的信息 : 可读可写 对共享区或已获授权的其他用户信息 : 可读不可写 对未获授权的信息 ( 如 OS 内核 页表等 ): 不可访问 memory.158

159 存储保护的硬件支持 为了对操作系统的存储保护提供支持, 硬件必须具有以下三种基本功能 : 支持至少两种运行模式 : 管理模式 (Supervisor Mode) 用于完成操作系统各种功能的进程为系统进程, 也称为内核 (Kernel) 进程 管理 (Supervisor) 进程 执行系统进程时处理器所处的模式称为管理模式 (Supervisor Mode), 或称管理程序状态, 简称管态 管理态 核心态 用户模式 (User Mode) 完成非操作系统功能的进程称为用户进程, 当系统运行用户进程时, 处理器模式就是用户模式, 或称用户状态 目标程序状态, 简称为目态或用户态 使一部分 CPU 状态只能由系统进程写而不能由用户进程写 ( 只能读 ): 这部分状态包括 :User/Supervisor 模式位 页表首地址 TLB 等 OS 内核可以用特殊的指令 ( 一般称为管态指令 ) 来写这些状态 提供让 CPU 在管理模式和用户模式相互转换的机制 : 异常 和 陷阱 ( 系统调用 ) 使 CPU 从用户模式转到管理模式 ; 异常处理中的 返回 指令 (return from exception) 使 CPU 从管理状态转到用户状态通过上述三个功能并把页表保存在 OS 的地址空间,OS 就可以更新页表, 并防止用户进程改变页表, 确保用户进程只能访问由 OS 分配给的存储空间 memory.159