计算机组成原理(02318) 第五章存储器层次结构

课程内容

存储器概述
半导体随机存取存储器
存储器芯片的扩展机器与CPU的连接
半导体制度存储器和Flash存储器
高速缓冲存储器(cache)
虚拟存储器

5.1 存储器概述

5.1.1 存储器的分类

存储的特点和使用方法不同, 可分为

按存储元件分类

存储元件必须具有两个截然不同的物理状态才能被用来表示二进制代码0和1.
目前使用的存储元件主要有
- 半导体器件 : 构成的存储器称为 半导体存储器
- 磁性材料 : 主要是 磁表面存储器, 磁盘存储器和磁带存储器
- 光介质 : 光盘存储器

按存取方式分类

随机存取存储器(Random Access Memory,RAM) : 特点是按地址访问存储单元, 因为每个地址译码事件相同, 不考虑芯片内部缓冲前提下, 每个单元的访问时间是一个常数与地址无关
- 目前的DRAM芯片内都具有行缓冲, 因而有的数据可能因为已在缓冲而缩短了访问时间
- 半导体存储器属于随机存取存储器, 可用作cache和主存储器
顺序存取存储器(Sequential Access Memoty,SAM) : 特点是信息按顺序放和读, 存取时间取决于信息存放位置, 以记录块为单位编址
- 磁带存储器就是一种顺序存取存储器, 存储容量大, 但存取速度慢
直接存取存储器(Direct Access Memory,DAM) : 存取方式兼有RAM和SAM的特点. 可直接选择所需信息的所在区域, 然后按SAM方式存取, 磁盘存储器就是如此
上述三类都是按所需信息地址来访问, 但有的情况下可能不知道所访问信息地址, 只知道要访问信息的内容特征, 此时只能按内容检索到存储位置进行读写
- 该类存储器称为 按内容访问存储器(Content Address Memory,CAM)/相联存储器(Associative Memoty,AM), 如快表就是一种相联存储器

按信息的可更改性分类

读写存储器(Read/Write Memory) : 信息可读出写入, RAM芯片是一种读写存储器
只读存储器(Read Only Memoty,ROM) : 信息一旦确定, 通常情况下只读不写, 某些情况下也可重新写入
RAM芯片和ROM芯片都采用 R随机存取方式 进行信息访问

按断点后信息的可保存性分类

非易失(不挥发)性存储器(Nonvolatile Memory) : 信息可一直保留, 不需要电源维持. 如ROM,磁表面存储器, 光存储器等
易失(挥发)性存储器(Volatile Memory) : 信息在电源关闭时信息自动丢失, 如RAM,cache等

5.1.2 主存储器的组成和基本操作

一个个存储0或1的 记忆单元(cell) 构成的存储阵列是存储器的核心部分
- 记忆单元称为 存储元/位元, 具有两种稳态能表示二进制0和1的物理器件
存储阵列 也称为 存储体/存储矩阵.
要存取存储体的信息, 必须对 存储单元 编号, 所编号码就是地址
- 编址单位(addressing unit) 是指具有相同地址的哪些位元构成的一个单位, 可以是一个字节或一个字
对各存储单元进行编号的方式称为 编址方式(addressing mode), 可以 按字节编址 ,也可以 按字编址
- 大多数通用计算机采用按字节编址时, 存储体内一个地址中有一个字节
指令执行过程需要访问主存时, CPU首先把被访问单元地址送到 主存地址寄存器MAR(Memory Address Register) 中, 通过地址线将主存地址送到主存中的地址寄存器,
- 以便地址译码器进行译码选中相应单元, 同时CPU将读写信号通过控制线送到主存的读写控制电路
- 写操作 : CPU同时将要写的信息送 主存数据寄存器MDR(Memory Data Register) 中, 在读写控制电路控制下经数据线将信息写入选中的单元
- 读操作 : 主存读出选中单元的内容送数据线, 然后送MDR.
- 数据线的宽度与MDR的宽度相同, 地址线的宽度与MAR的宽度相同
- 地址线的位数决定了主存地址空间的 最大可寻址范围

5.1.3 存储器的主要性能指标

