<4D F736F F F696E74202D20B5DAC6DFD5C220B4E6B4A2C6F7B2E3B4CEBDE1B9B92E707074>

Transcription

1 Computer Organization and Design Ch7: 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 addressable memory 按内容检索到存储位置进行读写 例如 : 快表 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 Memory) 位于主机之外, 用来存放暂不运行的程序 数据或存档文件 用磁表面或光存储器实现, 容量大而速度慢 memory.7

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

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

10 memory.10 存储容量和速度的单位 Notations and Conventions for Numbers H P CPrefix Appendix1: Abbreviation Notations Meaning and Conventions Numeric for Numbers Value 3 Amill m One thousandth 10 6 micro µ One millionth nano n One billionth pico p One trillionth femto f One quadrillionth 10 atta a One quintillionth kilo K (or k) Thousand or 2 mega M Million 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 个晶体管组成. 每 ms 必须刷新一次 对电器干扰比较敏感 比 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 回顾 :DRAM 的存储单元 字线 单管动态 MOS 存储单元 字线 位线 接地 C 位线 读放大器 存储单元 信息存储原理 电容 Cnode 处于充电状态时, 表示 1; 电容 Cnode 处于放电状态时, 表示 0 写入时 : 字线 位线 V 读出时 : 字线 位线 电容 C node V ~ C node / C BL memory.13

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

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

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

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

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

19 位扩展为芯片位数的 16 倍 字扩展为芯片字数的 4 倍 memory.19

20 回顾 :DRAM 存储器基本结构 wordline bit gnd 主要组成部分 : 存储矩阵 地址译码器 读 / 写缓冲及控制电路 工作过程 : 使用行地址和行选通信号 (RAS) 选择某一行存储单元 A 0 A 1 A i 行地址译码器 D 0 存储矩阵 D m-1 将该行所有单元的信息读 出送到芯片内部的行缓冲器 使用列地址和列选通信号 (CAS) 选择缓冲器的某一列 数据从缓冲器选出并拷贝 A i+1 A n+1 CS R/W 列地址译码器读 / 写控制电路 到数据总线, 然后送给 CPU 行地址列地址 I / O 0 I / O m-1 memory.20

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

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

23 举例 2: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.23 每次访存操作总是在某一个内存条内进行!

24 举例 2: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 cols DRAM Chip 0 DRAM Chip K x 8 = 2 Mb One page 512 rows 256K x 8 = 2 Mb 8 bits SRAM bits<127:0> 行缓冲 memory SRAM Memory Bus<127:0> bits<7:0> 16 个芯片的行缓冲可以缓存 16x512x8 位数据当 CPU 访问一块连续的内存区 ( 即 : 行地址相同 ) 时, 可直接从行缓冲读取, 行缓冲用 SRAM 实现, 速度极快! Cache 行读要求从内存读一块连续区, 给定一个首地址, 采用突发传输方式

25 举例 3:128MB 的 DRAM 存储器 ( 行地址 i, 列地址 j) 总容量 =128 MB DRAM 0 由 8 片 DRAM 芯片构成 每片 16Mx8 bits DRAM 7 行地址 列地址各 12 位 每 1 行共 4096 列 (8 位 / 列 ) 地址 A 4096 行 选中某一行并读出之后再由列地址选择其中的一列 bits bits bits bits bits bits bits 8-15 bits 0-7 (8 个二进位 ) 送出 主存储器地址 A 处的 64-bit 数据 0 存储控制器 : 行 列地址为 (i,j) 的 8 个单元 64-bit 双字 memory.25

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

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

28 分类 : 回顾 : 只读存储器 (Read Only Memory) MROM: 腌膜只读存储器 (Mask ROM) PROM: 可编程只读存储器 (Programmable ROM) EPROM: 可擦除可编程只读存储器 (Erasable PROM) EEPROM(E 2 PROM) : 电可擦除可编程只读存储器 (Electrically EPROM) flash memory: 闪存 memory.28

29 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.29

30 Principles of Memory Hierarchy( 分层原则 ) 数据总是在相邻两层之间复制传送 Upper Level: 上层更靠 CPU Smaller, faster, and uses more expensive technology Lower Level: 下层更远离 CPU Bigger, slower, and uses less expensive technology Block: 数据在相邻两层之间复制传送的最小单位是一个定长块 To Processor From Processor Upper Level Memory Blk X Lower Level Memory Blk Y memory.30

31 Memory Hierarchy: How Does it Work? To Processor From Processor Upper Level Memory Blk X Lower Level Memory Blk Y 时间局部性 (Temporal Locality) 含义 : 刚被访问过的单元很可能不久又被访问做法 : 让最近被访问过的信息保留在靠近 CPU 的存储器中 空间局部性 (Spatial Locality) 含义 : 刚被访问过的单元的邻近单元很可能不久被访问做法 : 将刚被访问过的邻近单元调到靠近 CPU 的存储器中 memory.31

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

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

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

