第三章 多层次的存储器

本章内容较多，主要包括各种存储器及存储方式存储器，其中重点为存储器基本概念、DRAM、SRAM、cache、命中率与平均访问时间、主存与cache映射方式和虚存等

3.1 存储器概述

3.1.1 存储器的分类

• 存储器是计算机系统中的记忆设备，用来存放程序和数据。
• 存储介质：目前主要采用半导体器件和磁性材料。
• 存储位元：一个双稳态半导体电路或一个CMOS晶体管或磁性材料的存储元，均可以存储一位二进制代码。这个二进制代码位是存储器中最小的存储单位，称为存储位元
• 存储单元：由若干个存储位元组成一个存储单元。由许多存储单元组成一个存储器。

根据存储材料的性能和使用方法的不同，存储器有不同分类方法
（1）根据存储介质分类，分为磁表面/半导体存储器
（2）根据存取方式分类，分为随机/顺序存取（磁带）
（3）根据读写功能分类，分为只读存储器(ROM)和随机读写存储器(RAM)
（4）根据信息的易失性分类：分为易失性和非易失性的
（5）根据存储器系统中的作用分类：分为主/辅/缓/控

3.1.2 存储器的分级

当前存储器的特点：

• 速度快的存储器价格贵，容量小；

• 价格低的存储器速度慢，容量大。
  在计算机存储器体系结构设计时，我们希望存储器的容量大、速度快、价格低，那么在存储器系统设计时，应当在存储器容量，速度和价格方面的因素作折中考虑，建立了多级存储器体系结构，如下图所示
  

• 高速缓冲存储器简称cache，它是计算机系统中的一个高速小容量半导体存储器

• 主存储器简称主存，是计算机系统的主要存储器，用来存放计算机运行期间的大量程序和数据。

• 外存储器简称外存，它是大容量辅助存储器。

3.1.3主存储器的技术指标

• 字存储单元：存放一个机器字的存储单元，相应的单元地址叫字地址。
• 字节存储单元：存放一个字节的单元，相应的地址称为字节地址。
• 存储容量：指一个存储器中可以容纳的存储单元总数。存储容量越大，能存储的信息就越多。
• 存取时间（又称存储器访问时间）：指一次读操作命令发出到该操作完成，将数据读出到数据总线上所经历的时间。通常取写操作时间等于读操作时间，故称为存储器存取时间。
• 存储周期：指连续启动两次读操作所需间隔的最小时间。通常，存储周期略大于存取时间，其时间单位为ns。
• 存储器带宽：单位时间里存储器所存取的信息量，通常以位/秒或字节/秒做度量单位。

3.2 SRAM存储器（静态读写存储器）

目前广泛使用的主存（内部存储器）是半导体存储器。根据信息存储的机理不同可以分为两类

• 静态读写存储器(SRAM)：存取速度快、但存储容量不如DRAM大
• 动态读写存储器(DRAM)：存取速度略慢、存储容量比SRAM大。

3.2.1 基本的静态存储元阵列

• 存储位元:一个锁存器（触发器）。只要直流供电电源一直加到这个记忆电路上，它就无限期地保持记忆的1状态或0状态。如果电源断电，那么存储的数据（1或0）就会丢失。
• 三组信号线（重点）：地址线、数据线（行线、列线）、控制线
• 地址线：若为6条，则指定了存储器的容量为2⁶ = 64个存储单元
• 数据线：若为4条，则制定了存储器的字长为4位，因此存储位元总数为64×4 = 256。
• 控制线：R/~W控制线，指定了对存储器进行读还是写

地址译码器输出有64条选择线，我们称之为行线，它的作用是打开每个存储位元的输入与非门。

3.2.2 基本的SRAM逻辑结构

• SRAM芯片大多采用双译码方式，以便组织更大的存储容量。

• 采用了二级译码：将地址分成x向、y向两部分如图所示。
  

• 存储体（256行×128列×8位）存储阵列

• 地址译码器

  • 采用双译码的方式（减少选择线的数目）。
  • A0~ A7为行地址译码线
  • A8~A14为列地址译码线

• 双向数据线为8条

3.2.3 读/写周期波形图

例1:图为SRAM的写入时序图。其中R/W是读/写命令控制线,当R/W线为低电平时，存储器按给定地址把数据线上的数据写入存储器。请指出图中写入时序中的错误，并画出正确的写入时序图。