存储器容量 : 指它能存放的二进制位数或字(字节)数;
- 存储器的价格可用总价格C或每位价格c来表示, 若存储器按位计算的容量为S, 则c=C/S
- 总价C中应包括存储单元本身的价格以及完成存储器操作所必须的外围电路价格
- 存储器速度可用存取(访问)时间 ,存储周期或带宽表示
存取时间 : $ 一般用读出时间 T_A 及写入时间 T_W 描述. $
- $ T_A 指从寄存器接到读命令开始到信息被送到数据线上所需的时间 $
- $ T_W 指从存储器接到写命令开始到信息被写入存储器中所需的时间 $
存储周期 : 指存储器进行一次读写操作所需的全部时间. 也就是存储器进行连续读写操作所允许的最短间隔时间
- $ 应等于存储器时间加上下一次存取开始钱所要求的附件时间一般用 T_M 表示 $
- 存储器中由于读出放大器,驱动电路等都有一段稳定恢复时间, 读出后不能立即进行下一次访问
- $ 一般T_M,T_W,T_A存在以下关系 : T_M>T_A>T_W $
存储器带宽B 表示存储器被连续访问时, 可提供的数据传送速率, 通常用每秒钟传送信息的位数(或字节数)来衡量

5.1.4 存储器的层次化结构

存储器容量和性能应随着处理器速度和性能的提高而同步提高, 以保持系统性能的平衡
通常在计算机内部采用层次化的存储器体系结构
数据一般只在相邻两层之间复制传送, 总是从慢速存储器复制到快速存储器被使用
- 传送的单位是一个定长块, 需要确定定长块的大小, 并在相邻两层间建立块映射关系
CPU执行指令时, 需要的操作数大多数来自寄存器.
- 如果需要从(向)存储器取(存)数据时, 先访问cache, 如果不在cache则访问主存, 如果不在主存则访问硬盘
- 此时操作数从硬盘读出送到主存,然后从主存送到cache

5.2 半导体随机存取存储器

半导体RAM体积小存取速度快, 适合作为内部存储器使用
- 静态RAM(Static RAM,SRAM)
- 动态RAN(Dynamic RAM,DRAM)

5.2.1 基本存储元件

基本存储元件用于存储一位二进制信息, 是组成存储器的最基本电路

六管静态MOS管存储元件

$ T_1和T_2构成触发器, T_3和T_4为门控管, T_5和T_6是触发器的负载管 $, 这6个MOS管可组成存储一位二进制信息的基本存储元

单管动态MOS管存储元件

MOS管栅极上存储的电荷会缓慢放电, 超过一定时间就会丢失信息, 因此必须定时给栅极电容充电, 这一过程称为 刷新(Refresh)

静态存储元件和动态存储元件的比较

SRAM存储元件所用MOS管多, 占硅片面积大, 功耗大, 集成度低;
- 但无需刷新, 也无需读后再生, 且读写速度快.
- 适合做高速小容量的半导体存储器
DRAM存储元件所用MOS管少, 占硅片面积小, 功耗小, 集成度高;
- 但必须定时刷新和读后再生, 读写速度相对SRAM元件要慢
- 适合做慢速大容量的主存

5.2.2 半导体RAM芯片

半导体RAM芯片由 存储体, I/O读写电路, 地址译码器和控制电路等部分 组成

存储体(存储矩阵) : 是存储单元的集合.
- 4096个存储单元被排成64x64的存储阵列, 称为 位平面
- 8个位平面构成4096字节的存储体, 由X选择线(行选择线)和Y选择线(列选择线)来选择所需单元, 不同位平面的相同行/列上的位同事被读出或写入
地址译码器 : 将地址转换为译码输出线上的高电平, 以便驱动相应的读写电路
- 地址位数较多时, 地址译码器输出线太多, 因此大容量的DRAM芯片大多采用 二维双译码结构
- 地址译码器分为X和Y方向两个译码器
- 选中的行列交叉点上的单元只有一位, 采用二维双译码结构的存储芯片被称为 位片芯片
  - 有的芯片的存储阵列采用三维结构, 用多个位平面构成存储阵列, 不同位平面相同行列的交叉点上的多位构成一个 存储字, 被同时写入或读出
驱动器 : 双译码结构中, 一条X方向的选择线要控制在其上的各个存储单元的字选择线, 负载较大, 因此需要在地址译码器后加驱动电路
I/O控制电路 : 用以控制被选中的单元的读出或写入, 具有放大信息的作用
读/写控制信号 : 根据CPU给出的读/写命令, 控制被选中存储单元进行读或写

5.2.3 SDRAM芯片技术

目前主存常用的是 基于SDRAM(Synchronous DRAM) 芯片技术的内存条,包括(DDR SDRAM,DDR2 SDRAM,DDR3 SDRAM)
SDRAM是一种与当年Intel推出的芯片组中北桥芯片的前端总线同步运行的DRAM芯片, 因此称为 同步DRAM