35 回顾 : 存储器与 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.35 从上图可以看出什么? DRAM 硬盘与 CPU 之间的速度差距愈来愈大! 解决内存访问速度慢的措施有三个 : 提高主存芯片本身的速度 采用多模块存储器技术 在主存和 CPU 之间加入 Cache

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

37 加快访存速度措施之二 : 多模块存储器 多体存储器和多模块存储器 多体存储器 由若干个小体组成 共用一个地址寄存器 MAR 和一个数据寄存器 MDR 不能提高数据访问速度 多模块存储器 也包含多个小体 每个体有其自己的 MAR MDR 和读写电路 可独立组成一个存储模块 能提高数据访问速度根据不同的编址方式可分为连续编址和交叉编址 memory.37

38 多体存储器结构图 memory.38 Back to Last

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

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

41 Increasing Bandwidth - Interleaving Cycle Time Access Time Time Cycle Time 和 Access Time 的关系 DRAM Cycle Time >> DRAM Access Time 大约为 2:1 需要再生 刷新 复位等操作为下次作准备 DRAM (Read/Write) Cycle Time : How frequent can you initiate an access? Analogy: A little kid can only ask his father for money on Saturday DRAM (Read/Write) Access Time: How quickly will you get what you want once you initiate an access? Analogy: As soon as he asks, his father will give him the money DRAM Bandwidth Limitation analogy: What happens if he runs out of money on Wednesday? Ask his mother for money on Wednesday! memory.41

42 Increasing Bandwidth - Interleaving Access Pattern without Interleaving: CPU Memory D1 available Start Access for D1 Start Access for D2 Access Pattern with 4-way Interleaving: CPU Memory Bank 0 Memory Bank 1 Memory Bank 2 Access Bank 0 memory.42 Access Bank 1 Access Bank 2 Access Bank 3 We can Access Bank 0 again Memory Bank 3

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

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

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

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

47 程序的局部性原理举例 程序局部性的表现 : memory.47 高级语言源程序 对应的汇编语言程序 sum = 0; for (i = 0; i < n; i++) sum += a[i]; *v = sum; I0: sum <-- 0 I1: ap <-- 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 每条指令 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

48 Cache( 高速缓存 ) 是什么样的? Cache 是一种小容量高速缓冲存储器, 它由 SRAM 组成 Cache 直接制作在 CPU 芯片内, 速度几乎与 CPU 一样快 程序运行时,CPU 使用的一部分数据 / 指令会预先成批拷贝在 Cache 中,Cache 的内容是主存储器中部分内容的映象 当 CPU 需要从内存读 ( 写 ) 数据或指令时, 先检查 Cache 中有没有, 若有, 就直接从 Cache 中读取, 而不用访问主存储器 数据访问过程 : Cache 存储器 主存储器 10 4 主存中的部分信息拷贝在 Cache 存储器中 memory.48

49 Cache-friendly 程序举例 以下程序 A 和 B 中, 哪一个对数组 A 引用的空间局部性更好? 时间局部性呢? 变量 sum 的空间局部性和时间局部性如何? 对于指令来说,for 循环体的空间局部性和时间局部性如何? memory.49 程序段 A: int sumarrayrows(int A[2048][2048]) { int i, j, sum=0; for (i=0; i<2048, i++) for (j=0; j<2048, j++) sum+=a[i][j]; return sum; } 程序段 B: int sumarraycols(int A[2048][2048]) { int i, j, sum=0; for (j=0; j<2048, j++) for (i=0; i<2048, i++) sum+=a[i][j]; return sum; } 提示 : 数组在存储器中按照先行后列存放 主存的布局 : 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 指令数据

50 memory.50 程序段 A: int sumarrayrows(int A[2048][2048]) { int i, j, sum=0; for (i=0; i<2048, i++) for (j=0; j<2048, j++) sum+=a[i][j]; return sum; } Cache-friendly 程序举例 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 分配在寄存器中, 最后才写回存储器! 指令数据

51 memory.51 Cache-friendly 程序举例 程序段 B: int sumarraycols(int A[2048][2048]) { int i, j, sum=0; for (j=0; j<2048, j++) for (i=0; i<2048, i++) sum+=a[i][j]; return sum; } 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 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 倍!! I1 I2 A sum 指令数据

52 Cache 的操作过程 如果被访问的信息不在 cache 中, 称为失效 (miss) 失靶处理 如果被访问的信息在 cache 中, 称为命中 (hit) memory.52