解：写入存储器的时序信号必须同步。通常，当R/W线加负脉冲时，地址线和数据线的电平必须是稳定的。当R/W线达到低电平时，数据立即被存储。因此，当R/W线处于低电平时，如果数据线改变了数值，那么存储器将存储新的数据⑤。同样，当R/W线处于低电平时地址线如果发生了变化，那么同样数据将存储到新的地址②或③。
正确的写入时序图见图(b)。

3.3 DRAM存储器（动态读写存储器）

SRAM存储器的存储元是一个触发器，它具有两个稳定的状态。
而DRAM存储器的存储元是由一个MOS晶体管和电容器组成的记忆电路。
MOS管做为开关使用所存储的信息为1或0则是由电容器上的电荷量来体现。

• 当电容器充满电荷时，代表存储了1；
• 当电容器放电没有电荷时，代表存储了0

DRAM与SRAM不同的是

• 增加了行地址锁存器和列地址锁存器。由于DRAM存储器容量很大，地址线宽度相应要增加，这势必增加芯片地址线的管脚数目。为避免这种情况，采取的办法是分时传送地址码。若地址总线宽度为10位，先传送地址码A0～A9，由行选通信号RAS打入到行地址锁存器；然后传送地址码A10～A19，由列选通信号CAS打入到列地址锁存器。芯片内部两部分合起来，地址线宽度达20位，存储容量为1M×4位。
• 增加了刷新计数器和相应的控制电路。DRAM读出后必须刷新，而未读写的存储元也要定期刷新，而且要按行刷新，所以刷新计数器的长度等于行地址锁存器。刷新操作与读/写操作是交替进行的，所以通过2选1多路开关来提供刷新行地址或正常读/写的行地址。

3.3.3 读/写周期、刷新周期（重点）

读/写周期

读周期、写周期的定义是从行选通信号RAS下降沿开始，到下一个RAS信号的下降沿为止的时间，也就是连续两个读周期的时间间隔。通常为控制方便，读周期和写周期时间相等。

刷新周期

DRAM存储位元是基于电容器上的电荷量存储，这个电荷量随着时间和温度而减少，因此必须定期地刷新，以保持它们原来记忆的正确信息。
刷新操作有两种刷新方式： 集中式刷新与分散式刷新

集中式刷新

DRAM的所有行在每一个刷新周期中都被刷新。 例如刷新周期为8ms的内存来说，所有行的集中式刷新必须每隔8ms进行一次。为此将8ms时间分为两部分：前一段时间进行正常的读/写操作，后一段时间（8ms至正常读/写周期时间）做为集中刷新操作时间。

分散式刷新

每一行的刷新插入到正常的读/写周期之中。 例如p70图3.7所示的DRAM有1024行，如果刷新周期为8ms，则每一行必须每隔8ms÷1024=7.8us进行一次。分散式刷新不存在死时间！

3.4 只读存储器（ROM）和闪速存储器(FLASH)

1、掩模ROM（MROM)

存储内容固定的ROM，由生产厂家提供产品。 一旦ROM芯片做成，就不能改变其中的存储内容 用于存储广泛使用的具有标准功能的程序或数据，或用户定做的具有特殊功能的程序或数据 （这些程序或数据均使用二进制码）

• 优点：可靠性和集成度高，价格便宜
• 缺点：不能重写

2、可编程ROM

用户可修改其存储内容
根据编程操作的不同，可编程ROM可分为

• 一次可编程(PROM)
  特点:用户可自行改变产品中某些存储元，用户可编程一次。
  优点:可以根据用户需要编程
  缺点:只能一次性改写
• 光擦可编程(EPROM)
  存储内容可以根据需要写入，当需要更新时将原存储内容抹去，再写入新的内容。
• 电擦可编程(EEPROM)

3、FLASH存储器

• FLASH存储器也翻译成闪速存储器，它是高密度非易失性的读/写存储器。
• 高密度意味着它具有巨大比特数目的存储容量。
• 非易失性意味着存放的数据在没有电源的情况下可以长期保存。
• 既有RAM的优点，又有ROM的优点，称得上是存储技术划时代的进展。

FLASH存储器的基本操作有编程操作、读取操作、擦除操作

3.5 并行存储器（重点）

• 由于CPU和主存储器之间在速度上是不匹配的，这种情况成为限制高速计算机设计的主要问题。
• 为了提高CPU和主存之间的数据传输率，除了主存采用更高速的技术来缩短读出时间外，还可以采用并行技术的存储器。
• 双端口存储器——空间并行技术
• 多模块交叉存储器——时间并行技术

