第 4章 存贮体系
4.1存贮体系的形成与性能
4.2虚拟存贮
4.3高速缓冲存贮器 Cache
4.4主存保护
?本章重点：
段页式和页式虚拟存贮器的原理；页式虚拟存
贮器的地址映像； LRU/FIFO/OPT替换算法进行页
面替换的过程模拟； LRU算法对页地址流的堆栈
处理模拟及性能分析； Cache存贮器的直接和组
相联地址映像； LRU替换算法的硬件实现及替换
过程模拟； Cache存贮器的性能分析等。
?本章难点：
段页式和页式中虚实地址的计算；各种页面替
换算法的模拟和页面命中率的计算； Cache组相
联映像和块替换算法的模拟。
4.1 存贮体系的形成与性能
4.1.1发展存贮体系的必要性
1.存贮器的性能要求
1)大容量
2)高速度
3)低价格
2.容量
SM=W ·l ·m
W：存贮体的字长，单位为 bit或 Byte。
l：每个存贮体的字数。
m：并行工作的存贮体的个数 。
3.速度
从下面三个方面来描述,
1)访问时间 TA
TA是存贮器接到访存到信息被读到数据总线上
所需的时间。是确定 CPU与存贮器时间关系的重
要指标。
2)存贮周期 TM
TM是连续启动一个存贮体所需要的时间间隔。
一般来说总比 TA大。
3)存贮器频宽
是指存贮器可以提供的数据传送率，一般用每
秒钟所传送的信息位数来衡量。
a)最大频宽 BM(极限频宽 )
是存贮器连续访问时能提供的频宽。
单体,BM =W/TM
m体并行工作,BM =mW/TM
b)实际频宽
实际频宽小于最大频宽 BM。
4.价格
可以用总价格 C或每位价格 c来表示。具有 SM
位的存贮器每位价格 c=C/SM。其中包括了存贮
器本身的价格和为该存贮器操作所必须的外围
电路的价格。
5.结论
由于存贮器的价格、速度和容量的要求是矛盾
的，为了同时满足三方面的要求，在一个完整
的存贮体系中，必须采用不同工艺的存贮器，
使得信息以各种方式分布于不同的存贮体。
比如：
主存 当前活跃的信息，快，少
辅存 暂时不用的信息，慢，多
虚存 swap
从速度来说，主存远远跟不上 CPU的要求，为
了弥补这一差距，特引入并行和重叠技术，构
成并行主存系统，但这种并行主存的方法提高
频宽是有限的，因此还需从系统结构入手，发
展存贮体系。
4.1.2并行主存系统频宽的分析
1.类型
1)单体单字
存贮器字长 W与 CPU字长 W
相同,一次访问一个存贮器
字,主存最大频宽 BM =W/TM
W位
读出寄存器
地址寄存器
单体单字存贮器
l
2)单体多字
存贮器字长等于 m个
CPU字,BM =mW/TM
W位W位 W位 W位
地址寄存器
单体多字 (m=4)存贮器
W位
单字长寄存器
3)多体单字交叉
总线控制
地址寄存器 0 地址寄存器 1 地址寄存器 2 地址寄存器 3
M0 M1 M2 M3
主控 (主存控制部件 )
CPU IOP
…… …… …… ……
多体 (m=4)交叉存贮器
a)存贮器字长等于 m个 CPU字,BM =mW/TM。实际
频宽大于单体多字。
?单体多字：并行读出的 m个字要地址顺序的存
在于同一主存单元。
?多体单字,m个 CPU字地址不必顺序存放，只
要不发生冲突。
b)编址模式
Mj体的编制模式为,m ·i+j；
其中 I=0,1,···,l-1，表示第 i个字；
j=0,1,···,m-1，表示第 j个分体；
m—模 单体多字：一个主存包含的 CPU字数
多体单字：分体体数
模体 地址编址序列 二进制地址码末二位状态
M0
M1
M2
M
3
0,4,8,12,···,4i+0,···
1,5,9,13,···,4i+1,···
2,6,10,14,···,4i+2,···
3,7,11,15,···,4i+3,···
00
01
10
11
地址的模 4低位交叉编址
4)多体多字交叉
多个存贮体，每个存贮体有 CPU字。
上述能并行读出多个 CPU字的单体多字和多体
单字或多体多字的交叉存贮主存系统统称为并行
主存系统。
2.分析
提高 m值，可以提高主存系统的最大频率，但
并不能线性提高实际频率。
原因：
1)模 m越高，存贮器数据总线越长，导致传输
延迟增加；
2)系统效率问题，对于顺序取指，效率可以
提高 m倍，但遇到转移指令，效率就会下降。
3.模型分析
对于 m个独立分体的主存系统，处理机发出一
串地址为 A1,A2,… Aq的访存申请队，在每个主
存周期到来前，申请队被扫描，截取从队头起
的 A1,A2,… Ak的申请序列。申请序列是个在要
求访存申请的 k个地址中，没有两个或两个以上
的地址处于同一分体中的最长序列。显然 k表示
可以同时访问的分体个数的随机变量，不大于 m，
系统效率取决于 k的均值 B，其值越大，可访问
的分体个数越多，系统效率越高。
1)数学模型
设 p(k)表示申请序列长度为 k的概率密度函数，
其中 k=1,2,… m。则 k的均值 B为
B=∑k ?p(k)
B实际就是每个主存周期所访问的平均字数。而
p(k)与程序的状态密切相关，特别是指令转移概
率 p，它定义为给定下条指令地址为非顺序地址
的概率。因此
p(k)=(1-p)k-1?p,1≤k<m —几何概率
p(m)=(1-p)m-1
k=1
m
所以,B=∑k ?p(k)=1?p+2?(1-p)?p
+ +m?(1-p)m-1
=(1-(1-p)m)/p
2)讨论：
a)若每条指令都是转移指令且转移成功，即
p=1,则 B=1，就是并行多体交叉存取的实际频宽
降到和单体单字一样；
b)若所有指令都不转移，即 p=0，则 B=m，此时
多体交叉存贮的效率最高。
k=1
m
…
3)结论
由于程序的转移概率不会很低，数据分布的离
散性较大，所以单纯靠增大 m来提高并行主存系
统的频宽是有限的，而且性价比还会随 m的增大
而下降。如果采用并行主存系统仍不能满足速度
上的要求，就必须从系统结构上改进，采用存贮
体系。
4.1.3存贮体系的形成与分支
1.容量需求
1)程序覆盖技术
方法：将大程序分块，
确定在辅存中的位置并放入辅存，然后根据要
求把当前用到的程序和数据调入主存中指定位
置以覆盖或替换那些已在主存但现在不用的段。
这只构成一个存贮系统而非存贮体系。主辅存
间的调入调出完全由程序员安排，增大编程难
度和负担，拉长程序运行时间，也难以使用更
好的算法。
主存 辅存
程序员
2)增设辅助软硬件
随着 I/O处理
机的出现及多道
程序的发展，一道
程序的运行可以与
另一道程序的调入调出同时进行。因此主辅存间
的地址定位可以改由辅助软硬件来完成，如图。
这样就构成了存贮体系，或存贮层次。
主存 辅存
辅助软硬设备
从整体来看，
速度是主存的
容量是辅存的
主存 —辅存存贮层次
如果存贮层次能以接近于辅存的每位价格构成
等于辅存容量的快速主存，存贮系统的性价比就
会大大提高。进一步完善发展就形成虚拟存贮系
统。这样程序员就可以用机器指令的地址码对整
个程序统一编址，这一空间远大于实际主存空间。
这种指令地址码称为虚地址、逻辑地址、程序地
址等，其对应的存贮容量称为虚存容量或程序空
间；而实际主存的地址称为物理地址、实 (存 )地
址，其对应的存贮容量称为主存容量、实存容量
或实 (主 )存空间
由于程序空间远大于主存空间，特别多道程序，
每个用户只用到主存空间的一部分，不能将程序
全部装入主存，只能把程序空间分成较小的块或
页，由系统负责把所需块或页按需调入主存。当
用虚地址访问主存时，首先检查其对应的内容是
否已在主存。若在，就由硬件自动把虚地址变换
成实地址去访存；否则需经辅助软硬件将包含所
要访问的单元在内的那一块程序由虚存调入主存，
然后进行访问。这样，不论是虚实地址的变换还
是程序的调入都不必程序员安排，而是透明的。
也正符合存贮层次的要求。
2.速度需求
由于主存和 CPU的速度差距已达一个数量级，
为了解决这一问题，提出了多种办法：
1)在 CPU中设置通用寄存器 (GR)，让运算直接在
CPU的 GR中进行，减少与主存的交往。但主存
与 GR间的传送要由程序设计者安排，且 GR的数
目不能过多。
2)采用存贮器的多体交叉并行存取来提高主存
的速度。但这种方法对速度的改善有限，且有
可能使性价比下降。
3)Cache—主存存贮层次
通过在 CPU与主存间加一级速度高、容量小、每
个价格较高的高速缓冲存贮器 (Cache)，借助于
硬件是 Cache和主存构成一个整体。信息在 Cache
与主存间的传送全部由硬件完成，所以 Cache对
应用程序员和系统程序员都是透明的。
高速缓冲
Cache
主 存
M
辅助硬件
CPU
从 CPU来看，
速度是 Cache的
容量是主存的
4)多级存贮层次
从 M1到 Mn，速度变慢，容量增大，价格降低。
CPU M1 M2 M3 Mn
从 CPU来看，
速度是 M1的，
容量是 Mn的，
价格 是 Mn的
程序局部性概念：
a)时间局部性：在最近的未来要用到的信息很
可能是现在正在使用的信息，这是由程序循环造
成的，即循环中的语句要被重复执行。
b)空间局部性：在最近的未来要用到的信息很
可能与现在正在使用的信息在程序空间上相邻或
相近，这是由于指令通常是顺序执行的。
利用程序局部性，可以预知下一步要访问的
程序块而在 M1中做好准备。
时间局部性：存放近期使用过的块或页。
空间局部性：从 M2级把访问字所在页或块一同取
到 M1中。
4.1.4存贮体系的性能参数
以如图所示的二级体系 (M1,M2)为例来分析
1.存贮体系的每位
平均价格 c
c1 ? SM1 +c2? SM2
SM1 +SM2
1)M2容量大且便宜,所以,SM1<< SM2，使 c接
近于 c2。
2) 应使辅助软硬件的价格占很小比例。
M1 M2
c1,SM1,TA1 c2,SM2,TA2
c,SM,TA
c=
2.命中率 H
CPU产生的逻辑地址能 M1在中访问到 (命中 )的
概率。
R1表示能在 M1中访问到的次数；
R2表示当时在 M2中还未调到 M1的次数。
失效率 (不命中率 ),1-H
R1
R1 + R2H=
3.等效访问时间
TA=HTA1+(1-H)TA2
TA TA1越好，即访问效率 e=TA1/TA 1越好。
相邻两级的访问时间比 r=TA2/TA1，则：
e= TA1/TA= TA1/(HTA1+(1-H)TA2)
=1/(H+(1-H)r)
由上式知，要是 e趋近 1,r越大要求 H越高。 H提
高不易，采用其它方法：
a)减小相邻两级的访问速度差距
b)减小相邻两级存贮器的容量差
4.2 虚拟存贮器
虚拟存贮器是主存 —辅存存贮层次的发展和完
善，主要为了克服高速主存容量满足不了要求而
提出的。在虚拟存贮器中，应用程序员直接用机
器指令的地址码对程序统一编址，这一地址码宽
度对应的程序空间比实际主存空间大的多，就好
像对应用程序员来说有一个比实际主存大得多的，
可以放得下整个程序得虚 (主 )存空间。程序不必
作任何修改就可以以接近于实际主存的速度在虚
拟存贮器上运行。
4.2.1不同的虚拟存贮管理方式
程序定位：
由于 CPU只能执行已装入主存的程序块，为了
提高主存空间的利用率，应及时释放主存中现已
不用的空间以装入别的程序块。随着程序的运行，
程序的各个部分就会在主存和辅存间来回调进调
出。当辅存中的程序调入主存时，必须进行程序
在主存中的定位。这种定位应该由系统提供的定
位机构来自动完成，从而对应用程序员透明。
虚拟存贮器程序定位的实现,
虚拟存贮器通过地址映像表来实现程序在主存
中的定位。其思想是把程序分割成若干较小的段
或页，用相应的映像表机构来指明该程序的某段
或页是否已装入主存。若已装入，则同时指明其
在主存中所处的开始位置；否则去辅存中调段或
页，并建立起程序空间和主存空间的地址映像关
系。这样，程序执行时通过查映像表将程序虚地
址变换成实际主存地址再访主存。
1.段式管理
1)思想
根据程序的模块性，把一个复杂的大程序分解
成多个逻辑上相对独立的模块。模块可以是主程
序、子程序或过程，也可以是表格、数组、树、
向量等某类数据元素的集合。其大小可以不同，
甚至事先无法确定。每个模块都是一个单独的程
序段，都以该段的起点为 0相对编址。调入主存
时，系统按照基址 (该段程序在主存中的起始地
址 )和每个单元在段内的相对位移组合来形成各
单元在主存的实际地址。这种按段分配的存贮管
理方式称为段式管理。
0段
1段
2段
3段
4段
5段
6段
A道程序的
程序空间
断表长度 断表基地址
断表基址寄存器
(主存中最多有 N道道程序 )
01
23
45
6
0
5k
1k
0
0
0
0
1
1
1
1k
3k
2k
访问方式段长装入位地址段名 (号 )
a
01
A
N-1
0
1k-10
0
0
0
0
0
2k-1
2k-1
2k-1
1k-1
4k-1
3k-1
a7
…
…
…
…
实主存空间
1k
2k
3k
0段
4段
2段
1k0k
5k
2.5k
段内位移段号基号 (程序号 )
多用户虚地址 A 4 1.5k?
?
?
+
??
?
+
已装入
段式管理的定位映像机构及其地址的变换过程
A道程序
的段表
2)断表
为了进行段式管理，每道程序都由一个断表 (映
像表 )，用以存放该程序各程序段装入主存的状
况信息。
段名 (号 ):实际由于段号与行对应，省略掉。
装入位,表征是 (1)否 (0)已调入主存。
地址,调入主存时，在主存的起始 (绝对 )地址。
段长,段的大小，限制偏移越界。
访问方式,只读、可写、只执行，提供访问保护。
3)断表基址寄存器
断表长度,该道程序的断数 (断表行数 )。
断表基地址,程序的断表在主存中的起始地址。
4)虚拟地址
基号 (程序号 ):断表在断表基址寄存器的位置。
段号,段在断表中的位置。
段内位移,所访问单元在段内的偏移。
5)地址变换
如上图所示。
6)优点
a)能使大程序分模块编制，便于多程序员并行
编程，缩短编制时间。且各段的修改增添方便。
b)便于多道程序共用已在主存的程序和数据。
c)有利于以段为单位实现存贮保护，这对发现
程序设计错误和非法使用是有用的。
7)实主存管理表
为了高效的为调入段分配主存区域,OS为整个
主存建立一个实主存管理表，来标明主存的使
用情况。
a)占用区域表
用来指明主存中的哪些区域被哪道程序的哪
个段占用以及该段程序在主存的起点和长度。
b)可用区域表
用来指明未被占用的区域的基地址和大小。
8)可用区域分配算法
由于各段的长度不等，必须采用不同的算法
对主存可用区域进行分配。
a)首先分配算法
顺序扫描可用区域表，当找到第一个不小于
要调入段长度的可用区域时就立即进行分配 。
优点是分配速度快，由于首先分配主存低区，
造成可用区零头数少，而且容易在主存高区保
留较大空间以备容纳大程序段。
b)最佳分配算法
先全部扫描可用区域表，然后寻找一个可用
区域进行分配，使之分配后段间可用区零头最
小。这一算法虽然考虑了尽量减小每一个段间
可用区的零头，但是会使段间可用区零头数较
多。
如下例：
A
B
C
A A
B B
C C
D
E
F
D
E
F D
E
0 0 0
0.5k 0.5k 0.5k
3k 3k 3k
7k 7k 7k
8k 8k 8k
10k 10k 10k
4k
1k
2.5k
2k
6.5k
5.5k
9k
主存
程序
主存 主存
(a)需依次调入 D,E,F段 (b)首先分配法D,E,F全被装入 (c)最佳分配法F段无法装入
段式存贮分配算法
2.页式管理
1)段式管理的缺点
a)各程序段装入主存的起点是任意的，断表中
的地址字段必须能够表示出主存中的任意一个
绝对地址。
b)各段长度受程序本身影响也是任意的，所以
地址字段和段长字段都很长。
c)容易产生较大的段间零头浪费。如下所示,
00
11
22
3
4
5
6
7
0
4k-1
32k-1
4k
4k
4k
主存页号 虚存页号主存空间
D道程序
程序空间
程序标志号
D
基号 虚页号 页内位移
?
?
实页号 页内位移
b
nv nrnp
Nv’ Nr
专用
位
访问
方式
装入
位
主存
起点
0
1
2
1
1
1
2
6
7
虚存
页号
(实页号 )(可省略 )
D道程序页表
b
采用页式存贮后 D道程序可装入
2)页式管理思想
把主存空间和程序空间都机械的等分成固定大
小的页 (页面大小因机器而已，一般在 512到几 kB)
然后按页顺序编号。
3)主存单元地址 np
实页号 nv,主存中实际划分的页。
页内位移 nr,单元在主存页内的偏移量。
4)虚地址
虚页号 Nv’：程序空间中划分的页。
页内位移 Nr：等于 nr,页大小相同。
页内位移用户虚页号用户标志 u
多用户虚页号 Nv
某道程序的地址 Ni
Nv’ NrX
多用户
虚地址 Ns ? ? ?
由 u转换成基号 b
页表基址寄存器
0
b
N-1
X ?
…
…
查
到
查不到 +
指
向
道
程
序
页
表
X
页内位移
实页号
nrnv np
实页号 装入位
nv 1
X
? ?
主存地址寄存器
已装入
主 存
X道
程序
的内
页表
Y道
程序
的内
页表
页式管理的定位映像机构
及其地址的变换过程
5)页表
保存虚页装入实页时的页面对应关系。
虚页号,与页表行号相同，可以省略。
实页号,主存起点 。
装入位,标志该页是否装入主存 。
访问方式,用于存贮保护。
专用位,区分该页是独占或共享 。
?用户标志 u:指明程序所使用的页表基址寄存器。
?页表寄存器,存放页表在主存中的地址。
6)地址变换
如上图。
3.段页式管理
页式对应用程序员完全透明，所需映像表硬件
少，地址变换速度快，调入操作简单等都优于段
式。页式虽然不能完全消除主存可用区的零头浪
费，因为程序大小不可能恰好是页面大小的整数
倍，产生的零头无法利用，但页内零头比段式的
小的多，所以在空间利用率上页式优于段式的。
因此很少使用纯粹的段式管理存贮器。
然而，段式本身也具有页式所没有的优点，如：
段式中每个段独立，有利于程序员灵活实现段的
链接、段的扩大 /缩小和修改，而不影响其它段；
每段只包含一种类型的对象，若过程或是数组、
堆栈、标量等的集合，易于针对其特定类型实现
保护；把共享的程序或数据单独构成一个段，易
于实现多用户、进程对共用段的管理等。因此，
为了取长补短，提出了把段式和页式相结合的段
页式存贮和管理。
1)思想
把内存机械的等分成固定大小的页，把程序按
模块分段，每个段分成与主存页面大小相同的页，
每道程序通过一个断表和相应于每段的一组页表
来进行定位。
2)段表
装入位,标识该段的页表是否已装入主存。
地址字段,指明已装入页表在主存中的起始地址。
访问方式,指明该段的控制保护信息。
段长,指明该段页表的行数。
3)页 表
装入位,指明此段该页是否已装入主存。
地址字段,装入页在主存中的页号。
段页式与纯段式的主要区别是：段的起点不
再是因程序段的大小而任意的，必须是位于主存
中页面的起点。
对于多道程序来说，每道程序都需要有一个
用户标志号 u(转换成基号 b)来指明该道程序的段
表起点存放在哪个基址寄存器中。
页内位移 d页号 p段号 s用户标志 u
程序标志 用户虚页号 Nv’
某道程序的地址 Ni
多用户
虚地址 NS
由 u转换成基号 b
? ? ? ?
段表基址寄存器
段表长度 段表起点 c
0
b
N-1
?
查不到
查
到
+
装入
位
页表
起点
访问
方式
段长
1 d1? ? 某用户 段表
主存 (多用户段表 )
c
实页号 装入位
主存 (多用户页表 )
1nv ? ?
d1
+
页内位移 nrnv
实页号
已装入
主存
地址 np
某用户
s段
的页表
段页式管理的定位映像机构
及其地址变换过程
4)多级页表
在虚拟存贮器中每访问一次主存都要进行一次
程序地址向实主存地址的转换，段页式的主要问
题就是这个地址变换至少要两次查表，即查段表
和页表。为了提高虚拟存贮器的速度，必须采取
措施加快这种地址转换查表速度。这一问题页式
管理同样存在，因为前面所讲的查页表是基于整
个页表连续存贮的，而当页表的大小超过一个页
面大小时，页表就会分存于主存中不连续的页面
上。这样前述由页表起点加页号查得该页在页表
中的行的查表方式就会出错。
例如：若程序虚地址为 24位，其中页内地址 Nr
为 10位，即
则页表就需要 214行，而页面大小只有 210行。所
以页表本身可能要分存于 16个页面。为此要建立
多级页表，用页表基址寄存器指明第一级页表的
基址，用第一级页表中各行的地址字段指明第二
级各个页表的基址，依此类推。为了节省存放映
像表的主存空间，通常只把第一级页表驻留在主
存内，其它各级页表则根据需要才调入，大部分
放在辅存中。
程序虚地址 Nr(10位 )Nv’(14位 )
4.2.2页式虚拟存贮器的构成
1.地址的映像和变换
多用户虚页号 Nv
指令中访存地址 Ni
u NrNv’
nrnv
多用户
虚地址 NS
实存地址 np
实存空间
2nv页
2nr 2Nr =2nr
…
… …
2Nv页包
括 2u个
用户，
每个用
户 2Nv’页
虚存总空间
虚实地址对应关系及空间的压缩
页式虚拟存贮器是采用页式管理的主存 —辅存
存贮层次。把主存空间和程序空间都等分成页，
让程序起点处于页的起点上。程序员用地址码 Ni
来编程，所以 Ni由用户虚页号 Nv’和页内地址 Nr组
成。主存地址分实页号 nv和页内地址 nr两部分，
且 nr与 Nr一样。大多数虚拟存贮器中每个用户的
程序空间比实际主存空间大得多，即一般 Nv’大于
nv。这样，虚拟存贮器系统总的多用户虚地址 NS
就由用户标志 u、用户的虚页号 Nv’及页内地址 Nr
3部分构成，则总的虚存空间为 2u?2Nv’页。
现在把 u和 Nv’合并成多用户虚页号 Nv，则 2Nv远
远大于 2nv。主存中最多能放 N道程序，即 N个用户，
其它放在辅存。因此就出现了如何把大的多用户
虚存空间压缩装入到小的主存空间中的问题，而
在程序运行时又要考虑如何把多用户虚地址 NS变
换成主存地址 np，再让 CPU去访问主存中该单元。
这就是地址的映像和变换。
1)地址映像
就是将每个虚存单元按某种规则 (算法 )装入 (定
位于 )实存，即建立多用户虚地址 NS与实存地址 np
的对应关系。对于页式就是将多用户虚页号 Nv的
页可以装入主存中的哪些页面位置，建立 Nv与 nv
的对应关系。
2)地址变换
指的是程序按这种映像关系装入实存后，在执
行时多用户虚地址 NS如何变换成对应的实地址 np。
对页式而言就是多用户虚页号 Nv如何变换成实页
号 nv。
3)页面争用
由于是把大的虚存空间压缩到小的主存空间中
去，主存中的一个页面位置就必须能与多个虚页
相对应，能对应多少个虚页与采用的映像方式有
关。这就不可避免的发生有两个以上的虚页想要
进入同一个主存页面的现象，这种现象就是页面
争用或实页冲突。一旦发生页面争用，只能装入
其中的一个虚页，其它的虚页只有等到该页推出
主存后方可装入，这就会使执行效率下降。
4)映像方式的选择
a)尽量减少页面争用概率；
b)考虑减少辅助硬件，降低成本；
c)有利于实现；
d)地址变换的速度快。
5)全相联映像
a)方法
让每道程序的任何虚页可以映像装入到主存
的任何实页位置。只有一个任务要求同时调入
主存的页数超出 2nv (很少有 )时 才会发生页面争
用。因此全相联的实页冲突概率很低。
主 存
虚 存
页面位置 0
1
2
2nv-1
…
页 0
1
2
2Nv’-1
… …
nv nr
NrNv’
np
Ni
每道
程序任
何虚页可
映像到任
何实页
位置
全相联映像
b)页表利用率
整个多用户虚存空间有 2u个用户 (程序 )，但
主存最多只对其中的 N个用户 (N道程序 )开放。
由基号 b标识的 N道程序中的每一道都有一个最
大行为 2Nv’的页表，而主存总共只有 2nv个实页位
置, 因此 N道程序页表的全部行 N?2Nv’中，装入位
为 1的最多只有 2nv行。由于 N?2Nv’>>2nv，使得页表
中绝大部分行中实页号 nv字段及其它字段都不
再有用了，这就会大大降低页表的空间利用率。
c)解决办法
?将页表中装入位为 0的行用实页号 nv字段存放
该程序此虚页在辅存中的实地址，以便调页时
实现用户虚页号到辅存实地址的变换。
?相联目录表法,把页表压缩成只存放已装入主
存的那些虚页 (用基号 b和 Nv’标识 )与实页位置
(nv)的对应关系。这样该表最多为 2nv行，简称
为目录表法，采用按内容访问的相联存贮器构
成。如下图：
基号 用户虚页号 页内位移
某用户虚地址
基号＋用户
虚页号
实页号 其它
信息
目录表 (存在相联存贮器中 )
相联比较
查找到
目录表法
Nv’b Nr
nv
nv
nr(Nr) np
b+Nv’
2nv行
d)相联存贮器
在一个存贮周期内能将给定的 Nv同时与目录表
的全部 2nv个单元对应的虚页号字段内容比较进行
相联查找。如有相符的即相联查找到时，表示此
虚页已装入主存，该单元存放的实页号 nv就是此
虚页所存放的实页位置，将其读出拼接上 Nr就可
形成访存实地址 np；如无相符的即相联查找不到，
表示此虚页未装入主存，发生页面失效，请求从
辅存中调页。由此可见，采用目录表法不用设置
装入位了。
6)虚页的调入
当发生页面失效时，要想把该道程序的虚页
调入主存，必须给出该页在辅存中的实际地址。
为了提高调页效率，辅存一般是按信息块编址
的，且块的大小等于页面大小。以磁盘为例，
辅存实 (块 )地址格式 Nvd为：
这样就需要将多用户虚页号 Nv变换成辅存实
地址 Nvd 。
磁盘号 柱面号 磁头号 块 号Nvd
?外页表,存放用户虚页号 Nv’与辅存实地址 Nvd的
映像关系，用于外部地址变换。
?内页表,存放用户虚页号 Nv’与主存实页号 nv的映
像关系，用于内部地址变换。
由于虚拟存贮器的页面失效率很低，很少调用
外页表进行地址变换，因此外页表存放在辅存中，
当某道程序初始运行时，才把外页表的内容转录
到已建立内页表的实页号地址字段中，这也是前
述当内页表装入位为 0时让实页号地址字段改放
该虚页在辅存中的实地址的原因。而且对外页表
速度要求低，可以用软件实现。如下图：
磁盘号 柱面号 磁头号 块号Nvd
多用户虚地址
辅存地址
NrNS u Nv’
Nvd1
装入位 辅存实地址
地址变换
(软件实现 )
? ?
已装入
外页表
虚地址到辅存实地址的变换
2Nv’
2.替换算法
1)解决问题
当处理机要用到的指令或数据不在主存中时，
就会产生页面失效，应去辅存中将包含该指令
或数据的一页调入主存。由于虚存空间比主存
空间大得多，必然会出现主存页面位置已全被
占用后又发生页面失效，这时再将辅存中的一
页调入主存时就发生页面争用。只用强制腾出
主存中某页后才能接纳从辅存调来的新页。具
体选择主存中哪一页作为被替换的页，就是替
换算法要解决的问题。
2)原则
a)有高的主存命中率
b)算法便于实现
c)辅助软、硬件成本尽量低
3)常用算法
a)随机算法 (Random,RAND)
用软的或硬的随机数产生器来形成主存中要
被替换页的页号。这种算法简单，易于实现，
但没有利用主存使用情况的历史信息，反映不
了程序的局部性，使主存命中率低，很少采用。
b)先进先出算法 (First In First Out,FIFO)
选择最早装入的页作为被替换的页。这种算法
实现方便，虽然利用了主存使用情况的历史信息，
但是不一定能正确反映出程序的局部性，因为最
先进入的页很可能是现在经常要用到的页 。
实页号 占用位 程序号 段页号
计数器
(使用位 ) 程序优先位 HS 其它信息
0
1
2nv-1
……
主存页面表
c)近期最少使用算法 (Least Recently Used,LRU)
选择近期最少访问的页作为被替换的页。这种
算法能比较正确的反映程序的局部性，因为当前
最少使用的页一般来说未来也将很少访问，但完
全按此算法实现比较困难，需要为每个实页都配
置一个字长很长的计数器字段才行。所以一般采
用它的变形，即近期最久没被访问过的页作为被
替换的页。这样把, 多, 和, 少, 简化成, 有,
和, 无,
之后，实现起来比较方便。
?主存页面表
OS为实现主存管理而设置的，是对主存而言
的，整个主存只有一个。每一行用来记录主存中
各页的使用状况。而页表是对程序空间而言的，
每道程序都有一个，是用来存贮地址映像关系和
实现地址变换的。
实页号,主存页号是顺序的，可以省略
占用位,表示该主存页面是否被占用
程序号 /段页号,该主存页被哪道程序的哪段
哪页占用
使用位,表示该主存页近期是否被使用过
开始时所有页的使用位全为, 0”，只要某个页
的
任何单元被访问过，硬件就自动将该页使用位置
,1”。由于采用全相联映像，调入页可进入对应
于主存页面表中任何占用位为, 0”的实页位置，
一旦装入主存某实页上，就置该实页的占用位为
,1”。只有当所有占用位都是 1且又发生页面失
效
时才有页面替换问题，这时就要用到使用位，只
需替换使用位为, 0”的页即可。
?使用位全, 1,处理
一种办法是由硬件强制全部使用位都为,0”。
从概念上看，近期最少使用的“期”是从上次
使用
位全 0到这次使用位全 0的这段时间。由于这个期
的长短是随机的，所以称为随机期法。
另一种办法是它定期的置全部使用位为,0”。
由“未用过计数器” HS(或称为历史位 )，定期地
每
隔 Δ t扫视使用位, 对使用位为 0的页，则加 1Hs，
并让使用位继续为 0；对使用位为 1的页，则置
0Hs，同时置 0使用位。扫描结束所有使用位为 0，
Hs大的就是最久未访问过的，作为替换页。
d)优化替换算法 (OPT)
?定义
无论是“近期最少使用”还是“近期最久未用
过”
都属于 LRU，与 FIFO类似，都是根据页面使用
的历史情况来预估未来的页面使用状况，只是
比 FIFO更好反映局部性而已。然而，这种“近
期”毕竟是过去了的近期，如果能根据未来实
际使用情况，替换出近期不用的页，主存命中
率会更高，这就是优化替换算法 (Optimal
Replacement Algorithm,OPT)
?方法
在时刻 t找出主存中每个页面将要用到的时刻 ti，
然后选择 ti－ t最大的那一页作为被替换的页。显
然，这只有让程序运行一遍得到实际的页地址流，
才能找到为实现这种替换算法所需要的各页使用
信息，这是不现实的。所以，优化替换算法只是
一种理想化的算法，它可以被用作评价其它替换
算法好坏的标准，看看哪种替换算法能使主存的
命中率接近于优化替换算法。
4)影响命命中率的因素
a)与替换算法有关
例：设有一道程序，有 1至 5共 5页，执行时的
页地址流 (即执行时依次使用到的程序页页号 )
为：
2,3,2,1,5,2,4,5,3,2,5,2
若分配给该道程序的主存有 3页，如下图表示
分别用 FIFO,LRU,OPT3种替换算法对这 3页的使
用和替换过程。 FIFO的命中率最低，而 LRU的
接近于 OPT的。
2*
3
1
2
3
2
3
命中
2
调进 调进 调进
5
3*
1
替换
5
2
1*
替换
5*
2
4
替换
5*
2
4
命中
3
2*
4
替换
3
2*
4
命中
3
5
4*
替换
3*
5
2
替换
FIFO
命中 3次
2
3
2
3
命中
2
调进 调进
2
3
2
3
命中
2
调进 调进
LRU
命中 5次
OPT
命中 6次
页地址流 2 3 2 1 5 2 4 5 3 2 5 2
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
2
3*
1
调进
2*
5
1
替换
2
5
1*
命中
2
5*
4
替换
2*
5
4
命中
3
5
4*
替换
3
5*
2
替换
3*
5
2
命中
3*
5
2
命中
2
3
1*
调进
2
3*
5
替换
2*
3
5
命中
4*
3
5
替换
4*
3
5
命中
4*
3
5
命中
2
3*
5
替换
2
3
5
命中
2
3
5
命中
3种替换算法对同一页地址流的替换过程
b)命中率与页地址流有关
例如一个循环程序，当所需页数大于分配给
它的主存页数时，无论是 FIFO还是 LRU算法的
命中率都明显低于 OPT的。如下图所示,LRU
和 FIFO一次都没有命中，因为它恰好总是将马
上要用到的页面给替换出去了，从而连续不断
的出现页面失效，产生所谓的颠簸现象。
1*
2
3
2
2
1 4
2*
3
4
1
3*
4*
1
2
3
1*
2
3
4
2*
FIFO
无命中
1
2
1
1
2
1
LRU
无命中
OPT
命中 3次
页地址流 1 2 3 4 1 2 3 4
时间 t 1 2 3 4 5 6 7 8
1
2*
4
1
3
4*
1
2
3*
1*
2
4
命中 命中
1
3*
4
命中
命中率与页地址流有关
1
2
4*
1*
2
3
4
2*
3
4
1
3*
4*
1
2
3
1*
2
3
4
2*
c)与主存容量 (即分配给程序的主存页数 )有关
一般来说，分配给程序的主存页数越多，虚
页装入主存的机会就越多，命中率也可能就越
高。但具体还与所采用的替换算法有很大关系。
如下图所示，当分配给程序的主存页数 n由 3增
加到 4时,FIFO的命中率反而由 3/12降到 2/12;
而 LRU的命中率却不会发生这种情况，随着分
配给该道程序的主存页数的增加，命中率一般
都会得到提高，至少不会降低。
1
2
1*
2
1 4
1
3*
4*
1
2
5
1*
2
5
1*
2
命中
5
1*
2
命中
5
3
2*
5*
3
4
5*
3
4
命中
n=3
命中 3次
1
2
1
2
1
n=4
命中 2次
页地址流 1 2 3 4 1 2 5 1 2 3 4 5
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
1*
2
3
命中
3
4
2*
3
3
4
1*
2
3
4
命中
1*
2
3
4
5
2*
3
4
5
1
3*
4
5
1
2
4*
5*
1
2
3
4
1*
2
3
4
5
2*
3
FIFO法的实页数增加，命中率反而有可能下降
5)堆栈型替换算法
a)定义
A：长度为 L的任意一个页面地址流
t,已处理过 t－ 1个页面的时间点
n：分配给该地址流的主存页面数
Bt(n)：在 t时间点、在 n页的主存中的页面集合
Lt：到 t时刻已遇到的地址流中相异页的页数
若 n< Lt时,Bt(n＋ 1) ?Bt(n)
n>= Lt时,Bt(n＋ 1) = Bt(n) 成立，则此替
换算法属于堆栈型的替换算法。
b)优点
?命中率随主存页数的增加只可能提高，至少不
会下降。
?只需采用堆栈处理技术对地址流模拟处理一次，
即可同时获得对此地址流在不同主存页数时的
命中率，大大节省存贮体系设计的工作量。
?对页地址流 A在 t时刻的 At页是否命中，只需看
St-1(主存在 t-1时刻的堆栈 )的前 n项是否有 At，
若有则命中。
c)LRU算法
属于堆栈型算法，把刚访问过的页面至于栈
顶，而把最久未被访问过的页面置于栈底。命
中率随着分配给该道程序的主存页数 n的增加
而单调上升，至少不会下降，这是堆栈型算法
具有的共同特点。
d)FIFO算法
非堆栈型算法，命中率总趋势是会随着主存
页数 n的增加而提高，但从某个局部来看，主
存页数 n的增加有时反倒可能降低其命中率。
5)页面失效频率法 (PFF)
由于堆栈型替换算法具有随分配给该道程序的实
页数 n的增加，命中率 H会单调上升的特点，所以可
对 LRU算法加以改进和发展：根据各道程序运行中
的主存页面失效率的高低，由 OS来动态调节分配给
每道程序的实页数。当主存页面失效率超过某个限
值时就自动增加给该道程序的主存页数来提高其命
中率；而当主存页面失效率低于某个限值时就自动
减少分配给该道程序的主存页数，以便释放出这部
分主存页面位置给其它程序用，从而使整个系统总
的主存命中率和主存利用率得到提高。
3.虚拟存贮器工作的全过程
具体过程见下页图：
Nvd 辅存实地址
外部地址变换
虚地址 =>辅存实地址
用户标志 u 虚页号 Nv’ Nr
6
多用户
虚地址 NS
内部地址变换
虚页号 =>主存实页号
nv nr np
5
2
1
2
页面 0
2nv-1
…
2nr
个字
2nv个页
3
3
2
是否在
主存？
“是,
(访主存 )
“否,
(主存页
面失效 )
4
5
主存 (页式 )2np个字
是否在
辅存？8
6
“否”
(辅存页
面失效 )
“是”
(访辅存 )
主存页面表9
6
页面替
换算法
11
12
已满未满
10
I/O处理机
13
主存
页号
页面 0
页面 0
1
1
2Nv’-1
…
…
(
选
页)
7
14
调
入
页
7
14替换页
被替换页退回
若未被修改则不必退回
辅存
2NS个字
4.2.3页式虚拟存贮器实现中的问题
1.页面失效处理
1)原因
页面的划分只是机械的对程序空间和主存空间
进行等分，与程序的逻辑结构毫无关系。这样，
对于按字节编址的存贮器就有可能出现一条指令
横跨在两页上存贮的情况。同理，也会出现一个
操作数跨在两页上存贮。另外，采用间接寻址，
特别是多重间接寻址时，在寻址的过程中，可能
出现跨页、甚至连续跨多个页访问的情况。每当
当前一页已在主存而跨页存放的另一页不在主存
时，就会发生页面失效。
2)解决方法
由于页面失效可能出现于取指、取操作数、间接
寻址等过程中，即会在一条指令的分析或执行中发
生。通常的中断都是依靠在每条指令执行的末尾去
设置一个访中断微操作，来检查系统中有无未屏蔽
的中断请求，以便对其进行响应和处理。而页面失
效不能采用这种办法，否则由于未能对页面失效进
行处理，就不可能调页，也就无法执行到访中断微
操作，从而就不可能对页面失效进行响应和处理，
机器的工作就被停顿下来。所以，页面失效不能按
一般的中断对待，应看作一种故障，一旦出现，处
理机必须立即予以响应和处理。
a)后援寄存器技术
把发生页面失效故障时指令的全部现场都保
存下来。在处理完故障并把所需要的页调入主
存后，取出后援寄存器的内容恢复故障点现场，
然后从故障点处继续执行完该条指令。
b)预判技术
执行指令前先预判操作数的首尾字符是否都
已在主存中。如果是，才执行这条指令；否则
就发生页面失效，直到调入该页后才开始执行
这条指令。
c)替换算法
不允许出现指令或操作数跨页存贮的那些页
被轮流从主存中替换出去的“颠簸”现象。因
此，
给某道程序分配的主存页数应该有个下限。
d)页面大小不能过大
以便多道程序的道数、每道程序所分配到的
主存页数都能在一个适当的范围内。如果页面
过大，就会使主存中页数过少，从而出现大量
的页面失效，严重降低虚拟存贮器的访问速率
和等效速度。
2.提高虚拟存贮器等效访问速度的措施
根据 虚拟存贮器等效访问速度公式
TA=HTA1+(1-H)TA2
希望 H提高,TA1, TA2缩短
关于高的主存命中率问题，其影响因素很多，
如地址流、页面调度策略、替换算法、页面大小
及分配给程序的页数 (主存容量 )等。这里主要讨
论怎样缩短访主存的时间。
从虚拟存贮器工作的全过程可以看到，每次访
问主存时，都必须进行内部地址变换 (因为页表都
存在主存中，每次查页表就要增加一次访存。若
采用段页式虚拟存贮器，查表要增加两次访存 )，
其概率是 100%。从缩短访主存的时间来看，关
键就是怎样加快多用户虚地址 NS到主存实地址 np
的变换。只有内部地址变换的速度高到使整个访
主存速度非常接近于不采用虚拟存贮器时的访主
存速度时，虚拟存贮器才能真正实用。如何从逻
辑结构上提高内部地址变换的速度，正是系统结
构设计的任务。
1)快表
由于程序的局部性特点，对页表内各行的使用
不是随机的，在一段时间内实际只用到表中很少
的几行。这样就可以用快速硬件构成比全表小的
多，如 8—16行的部分“目录表”，存放当前正
用
的虚实地址映像关系，那么其相联查找的速度就
会很快。这部分目录表就被称为快表。
?慢表：存放全部虚、实地址映像关系的表。实
质上，快表只是慢表中很小的一部分副本。
2)地址变换
查表时，由虚页号 u＋ Nv’(即 Nv)同时去查快表
和慢表。当在快表中有此虚页号时，就能很快找
到对应的实页号 nv，将其送入主存实地址寄存器，
并立即使慢表的查找作废，这时访存的速度没有
什么降低。如在快表中查不到时，则经过一个访
主存周期后，从慢表中查到的实页号 nv就会送入
主存实地址寄存器。同时将此虚页号和对应的实
页号送入快表。这里也要用到替换算法去替换快
表中应该移掉的内容。如下图：
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np
nv
装入位
nvu Nv’ 快表
(硬件构成 )
8—16行
相联比较
(按内容访问 )
快表中
查不到
慢表 (主存中 )
若查出对应的装入
位为 0发生页面失效
?由 2Nv中选 1(按地址访问 )
经快表与慢表实现内部地址变换
从上图可以看到，如果快表的命中率不高，系
统的效率就会大大下降。若快表采用堆栈型替换
算法，则快表容量越大其命中率就越高。但容量
大，其相联查找的速度就很慢，所以快表的命中
率和查表速度是有矛盾的。一般快表取 8—16行，
每页容量为 1—4K字，则快表容量可以反映主存
中的 8—64K单元。这样的快表命中率不会很低。
这样，快表与慢表实际上就构成了快表 —慢表存
贮层次。概念上等同于主存 —辅存存贮层次。快
表 —慢表存贮层次的替换算法一般也采用 LRU法。
3)减少快表相联比较的位数
在同样的容量下，相联比较的位数越少，相联
查找所花费的时间和设备量就越少。由于快表内
容在一段时间内总是对应于同一个任务或同一个
用户，它们的 u值是不变的。因此可以将参与相
联比较的位数中的 u字段去掉，从而由 Nv (u+Nv’)
位缩短到 Nv’位。需增设用户位来区分不同的任
务，用户位为 0的行，其映像关系无效。任务切
换时，通过硬件将所有用户位全部置 0，即都被
作废。
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np
nv
装入位
nvNv’ 快表
(硬件构成 )
8—16行
相联比较
(按内容访问 )
快表中
查不到
慢表 (主存中 )
若查出对应的装入
位为 0发生页面失效
?由 2Nv中选 1
(按地址访问 )
减少快表的相联比较位数
用户位
4)散列快表
a)思想
快表容量越大，命中率越高，相联比较越费
时，使快表会快不起来。为此可以改用高速的
按地址访问存贮器来构成容量更大的快表，并
用散列 (Hashing)法来实现按内容查找。其思想
是让内容 Nv与存放该内容的地址 A之间建立某
种散列函数关系，即让快表的地址 A=H(Nv)。
当需将虚、实地址 Nv与 nv的映像关系存入快表
存贮器中时，只需将 Nv对应的 nv等内容存入快
表寄存器的 A=H(Nv)单元即可。
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np比较相等
nvNv
散列变换
(硬化实现 )
相等不等
查慢表
快表
(按地址访问 )
经散列实现快表
A
?
b)查找过程
查找时，按现给出的 Nv经同样的散列函数变换
成 A后，按地址 A访问快表寄存器，就可以找到
存放该 Nv所对应的 nv及其余内容。只有硬化实现
散列函数变换才能保证必要的速度。如下图，为
解决多个不同的 Nv可能散列到同一个 A的散列冲
突，在快表中再增加 Nv项，在快表的 A单元中除
了存入当时的 nv，也存入当时的 Nv。这样在地址
变换时用现行 Nv经散列函数求得 A，查到 nv并访
存同时将同行中原保存的 Nv读出与现行 Nv比较。
若相等就继续进行由 nv形成的主存实地址访存；
否则就标明出现了冲突，即 A地址单元中的 nv不
是现行 Nv对应的实页号。就让刚才由 nv形成的主
存实地址进行的访存作废。经过一个主存周期，
用从慢表中读到的 nv再去访存。
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np比较相等
nvNv
散列变换
(硬化实现 )
相等不等
查慢表
快表
(按地址访问 )
?
A
c)改进散列冲突的办法
?在快表的每个地址 A单元中对应存放多个不同
的虚页号与实页号的映像关系，就可以降低由
于散列冲突所引起的不命中率。
?减小散列变换 (压缩 )的入、出位数差，散列冲
突的概率就会降低。
3.影响主存命中率和 CPU效率的某些因素
1)与 Sp有关
如图表示
了页面大小
Sp、分配给
某道程序的
主存容量 S1
与命中率 H的关系。可以看出分配给某道程序的
主存容量 S1一定时,H随 Sp的增大先升高，直到
一个最大值后逐渐降低；增大 S1能普遍提高 H,且
达到最高命中率时 Sp可以再大一些。
页面大小 Sp
命中率
H
1.0
S1
2S1
Sp1 Sp2
2)命中率与主存容量有关
如图实线表
示了堆栈型替换
算法的命中率 H
与 S1的关系。可以
看出开始随 S1的增大 H明显上升。但到一定程度
后,H的提供就逐级趋近于 1而不可能到达 1。当
S1过分增大后，主存空间的利用率可能由于程序
的不活跃部分所占比例增大而下降。实际中要折
衷权衡 Sp和 S1的选择，而不能过分追求 S1。
LRU
FIFO
1
命中率
H
S1
3)主存命中率与所采用的页面调度策略有关
通常大多数虚拟存贮器都采用请求式调度页面
的策略，即只有当页面失效时，才把所需的页调
入主存。针对程序存在局部性特点，可以采取工
作区的调度策略。所谓工作区是指在时间 t之前的
一段时间 Δt内已访问过的页面集合。
4.3 高速缓冲存贮器 (Cache)
高速缓冲存贮器 用以弥补主存速度的不足。
在 CPU与主存 (Main Memory—MM)之间设
置一个高速、小容量的缓冲存贮器 (Cache)，
构成 Cache——主存存贮层次。使之从 CPU
来看，速度是接近于 Cache的，容量却是主
存的。
4.3.1基本结构
1.工作过程
为了便于进行地址的映像和变换，如同虚拟存
贮器中将虚存空间和主存空间机械的分成大小相
同的页一样，在高速缓冲存贮器中把 Cache和主存
机械的分成大小相同的块 (或行 )。每一块由若干个
字 (或字节 )组成。从构成存贮层次的概念和原理上
讲,Cache存贮器中的块和虚拟存贮器中的页具有
相同的地位。只是实际块的大小比页的大小小的
多，一般只是页的几十分之一或几百分之一。
块内地址块号主存地址
主存－ Cache
地址映像变换机构
块内地址块号
Cache
主存Cache
替 换
策 略
Cache
地址
主存地址来自处理机
多字宽
单字宽
去处理机 直接通路
单字宽
访 主 存
替换 Cache
不命中
命中装不
进
可
装
入
访主存
装 入
Cache
图 4.32 Cache 存贮器的基本结构
?
?
?
?
2.特点
1)Cache—主存存贮层次和主存 —辅存存贮层次
原理相同。
2)Cache—主存存贮层次的速度要求高，在构成
与实现及透明性等问题上有自己的特点。
3)Cache存贮器一般采用与 CPU同类型的半导体
工艺构成。
4)Cache—主存间的地址映像和变换，以及替换
与调度算法全部采用专门的硬件来实现。
5)前一地址的访 Cache和后一地址的查表变换在
时间上重叠流水进行。
6)为了更好发挥 Cache的高速性，减小 CPU与
Cache之间的传输延迟，让 Cache在物理位置上
尽量靠近处理机或就放在处理机中而非主存中。
7)除了 Cache到处理机的通路外，在主存和处理
机间还设有直接通路。
8)为加速调块，每没块的容量等于一个主存周
期由主存所能访问的字数，因此在有 Cache存
贮器的主存系统都采用多体交叉存贮器。
9)主存被机器的多个部件共用，应提高 Cache的
访存优先级，一般应高于通道的访存级别。
4.3.2 地址的映像与变换
地址映像：将每个主存块按什么规则或方法装
入 (定位于 )Cache之中。
地址变换：当主存中的块按这种映像方法装入
Cache后，每次访 Cache时怎样将主存地址变
换成对应的 Cache地址。
块冲突：指出现了主存块要进入 Cache中的某块
位置已经被其它的主存块所占用。
1.全相联映像和变换
1)规则：如同虚拟存贮器中那样的全相联映像，
主存中的任意一块均可映像装入到 Cache内的
任意一块的位置。
…
Cache
块位置 0
1
2
2ncb-1
主存
块 0
1
2
2nmb-1
任何主
存块可映
像到任何
Cache块
的位置
……
图 4.33 全相联映像规则
2)地址变换过程
主存块号 块内地址
主存地址
nmnmb nmr
ncb ncr
Cache
块号
Cache地址
nc
nmb ncb
… … 2ncb 目录表
(专门硬件 )
相联比较
查到
查不到Cache
块失效
图 4.34 全相联映像的地址变换过程
3)优缺点
优点：块冲突率低，只有当 Cache中全部装满
后，才有可能出现块冲突。
缺点：要构成容量为 2ncb项的相联存贮器，代
价相对较大，而且目前 Cache的容量已
经大，这样查表速度就难以提高。
2.直接映像及其变换
1)规则：主存中每一块只能映像到 Cache中唯一
一个特定位置，如图所示，主存的第 i块只能映
像到第 i mod2ncb块位置上。
4.1存贮体系的形成与性能
4.2虚拟存贮
4.3高速缓冲存贮器 Cache
4.4主存保护
?本章重点：
段页式和页式虚拟存贮器的原理；页式虚拟存
贮器的地址映像； LRU/FIFO/OPT替换算法进行页
面替换的过程模拟； LRU算法对页地址流的堆栈
处理模拟及性能分析； Cache存贮器的直接和组
相联地址映像； LRU替换算法的硬件实现及替换
过程模拟； Cache存贮器的性能分析等。
?本章难点：
段页式和页式中虚实地址的计算；各种页面替
换算法的模拟和页面命中率的计算； Cache组相
联映像和块替换算法的模拟。
4.1 存贮体系的形成与性能
4.1.1发展存贮体系的必要性
1.存贮器的性能要求
1)大容量
2)高速度
3)低价格
2.容量
SM=W ·l ·m
W：存贮体的字长，单位为 bit或 Byte。
l：每个存贮体的字数。
m：并行工作的存贮体的个数 。
3.速度
从下面三个方面来描述,
1)访问时间 TA
TA是存贮器接到访存到信息被读到数据总线上
所需的时间。是确定 CPU与存贮器时间关系的重
要指标。
2)存贮周期 TM
TM是连续启动一个存贮体所需要的时间间隔。
一般来说总比 TA大。
3)存贮器频宽
是指存贮器可以提供的数据传送率，一般用每
秒钟所传送的信息位数来衡量。
a)最大频宽 BM(极限频宽 )
是存贮器连续访问时能提供的频宽。
单体,BM =W/TM
m体并行工作,BM =mW/TM
b)实际频宽
实际频宽小于最大频宽 BM。
4.价格
可以用总价格 C或每位价格 c来表示。具有 SM
位的存贮器每位价格 c=C/SM。其中包括了存贮
器本身的价格和为该存贮器操作所必须的外围
电路的价格。
5.结论
由于存贮器的价格、速度和容量的要求是矛盾
的，为了同时满足三方面的要求，在一个完整
的存贮体系中，必须采用不同工艺的存贮器，
使得信息以各种方式分布于不同的存贮体。
比如：
主存 当前活跃的信息，快，少
辅存 暂时不用的信息，慢，多
虚存 swap
从速度来说，主存远远跟不上 CPU的要求，为
了弥补这一差距，特引入并行和重叠技术，构
成并行主存系统，但这种并行主存的方法提高
频宽是有限的，因此还需从系统结构入手，发
展存贮体系。
4.1.2并行主存系统频宽的分析
1.类型
1)单体单字
存贮器字长 W与 CPU字长 W
相同,一次访问一个存贮器
字,主存最大频宽 BM =W/TM
W位
读出寄存器
地址寄存器
单体单字存贮器
l
2)单体多字
存贮器字长等于 m个
CPU字,BM =mW/TM
W位W位 W位 W位
地址寄存器
单体多字 (m=4)存贮器
W位
单字长寄存器
3)多体单字交叉
总线控制
地址寄存器 0 地址寄存器 1 地址寄存器 2 地址寄存器 3
M0 M1 M2 M3
主控 (主存控制部件 )
CPU IOP
…… …… …… ……
多体 (m=4)交叉存贮器
a)存贮器字长等于 m个 CPU字,BM =mW/TM。实际
频宽大于单体多字。
?单体多字：并行读出的 m个字要地址顺序的存
在于同一主存单元。
?多体单字,m个 CPU字地址不必顺序存放，只
要不发生冲突。
b)编址模式
Mj体的编制模式为,m ·i+j；
其中 I=0,1,···,l-1，表示第 i个字；
j=0,1,···,m-1，表示第 j个分体；
m—模 单体多字：一个主存包含的 CPU字数
多体单字：分体体数
模体 地址编址序列 二进制地址码末二位状态
M0
M1
M2
M
3
0,4,8,12,···,4i+0,···
1,5,9,13,···,4i+1,···
2,6,10,14,···,4i+2,···
3,7,11,15,···,4i+3,···
00
01
10
11
地址的模 4低位交叉编址
4)多体多字交叉
多个存贮体，每个存贮体有 CPU字。
上述能并行读出多个 CPU字的单体多字和多体
单字或多体多字的交叉存贮主存系统统称为并行
主存系统。
2.分析
提高 m值，可以提高主存系统的最大频率，但
并不能线性提高实际频率。
原因：
1)模 m越高，存贮器数据总线越长，导致传输
延迟增加；
2)系统效率问题，对于顺序取指，效率可以
提高 m倍，但遇到转移指令，效率就会下降。
3.模型分析
对于 m个独立分体的主存系统，处理机发出一
串地址为 A1,A2,… Aq的访存申请队，在每个主
存周期到来前，申请队被扫描，截取从队头起
的 A1,A2,… Ak的申请序列。申请序列是个在要
求访存申请的 k个地址中，没有两个或两个以上
的地址处于同一分体中的最长序列。显然 k表示
可以同时访问的分体个数的随机变量，不大于 m，
系统效率取决于 k的均值 B，其值越大，可访问
的分体个数越多，系统效率越高。
1)数学模型
设 p(k)表示申请序列长度为 k的概率密度函数，
其中 k=1,2,… m。则 k的均值 B为
B=∑k ?p(k)
B实际就是每个主存周期所访问的平均字数。而
p(k)与程序的状态密切相关，特别是指令转移概
率 p，它定义为给定下条指令地址为非顺序地址
的概率。因此
p(k)=(1-p)k-1?p,1≤k<m —几何概率
p(m)=(1-p)m-1
k=1
m
所以,B=∑k ?p(k)=1?p+2?(1-p)?p
+ +m?(1-p)m-1
=(1-(1-p)m)/p
2)讨论：
a)若每条指令都是转移指令且转移成功，即
p=1,则 B=1，就是并行多体交叉存取的实际频宽
降到和单体单字一样；
b)若所有指令都不转移，即 p=0，则 B=m，此时
多体交叉存贮的效率最高。
k=1
m
…
3)结论
由于程序的转移概率不会很低，数据分布的离
散性较大，所以单纯靠增大 m来提高并行主存系
统的频宽是有限的，而且性价比还会随 m的增大
而下降。如果采用并行主存系统仍不能满足速度
上的要求，就必须从系统结构上改进，采用存贮
体系。
4.1.3存贮体系的形成与分支
1.容量需求
1)程序覆盖技术
方法：将大程序分块，
确定在辅存中的位置并放入辅存，然后根据要
求把当前用到的程序和数据调入主存中指定位
置以覆盖或替换那些已在主存但现在不用的段。
这只构成一个存贮系统而非存贮体系。主辅存
间的调入调出完全由程序员安排，增大编程难
度和负担，拉长程序运行时间，也难以使用更
好的算法。
主存 辅存
程序员
2)增设辅助软硬件
随着 I/O处理
机的出现及多道
程序的发展，一道
程序的运行可以与
另一道程序的调入调出同时进行。因此主辅存间
的地址定位可以改由辅助软硬件来完成，如图。
这样就构成了存贮体系，或存贮层次。
主存 辅存
辅助软硬设备
从整体来看，
速度是主存的
容量是辅存的
主存 —辅存存贮层次
如果存贮层次能以接近于辅存的每位价格构成
等于辅存容量的快速主存，存贮系统的性价比就
会大大提高。进一步完善发展就形成虚拟存贮系
统。这样程序员就可以用机器指令的地址码对整
个程序统一编址，这一空间远大于实际主存空间。
这种指令地址码称为虚地址、逻辑地址、程序地
址等，其对应的存贮容量称为虚存容量或程序空
间；而实际主存的地址称为物理地址、实 (存 )地
址，其对应的存贮容量称为主存容量、实存容量
或实 (主 )存空间
由于程序空间远大于主存空间，特别多道程序，
每个用户只用到主存空间的一部分，不能将程序
全部装入主存，只能把程序空间分成较小的块或
页，由系统负责把所需块或页按需调入主存。当
用虚地址访问主存时，首先检查其对应的内容是
否已在主存。若在，就由硬件自动把虚地址变换
成实地址去访存；否则需经辅助软硬件将包含所
要访问的单元在内的那一块程序由虚存调入主存，
然后进行访问。这样，不论是虚实地址的变换还
是程序的调入都不必程序员安排，而是透明的。
也正符合存贮层次的要求。
2.速度需求
由于主存和 CPU的速度差距已达一个数量级，
为了解决这一问题，提出了多种办法：
1)在 CPU中设置通用寄存器 (GR)，让运算直接在
CPU的 GR中进行，减少与主存的交往。但主存
与 GR间的传送要由程序设计者安排，且 GR的数
目不能过多。
2)采用存贮器的多体交叉并行存取来提高主存
的速度。但这种方法对速度的改善有限，且有
可能使性价比下降。
3)Cache—主存存贮层次
通过在 CPU与主存间加一级速度高、容量小、每
个价格较高的高速缓冲存贮器 (Cache)，借助于
硬件是 Cache和主存构成一个整体。信息在 Cache
与主存间的传送全部由硬件完成，所以 Cache对
应用程序员和系统程序员都是透明的。
高速缓冲
Cache
主 存
M
辅助硬件
CPU
从 CPU来看，
速度是 Cache的
容量是主存的
4)多级存贮层次
从 M1到 Mn，速度变慢，容量增大，价格降低。
CPU M1 M2 M3 Mn
从 CPU来看，
速度是 M1的，
容量是 Mn的，
价格 是 Mn的
程序局部性概念：
a)时间局部性：在最近的未来要用到的信息很
可能是现在正在使用的信息，这是由程序循环造
成的，即循环中的语句要被重复执行。
b)空间局部性：在最近的未来要用到的信息很
可能与现在正在使用的信息在程序空间上相邻或
相近，这是由于指令通常是顺序执行的。
利用程序局部性，可以预知下一步要访问的
程序块而在 M1中做好准备。
时间局部性：存放近期使用过的块或页。
空间局部性：从 M2级把访问字所在页或块一同取
到 M1中。
4.1.4存贮体系的性能参数
以如图所示的二级体系 (M1,M2)为例来分析
1.存贮体系的每位
平均价格 c
c1 ? SM1 +c2? SM2
SM1 +SM2
1)M2容量大且便宜,所以,SM1<< SM2，使 c接
近于 c2。
2) 应使辅助软硬件的价格占很小比例。
M1 M2
c1,SM1,TA1 c2,SM2,TA2
c,SM,TA
c=
2.命中率 H
CPU产生的逻辑地址能 M1在中访问到 (命中 )的
概率。
R1表示能在 M1中访问到的次数；
R2表示当时在 M2中还未调到 M1的次数。
失效率 (不命中率 ),1-H
R1
R1 + R2H=
3.等效访问时间
TA=HTA1+(1-H)TA2
TA TA1越好，即访问效率 e=TA1/TA 1越好。
相邻两级的访问时间比 r=TA2/TA1，则：
e= TA1/TA= TA1/(HTA1+(1-H)TA2)
=1/(H+(1-H)r)
由上式知，要是 e趋近 1,r越大要求 H越高。 H提
高不易，采用其它方法：
a)减小相邻两级的访问速度差距
b)减小相邻两级存贮器的容量差
4.2 虚拟存贮器
虚拟存贮器是主存 —辅存存贮层次的发展和完
善，主要为了克服高速主存容量满足不了要求而
提出的。在虚拟存贮器中，应用程序员直接用机
器指令的地址码对程序统一编址，这一地址码宽
度对应的程序空间比实际主存空间大的多，就好
像对应用程序员来说有一个比实际主存大得多的，
可以放得下整个程序得虚 (主 )存空间。程序不必
作任何修改就可以以接近于实际主存的速度在虚
拟存贮器上运行。
4.2.1不同的虚拟存贮管理方式
程序定位：
由于 CPU只能执行已装入主存的程序块，为了
提高主存空间的利用率，应及时释放主存中现已
不用的空间以装入别的程序块。随着程序的运行，
程序的各个部分就会在主存和辅存间来回调进调
出。当辅存中的程序调入主存时，必须进行程序
在主存中的定位。这种定位应该由系统提供的定
位机构来自动完成，从而对应用程序员透明。
虚拟存贮器程序定位的实现,
虚拟存贮器通过地址映像表来实现程序在主存
中的定位。其思想是把程序分割成若干较小的段
或页，用相应的映像表机构来指明该程序的某段
或页是否已装入主存。若已装入，则同时指明其
在主存中所处的开始位置；否则去辅存中调段或
页，并建立起程序空间和主存空间的地址映像关
系。这样，程序执行时通过查映像表将程序虚地
址变换成实际主存地址再访主存。
1.段式管理
1)思想
根据程序的模块性，把一个复杂的大程序分解
成多个逻辑上相对独立的模块。模块可以是主程
序、子程序或过程，也可以是表格、数组、树、
向量等某类数据元素的集合。其大小可以不同，
甚至事先无法确定。每个模块都是一个单独的程
序段，都以该段的起点为 0相对编址。调入主存
时，系统按照基址 (该段程序在主存中的起始地
址 )和每个单元在段内的相对位移组合来形成各
单元在主存的实际地址。这种按段分配的存贮管
理方式称为段式管理。
0段
1段
2段
3段
4段
5段
6段
A道程序的
程序空间
断表长度 断表基地址
断表基址寄存器
(主存中最多有 N道道程序 )
01
23
45
6
0
5k
1k
0
0
0
0
1
1
1
1k
3k
2k
访问方式段长装入位地址段名 (号 )
a
01
A
N-1
0
1k-10
0
0
0
0
0
2k-1
2k-1
2k-1
1k-1
4k-1
3k-1
a7
…
…
…
…
实主存空间
1k
2k
3k
0段
4段
2段
1k0k
5k
2.5k
段内位移段号基号 (程序号 )
多用户虚地址 A 4 1.5k?
?
?
+
??
?
+
已装入
段式管理的定位映像机构及其地址的变换过程
A道程序
的段表
2)断表
为了进行段式管理，每道程序都由一个断表 (映
像表 )，用以存放该程序各程序段装入主存的状
况信息。
段名 (号 ):实际由于段号与行对应，省略掉。
装入位,表征是 (1)否 (0)已调入主存。
地址,调入主存时，在主存的起始 (绝对 )地址。
段长,段的大小，限制偏移越界。
访问方式,只读、可写、只执行，提供访问保护。
3)断表基址寄存器
断表长度,该道程序的断数 (断表行数 )。
断表基地址,程序的断表在主存中的起始地址。
4)虚拟地址
基号 (程序号 ):断表在断表基址寄存器的位置。
段号,段在断表中的位置。
段内位移,所访问单元在段内的偏移。
5)地址变换
如上图所示。
6)优点
a)能使大程序分模块编制，便于多程序员并行
编程，缩短编制时间。且各段的修改增添方便。
b)便于多道程序共用已在主存的程序和数据。
c)有利于以段为单位实现存贮保护，这对发现
程序设计错误和非法使用是有用的。
7)实主存管理表
为了高效的为调入段分配主存区域,OS为整个
主存建立一个实主存管理表，来标明主存的使
用情况。
a)占用区域表
用来指明主存中的哪些区域被哪道程序的哪
个段占用以及该段程序在主存的起点和长度。
b)可用区域表
用来指明未被占用的区域的基地址和大小。
8)可用区域分配算法
由于各段的长度不等，必须采用不同的算法
对主存可用区域进行分配。
a)首先分配算法
顺序扫描可用区域表，当找到第一个不小于
要调入段长度的可用区域时就立即进行分配 。
优点是分配速度快，由于首先分配主存低区，
造成可用区零头数少，而且容易在主存高区保
留较大空间以备容纳大程序段。
b)最佳分配算法
先全部扫描可用区域表，然后寻找一个可用
区域进行分配，使之分配后段间可用区零头最
小。这一算法虽然考虑了尽量减小每一个段间
可用区的零头，但是会使段间可用区零头数较
多。
如下例：
A
B
C
A A
B B
C C
D
E
F
D
E
F D
E
0 0 0
0.5k 0.5k 0.5k
3k 3k 3k
7k 7k 7k
8k 8k 8k
10k 10k 10k
4k
1k
2.5k
2k
6.5k
5.5k
9k
主存
程序
主存 主存
(a)需依次调入 D,E,F段 (b)首先分配法D,E,F全被装入 (c)最佳分配法F段无法装入
段式存贮分配算法
2.页式管理
1)段式管理的缺点
a)各程序段装入主存的起点是任意的，断表中
的地址字段必须能够表示出主存中的任意一个
绝对地址。
b)各段长度受程序本身影响也是任意的，所以
地址字段和段长字段都很长。
c)容易产生较大的段间零头浪费。如下所示,
00
11
22
3
4
5
6
7
0
4k-1
32k-1
4k
4k
4k
主存页号 虚存页号主存空间
D道程序
程序空间
程序标志号
D
基号 虚页号 页内位移
?
?
实页号 页内位移
b
nv nrnp
Nv’ Nr
专用
位
访问
方式
装入
位
主存
起点
0
1
2
1
1
1
2
6
7
虚存
页号
(实页号 )(可省略 )
D道程序页表
b
采用页式存贮后 D道程序可装入
2)页式管理思想
把主存空间和程序空间都机械的等分成固定大
小的页 (页面大小因机器而已，一般在 512到几 kB)
然后按页顺序编号。
3)主存单元地址 np
实页号 nv,主存中实际划分的页。
页内位移 nr,单元在主存页内的偏移量。
4)虚地址
虚页号 Nv’：程序空间中划分的页。
页内位移 Nr：等于 nr,页大小相同。
页内位移用户虚页号用户标志 u
多用户虚页号 Nv
某道程序的地址 Ni
Nv’ NrX
多用户
虚地址 Ns ? ? ?
由 u转换成基号 b
页表基址寄存器
0
b
N-1
X ?
…
…
查
到
查不到 +
指
向
道
程
序
页
表
X
页内位移
实页号
nrnv np
实页号 装入位
nv 1
X
? ?
主存地址寄存器
已装入
主 存
X道
程序
的内
页表
Y道
程序
的内
页表
页式管理的定位映像机构
及其地址的变换过程
5)页表
保存虚页装入实页时的页面对应关系。
虚页号,与页表行号相同，可以省略。
实页号,主存起点 。
装入位,标志该页是否装入主存 。
访问方式,用于存贮保护。
专用位,区分该页是独占或共享 。
?用户标志 u:指明程序所使用的页表基址寄存器。
?页表寄存器,存放页表在主存中的地址。
6)地址变换
如上图。
3.段页式管理
页式对应用程序员完全透明，所需映像表硬件
少，地址变换速度快，调入操作简单等都优于段
式。页式虽然不能完全消除主存可用区的零头浪
费，因为程序大小不可能恰好是页面大小的整数
倍，产生的零头无法利用，但页内零头比段式的
小的多，所以在空间利用率上页式优于段式的。
因此很少使用纯粹的段式管理存贮器。
然而，段式本身也具有页式所没有的优点，如：
段式中每个段独立，有利于程序员灵活实现段的
链接、段的扩大 /缩小和修改，而不影响其它段；
每段只包含一种类型的对象，若过程或是数组、
堆栈、标量等的集合，易于针对其特定类型实现
保护；把共享的程序或数据单独构成一个段，易
于实现多用户、进程对共用段的管理等。因此，
为了取长补短，提出了把段式和页式相结合的段
页式存贮和管理。
1)思想
把内存机械的等分成固定大小的页，把程序按
模块分段，每个段分成与主存页面大小相同的页，
每道程序通过一个断表和相应于每段的一组页表
来进行定位。
2)段表
装入位,标识该段的页表是否已装入主存。
地址字段,指明已装入页表在主存中的起始地址。
访问方式,指明该段的控制保护信息。
段长,指明该段页表的行数。
3)页 表
装入位,指明此段该页是否已装入主存。
地址字段,装入页在主存中的页号。
段页式与纯段式的主要区别是：段的起点不
再是因程序段的大小而任意的，必须是位于主存
中页面的起点。
对于多道程序来说，每道程序都需要有一个
用户标志号 u(转换成基号 b)来指明该道程序的段
表起点存放在哪个基址寄存器中。
页内位移 d页号 p段号 s用户标志 u
程序标志 用户虚页号 Nv’
某道程序的地址 Ni
多用户
虚地址 NS
由 u转换成基号 b
? ? ? ?
段表基址寄存器
段表长度 段表起点 c
0
b
N-1
?
查不到
查
到
+
装入
位
页表
起点
访问
方式
段长
1 d1? ? 某用户 段表
主存 (多用户段表 )
c
实页号 装入位
主存 (多用户页表 )
1nv ? ?
d1
+
页内位移 nrnv
实页号
已装入
主存
地址 np
某用户
s段
的页表
段页式管理的定位映像机构
及其地址变换过程
4)多级页表
在虚拟存贮器中每访问一次主存都要进行一次
程序地址向实主存地址的转换，段页式的主要问
题就是这个地址变换至少要两次查表，即查段表
和页表。为了提高虚拟存贮器的速度，必须采取
措施加快这种地址转换查表速度。这一问题页式
管理同样存在，因为前面所讲的查页表是基于整
个页表连续存贮的，而当页表的大小超过一个页
面大小时，页表就会分存于主存中不连续的页面
上。这样前述由页表起点加页号查得该页在页表
中的行的查表方式就会出错。
例如：若程序虚地址为 24位，其中页内地址 Nr
为 10位，即
则页表就需要 214行，而页面大小只有 210行。所
以页表本身可能要分存于 16个页面。为此要建立
多级页表，用页表基址寄存器指明第一级页表的
基址，用第一级页表中各行的地址字段指明第二
级各个页表的基址，依此类推。为了节省存放映
像表的主存空间，通常只把第一级页表驻留在主
存内，其它各级页表则根据需要才调入，大部分
放在辅存中。
程序虚地址 Nr(10位 )Nv’(14位 )
4.2.2页式虚拟存贮器的构成
1.地址的映像和变换
多用户虚页号 Nv
指令中访存地址 Ni
u NrNv’
nrnv
多用户
虚地址 NS
实存地址 np
实存空间
2nv页
2nr 2Nr =2nr
…
… …
2Nv页包
括 2u个
用户，
每个用
户 2Nv’页
虚存总空间
虚实地址对应关系及空间的压缩
页式虚拟存贮器是采用页式管理的主存 —辅存
存贮层次。把主存空间和程序空间都等分成页，
让程序起点处于页的起点上。程序员用地址码 Ni
来编程，所以 Ni由用户虚页号 Nv’和页内地址 Nr组
成。主存地址分实页号 nv和页内地址 nr两部分，
且 nr与 Nr一样。大多数虚拟存贮器中每个用户的
程序空间比实际主存空间大得多，即一般 Nv’大于
nv。这样，虚拟存贮器系统总的多用户虚地址 NS
就由用户标志 u、用户的虚页号 Nv’及页内地址 Nr
3部分构成，则总的虚存空间为 2u?2Nv’页。
现在把 u和 Nv’合并成多用户虚页号 Nv，则 2Nv远
远大于 2nv。主存中最多能放 N道程序，即 N个用户，
其它放在辅存。因此就出现了如何把大的多用户
虚存空间压缩装入到小的主存空间中的问题，而
在程序运行时又要考虑如何把多用户虚地址 NS变
换成主存地址 np，再让 CPU去访问主存中该单元。
这就是地址的映像和变换。
1)地址映像
就是将每个虚存单元按某种规则 (算法 )装入 (定
位于 )实存，即建立多用户虚地址 NS与实存地址 np
的对应关系。对于页式就是将多用户虚页号 Nv的
页可以装入主存中的哪些页面位置，建立 Nv与 nv
的对应关系。
2)地址变换
指的是程序按这种映像关系装入实存后，在执
行时多用户虚地址 NS如何变换成对应的实地址 np。
对页式而言就是多用户虚页号 Nv如何变换成实页
号 nv。
3)页面争用
由于是把大的虚存空间压缩到小的主存空间中
去，主存中的一个页面位置就必须能与多个虚页
相对应，能对应多少个虚页与采用的映像方式有
关。这就不可避免的发生有两个以上的虚页想要
进入同一个主存页面的现象，这种现象就是页面
争用或实页冲突。一旦发生页面争用，只能装入
其中的一个虚页，其它的虚页只有等到该页推出
主存后方可装入，这就会使执行效率下降。
4)映像方式的选择
a)尽量减少页面争用概率；
b)考虑减少辅助硬件，降低成本；
c)有利于实现；
d)地址变换的速度快。
5)全相联映像
a)方法
让每道程序的任何虚页可以映像装入到主存
的任何实页位置。只有一个任务要求同时调入
主存的页数超出 2nv (很少有 )时 才会发生页面争
用。因此全相联的实页冲突概率很低。
主 存
虚 存
页面位置 0
1
2
2nv-1
…
页 0
1
2
2Nv’-1
… …
nv nr
NrNv’
np
Ni
每道
程序任
何虚页可
映像到任
何实页
位置
全相联映像
b)页表利用率
整个多用户虚存空间有 2u个用户 (程序 )，但
主存最多只对其中的 N个用户 (N道程序 )开放。
由基号 b标识的 N道程序中的每一道都有一个最
大行为 2Nv’的页表，而主存总共只有 2nv个实页位
置, 因此 N道程序页表的全部行 N?2Nv’中，装入位
为 1的最多只有 2nv行。由于 N?2Nv’>>2nv，使得页表
中绝大部分行中实页号 nv字段及其它字段都不
再有用了，这就会大大降低页表的空间利用率。
c)解决办法
?将页表中装入位为 0的行用实页号 nv字段存放
该程序此虚页在辅存中的实地址，以便调页时
实现用户虚页号到辅存实地址的变换。
?相联目录表法,把页表压缩成只存放已装入主
存的那些虚页 (用基号 b和 Nv’标识 )与实页位置
(nv)的对应关系。这样该表最多为 2nv行，简称
为目录表法，采用按内容访问的相联存贮器构
成。如下图：
基号 用户虚页号 页内位移
某用户虚地址
基号＋用户
虚页号
实页号 其它
信息
目录表 (存在相联存贮器中 )
相联比较
查找到
目录表法
Nv’b Nr
nv
nv
nr(Nr) np
b+Nv’
2nv行
d)相联存贮器
在一个存贮周期内能将给定的 Nv同时与目录表
的全部 2nv个单元对应的虚页号字段内容比较进行
相联查找。如有相符的即相联查找到时，表示此
虚页已装入主存，该单元存放的实页号 nv就是此
虚页所存放的实页位置，将其读出拼接上 Nr就可
形成访存实地址 np；如无相符的即相联查找不到，
表示此虚页未装入主存，发生页面失效，请求从
辅存中调页。由此可见，采用目录表法不用设置
装入位了。
6)虚页的调入
当发生页面失效时，要想把该道程序的虚页
调入主存，必须给出该页在辅存中的实际地址。
为了提高调页效率，辅存一般是按信息块编址
的，且块的大小等于页面大小。以磁盘为例，
辅存实 (块 )地址格式 Nvd为：
这样就需要将多用户虚页号 Nv变换成辅存实
地址 Nvd 。
磁盘号 柱面号 磁头号 块 号Nvd
?外页表,存放用户虚页号 Nv’与辅存实地址 Nvd的
映像关系，用于外部地址变换。
?内页表,存放用户虚页号 Nv’与主存实页号 nv的映
像关系，用于内部地址变换。
由于虚拟存贮器的页面失效率很低，很少调用
外页表进行地址变换，因此外页表存放在辅存中，
当某道程序初始运行时，才把外页表的内容转录
到已建立内页表的实页号地址字段中，这也是前
述当内页表装入位为 0时让实页号地址字段改放
该虚页在辅存中的实地址的原因。而且对外页表
速度要求低，可以用软件实现。如下图：
磁盘号 柱面号 磁头号 块号Nvd
多用户虚地址
辅存地址
NrNS u Nv’
Nvd1
装入位 辅存实地址
地址变换
(软件实现 )
? ?
已装入
外页表
虚地址到辅存实地址的变换
2Nv’
2.替换算法
1)解决问题
当处理机要用到的指令或数据不在主存中时，
就会产生页面失效，应去辅存中将包含该指令
或数据的一页调入主存。由于虚存空间比主存
空间大得多，必然会出现主存页面位置已全被
占用后又发生页面失效，这时再将辅存中的一
页调入主存时就发生页面争用。只用强制腾出
主存中某页后才能接纳从辅存调来的新页。具
体选择主存中哪一页作为被替换的页，就是替
换算法要解决的问题。
2)原则
a)有高的主存命中率
b)算法便于实现
c)辅助软、硬件成本尽量低
3)常用算法
a)随机算法 (Random,RAND)
用软的或硬的随机数产生器来形成主存中要
被替换页的页号。这种算法简单，易于实现，
但没有利用主存使用情况的历史信息，反映不
了程序的局部性，使主存命中率低，很少采用。
b)先进先出算法 (First In First Out,FIFO)
选择最早装入的页作为被替换的页。这种算法
实现方便，虽然利用了主存使用情况的历史信息，
但是不一定能正确反映出程序的局部性，因为最
先进入的页很可能是现在经常要用到的页 。
实页号 占用位 程序号 段页号
计数器
(使用位 ) 程序优先位 HS 其它信息
0
1
2nv-1
……
主存页面表
c)近期最少使用算法 (Least Recently Used,LRU)
选择近期最少访问的页作为被替换的页。这种
算法能比较正确的反映程序的局部性，因为当前
最少使用的页一般来说未来也将很少访问，但完
全按此算法实现比较困难，需要为每个实页都配
置一个字长很长的计数器字段才行。所以一般采
用它的变形，即近期最久没被访问过的页作为被
替换的页。这样把, 多, 和, 少, 简化成, 有,
和, 无,
之后，实现起来比较方便。
?主存页面表
OS为实现主存管理而设置的，是对主存而言
的，整个主存只有一个。每一行用来记录主存中
各页的使用状况。而页表是对程序空间而言的，
每道程序都有一个，是用来存贮地址映像关系和
实现地址变换的。
实页号,主存页号是顺序的，可以省略
占用位,表示该主存页面是否被占用
程序号 /段页号,该主存页被哪道程序的哪段
哪页占用
使用位,表示该主存页近期是否被使用过
开始时所有页的使用位全为, 0”，只要某个页
的
任何单元被访问过，硬件就自动将该页使用位置
,1”。由于采用全相联映像，调入页可进入对应
于主存页面表中任何占用位为, 0”的实页位置，
一旦装入主存某实页上，就置该实页的占用位为
,1”。只有当所有占用位都是 1且又发生页面失
效
时才有页面替换问题，这时就要用到使用位，只
需替换使用位为, 0”的页即可。
?使用位全, 1,处理
一种办法是由硬件强制全部使用位都为,0”。
从概念上看，近期最少使用的“期”是从上次
使用
位全 0到这次使用位全 0的这段时间。由于这个期
的长短是随机的，所以称为随机期法。
另一种办法是它定期的置全部使用位为,0”。
由“未用过计数器” HS(或称为历史位 )，定期地
每
隔 Δ t扫视使用位, 对使用位为 0的页，则加 1Hs，
并让使用位继续为 0；对使用位为 1的页，则置
0Hs，同时置 0使用位。扫描结束所有使用位为 0，
Hs大的就是最久未访问过的，作为替换页。
d)优化替换算法 (OPT)
?定义
无论是“近期最少使用”还是“近期最久未用
过”
都属于 LRU，与 FIFO类似，都是根据页面使用
的历史情况来预估未来的页面使用状况，只是
比 FIFO更好反映局部性而已。然而，这种“近
期”毕竟是过去了的近期，如果能根据未来实
际使用情况，替换出近期不用的页，主存命中
率会更高，这就是优化替换算法 (Optimal
Replacement Algorithm,OPT)
?方法
在时刻 t找出主存中每个页面将要用到的时刻 ti，
然后选择 ti－ t最大的那一页作为被替换的页。显
然，这只有让程序运行一遍得到实际的页地址流，
才能找到为实现这种替换算法所需要的各页使用
信息，这是不现实的。所以，优化替换算法只是
一种理想化的算法，它可以被用作评价其它替换
算法好坏的标准，看看哪种替换算法能使主存的
命中率接近于优化替换算法。
4)影响命命中率的因素
a)与替换算法有关
例：设有一道程序，有 1至 5共 5页，执行时的
页地址流 (即执行时依次使用到的程序页页号 )
为：
2,3,2,1,5,2,4,5,3,2,5,2
若分配给该道程序的主存有 3页，如下图表示
分别用 FIFO,LRU,OPT3种替换算法对这 3页的使
用和替换过程。 FIFO的命中率最低，而 LRU的
接近于 OPT的。
2*
3
1
2
3
2
3
命中
2
调进 调进 调进
5
3*
1
替换
5
2
1*
替换
5*
2
4
替换
5*
2
4
命中
3
2*
4
替换
3
2*
4
命中
3
5
4*
替换
3*
5
2
替换
FIFO
命中 3次
2
3
2
3
命中
2
调进 调进
2
3
2
3
命中
2
调进 调进
LRU
命中 5次
OPT
命中 6次
页地址流 2 3 2 1 5 2 4 5 3 2 5 2
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
2
3*
1
调进
2*
5
1
替换
2
5
1*
命中
2
5*
4
替换
2*
5
4
命中
3
5
4*
替换
3
5*
2
替换
3*
5
2
命中
3*
5
2
命中
2
3
1*
调进
2
3*
5
替换
2*
3
5
命中
4*
3
5
替换
4*
3
5
命中
4*
3
5
命中
2
3*
5
替换
2
3
5
命中
2
3
5
命中
3种替换算法对同一页地址流的替换过程
b)命中率与页地址流有关
例如一个循环程序，当所需页数大于分配给
它的主存页数时，无论是 FIFO还是 LRU算法的
命中率都明显低于 OPT的。如下图所示,LRU
和 FIFO一次都没有命中，因为它恰好总是将马
上要用到的页面给替换出去了，从而连续不断
的出现页面失效，产生所谓的颠簸现象。
1*
2
3
2
2
1 4
2*
3
4
1
3*
4*
1
2
3
1*
2
3
4
2*
FIFO
无命中
1
2
1
1
2
1
LRU
无命中
OPT
命中 3次
页地址流 1 2 3 4 1 2 3 4
时间 t 1 2 3 4 5 6 7 8
1
2*
4
1
3
4*
1
2
3*
1*
2
4
命中 命中
1
3*
4
命中
命中率与页地址流有关
1
2
4*
1*
2
3
4
2*
3
4
1
3*
4*
1
2
3
1*
2
3
4
2*
c)与主存容量 (即分配给程序的主存页数 )有关
一般来说，分配给程序的主存页数越多，虚
页装入主存的机会就越多，命中率也可能就越
高。但具体还与所采用的替换算法有很大关系。
如下图所示，当分配给程序的主存页数 n由 3增
加到 4时,FIFO的命中率反而由 3/12降到 2/12;
而 LRU的命中率却不会发生这种情况，随着分
配给该道程序的主存页数的增加，命中率一般
都会得到提高，至少不会降低。
1
2
1*
2
1 4
1
3*
4*
1
2
5
1*
2
5
1*
2
命中
5
1*
2
命中
5
3
2*
5*
3
4
5*
3
4
命中
n=3
命中 3次
1
2
1
2
1
n=4
命中 2次
页地址流 1 2 3 4 1 2 5 1 2 3 4 5
时间 t 1 2 3 4 5 6 7 8 9 10 11 12
1*
2
3
命中
3
4
2*
3
3
4
1*
2
3
4
命中
1*
2
3
4
5
2*
3
4
5
1
3*
4
5
1
2
4*
5*
1
2
3
4
1*
2
3
4
5
2*
3
FIFO法的实页数增加，命中率反而有可能下降
5)堆栈型替换算法
a)定义
A：长度为 L的任意一个页面地址流
t,已处理过 t－ 1个页面的时间点
n：分配给该地址流的主存页面数
Bt(n)：在 t时间点、在 n页的主存中的页面集合
Lt：到 t时刻已遇到的地址流中相异页的页数
若 n< Lt时,Bt(n＋ 1) ?Bt(n)
n>= Lt时,Bt(n＋ 1) = Bt(n) 成立，则此替
换算法属于堆栈型的替换算法。
b)优点
?命中率随主存页数的增加只可能提高，至少不
会下降。
?只需采用堆栈处理技术对地址流模拟处理一次，
即可同时获得对此地址流在不同主存页数时的
命中率，大大节省存贮体系设计的工作量。
?对页地址流 A在 t时刻的 At页是否命中，只需看
St-1(主存在 t-1时刻的堆栈 )的前 n项是否有 At，
若有则命中。
c)LRU算法
属于堆栈型算法，把刚访问过的页面至于栈
顶，而把最久未被访问过的页面置于栈底。命
中率随着分配给该道程序的主存页数 n的增加
而单调上升，至少不会下降，这是堆栈型算法
具有的共同特点。
d)FIFO算法
非堆栈型算法，命中率总趋势是会随着主存
页数 n的增加而提高，但从某个局部来看，主
存页数 n的增加有时反倒可能降低其命中率。
5)页面失效频率法 (PFF)
由于堆栈型替换算法具有随分配给该道程序的实
页数 n的增加，命中率 H会单调上升的特点，所以可
对 LRU算法加以改进和发展：根据各道程序运行中
的主存页面失效率的高低，由 OS来动态调节分配给
每道程序的实页数。当主存页面失效率超过某个限
值时就自动增加给该道程序的主存页数来提高其命
中率；而当主存页面失效率低于某个限值时就自动
减少分配给该道程序的主存页数，以便释放出这部
分主存页面位置给其它程序用，从而使整个系统总
的主存命中率和主存利用率得到提高。
3.虚拟存贮器工作的全过程
具体过程见下页图：
Nvd 辅存实地址
外部地址变换
虚地址 =>辅存实地址
用户标志 u 虚页号 Nv’ Nr
6
多用户
虚地址 NS
内部地址变换
虚页号 =>主存实页号
nv nr np
5
2
1
2
页面 0
2nv-1
…
2nr
个字
2nv个页
3
3
2
是否在
主存？
“是,
(访主存 )
“否,
(主存页
面失效 )
4
5
主存 (页式 )2np个字
是否在
辅存？8
6
“否”
(辅存页
面失效 )
“是”
(访辅存 )
主存页面表9
6
页面替
换算法
11
12
已满未满
10
I/O处理机
13
主存
页号
页面 0
页面 0
1
1
2Nv’-1
…
…
(
选
页)
7
14
调
入
页
7
14替换页
被替换页退回
若未被修改则不必退回
辅存
2NS个字
4.2.3页式虚拟存贮器实现中的问题
1.页面失效处理
1)原因
页面的划分只是机械的对程序空间和主存空间
进行等分，与程序的逻辑结构毫无关系。这样，
对于按字节编址的存贮器就有可能出现一条指令
横跨在两页上存贮的情况。同理，也会出现一个
操作数跨在两页上存贮。另外，采用间接寻址，
特别是多重间接寻址时，在寻址的过程中，可能
出现跨页、甚至连续跨多个页访问的情况。每当
当前一页已在主存而跨页存放的另一页不在主存
时，就会发生页面失效。
2)解决方法
由于页面失效可能出现于取指、取操作数、间接
寻址等过程中，即会在一条指令的分析或执行中发
生。通常的中断都是依靠在每条指令执行的末尾去
设置一个访中断微操作，来检查系统中有无未屏蔽
的中断请求，以便对其进行响应和处理。而页面失
效不能采用这种办法，否则由于未能对页面失效进
行处理，就不可能调页，也就无法执行到访中断微
操作，从而就不可能对页面失效进行响应和处理，
机器的工作就被停顿下来。所以，页面失效不能按
一般的中断对待，应看作一种故障，一旦出现，处
理机必须立即予以响应和处理。
a)后援寄存器技术
把发生页面失效故障时指令的全部现场都保
存下来。在处理完故障并把所需要的页调入主
存后，取出后援寄存器的内容恢复故障点现场，
然后从故障点处继续执行完该条指令。
b)预判技术
执行指令前先预判操作数的首尾字符是否都
已在主存中。如果是，才执行这条指令；否则
就发生页面失效，直到调入该页后才开始执行
这条指令。
c)替换算法
不允许出现指令或操作数跨页存贮的那些页
被轮流从主存中替换出去的“颠簸”现象。因
此，
给某道程序分配的主存页数应该有个下限。
d)页面大小不能过大
以便多道程序的道数、每道程序所分配到的
主存页数都能在一个适当的范围内。如果页面
过大，就会使主存中页数过少，从而出现大量
的页面失效，严重降低虚拟存贮器的访问速率
和等效速度。
2.提高虚拟存贮器等效访问速度的措施
根据 虚拟存贮器等效访问速度公式
TA=HTA1+(1-H)TA2
希望 H提高,TA1, TA2缩短
关于高的主存命中率问题，其影响因素很多，
如地址流、页面调度策略、替换算法、页面大小
及分配给程序的页数 (主存容量 )等。这里主要讨
论怎样缩短访主存的时间。
从虚拟存贮器工作的全过程可以看到，每次访
问主存时，都必须进行内部地址变换 (因为页表都
存在主存中，每次查页表就要增加一次访存。若
采用段页式虚拟存贮器，查表要增加两次访存 )，
其概率是 100%。从缩短访主存的时间来看，关
键就是怎样加快多用户虚地址 NS到主存实地址 np
的变换。只有内部地址变换的速度高到使整个访
主存速度非常接近于不采用虚拟存贮器时的访主
存速度时，虚拟存贮器才能真正实用。如何从逻
辑结构上提高内部地址变换的速度，正是系统结
构设计的任务。
1)快表
由于程序的局部性特点，对页表内各行的使用
不是随机的，在一段时间内实际只用到表中很少
的几行。这样就可以用快速硬件构成比全表小的
多，如 8—16行的部分“目录表”，存放当前正
用
的虚实地址映像关系，那么其相联查找的速度就
会很快。这部分目录表就被称为快表。
?慢表：存放全部虚、实地址映像关系的表。实
质上，快表只是慢表中很小的一部分副本。
2)地址变换
查表时，由虚页号 u＋ Nv’(即 Nv)同时去查快表
和慢表。当在快表中有此虚页号时，就能很快找
到对应的实页号 nv，将其送入主存实地址寄存器，
并立即使慢表的查找作废，这时访存的速度没有
什么降低。如在快表中查不到时，则经过一个访
主存周期后，从慢表中查到的实页号 nv就会送入
主存实地址寄存器。同时将此虚页号和对应的实
页号送入快表。这里也要用到替换算法去替换快
表中应该移掉的内容。如下图：
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np
nv
装入位
nvu Nv’ 快表
(硬件构成 )
8—16行
相联比较
(按内容访问 )
快表中
查不到
慢表 (主存中 )
若查出对应的装入
位为 0发生页面失效
?由 2Nv中选 1(按地址访问 )
经快表与慢表实现内部地址变换
从上图可以看到，如果快表的命中率不高，系
统的效率就会大大下降。若快表采用堆栈型替换
算法，则快表容量越大其命中率就越高。但容量
大，其相联查找的速度就很慢，所以快表的命中
率和查表速度是有矛盾的。一般快表取 8—16行，
每页容量为 1—4K字，则快表容量可以反映主存
中的 8—64K单元。这样的快表命中率不会很低。
这样，快表与慢表实际上就构成了快表 —慢表存
贮层次。概念上等同于主存 —辅存存贮层次。快
表 —慢表存贮层次的替换算法一般也采用 LRU法。
3)减少快表相联比较的位数
在同样的容量下，相联比较的位数越少，相联
查找所花费的时间和设备量就越少。由于快表内
容在一段时间内总是对应于同一个任务或同一个
用户，它们的 u值是不变的。因此可以将参与相
联比较的位数中的 u字段去掉，从而由 Nv (u+Nv’)
位缩短到 Nv’位。需增设用户位来区分不同的任
务，用户位为 0的行，其映像关系无效。任务切
换时，通过硬件将所有用户位全部置 0，即都被
作废。
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np
nv
装入位
nvNv’ 快表
(硬件构成 )
8—16行
相联比较
(按内容访问 )
快表中
查不到
慢表 (主存中 )
若查出对应的装入
位为 0发生页面失效
?由 2Nv中选 1
(按地址访问 )
减少快表的相联比较位数
用户位
4)散列快表
a)思想
快表容量越大，命中率越高，相联比较越费
时，使快表会快不起来。为此可以改用高速的
按地址访问存贮器来构成容量更大的快表，并
用散列 (Hashing)法来实现按内容查找。其思想
是让内容 Nv与存放该内容的地址 A之间建立某
种散列函数关系，即让快表的地址 A=H(Nv)。
当需将虚、实地址 Nv与 nv的映像关系存入快表
存贮器中时，只需将 Nv对应的 nv等内容存入快
表寄存器的 A=H(Nv)单元即可。
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np比较相等
nvNv
散列变换
(硬化实现 )
相等不等
查慢表
快表
(按地址访问 )
经散列实现快表
A
?
b)查找过程
查找时，按现给出的 Nv经同样的散列函数变换
成 A后，按地址 A访问快表寄存器，就可以找到
存放该 Nv所对应的 nv及其余内容。只有硬化实现
散列函数变换才能保证必要的速度。如下图，为
解决多个不同的 Nv可能散列到同一个 A的散列冲
突，在快表中再增加 Nv项，在快表的 A单元中除
了存入当时的 nv，也存入当时的 Nv。这样在地址
变换时用现行 Nv经散列函数求得 A，查到 nv并访
存同时将同行中原保存的 Nv读出与现行 Nv比较。
若相等就继续进行由 nv形成的主存实地址访存；
否则就标明出现了冲突，即 A地址单元中的 nv不
是现行 Nv对应的实页号。就让刚才由 nv形成的主
存实地址进行的访存作废。经过一个主存周期，
用从慢表中读到的 nv再去访存。
虚地址
Nv
NrNv’u NS
nv nr 主存实地址 np比较相等
nvNv
散列变换
(硬化实现 )
相等不等
查慢表
快表
(按地址访问 )
?
A
c)改进散列冲突的办法
?在快表的每个地址 A单元中对应存放多个不同
的虚页号与实页号的映像关系，就可以降低由
于散列冲突所引起的不命中率。
?减小散列变换 (压缩 )的入、出位数差，散列冲
突的概率就会降低。
3.影响主存命中率和 CPU效率的某些因素
1)与 Sp有关
如图表示
了页面大小
Sp、分配给
某道程序的
主存容量 S1
与命中率 H的关系。可以看出分配给某道程序的
主存容量 S1一定时,H随 Sp的增大先升高，直到
一个最大值后逐渐降低；增大 S1能普遍提高 H,且
达到最高命中率时 Sp可以再大一些。
页面大小 Sp
命中率
H
1.0
S1
2S1
Sp1 Sp2
2)命中率与主存容量有关
如图实线表
示了堆栈型替换
算法的命中率 H
与 S1的关系。可以
看出开始随 S1的增大 H明显上升。但到一定程度
后,H的提供就逐级趋近于 1而不可能到达 1。当
S1过分增大后，主存空间的利用率可能由于程序
的不活跃部分所占比例增大而下降。实际中要折
衷权衡 Sp和 S1的选择，而不能过分追求 S1。
LRU
FIFO
1
命中率
H
S1
3)主存命中率与所采用的页面调度策略有关
通常大多数虚拟存贮器都采用请求式调度页面
的策略，即只有当页面失效时，才把所需的页调
入主存。针对程序存在局部性特点，可以采取工
作区的调度策略。所谓工作区是指在时间 t之前的
一段时间 Δt内已访问过的页面集合。
4.3 高速缓冲存贮器 (Cache)
高速缓冲存贮器 用以弥补主存速度的不足。
在 CPU与主存 (Main Memory—MM)之间设
置一个高速、小容量的缓冲存贮器 (Cache)，
构成 Cache——主存存贮层次。使之从 CPU
来看，速度是接近于 Cache的，容量却是主
存的。
4.3.1基本结构
1.工作过程
为了便于进行地址的映像和变换，如同虚拟存
贮器中将虚存空间和主存空间机械的分成大小相
同的页一样，在高速缓冲存贮器中把 Cache和主存
机械的分成大小相同的块 (或行 )。每一块由若干个
字 (或字节 )组成。从构成存贮层次的概念和原理上
讲,Cache存贮器中的块和虚拟存贮器中的页具有
相同的地位。只是实际块的大小比页的大小小的
多，一般只是页的几十分之一或几百分之一。
块内地址块号主存地址
主存－ Cache
地址映像变换机构
块内地址块号
Cache
主存Cache
替 换
策 略
Cache
地址
主存地址来自处理机
多字宽
单字宽
去处理机 直接通路
单字宽
访 主 存
替换 Cache
不命中
命中装不
进
可
装
入
访主存
装 入
Cache
图 4.32 Cache 存贮器的基本结构
?
?
?
?
2.特点
1)Cache—主存存贮层次和主存 —辅存存贮层次
原理相同。
2)Cache—主存存贮层次的速度要求高，在构成
与实现及透明性等问题上有自己的特点。
3)Cache存贮器一般采用与 CPU同类型的半导体
工艺构成。
4)Cache—主存间的地址映像和变换，以及替换
与调度算法全部采用专门的硬件来实现。
5)前一地址的访 Cache和后一地址的查表变换在
时间上重叠流水进行。
6)为了更好发挥 Cache的高速性，减小 CPU与
Cache之间的传输延迟，让 Cache在物理位置上
尽量靠近处理机或就放在处理机中而非主存中。
7)除了 Cache到处理机的通路外，在主存和处理
机间还设有直接通路。
8)为加速调块，每没块的容量等于一个主存周
期由主存所能访问的字数，因此在有 Cache存
贮器的主存系统都采用多体交叉存贮器。
9)主存被机器的多个部件共用，应提高 Cache的
访存优先级，一般应高于通道的访存级别。
4.3.2 地址的映像与变换
地址映像：将每个主存块按什么规则或方法装
入 (定位于 )Cache之中。
地址变换：当主存中的块按这种映像方法装入
Cache后，每次访 Cache时怎样将主存地址变
换成对应的 Cache地址。
块冲突：指出现了主存块要进入 Cache中的某块
位置已经被其它的主存块所占用。
1.全相联映像和变换
1)规则：如同虚拟存贮器中那样的全相联映像，
主存中的任意一块均可映像装入到 Cache内的
任意一块的位置。
…
Cache
块位置 0
1
2
2ncb-1
主存
块 0
1
2
2nmb-1
任何主
存块可映
像到任何
Cache块
的位置
……
图 4.33 全相联映像规则
2)地址变换过程
主存块号 块内地址
主存地址
nmnmb nmr
ncb ncr
Cache
块号
Cache地址
nc
nmb ncb
… … 2ncb 目录表
(专门硬件 )
相联比较
查到
查不到Cache
块失效
图 4.34 全相联映像的地址变换过程
3)优缺点
优点：块冲突率低，只有当 Cache中全部装满
后，才有可能出现块冲突。
缺点：要构成容量为 2ncb项的相联存贮器，代
价相对较大，而且目前 Cache的容量已
经大，这样查表速度就难以提高。
2.直接映像及其变换
1)规则：主存中每一块只能映像到 Cache中唯一
一个特定位置，如图所示，主存的第 i块只能映
像到第 i mod2ncb块位置上。