53 命中率 失靶率 失靶损失 Hit: 要访问的信息在 Cache 中 Hit Rate( 命中率 ): 在 Cache 中的概率 Hit Time ( 命中时间 ) : 在 Cache 中的访问时间, 包括 : Cache access time + Time to determine hit/miss ( 即 : Cache 访问 + 判断时间 ) Miss: 要找的信息不在 Cache 中 Miss Rate ( 失靶率 / 失效率 ) = 1 - (Hit Rate) Miss Penalty ( 失靶损失 ): 从主存替换到 Cache, 并送 CPU 的时间 Time to replace a block in Cache + Time to deliver the block to the processor ( 即 :Cache 替换 + 送 CPU 时间 ) Hit Time << Miss Penalty (Why?) Average Access Time = Hit Rate Hit Time + Miss Rate Miss Penalty memory.53

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

55 看看命中率对平均访问时间的影响 设平均访问时间 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.55

56 看看命中率该有多高? 怎样才能得到这么高的命中率? 实现 Cache 要解决的问题 : 主存和 Cache 怎样分块? 它们之间如何映射 (Mapping)? 块的大小多大为好? Cache 已满的情况下, 要装入新块, 怎么办? 信息被修改时, 是不是要同时修改 Cache 和主存中的内容? memory.56

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

58 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.58 SKIP

59 直接映射 Cache 组织示意图 假定 : 数据在主存和 Cache 之间按块传送的单位为 512 字 Cache 大小 :2 13 字 =8K 字 =16 槽 x 512 字 / 槽 主存大小 : 2 20 字 =1024K 字 =2048 块 x 512 字 / 块 Cache 标记 (tag) 指出对应槽取自哪个主存块群 主存 tag 指出对应地址位于哪个块群 两个标记相等时, 说明要找的地址在对应槽中 memory.59 BACK

60 Ex1: 极端直接映射 Cache ( 容量 4B, 每槽 1B) Memory Address A B C D E F Memory 4 Byte Direct Mapped Cache Cache Index 一个主存块应该放到哪个 Cache 槽中? Cache 槽号 : (Block Addr) module 4 即 :Address<1:0> => cache index Location 0 can be occupied by data from: Memory location 0, 4, 8,... etc. In general: any memory location whose 2 LSBs of the address are 0s memory.60

61 memory.61 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 N bits Cache Address 31 Valid Bit 3 =1 否? 1 : Cache Tag Example: 0x50 Cache Index Ex: 0x03 Cache tag 0x50 : 2 = 否? N 2 N Bytes Cache Data Byte 0 Byte 1 Byte 2 Byte 3 : N Byte N 2-1 这里假设一个 Cache 行 ( 等于一个主存块 ) 只有一个字节 ( 不合理!) 0 1

62 Definition of a Cache Block ( 块大小多大为好?) 对于前面给出的极端例子 : 4-byte Direct Mapped cache: Block Size = 1 Byte Valid Cache Tag Direct Mapped Cache Data Byte 0 Byte 1 Byte 2 Byte 3 利用了时间局部性 : 某字节不久又可能被用 没有利用空间局部性 : 某字节的邻近字节不久可能也被用, 但没有被调到 Cache( 每次调入的一块信息只有一个字节!) 可以通过增大块的大小来利用空间局部性 1. Can we say the larger, the better for the block size? 2. How big should Cache Block(slot / line / entry)be? 后面会来说明这个问题! memory.62

63 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 3 Valid Bit 4 1 : Cache Tag 0x50 : Cache Data Byte 31 Byte 63 : : Byte 1 Byte 33 : 2 Byte 0 Byte Byte 1023 : Byte memory.63

64 Ex3: 64 KB Direct Mapped Cache with 16B Blocks For a 2 N byte cache (N=16 in this example) The uppermost (32 - N) bits are always the Cache Tag The lowest M bits of the Byte Select (M=4 in this example) are further divided into block offset and byte offset 块大小为多少? 31 Memory Address 0 共有 (64K / 16)= 4K 项 Byte Hit V Tag 16 tag 2 Index Byte offset 1 5 Block offset 128 data Mux Word 4K Entries memory.64 = 3 Mux 32 4 Data

65 如何计算 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) 书中 P314 有错! memory.65

66 全相联映射 (Fully Associative) 每个主存块可装入到 Cache 的任一槽 Slot( 行 Line 或入口 Entry) 中 称为全映射或全相联映射 每个槽有个标志字段, 用于指出该槽取自主存的哪个块 假如主存有 2048 块, 每块大小为 512 字, 则主存地址共有 20 位, 其中 : 11 位标志 9 位块内字号 高 11 位表示该地址位于主存哪一块 特点 : 比直接映射灵活 采用相联存取技术 ( 按内容访问 ), 实现复杂 速度慢 Cache 标志位数增加, 比较逻辑成本随之增加 SKIP memory.66