3.5.1 双端口存储器

1、双端口存储器的逻辑结构

双端口存储器由于同一个存储器具有两组相互独立的读写控制电路而得名。
由于进行并行的独立操作，因而是一种高速工作的存储器，在科研和工程中非常有用。
举例说明，双端口存储器IDT7133的逻辑框图。如下页图。

2、无冲突读写控制

• 当两个端口的地址不相同时，在两个端口上进行读写操作，一定不会发生冲突。
• 当任一端口被选中驱动时，就可对整个存储器进行存取，每一个端口都有自己的片选控制(CE)和输出驱动控制(OE)。
• 读操作时，端口的OE(低电平有效)打开输出驱动器，由存储矩阵读出的数据就出现在I/O线上。

3、有冲突读写控制

• 当两个端口同时存取存储器同一存储单元时，便发生读写冲突。
• 为解决此问题，特设置了BUSY标志。在这种情况下，片上的判断逻辑可以决定对哪个端口优先进行读写操作，而对另一个被延迟的端口置BUSY标志(BUSY变为低电平)，即暂时关闭此端口。

3.5.2多模块交叉存储器

1、存储器的模块化组织

一个由若干个模块组成的主存储器是线性编址的。这些地址在各模块中如何安排，有两种方式：一种是顺序方式，一种是交叉方式
[例]M0－M3共四个模块，则每个模块8个字
顺序方式：　　M0：0-7
　　　　　　　M1：8-15
　　　　　　　M2：16-23
　　　　　　　M3：24-31
5位地址组织如下： X X X X X
　高位选模块，低位选块内地址

• 特点：某个模块进行存取时，其他模块不工作。
• 优点：某一模块出现故障时，其他模块可以照常工作，通过增添模块来扩充存储器容量比较方便。
• 缺点：各模块串行工作，存储器的带宽受到了限制。

[例]M0－M3共四个模块，则每个模块8个字
交叉方式：　　　M0：0，4，……除以4余数为0
　　　　　　　　M1：1，5，……除以4余数为1
　　　　　　　　M2：2，6，……除以4余数为2
　　　　　　　　M3：3，7，……除以4余数为3
5位地址组织如下： X X X X X
高位选块内地址，低位选模块

• 特点：连续地址分布在相邻的不同模块内，同一个模块内的地址都是不连续的。
• 优点：对连续字的成块传送可实现多模块流水式并行存取，大大提高存储器的带宽。使用场合为成批数据读取。

2、多模块交叉存储器的基本结构

下图为四模块交叉存储器结构框图。主存被分成4个相互独立、容量相同的模块M0，M1，M2，M3，每个模块都有自己的读写控制电路、地址寄存器和数据寄存器，各自以等同的方式与CPU传送信息。在理想情况下，如果程序段或数据块都是连续地在主存中存取，那么将大大提高主存的访问速度。

3.6 cache存储器（重点）

3.6.1 cache基本原理

1、cache的功能

• 为了解决CPU和主存之间的速度不匹配问题而采用的一项重要技术
• 介于CPU和主存之间的小容量高速缓冲存储器
• 基于程序访问的局部性原理
• 能高速地向CPU提供指令和数据，从而加快了程序的执行速度。
• 为追求高速，包括管理在内的全部功能由硬件实现。

程序访问的局部性原理

在一个较短的时间间隔内，程序对局部范围的存储器地址的频繁访问，而对局部范围以外的地址访问甚少的现象，称为程序的局部性。
一般cache采用高速的SRAM制作，其价格比主存贵，但因其容量远小于主存，因此能较好地解决速度和价格的矛盾。

2、cache基本原理

• cache的设计依据:CPU这次访问过的数据，下次有很大的可能也是访问附近的数据。(程序访问的局部性)
• CPU与Cache之间的数据交换是以字为单位
• 主存与Cache之间的数据交换是以块为单位
• CPU读取内存中一个字时，便发出此字的内存地址到Cache和主存。此时Cache控制逻辑依据地址判断此字当前是否在Cache中。若是，此字立即传送给CPU;若非，则用主存读周期把此字从主存读出送到CPU，与此同时，把含有这个字的整个数据块从主存读出送到cache中。

下图中，cache分为4行，每行4个字。分配给cache的地址存在一个相联存储器CAM中，它是按内容寻址的存储器。当CPU执行访存指令时，就把所要访问的字的地址送到CAM和主存。送到CAM的地址按内容进行比较判断，若该字不在cache中，则从主存找到这个字，并将该字从主存传送到CPU。与此同时，把包含该字的前后相继的4个字的一行数据送入cache。