SDRAM芯片技术

SDRAM工作方式与传统DRAM有很大不同
- 传统DRAM与CPU之间采用 异步方式 交换数据, CPU发出地址和控制信号后经过一段延迟时间数据才读出或写入
  - 这段时间里CPU不断采样DRAM的完成信号, 没完成前CPU插入等待状态而不能做其他功能
- SDRAM芯片则于DRAM不同, 它的读写受系统时钟(前端总线时钟Clk)控制, 与CPU之间用 同步方式 交换数据
  - 将CPU或其他主设备发出的地址和控制信息锁存起来, 经过确定的几个时钟周期后给出响应
  - 主设备在这段时间内可安全地进行其他操作
- SDRAM每一步操作都在外部系统时钟Clk的控制下运行, 支持 突发(burst)传送方式.
  - 在第一次存取时给出首地址, 以后按地址顺序读写即可, 不再需要地址建立时间和行列预充电时间, 就能连续快速从 行缓冲器(row buffer) 中输出一连串数据
- 内部的工作方式寄存器(也称模式寄存器)可用于设置传送数据的长度以及收到读命令(与CAS信号同时发出)到传送数据的延迟时间等
  - 前者称为 突发长度(brust lengths,BL), 后者称为 CAS潜伏期(CAS Latency,CL)
- 根据设定的BL和CL, CPU可以确定何时从总线上取数以及连续取多少数据
  - 第一个数据被读出后, 同行的所有数据都被送到行缓冲器中, SDRAM的行缓冲器由快速的SRAM实现
  - 每个时钟可从SDRAM的行缓冲器中读取一个数据, 并在下个时钟周期内通过总线传送到CPU
- 基于SDRAM技术芯片的工作过程大致如下
  1. 在Clk时钟上升沿片选信号(CS)和行地址选通信号(RAS)有效
  2. 经过一段延时$ t_{RCD}(RAS to CAS delay) $, 列选通信号CAS有效, 并同时发出读/写命令, 此时行列地址被确定, 已选中具体存储单元
  3. 对于读操作, 经过一个CAS潜伏期后输出数据开始有效, 其后每个时钟都有一个或多个数据连续从总线上传出, 直到完成突发长度BL指定的所有数据的传送
    - 对于写操作, 则没有CL延时而直接开始写入
  - 由于只有读操作有CL, 所以CL又称为 读取潜伏期(Read Latency, RL)
  - $ t_{RCD}和CL都是以时钟周期 T_{CK}为单位 $

DDR SDRAM芯片技术

DDR(Double Data Rate)SDRAM 是对标准SDRAM的改进设计, 通过芯片内部IO缓冲(IO buffer)中数据的两位预取功能并利用存储器总线上时钟信号的上升沿与下降沿进行两次传送,
- 以实现一个时钟内传送两次数据的功能
采用DDR SDRAM技术的PC-3200(DDR-400)存储芯片内Clk时钟的频率为200MHz, 意味着存储器总线上的时钟频率也为 200MHz
- 利用存储器芯片内部的两位预取技术, 使得一个时钟内有两个数据被取到IO缓冲中
存储器中线在每个时钟内可传送两次数据, 而存储器总线中的数据线位宽为64, 即每次传送64位, 因此存储器总线上数据的最大传输率(带宽)为200MHz × 2×64/8=3.2GB/s

DDR2 SDRAM芯片技术

DDR2 SDRAM内存条采用DDR类似技术, 利用芯片内部的IO缓冲可进行4位预取.
PC2-3200(DDR2-400)DDR2 SDRAM存储芯片内部Clk时钟频率为200MHz, 意味着存储器总线上的时钟频率应为400MHz, 利用存储器芯片内部的4位预取技术, 使得一个时钟内有4个数据被取到IO缓冲中,
- 存储器总线在每个时钟内传送两次数据, 若每次传送64位, 则存储器总线最大数据传输率(带宽)为 200MHz×4×64/8=6.4GB/s

DDR3 SDRAM芯片技术

芯片内部IO缓冲可进行8位预取.
200MHz×8×64/8=12.8GB/s

5.3 存储器芯片的扩展机器与CPU的连接

5.3.1 内存条和内存条插槽