67 假定 : 数据在主存和 Cache 之间按块传送的单位为 512 字 Cache 大小 :2 13 字 =8K 字 =16 槽 x 512 字 / 槽 主存大小 : 2 20 字 =1024K 字 =2048 块 x 512 字 / 块 全相联映射 Cache 组织示意图 Cache 标记 (tag) 指出对应槽取自哪个主存块 主存 tag 指出对应地址位于哪个主存块 两个标记相等时, 说明要找的地址在对应槽中 每个主存块可以放到任一个 Cache 槽中, 所以需要将主存块号和所有 Cache 标记进行比较, 若都不相等, 则说明要找的地址不在 Cache 中 memory.67 BACK

68 举例 :Fully Associative Fully Associative Cache 无需 Cache 索引, 为什么? 因为同时比较所有 Cache 项的标志 By definition: Conflict Miss = 0 for a fully associative cache ( 全相联映射没有冲突失靶, 因为只要有空闲 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.68

69 memory.69

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

71 假定 : 数据在主存和 Cache 之间按块传送的单位为 512 字 Cache 大小 :2 13 字 =8K 字 =16 槽 x 512 字 / 槽 =8 组 x2 槽 / 组 x512 字 / 槽 主存大小 : 2 20 字 =1024K 字 =2048 块 x 512 字 / 块 Cache 标记 (tag) 指出对应槽取自哪个主存组群 主存 tag 指出对应地址位于哪个主存组群中 组相联映射的 Cache 组织图 两个标记相等时, 说明要找的地址在对应槽中 memory.71 将主存地址标记和固定 Cache 组中每个 Cache 标记进行比较 BACK

72 例 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 中 Valid 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.72 3 Hit OR 4 Cache Block 3

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

74 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.74 Hit Cache Block

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

76 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.76

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

78 memory.78 ( 自学 ) 替换算法 - 先进先出 (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 不是一种堆栈算法, 即命中率并不随组的增大而提高

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

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

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

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

83 有效位 (Valid Bit) 通过使 V=0 冲刷 Cache 命中时 V=1 开机或复位时使 V=0 第一次被替换时使 V=1 memory.83

84 举例 假定计算机系统有一个容量为 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.84

85 举例 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/(ptc+(1-p)tm)=10/(p+10x(1-p))=9.5 倍 memory.85

86 举例 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/(ptc+(1-p)tm)=10/(p+10x(1-p))=9.77 倍 memory.86

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

88 基本的 Cache 处理算法 memory.88

89 Write Policy: Write Through versus Write Back 处理 Cache 读比 Cache 写更容易 所以, 指令 Cache 比数据 Cache 容易设计 Cache write:( 数据一致性问题 ) 如何保持 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 块 每块有个 脏 位 大大降低主存带宽需求 SKIP 控制可能很复杂 memory.89

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

91 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.91

92 写策略 1:Write Through 算法 memory.92 BACK

93 写策略 2:Write Back 算法 memory.93

94 写策略 2:Write Back 中的脏位 BACK memory.94

95 Cache 大小 Block 大小和失靶率 Cache 大小 :Cache 越大,Miss 率越低! Block 大小 : 合理的 Block 大小与 Cache 大小有关, 且不能太大, 也不能太小! memory.95

96 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.96

97 系统中的 Cache 数目 当 Cache 技术刚被引入时通常系统只有一个 Cache 近年来, 多 Cache 系统已成为主流 多 Cache 系统中, 主要有两个考虑因素 : [1] 单级 / 多级片内 (On-chip)Cache: 将 Cache 和 CPU 作在一个芯片上 外部 (Off-chip)Cache: 不做在 CPU 内而是独立设置一个 Cache 单级 Cache: 只用一个片内 Cache. 多级 Cache: 同时使用片内 L1 Cache 和 L2 Cache [2] 联合 / 分立联合 : 指数据和指令都放在一个 Cache 中 一般 L2 Cache 都是联合 Cache 分立 : 指数据和指令分开存放在各自的数据和指令 Cache 中 一般 L1 Cache 都是分立 Cache memory.97

98 复习 :Cache 的操作过程 如果被访问的信息不在 cache 中, 称为失效 (miss) 硬件如何进行失靶处理? 失靶处理 如果被访问的信息在 cache 中, 称为命中 (hit) memory.98

99 Cache 失靶处理 在使用 Cache 的系统中, 数据通路中的指令存储器 IM 和数据存储器 DM 就分别是 Code Cache 和 Data Cache CPU 执行指令过程中, 取指令或取数据时, 如果发生失靶, 则指令执行被阻塞 发生缺失的检测 Cache 中有相应的检测线路 ( 地址高位与 Cache 标志比较 ) 阻塞处理过程 冻结所有临时寄存器和程序员可见寄存器的内容 ( 即 : 使整个计算机阻塞 ) 由一个单独的控制器处理 Cache 失靶, 其过程 ( 假定是指令失靶 ): 把发生失靶的指令地址 ( 如 :PC-4) 所在的主存块首址送到主存 启动一次 主存块读 操作, 并等待主存完成一个主存块 (Cache 行 ) 的读操作 把读出的一个主存块写到 Cache 对应表项 ( 槽 / 行 / 块 ) 的数据区 ( 若对应表项全满的话, 还要考虑淘汰掉一个已在 Cache 中的主存块 ) 把地址高位部分 ( 标记 ) 写到 Cache 的 tag 字段, 并置 有效位 重新执行指令的第一步 : 取指令 若是读数据失靶, 其处理过程和指令失靶类似 从主存读出数据后, 从 取数 那一步开始重新执行就可以了 若是写数据失靶, 则要考虑用哪种 写策略 解决 一致性 问题 比数据相关或分支指令引起的流水线阻塞简单 : 只要保持所有寄存器不变 与中断引起的阻塞处理不同 : 不需要程序切换 memory.99

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

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

102 复习 :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 cols DRAM Chip 0 页模式 : 一行为一页 ( 块 ) DRAM Chip K x 8 = 2 Mb One page 512 rows 256K x 8 = 2 Mb 8 bits SRAM bits<127:0> 行缓冲 memory SRAM Memory Bus<127:0> bits<7:0> 16 个芯片的行缓冲可以缓存 16x512x8 位数据当 CPU 访问一块连续的内存区 ( 即 : 行地址相同 ) 时, 可直接从行缓冲读取, 行缓冲用 SRAM 实现, 速度极快! Cache 行读要求从内存读一块连续区, 给定一个首地址, 采用突发传输方式

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

104 复习 : 提高 DRAM 存储器速度的措施 之一 : 采用芯片内部行缓冲, 以提高芯片本身的速度反复多次使用芯片内部缓冲器中的内容, 不要每次都重复地进行 行访问 DDR SDRAM (Double data-rate synchronous DRAM) 和 DDR2 SDRAM 时钟频率 =100MHz 内部频率 =100MHz 传输频率 =200MHz 时钟频率 =100MHz 内部频率 =200MHz 传输频率 =400MHz 存储单元阵列 数据总线 存储单元阵列 数据总线 DDR SDRAM DDR2 SDRAM 之二 : 多模块交叉存取 2 个 4 个或多个存储器同时工作 memory.104

105 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.105

106 举例 : 失靶带来的损失到底多大? 设 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.106

107 举例 : 处理器速度提高而存储器不变时的情况 例 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.107 由此可知 : 时钟快的机器的性能只是较慢时钟机器的 1.2 倍 如果没有 Cache 失靶的话, 应该是 2 倍! 结论 :CPU 时钟频率越高,Cache 缺失损失就越大 上述两个例子说明 : 处理器性能越高, 高速缓存的性能就越重要!

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

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

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

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

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

113 实例 : 奔腾机的 Cache 组织 Pentium 的数据 Cache 内部组织 : 主存 :4GB=2 20 x 2 7 块 x 2 5 B/ 块 Cache:8KB=128 组 x2 槽 / 组 x32b/ 槽主存地址划分 :: 20 标志位 组号 替换算法 : LRU, 每组有一位 LRU 位, 用于记录该组 2 个槽的使用情况 可以这样规定 : 该位为 0, 则下次将淘汰第 0 槽 该位为 1, 则下次淘汰第 1 槽 写策略 : 默认方式为一次性写 (Write Back), 也可动态设置为通过式写 (Write Through) Cache 一致性 : 支持 MESI 协议 ( 有关该协议将来其他课程将详细介绍 ) memory.113

114 memory.114

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

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

117 第一次作业 memory.117

118 第三讲虚拟存储器 主要内容 存储管理技术的发展过程 虚拟存储器的基本概念 页面大小的选择 存储器管理方式 页式 段式 段页式 逻辑地址和物理地址的转换 主存与辅存之间替换策略 页表的实现 ( 页表项中要记录哪些信息等 ) 快表 ( 如何加快访问页表的速度 ) 缺页处理 存储保护 地址越界检查 存取权限检查 memory.118

119 复习 : 一个典型程序的转换处理过程 经典的 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.119

120 复习 :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.120

121 复习 :Hello 程序的数据流动过程 Red:shell 命令行处理 Blue: 可执行文件加载 Cyan:hello 程序执行过程 hello hello,world/n hello hello,world/n Hello 可执行文件 memory.121 数据经常在各存储部件间传送 故现代计算机大多采用 缓存 技术! 所有过程都是在 CPU 执行指令所产生的控制信号的作用下进行的

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

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

124 虚拟地址空间 虚存为每个进程提供了一个假象 好像每个进程都独占使用主存, 并且主存空间极大 虚存是主存和磁盘 I/O 设备的抽象 OS 使每个进程看到的存储空间都一致, 称为虚拟 ( 逻辑 ) 地址空间 Linux 操作系统的虚拟地址空间 ( 其他 Unix 系统的设计类此 ) 内核 (Kernel) 用户栈 (User Stack) 共享库 (Shared Libraries) 堆 (heap) 可读写数据 (Read/Write Data) 只读数据 (Read-only Data) 代码 (Code) memory.124

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

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

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

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

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

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

131 分页 (Paging) 基本思想 : 把内存分成固定长且比较小的存储块, 每个进程也被划分成固定长的程序块 程序块 ( 页 /page) 可装到存储器可用的存储块 ( 页框 /page frame) 中 无需用连续页框来存放一个进程 操作系统为每个进程生成一个页表 通过页表 (page table) 实现逻辑地址向物理地址转换 (Address Mapping ) 逻辑地址 (Logical 或 Virtual Address): 程序中的指令所用的地址 物理地址 (physical 或 Memory Address): 存放指令或数据的实际内存地址 浪费的空间最多是最后一页的一小部分! memory.131 BACK

132 虚拟存储器的概念 每个程序链接后都映射到同样的虚拟地址空间 用户程序加载后, 操作系统内核生成程序的一个进程, 其中包括该进程的页表, 通过页表建立用户进程的虚拟地址空间和物理存储器 ( 磁盘和主存 ) 之间的映射关系 所有用户进程所用的虚拟地址空间一样, 由虚拟地址的位数确定大小 采用 按需调页 / Demand Paging 方式对主存进行分配 : 在进程执行过程中, 操作系统把当前需要的用户程序的一部分从磁盘调到内存中, 并把存放的物理地址信息记录到页表中, 进行虚拟地址空间到物理地址空间的重定位 存储管理机制分为有三种 : 分页式 分段式 段页式 虚拟存储器的实现 : 由 CPU 芯片内的存储管理部件 (MMU) 和 OS 两者协调完成 memory.132

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

134 分页式系统 缺页的代价是什么? 读磁盘 ( 需花几百万个时钟周期!) 物理存储器和虚拟地址空间都被划分成大小物相等的页面 磁盘和主存之间按页面为单位交换信息 指令中给出的虚拟 ( 逻辑 ) 地址由虚页号和页内偏移量组成 每个页表项记录对应虚页的情况 Valid 为 0 说明 miss ( 称为 page fault / 缺页 ) CPU 执行指令时, 首先需要将逻辑地址转换为主存的物理地址 地址转换由 CPU 中的 MMU 实现 memory.134 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?

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

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

137 逻辑地址转换为物理地址的过程 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

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

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

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

141 举例 : 三种不同缺失的组合 三种不同缺失 :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.141

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

143 Putting VM TLB Cache all together memory.143

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

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

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

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

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

149 ( 自学 )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.149

150 ( 自学 ) 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.150

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

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

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

154 通过程序重定位进行存储保护 把逻辑地址转换为实际的物理地址的过程称为 地址转换 或 程序重定位 重定位方式 : 静态 : 在装入前将所有地址全部转换为物理地址 动态 : 靠硬件的地址转换机构来实现, 在程序执行过程中动态进行地址转换 动态定位可实现程序在主存中的浮动 程序重定位是通过逻辑地址加界 ( 即加基准地址 ) 来实现的 通过对程序生成的地址进行越界判断, 可实现程序的保护 对程序生成的地址进行判断, 若在界限内, 则说明没有越界, 否则访问越界 memory.154

155 键保护和环保护方式 键保护方式 系统为每道作业设置一个保护键 为某作业分配主存时, 根据它的保护键在页表中建立键标志 进程运行时, 将程序状态寄存器中的键 ( 程序键 ) 和访问页的键 ( 存储键 ) 进行核对, 相符时才可访问该块, 如同 锁 与 钥匙 的关系 为使某块能被各进程访问, 或某个进程可访问任何一块, 规定键标志为 0, 此时不进行核对工作 例如, 操作系统有权访问所有块, 所以可让 OS 的程序状态字中的键为 0 环保护方式 主存中各进程按其重要性分为多个保护级, 各级别构成同心环 最内环的进程保护级别最高, 向外逐次降低 内环进程可以访问外环和同环进程的空间, 而外环不得访问内环进程空间 系统进程的保护级别高, 环号小, 而用户进程大都处于外环 Pentium 采用该方案 memory.155

156 TLB 失靶处理和缺页处理 TLB 失靶处理 当 TLB 中没有一项的虚页号与要找的虚页号相等时, 发生 TLB miss TLB miss 说明可能发生以下两种情况之一 : 页在内存中 : 只要把主存中的页表项装载到 TLB 中 页不在内存中 ( 缺页 ):OS 从磁盘调入一页, 并更新主存页表和 TLB 缺页 (page fault) 处理 当主存页表的页表项中 valid 位为 0 时, 发生 page fault Page fault 是一种 故障 异常, 按以下过程处理 (MIPS 异常处理 ) 在 Cause 寄存器置相应位为 1 发生缺页的指令地址 (PC 减 4) 送 EPC 0x ( 异常查询程序入口 ) 送 PC 执行 OS 的异常查询程序, 取出 Cause 寄存器中相应的位分析, 得知发生了 缺页, 转到 缺页处理程序 执行 page fault 一定要在发生失靶的存储器操作时钟周期内捕获到, 并在下个时钟转到异常处理, 否则, 会发生错误 例 :lw $1, 0($1), 若没有及时捕获 异常 而使 $1 改变, 则再重新执行该指令时, 所读的内存单元地址被改变, 发生严重错误! memory.156

157 ( 自学 ) 缺页处理程序 保存正在运行的进程的所有状态, 包括程序可见寄存器 页表地址寄存器 EPC 和 Cause 寄存器 确定缺失的是指令还是数据 若是指令, 则发生在取指令阶段 (EPC 中的地址是缺失地址 ) 若是数据, 则发生在取数或存数阶段 完成磁盘读 / 写操作 查找页表项, 得到磁盘地址, 找到盘上被访问页的位置 选择被替换的页, 若被替换页已 脏, 则把新页替换到内存前先写回磁盘 启动磁盘读操作, 把被访问页调到所选择的物理页框中 ( 注 : 磁盘读 ( 替换时写磁盘 ) 要花费几百万个时钟周期, 所以, 此时,OS 会挂起当前进程, 把另一个进程调到处理器执行, 直到磁盘访问结束 ) 恢复引起缺页的进程的状态 执行 从异常返回 指令 修改机器状态使处理器从核心态转到用户态, 并将 EPC 中的地址装入到 PC memory.157

158 ( 缺页 ) 异常处理时要考虑的一些细节 缺页异常结束后, 回到哪里继续执行? 指令缺页 : 重新执行缺页指令 数据缺页 : 简单指令 ( 仅一次访存 ): 强迫指令结束, 重新执行缺页指令 复杂指令 ( 多次访存 ): 可能会发生多次缺页, 指令被中止在中间某个阶段, 缺页处理后, 从中间阶段继续执行 ; 因而, 需要能够保存和恢复中间机器状态 异常发生后, 又发生新的异常, 怎么办? 在发现异常 转到异常处理程序中, 若在保存正在运行进程的状态时又发生新的异常, 则因为要处理新的异常, 会把原来进程的状态和保存的返回断点破坏掉, 所以, 应该有一种机制来 禁止 响应新的异常处理 通过 中断 / 异常允许 状态位 ( 或 中断 / 异常允许 触发器 ) 来实现 中断 / 异常允许 状态位置 1, 则 开中断 ( 允许异常 ), 清 0 则 关中断 ( 禁止异常 ) OS 通过管态指令来设置该位的状态 memory.158

159 第三讲小结 虚拟存储器是磁盘和主存之间的缓存管理机制, 而不是一种物理存储器 引入虚拟存储器, 使程序员可以在一个极大的存储空间写程序, 无需知道运行程序的物理存储器有多大 虚拟存储器采用 按需调页 技术, 把一部分程序调到主存, 一部分存放在磁盘上 交换的块 ( 称为页 ) 比 Cache-MM 层次的块要大得多 采用全相联映射, 通过页表实现逻辑地址和物理地址转换, 由硬件实现 缺页处理由 OS 完成 (cache miss 处理由硬件实现 ) 采用 Write Back 写策略 页表中记录装入位 访问方式 使用情况 修改位 磁盘地址或页框号 经常使用的页表项放到特殊的 Cache 中, 称为快表 TLB 有分页式 分段式 段页式三种管理模式 两类存储保护形式 可利用程序重定位进行地址越界判断 可利用访问方式进行存取权限的判断 memory.159

160 第二次作业 memory.160

161 本章总结 1 存储器的分类 按存取方式分 : 随机 顺序 直接 相联 按存储介质分 : 半导体 磁表面 激光盘 按信息可更改性 : 可读可写 只读 按断电后可否保存 : 易失 非易失 按功能 / 容量 / 速度分 : 寄存器 Cache 主存( 内存 ) 辅存( 外存 ) 存储器的分层结构 : 速度从快到慢 容量从小到大 价格从贵到便宜, 按与 CPU 连接的距离由近到远的顺序, 构成的分层次结构为 : 寄存器 Cache 主存 磁盘 光盘 磁带 memory.161

162 半导体随机存取存储器的组织 本章总结 2 存储元 ( 记忆单元 ) 存储芯片 存储模块 ( 内存条 ) 存储器 存储器芯片与 CPU 的连接 地址线的连接 : 考虑芯片在字方向上扩展, 低位用于芯片内地址 高位用于片选逻辑, 送到片选信号译码器, 译码输出连到芯片的片选信号引脚上 数据线的连接 : 考虑芯片在位方向上扩展, 分别连到位扩展的芯片上 控制线的连接 : 读 / 写信号 主存 /IO 访问信号等经过组合连到芯片相应的引脚 只读存储器 :MROM PROM EPROM EEPROM Flash ROM 多体交叉编址存储器 连续编址 : 按高位地址划分模块 交叉编址 : 按低位地址划分模块 memory.162

163 本章总结 3 Cache 的基本原理 利用程序访问的局部性特点, 把主存中的一块数据复制到 Cache 时间局部性 : 某个单元在一个集中的时间段被重复访问的可能性很大 空间局部性 : 某个单元被访问后, 其周围单元不久也将被访问的可能性很大 Cache 和主存间的映射 直接映射 : 每个主存块只能存放到一个固定的 Cache 块 ( 槽 ) 中 全相联映射 : 每个主存块可以存放到任何一个 Cache 块 ( 槽 ) 中 组相联映射 :Cache 分成若干组, 每组有多个块 ( 槽 ), 每个主存块存放到一个固定组的任意块 ( 槽 ) 中 替换算法 FIFO: 总是把最先调到 Cache 的那个主存块淘汰掉 LRU: 总是把最近最少用到的那个主存块淘汰掉 写策略 写回法 : 暂时只写入 Cache, 直到从 Cache 中替换出来时, 才一次写入主存 写直达法 : 每次写入 Cache 时也同时写入主存, 一般在 Cache 和主存之间加一个 Witre Buffer memory.163

164 本章总结 4 虚拟存储器的基本原理 程序员在一个极大的虚拟地址空间中写程序, 每个程序按照等长的页或变长的段来划分, 主存也按等长的页框或段帧来划分, 当程序启动运行后, 当前用到的程序快 ( 代码或数据 ) 装入到主存的页框或段帧中, 其他暂时不用的部分放在磁盘上, 通过页表或段表把程序块和主存页框 ( 或段帧 ) 建立对应关系 不在主存的页则在页表中记录其在磁盘上的地址 在指令执行过程中, 由特殊的硬件 (MMU) 和操作系统一起实现存储访问的操作 引入虚拟存储器的好处 使得程序员写程序时不受主存空间大小的限制 便于主存空间的利用, 因为无需分配连续的页框给连续的虚页 方便存储保护 虚拟存储器的实现方案 : 分页式 分段式 段页式 地址转换 : 根据逻辑地址中的虚页号, 找到对应的页表项 通过页表项得到对应虚页的页框号, 再和页内地址相加得到物理地址 页表和页表项 : 每个进程有一个页表, 每个页表项由有效位 使用位 修改位 存取权限位 主存页框号或磁盘地址等组成 缺页 : 在指令执行时可能发生缺页, 是一种程序性中断 操作系统的缺页处理程序从磁盘读入一个页面到主存, 并修改页表 缺页处理完后, 回到原来发生缺页的指令重新执行 TLB( 快表 ): 用来存放若干常用页表项的 Cache 可减少访问主存页表的次数 存储保护 : 访问越界和存取方式违例 memory.164

165 附录 : 数据的检 / 纠错码 为什么要进行数据的错误检测与校正? 数据在计算机内部计算 存取和传送的过程中, 由于元器件故障或噪音干扰等原因会出现差错 为了减少和避免这些错误, 应该 : (1) 从计算机硬件本身的可靠性入手, 在电路 电源 布线等各方面采取必要的措施, 提高计算机的抗干扰能力 ; (2) 采取相应的数据检错和校正措施, 自动地发现并纠正错误 如何进行健 / 纠错? 压缩信息量时, 要去冗余 ; 但有时也需要一些冗余编码, 原因为 : (1) 简化处理 ( 定长编码 );(2) 便于检错与纠错 memory.165