3、cache结构

• Cache的数据块称为行，用L_i表示，其中i=0, 1, … , m-1
• 主存的数据块称为块，用B_j表示，其中j=0, 1, … , n-1
• 行与块是等长的，每行(块)包含k个主存字
• Cache由数据存储器和标签存储器组成
  • 数据存储器：存放主存一个数据块的数据
  • 标签存储器：保存数据所在主存的地址信息
    

4、命中与未命中

命中：

• 主存块调入缓存
• 主存块与缓存块建立了对应关系
• 用标记记录与某缓存块建立了对应关系的主存块号

未命中：

• 主存块未调入缓存
• 主存块与缓存块未建立对应关系

命中率：

• 从CPU来看，增加一个cache的目的，就是在性能上使主存的平均读出时间尽可能接近cache的读出时间。
• 为了达到这个目的，在所有的存储器访问中由cache满足CPU需要的部分应占很高的比例，即cache的命中率应接近于1。
• 在一个程序执行期间，设 Nc 表示cache完成存取的总次数，Nm 表示主存完成存取的总次数，h定义为命中率，则有 h = Nc /（ Nc + Nm)
• 若Tc表示命中时的cache访问时间，Tm表示未命中时的主存访问时间，1-h表示未命中率，则cache/主存系统的平均访问时间Ta为： $$T_a=h\ast T_c+(1-h)\ast T_m$$
• 我们追求的目标是，以较小的硬件代价使cache/主存系统的平均访问时间T_a越接近T_c越好。
• 设r表示主存慢于cache的倍率$$r=\frac{T_m}{T_c}$$
  e表示访问效率，则有
  $$\begin{gathered} e=T_c/T_a \\ =\frac{T_c}{h\ast T_c+（1-h)\ast T_m} \\ =\frac{1}{h+（1-h）\ast r} \\ =\frac{1}{r+（1-r)\ast h} \end{gathered}$$
  即$$e=\frac{1}{r+（1-r)\ast h}$$
• 由表达式看出，为提高访问效率，命中率h越接近1越好，r值以5—10为宜，不宜太大。
• 命中率h与程序的行为、cache的容量、组织方式、块的大小有关。