CPU通过其芯片内的总线接口部件(总线控制逻辑)与系统总线相连, 再通过总线之间的IO桥接器,存储器总线连接到主存
总线是连接其上的各部件共享的传输介质, 总线由控制线数据线和地址线构成
CPU通过处理器总线和存储器总线与主存相连
CPU与竹村之间交换数据通过数据线传输, 每根数据线传送一位数据
受集成度和功耗等因素限制, 单个芯片的容量不可能很大, 一般通过存储器芯片的扩展技术, 将多个芯片做在一个主存模块(内存条)上,
- 然后由多个主存模块以及主板或扩充板上的RAM芯片和ROM芯片组成一台计算机所需的主存空间
内存插槽就是存储器总线, 内存条中的信息通过内存条引脚再通过插槽内的引线连接到主板上, 通过主板上的导线连接到北桥芯片或CPU芯片
现代计算机中可以有多条存储器总线同时进行数据传输, 支持两条总线同时进行传输的内存条插槽为双通道内存插槽(还有三四通道内存插槽), 其总线传输带宽可提高到单通道的两倍(三倍四倍)

5.3.2 存储器芯片的扩展

多个存储器芯片可构成一个内存条, 需要在字方向和位方向上进行扩展
若干片位数较少的存储器芯片构成给定存储字长的内存条时, 需要进行 位扩展
字扩展 是容量的扩充, 位数不变

5.3.3 连续编址和交叉编址

每个DRAM芯片就是一个存储模块, 每个存储模块具有相同容量和存取速度, 并各自具有独立的地址译码器/驱动电路和读写电路,
- 能够独立并行工作, 每个存储模块的容量之和就是内存条的容量
- 通常把这种由多个独立并行工作的存储模块构成的存储器称为 多模块存储器
根据不同编址方式, 多模块存储器分为 连续编址 和 交叉编址 两种结构

连续编址方式

连续编址的多模块主存储器中, 主存地址的高位表示模块号(或体号), 低位表示模块内地址(或体内地址), 也称为 按高位地址划分模块方式, 地址在模块内连续
连续编址的多模块存储器不能提高存取速度

交叉编址方式

交叉编制存储器中, 主存地址的低位表示模块号, 高位表示模块内地址, 也称为 按低位地址划分模块方式
- 若有m个存储模块, 每个模块按"模m"交叉方式编址, 称为 m体交叉编址方式
交叉编址多模块存储器可采用轮流启动或同时启动两种方式

轮流启动
同时启动

5.4 半导体制度存储器和Flash存储器

5.4.1 半导体只读存储器

根据只读存储器的工艺, 可分成 MROM, PROM, EPROM和EEPROM 等类型
掩膜只读存储器(Mask ROM, MROM) : 存储的信息由生产厂家在掩膜工艺过程中"写入", 用户不能修改.
- 存储内容固定, 可靠性高, 但灵活性差, 生产周期长, 只适合定型批量生产
可编程只读存储器(Programmable ROM, PROM) : 芯片出场时内容全部为0(半成品), 用户可用专门的PROM写入器将信息写入, 但写入不可逆, 因此称为 一次编程型只读存储器
可擦除可编程只读存储器(Erasable Programmable ROM, EPROM) : 允许用户通过某种编程器向ROM芯片写入信息, 并可擦除所有信息后重写.
- 可反复擦除,写入多次
电擦除电改写只读存储器(Electrically Erasable Programmable ROM, EEPROM) :
- 该类型存储器在读数据的方式上与EPROM完全一样, 但有一个优点, 即可用电来擦除和重编程,
- 所以可以选择只删除个别字, 而不用删除全部信息, 给现场重编程带来极大方便

5.4.2 半导体Flash存储器

Flash存储器也称为闪存, 是高密度非易失性读写存储器, 兼有RAM和ROM的优点, 且功耗低集成度高, 不需要后备电源
沿用EPROM的简单结构和浮栅/热电子注入的编程写入方式, 又兼备EEPROM的可擦除特点, 可在计算机内进行擦除和编程写入, 因此又称为 快擦型电可擦除重编程ROM
- 目前广泛使用的U盘和存储卡等都属于Flash存储器
Flash存储元是在EPROM存储元基础上发展起来的. 每个存储元由单个MOS管组成, 包括漏极D/源极S/控制栅和浮空栅
- 当控制栅加上足够正电压时浮空栅将储存大量电子(即带有许多负电荷), 可将存储元的这种状态定义为0
- 当控制栅不加正电压, 则浮空栅少带或不带负电荷, 这种状态定义为1
闪存有三种基本状态 :
- 编程(充电) : 最初所有存储元都是1状态, 通过’编程’在需要改写为0的存储元的控制栅加上一个正电压 $ V_P$
  - 一旦某存储元被编程, 则存储的数据可保持100年而无需外电源
