第 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块位置上。