例6:CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间。
解： h= Nc /（ Nc + Nm) =1900/(1900+100)=0.95
r= tm / tc =250ns/50ns=5
e=1/(r+(1-r)h)=1/(5+(1-5)×0.95=83.3%
e= tc /ta
ta= tc /e=50ns/0.833=60ns

3.6.2 主存与cache的地址映射

• 与主存相比，cache的容量很小，保存的内容只是主存内容的一个子集，且cache与主存的数据交换是以块为单位。
• 为了把主存块放到cache中，必须应用某种方法把主存地址定位到cache中，称为地址映射。
• 无论选择哪种映射方式，都要把主存和cache划分为同样大小的“块”。
• 选择哪种映射方式，要考虑：
  • 硬件是否容易实现
  • 地址变换的速度是否快
  • 主存空间的利用率是否高
  • 主存装入一块时，发生冲突的概率
• 以下我们介绍三种映射方法
  • 全相联映射、直接映射、组相联映射

全相联映射方式

主存中一个块的地址(块号)与块的内容(字)一起存于cache的行中，其中块地址存于cache行的标记部分主存的每一块都可映射到cache任意一行中

• CPU访存指令指定一个内存地址(由块号和字组成)
• 为了快速检索，主存地址中的块号与Cache 中所有行的标记同时在比较器中进行比较。相同表示块号命中，按字地址从cache中读取一个字；如果块号未命中，则按内存地址从主存中读取这个字
• 转换公式
  • 主存地址长度＝(s+w)位
  • 寻址单元数＝2^w个字或字节
  • 块大小＝行大小＝2^w个字或字节
  • 主存的块数＝2^s
  • 标记大小＝s位
  • cache的行数＝不由地址格式确定
• 优点：可使主存的一个块直接拷贝到cache中的任意一行上，非常灵活，cache空间的利用率高，cache的块冲突概率低
• 缺点：比较器难实现，需要一个访问速度很快代价高的相联存储器，只适合于小容量cache采用

直接映射方式

• 一种多对一的映射关系
• 一个主存块只能拷贝到cache的一个特定行位置上
• Cache的行号i与主存的块号j有如下函数关系
  • i= j mod m （m为cache的总行数）
  • 主存第j块内容拷贝到Cache的i行
    

直接映射方式的检索过程

• 利用行号选择相应行；
• 把行标记与CPU访问地址进行比较。相同表示命中，访问Cache；如果没有命中，访问主存，并将相应块写入Cache
  
  转换公式
• 主存地址长度 = (s+w)位
• 寻址单元数 = 2^s+w个字或字节
• 块大小 = 行大小 = 2^w个字或字节
• 主存的块数=2^s
• cache的行数 = m =2^r
• 标记大小=(s-r)位

优点：比较电路少m倍线路，所以硬件实现简单，Cache地址为主存地址的低几位，不需变换。
缺点：冲突概率高
应用场合：适合大容量Cache

组相联映射方式

全相联映射和直接相联映射两种方式的优缺点正好相反，从存放位置的灵活性和命中率来看，前者为优；从比较器电路简单及硬件投资来说，后者为佳

• 将cache分成u组，每组v行
• 主存块与cache组之间采用直接映射方式，即主存块存放到哪个组是固定的；每个组内部的行之间则采用全相联的映射方式，即主存块可以映射到cache固定组的任一行中
• Cache组号q与主存块号j的关系为
  • q= j mod u (u为cache的总组数)
  • 主存第j块内容拷贝到Cache的q组中的某行
• 地址变换
  • 设主存地址x，看是不是在cache中，先y= x mod u，则在y组中一次查找

比全相联容易实现，冲突低
若v=1，则为直接相联映射方式
若u=1，则为全相联映射方式
v的取值一般比较小， 一般是2的幂(典型值是2，4，8，16)，称之为v路组相联cache。
转换公式

• 主存地址长度＝(s+w)位
• 寻址单元数＝2^s+w个字或字节
• 块大小＝行大小＝2^w个字或字节
• 主存的块数＝2^s
• 每组的行数＝v
• 组数u＝2^d
• cache的行数＝uv
• 标记大小＝(s-d)位

p96例6：一组相联cache由64个行组成，每组4行，主存储器包含4K个块，每块128字，请表示内存地址的格式。
解：块大小 = 行大小 = 2^w个字 = 128 = 2⁷ 所以w = 7
每组的行数 = v = 4
cache的行数 = uv = 64，故组数u = 16
u = 2^d = 16 = 2⁴，故d = 4
主存的块数 = 2^s = 4K = 2² * 2¹⁰ = 2¹²，故s = 12
地址格式如下：

标记s-d	组号d	字号w
8位	4 位	7位

3.6.3 替换策略

• Cache工作原理要求尽量保存最新数据。
• 当一个新的内存块需要拷贝到cache，而允许存放此块的行位置都被其它主存块占满时，就需要替换。
• 直接映射方式：直接替换
• 全相连和组相连方式：从允许存放新主存块的若干特定行中选取一行换出。
• 替换常用的三种算法:
  • 最不经常使用(LFU)算法
  • 近期最少使用(LRU)算法
  • 随机替换

最不经常使用(LFU)算法

• 将一段时间内被访问次数最少的那行数据换出。
• 每行设置一个计数器。新行建立后从0开始计数，每访问一次，被访行的计数器增1。当需要替换时，将计数值最小的行换出，同时将这些行的计数器都清零
• 这种算法，计数周期限定在对特定行两次替换之间的间隔时间内，不能反映近期cache的访问情况

近期最少使用(LRU)算法

• 将近期内长久未被访问过的行换出。
• 每行也设置一个计数器，cache每命中一次，命中行计数器清零，其他各行计数器增1。当需要替换时，将计数值最大的行换出。
• 这种算法保护了刚拷贝到cache中的新数据行，有较高的命中率

随机替换

• 从特定的行位置中随机地选取一行换出
• 这种策略在硬件上容易实现，且速度也比前两种策略快
• 缺点是随意换出的数据很可能马上又要使用，从而降低命中率和cache工作效率。但这个不足随着cache容量增大而减小。

3.7 虚拟存储器（重点）

3.7.1 虚拟存储器的基本概念

1、实地址与虚地址

• 用户编制程序时使用的地址称为虚地址或逻辑地址，其对应的存储空间称为虚存空间或逻辑地址空间
• 计算机物理内存的访问地址则称为实地址或物理地址，其对应的存储空间称为物理存储空间或主存空间。
• 程序进行虚地址到实地址转换的过程称为程序的重定位。

2、虚存的访问过程

• 虚存空间的用户程序按照虚地址编程并存放在辅存中。程序运行时，由地址变换机构依据当时分配给该程序的实地址空间把程序的一部分调入实存。
• 每次访存时，首先判断该虚地址所对应的部分是否在实存中：
  • 如果是，则进行地址转换并用实地址访问主存；
  • 否则，按照某种算法将辅存中的部分程序调度进内存，再按同样的方法访问主存。
• 由此可见，每个程序的虚地址空间可以远大于实地址空间，也可以远小于实地址空间。
  • 前一种情况以提高存储容量为目的，后一种情况则以地址变换为目的。
  • 后者通常出现在多用户或多任务系统中：实存空间较大，而单个任务并不需要很大的地址空间，较小的虚存空间则可以缩短指令地址字段长度。
• 每个程序就可以拥有一个虚拟的存储器，它具有辅存的容量和接近主存的访问速度。但这个虚存是由主存和辅存以及辅存管理部件构成的概念模型，不是实际的物理存储器。虚存是在主存和辅存之外附加一些硬件和软件实现的。

3、cache与虚存的异同

• 从虚存的概念可以看出，主存-辅存的访问机制与cache-主存的访问机制是类似的。这是由cache存储器、主存和辅存构成的三级存储体系中的两个层次。
• cache和主存之间以及主存和辅存之间分别有辅助硬件和辅助软硬件负责地址变换与管理，以便各级存储器能够组成有机的三级存储体系。
• cache和主存构成了系统的内存，而主存和辅存依靠辅助软硬件的支持构成了虚拟存储器。

在三级存储体系中，cache-主存和主存-辅存这两个存储层次有许多相同点；

• 出发点相同 二者都是为了提高存储系统的性能价格比而构造的分层存储体系，都力图使存储系统的性能接近高速存储器，而价格和容量接近低速存储器
• 原理相同 都是利用了程序运行时的局部性原理把最近常用的信息块从相对慢速而大容量的存储器调入相对高速而小容量的存储器。

但cache-主存和主存-辅存这两个存储层次也有许多不同之处:

• 侧重点不同 cache主要解决主存与CPU的速度差异问题；而就性能价格比的提高而言，虚存主要是解决存储容量问题，另外还包括存储管理、主存分配和存储保护等方面。
• 数据通路不同 CPU与cache和主存之间均有直接访问通路，cache不命中时可直接访问主存；而虚存所依赖的辅存与CPU之间不存在直接的数据通路，当主存不命中时只能通过调页解决，CPU最终还是要访问主存。
• 透明性不同 cache的管理完全由硬件完成，对系统程序员和应用程序员均透明；而虚存管理由软件（操作系统）和硬件共同完成，由于软件的介入，虚存对实现存储管理的系统程序员不透明，而只对应用程序员透明（段式和段页式管理对应用程序员“半透明”）。
• 未命中时的损失不同 由于主存的存取时间是cache的存取时间的5～10倍，而主存的存取速度通常比辅存的存取速度快上千倍，故主存未命中时系统的性能损失要远大于cache未命中时的损失。

4、虚存机制要解决的关键问题

• 调度问题——决定哪些程序和数据应被调入主存。
• 地址映射问题——在访问主存时把虚地址变为主存物理地址（这一过程称为内地址变换），在访问辅存时把虚地址变成辅存的物理地址（这一过程称为外地址变换），以便换页。此外还要解决主存分配、存储保护与程序再定位等问题。
• 替换问题——决定哪些程序和数据应被调出主存。
• 更新问题——确保主存与辅存的一致性。在操作系统的控制下，硬件和系统软件为用户解决了上述问题，从而使应用程序的编程大大简化。

3.7.2 页式虚拟存储器

1、页式虚存地址映射

• 页式虚拟存储系统中，虚地址空间被分成等长大小的页，称为逻辑页；
• 主存空间也被分成同样大小的页，称为物理页。
• 虚地址分为两个字段：高字段为逻辑页号，低字段为页内地址（偏移量）；
• 实存地址也分两个字段：高字段为物理页号，低字段为页内地址。
• 通过页表可以把虚地址（逻辑地址）转换成物理地址。页式虚拟存储器的地址映射过程见下图。
• 在大多数系统中，每个进程对应一个页表。页表中对应每一个虚存页面有一个表项，表项的内容包含该虚存页面所在的主存页面的地址（物理页号），以及指示该逻辑页是否已调入主存的有效位。
• 地址变换时，用逻辑页号作为页表内的偏移地址索引页表（将虚页号看作页表数组下标）并找到相应物理页号，用物理页号作为实存地址的高字段，再与虚地址的页内偏移量拼接，就构成完整的物理地址。
• 每个进程所需的页数并不固定，所以页表的长度是可变的，因此通常的实现方法是把页表的基地址保存在寄存器中，而页表本身则放在主存中。由于虚存地址空间可以很大，因而每个进程的页表有可能非常长为了节省页表本身占用的主存空间，一些系统把页表存储在虚存中，因而页表本身也要进行分页。
• 当一个进程运行时，其页表中一部分在主存中，另一部分则在辅存中保存。
• 另一些系统采用二级页表结构。每个进程有一个页目录表，其中的每个表项指向一个页表。因此，若页目录表的长度（表项数）是m,每个页表的最大长度（表项数）为n,则一个进程最多可以有m×n个页。
• 在页表长度较大的系统中，还可以采用反向页表实现物理页号到逻辑页号的反向映射。

2、转换后援缓冲器（快表TLB）

• 由于页表通常在主存中，因而即使逻辑页已经在主存中，也至少要访问两次物理存储器才能实现一次访存，这将使虚拟存储器的存取时间加倍。
• 为了避免对主存访问次数的增多，可以对页表本身实行二级缓存，把页表中的最活跃的部分存放在高速存储器中，组成快表。
• 这个专用于页表缓存的高速存储部件通常称为转换后援缓冲器(TLB)。
• 保存在主存中的完整页表则称为慢表。
• TLB（快表）的地址映射过程见图
• 

3、内页表和外页表

• 页表是虚地址到主存物理地址的变换表，通常称为内页表。
• 外页表：用于虚地址与辅存地址之间的变换。
• 当主存缺页时，调页操作首先要定位辅存，而外页表的结构与辅存的寻址机制密切相关。
  • 例如对磁盘而言，辅存地址包括磁盘机号、磁头号、磁道号和扇区号等。

页式存储主要优点：

• 主存储器的利用率比较高
• 页表相对比较简单
• 地址变换的速度比较快
• 对磁盘的管理比较容易

主要缺点：

• 程序的模块化性能不好
• 页表很长，需要占用很大的存储空间

3.7.3 段式虚拟存储器和段页式虚拟存储器

1、段式虚拟存储器

• 段是按照程序的自然分界划分的长度可以动态改变的区域。
• 程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中，并且每个程序可以有多个相同类型的段。
• 在段式虚拟存储系统中，虚地址由段号和段内地址（偏移量）组成。虚地址到实主存地址的变换通过段表实现。
• 每个程序设置一个段表，段表的每一个表项对应一个段。每个表项至少包含下面三个字段：
  • 有效位：指明该段是否已经调入实存。
  • 段起址：指明在该段已经调入实存的情况下，该段在实存中的首地址。
  • 段长：记录该段的实际长度。设置段长字段的目的是为了保证访问某段的地址空间时，段内地址不会超出该段长度导致地址越界而破坏其他段。 段表本身也是一个段，可以存在辅存中，但一般是驻留在主存中。

段式虚地址向实存地址的变换过程

段式虚拟存储器有许多优点：

• ①段的逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享。
• ②段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间。
  缺点：
• ①因为段的长度不固定，主存空间分配比较麻烦。
• ②容易在段间留下许多外部碎片，造成存储空间利用率降低。
• ③由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚地址和实地址的最低若干二进制位作为段内偏移量，并与段号进行直接拼接，必须用加法操作通过段起址与段内偏移量的求和运算求得物理地址。因此，段式存储管理比页式存储管理方式需要更多的硬件支持。

2、段页式虚拟存储器

• 段页式虚拟存储器是段式虚拟存储器和页式虚拟存储器的结合。实存被等分成页。每个程序则先按逻辑结构分段，每段再按照实存的页大小分页，程序按页进行调入和调出操作，但可按段进行编程、保护和共享。

[例1] 假设有三道程序，基号用A、B和C表示，其基址寄存器的内容分别为S_A、S_B和S_C。程序A由4个段构成，程序C由3个段构成。段页式虚拟存储系统的逻辑地址到物理地址的变换过程如图所示。在主存中，每道程序都有一张段表，A程序有4段，C程序有3段，每段应有一张页表，段表的每行就表示相应页表的起始位置，而页表内的每行即为相应的物理页号。请说明虚实地址变换过程。

解：地址变换过程如下：
（1）由存储管理部件根据基号C找到段表基址寄存器表第c个 表项，获得程序C的段表基址SC。再根据段号S(=1)找到 程序C段表的第S个表项，得到段S的页表起始地址b。
（2）根据段内逻辑页号P(=2)检索页表，得到物理页号（图中 为10）。
（3）物理页号与页内地址偏移量拼接即得物理地址。 假如计算机系统中只有一个基址寄存器，则基号可不要。 多道程序切换时，由操作系统修改基址寄存器内容。

可以看出，段页式虚拟存储器的缺点是在由虚地址向主存地址的映射过程中需要多次查表，因而实现复杂度较高．

3.7.4 虚存的替换算法

当从辅存调页至主存而主存已满时，也需要进行主存页面的替换。虚拟存储器的替换算法与cache的替换算法类似：有FIFO算法、LRU算法、LFU算法等。

虚拟存储器的替换算法与cache的替换算法不同的是：

• （1）cache的替换全部靠硬件实现，而虚拟存储器的替换有操作系统的支持。
• （2）虚存缺页对系统性能的影响比cache未命中要大得多，因为调页需要访问辅存，并且要进行任务切换。
• （3）虚存页面替换的选择余地很大，属于一个进程的任何页面都可替换。

本章小结

• 对存储器的要求是容量大、速度快、成本低。为了解决了这三方面的矛盾，计算机采用多级存储体系结构，即cache、主存和外存。CPU能直接方问内存(cache、主存），但不能直接访问外存。存储器的技术指标有存储容量、存取时间、存储周期、存储器带宽。
• 广泛使用的SRAM和DRAM都是半导体随机读写存储器，前者速度比后者快，但集成度不如后者高。二者的优点是体积小，可靠性高，价格低廉，缺点是断电后不能保存信息。
• 只读存储器和闪速存储器正好弥补了SRAM和DRAM的缺点，即使断电也仍然保存原先写入的数据。特别是闪速存储器能提供高性能、低功耗、高可靠性以及移动性，是一种全新的存储器体系结构。
• 双端口存储器和多模块交叉存储器属于并行存储器结构。前者采用空间并行技术，后者采用时间并行技术。这两种类型的存储器在科研和工程中大量使用。
• cache是一种高速缓冲存储器，是为了解决CPU和主存之间速度不匹配而采用的一项重要的硬件技术，并且发展为多级cache体系，指令cache与数据cache分设体系。要求cache的命中率接近于1。主存与cache的地址映射有全相联、直接、组相联三种方式。其中组相联方式是前二者的折衷方案，适度地兼顾了二者的优点又尽量避免其缺点，从灵活性、命中率、硬件投资来说较为理想，因而得到了普遍采用。
• 用户程序按照虚地址（逻辑地址）编程并存放在辅存中。程序运行时，由地址变换机构依据当时分配给该程序的实地址空间把程序的一部分调入实存（物理存储空间或主存空间）。由操作系统在硬件的支持下对程序进行虚地址到实地址的变换，这一过程称为程序的再定位。每次访存时，首先判断该虚地址所对应的部分是否在实存中：如果是，则进行地址转换并用实地址访问主存；否则，按照某种算法将辅存中的部分程序调度进内存，再按同样的方法访问主存。 对应用程序而言，如果主存的命中率很高，虚存的访问时间就接近于主存访问时间，而虚存的大小仅仅依赖于辅存的大小。
• 虚存机制也要解决一些关键问题，包括调度问题、地址映射问题和替换问题等。在操作系统的控制下，硬件和系统软件为用户解决了上述问题，从而使应用程序的编程大大简化。
• 页式虚拟存储系统中，虚地址空间和主存空间都被分成大小相等的页，通过页表可以把虚地址转换成物理地址。为了避免对主存访问次数的增多，可以对页表本身实行二级缓存，把页表中的最活跃部分存放在转换后援缓冲器（TLB）中。
• 分页方式的缺点是页长与程序的逻辑大小不相关，而分段方式则可按照程序的自然分界将内存空间划分为长度可以动态改变的存储区域。在段式虚拟存储系统中，虚地址由段号和段内地址（偏移量）组成。虚地址到实主存地址的变换通过段表实现。
• 段页式虚拟存储器是段式虚拟存储器和页式虚拟存储器的结合，程序按页进行调入和调出操作，但可按段进行编程、保护和共享。 虚拟存储器还解决存储保护等问题。在虚拟存储系统中，通常采用页表保护、段表保护和键式保护方法实现存储区域保护。还可以结合对主存信息的使用方式实现访问方式保护。