- 擦除(放电) : 采用电擦除. 在所有存储元的源极S加正电压$ V_E$, 使浮空栅中的电子被吸收掉, 从而让所有存储元都变成1状态
  - 写的过程实际上是先全部擦除, 使全部变成1状态后再在需要的地方改写成0(全部放电后再在写0的地方充电)
- 读取操作 : 在控制栅加上正电压$V_R $, 若原存为0则读出电路检测检测不到电流
  - 若原存为1则浮空栅不带负电荷, 控制栅上的正电压足以开启晶体管, 电源Vd提供从漏极D到源极S的电流, 读出电路检测到电流
Flash存储器的读操作速度和写操作速度相差很大, 读取速度与半导体RAM芯片相当, 而写数据(快擦–编程)的速度则与硬磁盘存储器相当

5.5 高速缓冲存储器(cache)

提高存储芯片本身的速度或采用并行存储器结构可以缓解CPU和主存之间的速度匹配问题
也可以在CPU和主存之间设置高速缓冲(cache)也可以提高CPU访问指令和数据的速度

5.5.1 程序访问的局部性

大量典型程序运行情况分析结果表明, 较短时间内程序产生的地址往往集中在存储空间的一个很小范围, 该现象称为 程序访问的局部性, 可细分为时间局部性和空间局部性
- 时间局部性 : 指被访问的某个存储单元在较短时间间隔内很可能又被访问
- 空间局部性 : 指被访问的某个存储单元的邻近单元在一个较短时间间隔内很可能也被访问
因为程序是由指令和数据组成, 这是出现程序访问局部性特征的原因
- 指令在主存按顺序存放, 其地址连续, 循环程序段或子程序段通常被重复执行, 所以指令访问具有明星的局部化特性
- 数据在主存也是按顺序, 特别是数组元素, 常常被按序重复访问, 所以数据也具有明显的访问局部性特征
更好利用程序访问的空间局部性, 通常把当前访问单元以及邻近单元作为一个主存块一起调入cache
- 主存块大小以及程序对数组元素的访问顺序等都对程序的性能有一定影响

5.5.2 cache的基本工作原理

cache是一种小容量高速缓冲存储器, 由快速的SRAM组成, 直接制作在CPU芯片内, 速度几乎与CPU一样快
- 在CPU和主存之间设置cache总是把主存中被频繁访问的活跃程序块和数据块复制到cache中
- 由于程序访问的局部性, CPU能直接从cache中取得指令和数据不必访问主存
方便cache和主存间交换信息,cache和主存空间都被划分为相等的区域.
- 主存中的区域称为 块(block), 也称为 主存块, 是cache和主存间信息交换单位
- cache中存放一个著存款的区域称为 cache行(line)/槽(slot)
- 系统启动或复位时, 每个cache行都为空, 其中信息无效, 只有装了主存块后信息才有效
  - 为了说明cache行中信息是否有效, 每个cache行需要一个 有效位(valid bit)
  - 有了有效位, 就可通过有效位清0来淘汰某cache行中的主存块, 称为 冲刷(flush), 装入一个新主存块时再使有效位置1
- CPU执行程序时需要从主存块取指令或读数据时, 先检查cache中有没有要访问的信息, 有则直接从cache读取就不用访问主存
  - 若无则从主存中把当前访问信息所在的一个主存块复制到cache中, 因此cache中内容是主存中部分内容的副本
CPU访问单元所在的块在cache中, 则称 cache命中(Hit), 命中的概率称为 命中率(Hit Rate)p, 等于命中次数与访问总次数之比
- 若不在cache中则为 不命中或缺失(Miss), 概率称为 缺失率(Miss Rate), 等于不命中次数与访问总次数之比
命中时,CPU在cache中直接存取信息所用时间开销就是cache访问时间T, 称为 命中时间(Hit Time)
- 缺失时, 需要从主存读取一个主存块送cache, 并同时将所需信息送CPU, 所用时间开销为主存访问时间 $ T_m 和cache访问时间 T_c之和$
通常把主存读入到一个主存块到cache的时间 $ T_m $ 称为 缺失损失(Miss Penalty)
CPU在cache到主存层次的平均访问时间为
$$ T_a=p×T_c+(1-p)×(T_m+T_c)=T+(1-p)×T_m $$
由于程序访问的局部性特点, cache 的命中率可以达到很高接近于1.
- 因此虽然Miss Penalty » Hit Time, 但最终的平均访问时间仍可接近cache的访问时间

5.5.3 cache行和主存块之间的映射关系

cache行的信息取自主存中某个块. 将主存块复制到cache行时, 主存块和cache行之间必须遵循一定的映射规则,
- 这样CPU访问某个主存单元时可依据映射规则到cache对应行查找要访问的信息, 而不是在整个cache中查找
根据不同映射规则, 主存块和cache行之间有三种映射关系

直接映射(direct map) : 每个主存块映射到cache的固定行中

基本思想是把主存的每一块映射到固定的一个cache行中, 也称 模映射 , 映射关系如下
- cache行号 = 主存块号 mod cache行数
每个主存地址总是属于某块群中某块内的某一个地址, 直接映射关系下, 主存地址被分成三个字段
- 块群号 : 是绝对主存块号的高位部分
- 块号 : 是块群内的相对块号, 即映射到的cache行号
- 块内地址

全相联映射(full associate map) : 每个主存块映射到cache的任意行中

基本思想是一个主存块可装入cache任意一行中
- 全相联映射cache中每行的标记用于指出改行取自主存哪个快
一个主存块可能在任意一行中, 要比较所有cache行的标记, 因此主存地址中无需cache行索引, 只有标记和块内地址两个字段
全相联映射方式下, 只要由空闲cache行就不会发生冲突, 因而块冲突概率低

组相联映射(set associate map) : 每个主存块映射到cache的固定组的任意行中

全相联映射和直接映射, 两者优缺点正好相反, 二者组合可以取长补短, 两者结合产生了 组相联映射方式
基本思想是, 将cache所有行分成$2^q$个大小相等的组, 每组有$2^s$行
- 每个主存块被映射到cache固定组的任意一行, 即采用组间模映射, 组内全映射的方式
映射关系 : cache组号 = 主存块号 mod cache组数
假定8K字的cache划分为 $ 2^3组×2^1行/组x512字/行$, 则主存第100块应映射到cache的第4组的任意一行, 因为 $ 100 mod 2^3 = 4 $
该类型的cache映射方式称为$ 2_s路组相连映射 $, 即s=1为 2路组相联, s=2为 4路相联. 以此类推

5.5.4 cache中主存块的替换算法

cache行数比主存块少得多, 往往多个主存块会映射到同一个cache行中. 当新的一个主存块复制到cache时, cache中对应行可能已经被占满,
- 此时必须选择淘汰一个cache行中的主存块. 淘汰哪一块主存块的问题是 淘汰策略 的问题, 也称为 替换算法/替换策略
常用的替换算法有
- 先进先出(First-in-First-out,FIFO)
- 最近最少用(least-recently used,LRU)
- 最不经常用(least-frequently used,LFU)
- 随机替换算法
- 等等等
先进先出算法(FIFO) : 总是选择最早装入cache的主存块被替换掉. 实现较为方便, 但不能正确反映程序的访问局部性, 因为最先进入的主存块可能是经常要用的. 该算法可能产生较大的缺失率
最近最少用算法(LRU) : 总是选择近期最少使用的主存块被替换掉. 比较正确反映程序的访问局部性, 但实现比FIFO要复杂一些
最不经常用算法(LFU) : 替换掉cache中引用次数最少的块. 也用与每行相关的计数器实现. 与LRU类似, 但实现不完全相同
随机替换算法 : 从候选行的主存块中随机选取一个淘汰, 与使用情况无关. 在性能上只稍逊于基于使用情况的算法, 代价低

5.5.5 cache的一致性问题

cache的内容是主存副本, 当对cache内容跟新时, 就存在cache和主存如何保持一致的问题
- 磁盘这类高速IO设备可通过DMA方式直接读写主存, 如果cache中内容被CPU修改而主存块没有更新,则从主存传送到IO设备的内容就无效
- 若IO设备修改了主存块内容, 则对应cache行中内容就无效
解决cache一致性问题的关键是处理好 写操作. 通常有 全写法 和 回写法

全写法

全写法(write through) 基本做法是 : 若写命中则同时写cache和主存; 若写不命中, 则有以下两种处理方式
- 写分配法(write allocate) : 先在主存块中更新相应存储单元, 然后分配一个cache行将更新后的主存块装入到分配的cache行中
  - 该方式可充分利用空间局部性, 但每次写不命中都要从主存读一个块到cache中, 增加了读主存块的开销
- 非写分配法(not write allocate) : 仅更新主存单元而不装入主存块到cache中.
  - 该方式可减少读入主存块的时间, 但没有很好利用空间局部性
全写法实际上采用的是对主存块信息及其所有副本信息全都直接同步更新的做法, 这种方式通常也被称为 通写法/直写法/透写法, 也有称之为 写直达法/写穿透法

回写法

回写法(write back) 基本做法是 : 若写命中则信息只被写入cache而不被写入主存
- 若写不命中则在cache中分配一行, 将主存块调入该cache行中并更新相应单元内容
- 该方式下在写不命中时, 通常采用写分配法进行写操作
该方式实际上采用的是回头再写或最后一次性写的做法, 通常被称为 回写法/一次性写方式, 也有的称为 写回法
CPU执行写操作时, 回写法不会更新主存单元, 只有当cache行中的主存块被天幻时才将该块内容一次性写回主存
- 好处是减少了写主存的次数, 大大降低了主存带宽需求
要减少写回主存块的开销, 每个cache行设置了一个 修改位(dirty bit,也称脏位)
- 若修改为1, 说明对应cache行主存块被修改过, 替换时需要写回主存
- 若修改为0, 说明对应主存块未被修改, 替换时无需写回主存
由于回写法没有同步更新cache和主存内容, 所以存在cache和主存内容不一致而带来的潜在隐患
通常需要其他的同步机制来保证存储信息的一致性

5.6 虚拟存储器

目前计算机主存由DRAM芯片构成, 由于技术和成本的原因, 主存的存储容量容易收到限制, 且各种不同计算机所配置的物理内存容量多半也不相同, 而程序设计时人们显然不希望受到特定计算机的物理内存大小的制约
- 如果解决这两者之间的矛盾是一个重要的问题
解决以上问题计在计算机中采用了虚拟存储技术:
- 程序员在一个不受物理内存空间限制并且比物理内存空间大得多的虚拟的逻辑地址空间中编写程序, 好像每个程序都独立拥有一个巨大的存储空间
- 程序执行过程中, 把当前执行到的第一部分程序和相应数据调入主存, 其他暂不用的部分暂时存放在磁盘上
- 这种借用外存微程序提供的大虚拟存储空间称为 虚拟存储器

5.6.1 程序与进程的概念

程序(program) 就是代码和数据的集合, 程序的代码是一个机器指令序列, 因而程序是一种静态的概念, 可作为目标模块存放在磁盘中
进程(process) 就是程序一次运行过程. 是一个具有一定独立功能的程序关于某个数据集合的一次运行活动, 因而进程具有动态的含义
- 计算机处理的所有任务实际上是由进程完成的
进程是操作系统对处理器中程序运行的过程的一种抽象
- 进程有自己的生命周期, 由于任务的启动而创建, 随着任务的完成(或终止)而消亡
- 所占用资源也随着进程终止而释放
一个可执行目标文件可被多次加载执行, 即一个程序可能对应多个不同进程
现代多任务操作系统通常一段时间内会有多个不同的进程在系统运行, 这些进程轮流使用处理器并共享同一个主存储器
- 程序员和语言处理系统可以把一台计算机所有资源看成是由自己的程序独占, 可以认为自己的程序是在处理器上执行的和在存储空间中存放的唯一的用户程序
- 显然这是一种错觉, 却带来了极大的好处, 简化了程序员的编程以及语言处理系统的处理,
  - 即简化了编程/编译/链接/共享和加载等整个过程

5.6.2 虚拟地址空间

虚拟存储器管理方式采用 请求分页 思想, 每次访问仅将当前需要的页面调入主存, 而将不活跃的页面放在磁盘上
- 当访问某个信息所在页不在主存时发生缺页, 此时从磁盘将缺失的页面调入主存
虚拟存储器机制为程序员提供了一个极大的 虚拟地址空间(逻辑地址空间), 给每个进程带来了一个假象, 好像每个进程都独占主存, 且主存空间极大
- 带来三个好处:
  1. 每个进程具有一致的虚拟地址空间,从而简化存储管理
  2. 把主存看成是磁盘存储器的一个缓存, 在主存中仅保存当前活动的程序段和数据区, 并根据需要在磁盘和主存之间进行信息交换
    - 通过这种方式, 让有限的主存空间得到有效利用
  3. 每个进程的虚拟地址空间是私有的, 因此可保护各自进程不被其他进程破坏
虚拟存储器机制中, 每个源程序编译/汇编/链接处理生成可执行的二进制及其目标代码时, 每个程序目标代码都被映射到同样的虚拟地址空间, 因此所有进程的虚拟地址空间是一致的
Linux操作系统下一个程序的一个进程对应的虚拟地址空间分为两大部分
- 内核区(kernel area)
- 用户区(user area)

5.6.3 虚拟存储器的实现

虚拟存储器分成三种不同类型 : 分页式, 分段式和段页式

分页式虚拟存储器

分页式虚拟存储系统中, 主存储器和虚拟地址空间都被划分称大小相等的页面, 磁盘和主存之间按页面为单位交换信息
通常把虚拟地址空间中的页面称为 虚拟页/逻辑页或虚页
- 主存空间中的页面被称为 页框(页帧)/物理页或实页
- 有时虚拟页简称为 VP(virtual page), 物理页简称为 PF(page frame)或PP(physical page)
页表(Page Table)
- 为了对每个虚拟页的存放位置/存取权限/使用情况/修改情况等进行说明, 操作系统在主存中给每个进程都生成了一个页表, 每个虚拟页在页表中都有一个对应的页表项,
  - 内容是该虚拟页的存放位置/装入位/修改位/使用位(替换控制位)/存取权限和禁止缓存位等
- …
地址转换(Address Translation)
- 对于采用虚拟存储机制的系统.指令中给出的地址是虚拟地址, 所以CPU执行指令时首先要将虚拟地址转换为主存物理地址, 才能到主存取指令和数据
- 地址转换工作由CPU的 存储器管理部件(Memory Managerment Unit,MMU) 来完成
快表(TLB)
- 为了减少访存次数, 往往把页表中最活跃的几个页表项复制到高速缓存中, 在高速缓存中的页表项组成的页表称为 后背转换缓冲器(Translation Lookaside Buffer),
  - 通常简称为 TLB或快表, 相应地称主存中的页表为慢表
- 快表是减少访存时间开销的有效方法
CPU访存过程
- 在一个具有cache和虚拟存储器的系统中, CPU的一次访存操作可能涉及TLB/页表/cache/主存和磁盘的访问
- cache缺失处理由硬件完成
- 缺页处理由软件完成, 操作系统通过"缺页异常处理程序"来实现
- 对于TLB缺失, 则既可以用硬件也可以用软件来处理
- 用软件方式处理TLB缺失时, 操作系统通过专门的TLB缺失异常处理程序来实现

分段式虚拟存储器

根据程序模块化性质, 按程序逻辑结构划分成多个相对独立的部分
- 代码区/静态只读数据区/静态可读写数据区等
相对独立的部分被称为 段(segment), 每个段的描述信息通常有
- 段名/段起点/段长等
分段方式下, 将主存空间按实际程序中的段来划分, 每个段在主存中的位置记录在段表中, 段的长度可变, 段表中须有长度指示(段长)
- 每个进程都有一个段表, 每个段在段表中有一个 段表项, 用于指明对应段在主存中的位置/段长/访问权限/使用和装入情况等
分段式虚拟存储器系统中, 虚拟地址由段号和段内地址组成.
- 通过段表把虚拟地址变换成主存物理地址
每个用户进程有一个 段表基址寄存器

段页式虚拟存储器

段页式虚拟存储器中, 程序按模块分段, 段内再分页, 用段表和页表(每段一个页表)进行两级定位管理

计算机组成原理(02318) 第五章 存储器层次结构

课程内容

5.1 存储器概述

5.1.1 存储器的分类

5.1.2 主存储器的组成和基本操作

5.1.3 存储器的主要性能指标

5.1.4 存储器的层次化结构

5.2 半导体随机存取存储器

5.2.1 基本存储元件

5.2.2 半导体RAM芯片

5.2.3 SDRAM芯片技术

5.3 存储器芯片的扩展机器与CPU的连接

5.3.1 内存条和内存条插槽

5.3.2 存储器芯片的扩展

5.3.3 连续编址和交叉编址

5.4 半导体制度存储器和Flash存储器

5.4.1 半导体只读存储器

5.4.2 半导体Flash存储器

5.5 高速缓冲存储器(cache)

5.5.1 程序访问的局部性

5.5.2 cache的基本工作原理

5.5.3 cache行和主存块之间的映射关系

5.5.4 cache中主存块的替换算法

5.5.5 cache的一致性问题

5.6 虚拟存储器

5.6.1 程序与进程的概念

5.6.2 虚拟地址空间

5.6.3 虚拟存储器的实现

计算机组成原理(02318) 第五章存储器层次结构