?第7章 存储系统
7.1 计算机存储系统的层次结构
?计算机系统对存储器的要求是：容量大、速度快、成本低，但由于各类存储器各具其特点，
即半导体存储器速度快、成本较高；磁表面存储器容量大、成本低但速度慢，无法与CPU高速处理信息的能力相匹配。因此，在计算机系统中，通常采用三级存储器结构，即使用高速缓冲存储器、主存储器和外存储器组成的结构。
CPU能直接访问的存储器称为内存储器，它包括高速缓冲存储器和主存储器；CPU不能直接访问外存储器，外存储器的信息必须调入内存储器后才能为CPU进行处理。
? Cache－主存－辅存三级存储层次如图所示。其中Cache容量最小，辅存容量最大，
各层次中存放的内容都可以在下一层次中找到。这种多层次结构已成为现代计算机的典型存储结构。
Cache
CPU 高速缓冲
寄存器组 存储器
主 外
存 设
主 机
7．2 高速缓冲存储器
? 7．2．1 cache 存储器工作原理
?掌握要点：
? 1．程序访问的局部性
?在一个较短的时间间隔内，CPU对局部范围的存储器地址频繁访问，而对此地址范围之外的地址访问很少，这种现象称程序访问的局部性。
? 2．设立cache 存储器的理论依据
?它是为了提高存储系统的存取速度而设立的，
其理论依据是程序访问的局部性原理。
? 3．什么是cache 存储器
? cache 存储器是位于CPU和主存之间的一个容量相对较小的存储器，它的工作速度倍于主存，
全部功能由硬件实现，并且对程序员是透明的
? 4．cache 存储器的基本结构
?设主存有2
n
个单元，地址码为n位，将主存分块(block)，每块有2
b
个字节；Cache
也由同样大小的块组成，由于其容量小，
所以块的数目小得多，主存中只有一小部分块的内容可存放在Cache中。
?设n＝m＋b，则可得出：主存的块数M＝
2
m
，块内字节数＝2
b
。Cache地址码为(c
＋b)位，Cache的块数为2
c
，块内字节数与主存相同，如图4.29所示。
主存的地址
主存块号
块标记 Cache块号 块内地址
m 位 b位
c位 b位
Cache的地址格式
图4,29 Cache和主存的地址的地址格式
?当CPU发出读请求时，将主存地址的m－c位与
Cache某块的标记相比较，根据其比较结果是否相等而区分出两种情况：当比较结果相等时，
说明需要的数已在Cache中，那么直接访问
Cache就行了，在CPU与Cache之间，通常一次传送一个字块；当比较结果不相等时，说明需要的数据尚未调入Cache，那么就要把该数据所在的整个字块从主存一次调进来。前一种情况称为访问Cache命中，后一种情况称为访问
Cache不命中。
? 5．块长
?块的大小称为“块长”。块长一般取一个主存周期所能调出的信息长度。
? 6．如何保持Cache与主存的一致性
? Cache存储器中保存的字块是主存中相应字块的一个副本。如果程序执行过程中要对该字块的某个单元进行写操作，就会遇到如何保持
Cache与主存的一致性问题。通常有两种写入方式：
?（1）标志交换(flag－swap)方式或“写回法”。
?这种方式是暂时只向Cache存储器写入，并用标志加以注明，直到经过修改的字块被从
Cache中替换出来时才一次写入主存。这种方式写操作速度快，但因在此以前，主存中的字块未经随时修改而可能失效。
?（2）写直达法
?这种方式是每次写入Cache存储器时也同时写入主存，使Cache和主存保持一致。
这种方式实现简单，且能随时保持主存数据的正确性。但是，有可能要增加多次不必要的向主存的写入。假如向Cache
存储器某一单元写入多少次，也要向主存相应单元写入多少次。
?当被修改的单元根本就不在Cache存储器时，写操作直接对主存进行，而不写入Cache存储器。
? 7．2．2 Cache存储器的地址映像
?为了把信息放到Cache存储器中，必须应用某种函数把主存地址映像到
Cache，称作地址映像。在信息按照这种映像关系装入Cache后，执行程序时，
应将主存地址变换成Cache地址，这个变换过程叫做地址变换。
? 1．直接地址映像方式
?在直接映像方式中，映像函数可定为：
j＝i mod 2
c
?其中，j是Cache的字块号，i是主存的字块号。在这种映像方式中，主存的第0
块，第2
c
块，第2
c＋1
块，…，只能映像到
Cache的第0块，而主存的第l块，第2
c
＋1
块，第2
c+1
＋1块…，只能映像到Cache的第l块。
?
?例1 设主存容量1MB，高缓容量16KB，块的大小为512字节。
? (1)Cache地址格式
? (2)写出主存地址格式
? (3)块表的容量为多大？
? (4)画出直接方式地址映像及变换示意图
? (5)主存地址为CDE8FH的单元在cache中的什么位置？
?【例题解答】
? (1) Cache容量16KB，16KB=2
14
，所以Cache
地址为14位；块的大小为512字节，所以块内地址为9位，块地址为5位。
? Cache地址格式为：
13 9 8 0
?块地址块内地址
? (2)主存容量1MB，1MB=2
20
，所以主存地址为20位；
块的大小为512字节，所以块内地址为9位，块地址为
5位，块标记为6位。
?主存地址格式为：
? 19 14 13 9 8 0
?块标记块地址块内地址
? (3)Cache的每一块在块表中有一项，Cache的块地址为5位，所以块表的单元数为2
5；块表中存放的是块标记，由于块标记为6位，所以块表的字长为6位。
?故块表的容量为：2
5
字×6位。
(4)直接方式地址映像及变换示意图如图4.29所示：
MM
主存地址
第
0
块
主存区号
区内块号
块内地址
第
1
块
6
位
5
位
9
位
………
第
0
区
Cache
地址
第
31
块
比较
命中
Cache
第
0
块
0
第
0
块
第
1
块
1
第
1
块
………
第
1
区
2
第
31
块
第
0
块
区号
Y
第
Y
块
第
1
块
………
第
2
区
30
第
30
块
第
31
块
31
第
31
块
第
0
块
第
1
块
图
4, 29
例
4.8
直接映像方式的变换示意图
………
第
63
区
第
31
块
? (5)因为cache容量为16KB=2
14
B，块长为512B，
所以cache有16×1024/512=32个块。
?因为CDE8F H= 1100，1101，1110，1000，
1111
?所以块号= 1100，1101，111 块内地址=0，
1000，1111
?在直接映射方式下，主存中的第i块映射到
cache中第i mod 2
5
个块中；
? 1100，1101，111 mod 32 = 01111；
?所以，地址CDE8F的单元在cache中的地址为
01111，010001111。
?直接映像的优点是实现简单。
?直接映像方式的缺点是不够灵活，即主存的2
t
个字块只能对应唯一的Cache存储器字块，因此，即使Cache存储器别的许多地址空着也不能占用。这使得
Cache存储空间得不到充分利用，并降低了命中率。
? 2．全相联映像
?全相联映像方式是最灵活但成本最高的一种方式，如图所示。它允许主存中的每一个字块映像到Cache存储器的任何一个字块位置上，也允许从确实已被占满的Cache存储器中替换出任何一个旧字块。这是一个理想的方案，但实际上由于它的成本太高而不能采用。不只是它的标记位数从m－c位增加到m位(与直接映像相比)，使Cache标记容量加大，主要问题是在访问Cache时，需要和Cache的全部标记进行“比较”才能判断出所访主存地址的内容是否已在
Cache中。由于Cache速度要求高，所以全部
“比较”操作都要用硬件实现，通常由“按内容寻址的”相联存储器完成。所需逻辑电路甚多，
以致无法用于Cache中。
块表 Cache存储器 主存储器
字块0
标记 字块0 字块1
标记 字块1
字块i
标记 字块2
c
-1
字块2
m
-1
主存地址
主存字块标记 字块内地址
m= t+c位 b位
m=t+c
图4.32 全相联映像Cache组织
?在上面的例1中
? (1) Cache容量16KB，16KB=2
14
，所以Cache
地址为14位；块的大小为512字节，所以块内地址为9位，块地址为5位，共32个块。
? Cache地址格式为：
? 13 9 8 0
?块地址块内地址
(2)主存容量1MB，1MB=2
20
，所以主存地址为20
位；块的大小为512字节，所以块内地址为9位，
块地址为11位，共2
11
=2048个块。
? (2)主存容量1MB，1MB=2
20
，所以主存地址为
20位；块的大小为512字节，所以块内地址为9
位，块地址为11位，共2
11
=2048个块。
?主存地址格式为：
? 19 9 8 0
?块标记块内地址
? (3)Cache的每一块在块表中有一项，
Cache的块地址为5位，所以块表的单元数为2
5；块表中存放的是块标记，由于块标记为11位，所以块表的字长为11位。
?故块表的容量为：2
5
字×11位。
(4) 全相联映像方式地址映像及变换示意图如图所示：
块表 Cache存储器 主存储器
字块0
标记 字块0 字块1
标记 字块1
字块i
标记 字块31
字块2047
主存地址
主存字块标记 字块内地址
m=11位 b=9位
11
?
? 3.组相联地址映像方式
?组相联映像方式是直接映像和全相联映像方式的一种折衷方案。组相联映像Cache组织如图4.33所示。它把Cache字块分为2
c’
组，每组包含2
r
个字块，于是有c＝c’＋r。那么，主存字块M
m
(i)(0≤i≤2
m
－1)可以用下列映像函数映像到Cache字块M
c
(j) (0≤j≤2
c
－1)上。
? j＝(i mod 2
c’
)×2
r
＋k 0≤k≤2
r
－1
? k是为位于上列范围内的可选参数(整数)。按这种映像方式，组间为直接映像，而组内的字块为全相联映像方式。
?例2 一个组相联映象Cache由64个存储块构成，每组包含4个存储块。主存包含
4096个存储块，每块由8字组成，每字为
32位。存储器按字节编址，访存地址为字地址。
? (1)写出主存地址位数和地址格式。
? (2)Cache地址位数和地址格式。
? (3)画出组相联映像方式的示意图。
? (4)主存地址18AB9H映射到Cache的哪个字块？
?【相关知识】Cache存储器的地址格式和组相联地址映像方式。
?【例题解答】
? (1) Cache由64个存储块构成，每块由8字组成，每字为32位，存储器按字节编址，
?所以Cache容量=64×8字×4B=2
11
B，所以
Cache的地址总数为11位。
?每组包含4个存储块，所以组内块号为2位；
Cache有64/4=16个组，所以组号为4位。
? Cache地址格式为：
? 10 9 8 5 4 2 1 0
?组内块号组号块内字地址块内字节地址
?
? (1)主存包含4096个存储块，主存容量
=4096×8字×4字节=2
17
字节
?主存字块标记为17-11=6位。
?主存地址格式为：
? 16 11 10 9 8 5 4 2 1 0
主存字块标记组内块号组号块内字地址块内字节地址
?
? (3)组相联映像方式的示意图如图所示。
?由于访存地址为字地址，所以块内字节地址无用，图中由主存高位地址和组内块号组成标记，
分别与由组号选中的组中的四个标记进行比较，
比较符合即可访问相应的字块。
?
? (4)主存地址18AB9H = 1 1000 1010 1011 1001
?方法1：
?组号为0101，所以主存地址18AB9H可以映射到Cache的第5组中的字块21、字块22、字块23
或字块24。
?方法2：
?块内地址位1 1001；块号位i= 1 1000
1010 101；设Cache的块号为j，因为
? j=(i mod 2
4
) ×2
2
＋k 0≤k≤2
2
－1
?所以j=(1 1000 1010 101 mod 2
4
) ×2
2
＋
k =0101×2
2
＋k =5×4＋k
?所以主存地址18AB9H可以映射到Cache
的第5组中的字块21、字块22、字块23或字块24。
?
第
0
块
第
1
块
1
区
组
cache (r=2)
0
标记
字块
0
标记
字块
1
标记
字块
2
标记
字块
3
第
15
块
1
标记
字块
4
标记
字块
5
标记
字块
6
标记
字块
7
第
16
块
第
17
块
14
标记
字块
56
标记
字块
57
标记
字块
58
标记
字块
59
第
31
块
15
标记
字块
60
标记
字块
61
标记
字块
62
标记
字块
63
第
4079
块
比
较
第
4080
块
64
区
主存高位地址
组内块号
组号
块内地址
第
4095
块
16 11 10 9 8 5 4 0
图
组相联映像方式的示意图
?在实际Cache中用得最多的是直接映像(r＝0)，
两路组相联映像(r＝1)和4路组相联映像(r＝2)。
如r＝2，则0≤k≤3，所以主存某一字块可映像到Cache某组4个字块的任一字块中，这大大地增加了映像的灵活性，提高了命中率。
?组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。当r＝0时，它就成为直接映像方式；当r＝c时，就是全相联映像方式。
? Cache的命中率除了与地址映像的方式有关外，
还与Cache的容量有关。Cache容量大，命中率高，但达到一定容量后，命中率的提高就不明显了。
? 4．替换算法
?当新的主存字块需要调入Cache存储器而它的可用位置又已被占满；辅存的页需要调入主存而主存的页已被占满时，就产生替换问题。
常用的替换算法有：先进先出(FIFO)算法和近期最少使用(LRU)算法。
? FIFO算法总是把一组中最先调入的块或页替换出去，它不需要随时记录各个字块或页的使用情况，所以实现容易、开销小。
? LRU算法是把一组中近期最少使用的字块或页替换出去。这种替换算法需随时记录Cache
存储器中各个字块或主存中的各页的使用情况，
以便确定那个字块是近期最少使用的字块。
LRU替换算法的平均命中率比FIFO要高，并且当分组容量加大时，能提高LRU替换算法的命中率。见习题7.10
7.3 虚拟存储器
? 1,虚拟存储器概述
? (1) 什么是虚拟存储器
?虚拟存储技术是为了扩大主存的寻址空间而采用的。
虚拟存储器是建立在主存与辅存物理结构基础之上，
由附加硬件装置以及操作系统存储管理软件组成的一种存储体系。它把主存和辅存的地址空间统一编址，
形成一个庞大的存储空间，在这个大空间里，用户可自由编程，完全不必考虑程序在主存中是否装得下，
或者放在辅存的程序将来在主存中的实际位置，编好的程序由计算机操作系统装入辅助存储器中，程序运行时，附加的辅助硬件机构和存储管理软件会把辅存的程序一块块自动调入主存由CPU执行或从主存调出，
用户感觉到的不再是处处受主存容量限制的存储系统，
而是一个容量充分大的存储器。因为实质上CPU仍只能执行调入主存的程序，所以这样的存储体系称为“虚拟存储器”。
? (2) 虚地址和实地址
?虚拟存储器的辅存部分也能让用户像内存一样使用，用户编程时指令地址允许涉及到辅存的空间范围，这种指令地址称为“虚地址”(即虚拟地址)，或叫“逻辑地址”，虚地址对应的存储空间称为
“虚拟空间”，或叫“逻辑空间”。
?实际的主存储器单元的地址则称为“实地址”(即主存地址)，或叫“物理地址”，实地址对应的是“主存空间”，也称物理空间。显然，虚地址范围要比实地址大得多。
? (3) 主存—辅存层次与主存—Cache层次的比较
?虚拟存储器和主存Cache存储器是两个不同存储层次的存储体系。但在概念上有不少相同之处：
?它们都把程序划分为一个个信息块，运行时都能自动地把信息块从慢速存储器向快速存储器调度，信息块的调度都采用一定的替换策略，
新的信息块将淘汰最不活跃的旧的信息块，以提高继续运行时的命中率，新调入的信息块需遵守一定的映射关系变换地址后来确定其在存储器的位置。
?两个存储体系均以信息块作为存储层次之间基本信息的传递单位，主存—Cache存储器每次传递是定长的的信息块，长度只有几十字节，
而虚拟存储器信息块划分方案很多，有页、段等等，长度均在几百字节至几百千字节左右。
?由主存与辅存组成的虚拟存储器和主存Cache
存储器也有很多不同之处。主存Cache存储器采用与CPU速度匹配的快速存储元件来弥补主存和CPU之间的速度差距，而虚拟存储器虽然最大限度地减少了慢速辅存对CPU的影响，但它却弥补了主存的容量不足，具有容量大和程序编址方便的优点。
? CPU访问快速Cache存储器的速度比访问慢速主存快5～10倍。虚拟存储器中主存的速度要比辅存快100～1000倍以上。
?主存Cache存储体系中CPU与Cache和主存都建立了直接访问的通路，一旦在Cache中命中，CPU就直接访问Cache，并同时向Cache
调度信息块，从而减少了CPU等待的时间，辅助存储器与CPU之间没有直接通路，一旦在主存中不命中，则只能从辅存调度信息块到主存，
因为辅存的速度与CPU的速度差距太大，调度需要毫秒级时间，因此，CPU一般将改换执行另一个程序，等到调度完成后再返回原程序继续工作。
?主存—Cache存储器存取信息的过程、地址变换和替换策略全部用硬件实现，所以对各类程序员均是透明的。主—辅层次的虚拟存储器基本上由操作系统的存储管理软件辅助一些硬件进行信息块的划分和主—辅存之间的调度，所以对设计存储管理软件的系统程序员来说，它是不透明的，而对于广大用户，因为虚拟存储器提供了庞大的逻辑空间可以任意使用，对应用程序员来说是透明的。
?2,虚拟存储器的结构
? (1)段式虚拟存储器
?段是利用程序的模块化性质，按照程序的逻辑结构划分成的多个相对独立的部分。例如，过程、子程序、数据表、阵列等。段作为独立的逻辑单位可以被其他程序段调用，这样就形成段间连接，
产生规模较大的程序。段式虚拟存储器一般用段表来指明各段在主存中的位置，
如图4.34所示。
程序逻辑空间 长度 实主存空间 地址 起始地址 装入位 长度
段1 1K 段1 1 0 1 1K
段2 2K 段5 2 0
3 5K 1 3K
段3 3K 4 0
段3 5 1K 1 2K
段4 1K 段 表
段5 2K
（a） (b)
0
1K
3K
8K-1
5K
?把主存按段分配的存储管理方式称为段式管理。段式管理系统的优点是段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享。其缺点是容易在段间留下许多空余的零碎存储空间不好利用，造成浪费。
? (2) 页式虚拟存储器
?页式管理系统的信息传送单位是定长的页，主存的物理空间也被划分为等长的固定区域，
称为页面。新页调入主存也很容易掌握，只要有空白页面就可。可能造成浪费的是程序最后一页的零头，是不能利用的页内空间，它比段式管理系统的空间浪费要小得多。页式管理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理、保护和共享都不及段式来得方便。
?在页式虚拟存储系统中，把虚拟空间分成页，
主存空间也分成同样大小的页，称为实页或物理页，而把前者称为虚页或逻辑页。假设虚页号为0，1，2，…，m，实页号为0，l，…，l，
显然有m>l。可把虚拟地址分为两个字段，高位字段为虚页号，低位字段为页内字地址。
?虚拟地址到主存实地址的变换是由页表来实现的。在页表中，对应每一个虚存页号有一个表目，表目内容至少要包含该虚页所在的主存页面号，用它作为主存地址的高字段；与虚拟地址的页内地址字段相拼接，就产生完整的实主存地址，据此访问主存。页式管理的地址变换见例3。
?例3 设主存容量64KB，虚存容量1MB，
页面大小为512B。
? (1)写出主存地址格式
? (2)写出虚拟地址格式
? (3)页表的长度为多少？
? (4)画出虚实地址转换示意图
?【相关知识】虚拟存储器的地址格式和虚实地址转换过程。
?【例题解答】
? (1)主存容量64KB，64KB=2
16
，所以主存地址为16位。
?主存地址格式为：
? 15 9 8 0
?物理页号(7位) 页内地址(9位)
? (2)虚存容量1MB，1MB=2
20
，所以虚存地址为20位。
?虚拟地址格式为：
?
? 19 9 8 0
?虚页面号(11位) 页内地址(9位)
? (3)每一个虚页面号在页表中有一项，所以页表的长度为2
11
=2048
? (4)虚实地址转换示意图4.31所示：
虚
地
址
页
面
号
页
内
地
址
页表起址寄存器
0 0 5 H 1 5 0 H 1 0 0 0 H
虚页面号
物理页号
特征位
其它位
0 0 0 H 0
0 0 1 H 5 0 H 1
0 0 5 H 4 5 H 1
7 F E H 0
7 F F H 7 0 H 1
4 5 H 1
其它位
左移
9
位
实地址
8B50H
? (3)段页式虚拟存储器见P246
?
? Cache技术指标的计算
? 1,CPU执行一段程序时，Cache完成存取的次数为5000次，主存完成存取的次数为200次。
已知Cache存取周期为40ns，主存存取周期为
160ns。求：
? (1)Cache 命中率H。
? (2)Cache／主存系统的访问效率e。
? (3)平均访问时间Ta。
?解：(1)命中率H＝N
c
／(N
c
＋N
m
) ＝5000／
(5000＋200)＝0.96
? (2)平均访问时间：T
a
＝T
c
＋(1 – H)×T
m
＝
40ns＋(1 – 0.96)×160ns＝46.4ns
? (1)访问效率：e＝T
c
／T
a
＝40ns／
46.4ns×100%＝86.2%
?2．以知cache 命中率H=0.98，主存比cache
慢四倍，以知主存存取周期为200ns，求
cache/主存的效率和平均访问时间。
?解：R=Tm/Tc=4；Tc=Tm/4=50ns
?平均访问时间：T
a
=H×T
c
+ (1 – H)
×T
m
=0.98×50ns + (1 – 0.98)×200ns=53ns
?访问效率：e = T
c
/
T
a
=50ns/53ns×100%=94.3%
?3．已知cache/主存系统效率为85%，平均访问时间为60ns，cache比主存快4倍，
求主存存储器周期是多少？cache 命中率是多少？
?解：因为Ta=Tc/e 所以Tc=Ta×e
=60ns×0.85=51ns (cache存取周期)
? r=4,Tm=Tc×r =51×4 =204ns (主存存取周期)
?因为：T
a
=H×T
c
+ (1 – H)
×T
m
=H×51ns + (1 – H)×204ns=60ns
?所以：命中率H=144/153=94%
7.1 计算机存储系统的层次结构
?计算机系统对存储器的要求是：容量大、速度快、成本低，但由于各类存储器各具其特点，
即半导体存储器速度快、成本较高；磁表面存储器容量大、成本低但速度慢，无法与CPU高速处理信息的能力相匹配。因此，在计算机系统中，通常采用三级存储器结构，即使用高速缓冲存储器、主存储器和外存储器组成的结构。
CPU能直接访问的存储器称为内存储器，它包括高速缓冲存储器和主存储器；CPU不能直接访问外存储器，外存储器的信息必须调入内存储器后才能为CPU进行处理。
? Cache－主存－辅存三级存储层次如图所示。其中Cache容量最小，辅存容量最大，
各层次中存放的内容都可以在下一层次中找到。这种多层次结构已成为现代计算机的典型存储结构。
Cache
CPU 高速缓冲
寄存器组 存储器
主 外
存 设
主 机
7．2 高速缓冲存储器
? 7．2．1 cache 存储器工作原理
?掌握要点：
? 1．程序访问的局部性
?在一个较短的时间间隔内，CPU对局部范围的存储器地址频繁访问，而对此地址范围之外的地址访问很少，这种现象称程序访问的局部性。
? 2．设立cache 存储器的理论依据
?它是为了提高存储系统的存取速度而设立的，
其理论依据是程序访问的局部性原理。
? 3．什么是cache 存储器
? cache 存储器是位于CPU和主存之间的一个容量相对较小的存储器，它的工作速度倍于主存，
全部功能由硬件实现，并且对程序员是透明的
? 4．cache 存储器的基本结构
?设主存有2
n
个单元，地址码为n位，将主存分块(block)，每块有2
b
个字节；Cache
也由同样大小的块组成，由于其容量小，
所以块的数目小得多，主存中只有一小部分块的内容可存放在Cache中。
?设n＝m＋b，则可得出：主存的块数M＝
2
m
，块内字节数＝2
b
。Cache地址码为(c
＋b)位，Cache的块数为2
c
，块内字节数与主存相同，如图4.29所示。
主存的地址
主存块号
块标记 Cache块号 块内地址
m 位 b位
c位 b位
Cache的地址格式
图4,29 Cache和主存的地址的地址格式
?当CPU发出读请求时，将主存地址的m－c位与
Cache某块的标记相比较，根据其比较结果是否相等而区分出两种情况：当比较结果相等时，
说明需要的数已在Cache中，那么直接访问
Cache就行了，在CPU与Cache之间，通常一次传送一个字块；当比较结果不相等时，说明需要的数据尚未调入Cache，那么就要把该数据所在的整个字块从主存一次调进来。前一种情况称为访问Cache命中，后一种情况称为访问
Cache不命中。
? 5．块长
?块的大小称为“块长”。块长一般取一个主存周期所能调出的信息长度。
? 6．如何保持Cache与主存的一致性
? Cache存储器中保存的字块是主存中相应字块的一个副本。如果程序执行过程中要对该字块的某个单元进行写操作，就会遇到如何保持
Cache与主存的一致性问题。通常有两种写入方式：
?（1）标志交换(flag－swap)方式或“写回法”。
?这种方式是暂时只向Cache存储器写入，并用标志加以注明，直到经过修改的字块被从
Cache中替换出来时才一次写入主存。这种方式写操作速度快，但因在此以前，主存中的字块未经随时修改而可能失效。
?（2）写直达法
?这种方式是每次写入Cache存储器时也同时写入主存，使Cache和主存保持一致。
这种方式实现简单，且能随时保持主存数据的正确性。但是，有可能要增加多次不必要的向主存的写入。假如向Cache
存储器某一单元写入多少次，也要向主存相应单元写入多少次。
?当被修改的单元根本就不在Cache存储器时，写操作直接对主存进行，而不写入Cache存储器。
? 7．2．2 Cache存储器的地址映像
?为了把信息放到Cache存储器中，必须应用某种函数把主存地址映像到
Cache，称作地址映像。在信息按照这种映像关系装入Cache后，执行程序时，
应将主存地址变换成Cache地址，这个变换过程叫做地址变换。
? 1．直接地址映像方式
?在直接映像方式中，映像函数可定为：
j＝i mod 2
c
?其中，j是Cache的字块号，i是主存的字块号。在这种映像方式中，主存的第0
块，第2
c
块，第2
c＋1
块，…，只能映像到
Cache的第0块，而主存的第l块，第2
c
＋1
块，第2
c+1
＋1块…，只能映像到Cache的第l块。
?
?例1 设主存容量1MB，高缓容量16KB，块的大小为512字节。
? (1)Cache地址格式
? (2)写出主存地址格式
? (3)块表的容量为多大？
? (4)画出直接方式地址映像及变换示意图
? (5)主存地址为CDE8FH的单元在cache中的什么位置？
?【例题解答】
? (1) Cache容量16KB，16KB=2
14
，所以Cache
地址为14位；块的大小为512字节，所以块内地址为9位，块地址为5位。
? Cache地址格式为：
13 9 8 0
?块地址块内地址
? (2)主存容量1MB，1MB=2
20
，所以主存地址为20位；
块的大小为512字节，所以块内地址为9位，块地址为
5位，块标记为6位。
?主存地址格式为：
? 19 14 13 9 8 0
?块标记块地址块内地址
? (3)Cache的每一块在块表中有一项，Cache的块地址为5位，所以块表的单元数为2
5；块表中存放的是块标记，由于块标记为6位，所以块表的字长为6位。
?故块表的容量为：2
5
字×6位。
(4)直接方式地址映像及变换示意图如图4.29所示：
MM
主存地址
第
0
块
主存区号
区内块号
块内地址
第
1
块
6
位
5
位
9
位
………
第
0
区
Cache
地址
第
31
块
比较
命中
Cache
第
0
块
0
第
0
块
第
1
块
1
第
1
块
………
第
1
区
2
第
31
块
第
0
块
区号
Y
第
Y
块
第
1
块
………
第
2
区
30
第
30
块
第
31
块
31
第
31
块
第
0
块
第
1
块
图
4, 29
例
4.8
直接映像方式的变换示意图
………
第
63
区
第
31
块
? (5)因为cache容量为16KB=2
14
B，块长为512B，
所以cache有16×1024/512=32个块。
?因为CDE8F H= 1100，1101，1110，1000，
1111
?所以块号= 1100，1101，111 块内地址=0，
1000，1111
?在直接映射方式下，主存中的第i块映射到
cache中第i mod 2
5
个块中；
? 1100，1101，111 mod 32 = 01111；
?所以，地址CDE8F的单元在cache中的地址为
01111，010001111。
?直接映像的优点是实现简单。
?直接映像方式的缺点是不够灵活，即主存的2
t
个字块只能对应唯一的Cache存储器字块，因此，即使Cache存储器别的许多地址空着也不能占用。这使得
Cache存储空间得不到充分利用，并降低了命中率。
? 2．全相联映像
?全相联映像方式是最灵活但成本最高的一种方式，如图所示。它允许主存中的每一个字块映像到Cache存储器的任何一个字块位置上，也允许从确实已被占满的Cache存储器中替换出任何一个旧字块。这是一个理想的方案，但实际上由于它的成本太高而不能采用。不只是它的标记位数从m－c位增加到m位(与直接映像相比)，使Cache标记容量加大，主要问题是在访问Cache时，需要和Cache的全部标记进行“比较”才能判断出所访主存地址的内容是否已在
Cache中。由于Cache速度要求高，所以全部
“比较”操作都要用硬件实现，通常由“按内容寻址的”相联存储器完成。所需逻辑电路甚多，
以致无法用于Cache中。
块表 Cache存储器 主存储器
字块0
标记 字块0 字块1
标记 字块1
字块i
标记 字块2
c
-1
字块2
m
-1
主存地址
主存字块标记 字块内地址
m= t+c位 b位
m=t+c
图4.32 全相联映像Cache组织
?在上面的例1中
? (1) Cache容量16KB，16KB=2
14
，所以Cache
地址为14位；块的大小为512字节，所以块内地址为9位，块地址为5位，共32个块。
? Cache地址格式为：
? 13 9 8 0
?块地址块内地址
(2)主存容量1MB，1MB=2
20
，所以主存地址为20
位；块的大小为512字节，所以块内地址为9位，
块地址为11位，共2
11
=2048个块。
? (2)主存容量1MB，1MB=2
20
，所以主存地址为
20位；块的大小为512字节，所以块内地址为9
位，块地址为11位，共2
11
=2048个块。
?主存地址格式为：
? 19 9 8 0
?块标记块内地址
? (3)Cache的每一块在块表中有一项，
Cache的块地址为5位，所以块表的单元数为2
5；块表中存放的是块标记，由于块标记为11位，所以块表的字长为11位。
?故块表的容量为：2
5
字×11位。
(4) 全相联映像方式地址映像及变换示意图如图所示：
块表 Cache存储器 主存储器
字块0
标记 字块0 字块1
标记 字块1
字块i
标记 字块31
字块2047
主存地址
主存字块标记 字块内地址
m=11位 b=9位
11
?
? 3.组相联地址映像方式
?组相联映像方式是直接映像和全相联映像方式的一种折衷方案。组相联映像Cache组织如图4.33所示。它把Cache字块分为2
c’
组，每组包含2
r
个字块，于是有c＝c’＋r。那么，主存字块M
m
(i)(0≤i≤2
m
－1)可以用下列映像函数映像到Cache字块M
c
(j) (0≤j≤2
c
－1)上。
? j＝(i mod 2
c’
)×2
r
＋k 0≤k≤2
r
－1
? k是为位于上列范围内的可选参数(整数)。按这种映像方式，组间为直接映像，而组内的字块为全相联映像方式。
?例2 一个组相联映象Cache由64个存储块构成，每组包含4个存储块。主存包含
4096个存储块，每块由8字组成，每字为
32位。存储器按字节编址，访存地址为字地址。
? (1)写出主存地址位数和地址格式。
? (2)Cache地址位数和地址格式。
? (3)画出组相联映像方式的示意图。
? (4)主存地址18AB9H映射到Cache的哪个字块？
?【相关知识】Cache存储器的地址格式和组相联地址映像方式。
?【例题解答】
? (1) Cache由64个存储块构成，每块由8字组成，每字为32位，存储器按字节编址，
?所以Cache容量=64×8字×4B=2
11
B，所以
Cache的地址总数为11位。
?每组包含4个存储块，所以组内块号为2位；
Cache有64/4=16个组，所以组号为4位。
? Cache地址格式为：
? 10 9 8 5 4 2 1 0
?组内块号组号块内字地址块内字节地址
?
? (1)主存包含4096个存储块，主存容量
=4096×8字×4字节=2
17
字节
?主存字块标记为17-11=6位。
?主存地址格式为：
? 16 11 10 9 8 5 4 2 1 0
主存字块标记组内块号组号块内字地址块内字节地址
?
? (3)组相联映像方式的示意图如图所示。
?由于访存地址为字地址，所以块内字节地址无用，图中由主存高位地址和组内块号组成标记，
分别与由组号选中的组中的四个标记进行比较，
比较符合即可访问相应的字块。
?
? (4)主存地址18AB9H = 1 1000 1010 1011 1001
?方法1：
?组号为0101，所以主存地址18AB9H可以映射到Cache的第5组中的字块21、字块22、字块23
或字块24。
?方法2：
?块内地址位1 1001；块号位i= 1 1000
1010 101；设Cache的块号为j，因为
? j=(i mod 2
4
) ×2
2
＋k 0≤k≤2
2
－1
?所以j=(1 1000 1010 101 mod 2
4
) ×2
2
＋
k =0101×2
2
＋k =5×4＋k
?所以主存地址18AB9H可以映射到Cache
的第5组中的字块21、字块22、字块23或字块24。
?
第
0
块
第
1
块
1
区
组
cache (r=2)
0
标记
字块
0
标记
字块
1
标记
字块
2
标记
字块
3
第
15
块
1
标记
字块
4
标记
字块
5
标记
字块
6
标记
字块
7
第
16
块
第
17
块
14
标记
字块
56
标记
字块
57
标记
字块
58
标记
字块
59
第
31
块
15
标记
字块
60
标记
字块
61
标记
字块
62
标记
字块
63
第
4079
块
比
较
第
4080
块
64
区
主存高位地址
组内块号
组号
块内地址
第
4095
块
16 11 10 9 8 5 4 0
图
组相联映像方式的示意图
?在实际Cache中用得最多的是直接映像(r＝0)，
两路组相联映像(r＝1)和4路组相联映像(r＝2)。
如r＝2，则0≤k≤3，所以主存某一字块可映像到Cache某组4个字块的任一字块中，这大大地增加了映像的灵活性，提高了命中率。
?组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。当r＝0时，它就成为直接映像方式；当r＝c时，就是全相联映像方式。
? Cache的命中率除了与地址映像的方式有关外，
还与Cache的容量有关。Cache容量大，命中率高，但达到一定容量后，命中率的提高就不明显了。
? 4．替换算法
?当新的主存字块需要调入Cache存储器而它的可用位置又已被占满；辅存的页需要调入主存而主存的页已被占满时，就产生替换问题。
常用的替换算法有：先进先出(FIFO)算法和近期最少使用(LRU)算法。
? FIFO算法总是把一组中最先调入的块或页替换出去，它不需要随时记录各个字块或页的使用情况，所以实现容易、开销小。
? LRU算法是把一组中近期最少使用的字块或页替换出去。这种替换算法需随时记录Cache
存储器中各个字块或主存中的各页的使用情况，
以便确定那个字块是近期最少使用的字块。
LRU替换算法的平均命中率比FIFO要高，并且当分组容量加大时，能提高LRU替换算法的命中率。见习题7.10
7.3 虚拟存储器
? 1,虚拟存储器概述
? (1) 什么是虚拟存储器
?虚拟存储技术是为了扩大主存的寻址空间而采用的。
虚拟存储器是建立在主存与辅存物理结构基础之上，
由附加硬件装置以及操作系统存储管理软件组成的一种存储体系。它把主存和辅存的地址空间统一编址，
形成一个庞大的存储空间，在这个大空间里，用户可自由编程，完全不必考虑程序在主存中是否装得下，
或者放在辅存的程序将来在主存中的实际位置，编好的程序由计算机操作系统装入辅助存储器中，程序运行时，附加的辅助硬件机构和存储管理软件会把辅存的程序一块块自动调入主存由CPU执行或从主存调出，
用户感觉到的不再是处处受主存容量限制的存储系统，
而是一个容量充分大的存储器。因为实质上CPU仍只能执行调入主存的程序，所以这样的存储体系称为“虚拟存储器”。
? (2) 虚地址和实地址
?虚拟存储器的辅存部分也能让用户像内存一样使用，用户编程时指令地址允许涉及到辅存的空间范围，这种指令地址称为“虚地址”(即虚拟地址)，或叫“逻辑地址”，虚地址对应的存储空间称为
“虚拟空间”，或叫“逻辑空间”。
?实际的主存储器单元的地址则称为“实地址”(即主存地址)，或叫“物理地址”，实地址对应的是“主存空间”，也称物理空间。显然，虚地址范围要比实地址大得多。
? (3) 主存—辅存层次与主存—Cache层次的比较
?虚拟存储器和主存Cache存储器是两个不同存储层次的存储体系。但在概念上有不少相同之处：
?它们都把程序划分为一个个信息块，运行时都能自动地把信息块从慢速存储器向快速存储器调度，信息块的调度都采用一定的替换策略，
新的信息块将淘汰最不活跃的旧的信息块，以提高继续运行时的命中率，新调入的信息块需遵守一定的映射关系变换地址后来确定其在存储器的位置。
?两个存储体系均以信息块作为存储层次之间基本信息的传递单位，主存—Cache存储器每次传递是定长的的信息块，长度只有几十字节，
而虚拟存储器信息块划分方案很多，有页、段等等，长度均在几百字节至几百千字节左右。
?由主存与辅存组成的虚拟存储器和主存Cache
存储器也有很多不同之处。主存Cache存储器采用与CPU速度匹配的快速存储元件来弥补主存和CPU之间的速度差距，而虚拟存储器虽然最大限度地减少了慢速辅存对CPU的影响，但它却弥补了主存的容量不足，具有容量大和程序编址方便的优点。
? CPU访问快速Cache存储器的速度比访问慢速主存快5～10倍。虚拟存储器中主存的速度要比辅存快100～1000倍以上。
?主存Cache存储体系中CPU与Cache和主存都建立了直接访问的通路，一旦在Cache中命中，CPU就直接访问Cache，并同时向Cache
调度信息块，从而减少了CPU等待的时间，辅助存储器与CPU之间没有直接通路，一旦在主存中不命中，则只能从辅存调度信息块到主存，
因为辅存的速度与CPU的速度差距太大，调度需要毫秒级时间，因此，CPU一般将改换执行另一个程序，等到调度完成后再返回原程序继续工作。
?主存—Cache存储器存取信息的过程、地址变换和替换策略全部用硬件实现，所以对各类程序员均是透明的。主—辅层次的虚拟存储器基本上由操作系统的存储管理软件辅助一些硬件进行信息块的划分和主—辅存之间的调度，所以对设计存储管理软件的系统程序员来说，它是不透明的，而对于广大用户，因为虚拟存储器提供了庞大的逻辑空间可以任意使用，对应用程序员来说是透明的。
?2,虚拟存储器的结构
? (1)段式虚拟存储器
?段是利用程序的模块化性质，按照程序的逻辑结构划分成的多个相对独立的部分。例如，过程、子程序、数据表、阵列等。段作为独立的逻辑单位可以被其他程序段调用，这样就形成段间连接，
产生规模较大的程序。段式虚拟存储器一般用段表来指明各段在主存中的位置，
如图4.34所示。
程序逻辑空间 长度 实主存空间 地址 起始地址 装入位 长度
段1 1K 段1 1 0 1 1K
段2 2K 段5 2 0
3 5K 1 3K
段3 3K 4 0
段3 5 1K 1 2K
段4 1K 段 表
段5 2K
（a） (b)
0
1K
3K
8K-1
5K
?把主存按段分配的存储管理方式称为段式管理。段式管理系统的优点是段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享。其缺点是容易在段间留下许多空余的零碎存储空间不好利用，造成浪费。
? (2) 页式虚拟存储器
?页式管理系统的信息传送单位是定长的页，主存的物理空间也被划分为等长的固定区域，
称为页面。新页调入主存也很容易掌握，只要有空白页面就可。可能造成浪费的是程序最后一页的零头，是不能利用的页内空间，它比段式管理系统的空间浪费要小得多。页式管理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理、保护和共享都不及段式来得方便。
?在页式虚拟存储系统中，把虚拟空间分成页，
主存空间也分成同样大小的页，称为实页或物理页，而把前者称为虚页或逻辑页。假设虚页号为0，1，2，…，m，实页号为0，l，…，l，
显然有m>l。可把虚拟地址分为两个字段，高位字段为虚页号，低位字段为页内字地址。
?虚拟地址到主存实地址的变换是由页表来实现的。在页表中，对应每一个虚存页号有一个表目，表目内容至少要包含该虚页所在的主存页面号，用它作为主存地址的高字段；与虚拟地址的页内地址字段相拼接，就产生完整的实主存地址，据此访问主存。页式管理的地址变换见例3。
?例3 设主存容量64KB，虚存容量1MB，
页面大小为512B。
? (1)写出主存地址格式
? (2)写出虚拟地址格式
? (3)页表的长度为多少？
? (4)画出虚实地址转换示意图
?【相关知识】虚拟存储器的地址格式和虚实地址转换过程。
?【例题解答】
? (1)主存容量64KB，64KB=2
16
，所以主存地址为16位。
?主存地址格式为：
? 15 9 8 0
?物理页号(7位) 页内地址(9位)
? (2)虚存容量1MB，1MB=2
20
，所以虚存地址为20位。
?虚拟地址格式为：
?
? 19 9 8 0
?虚页面号(11位) 页内地址(9位)
? (3)每一个虚页面号在页表中有一项，所以页表的长度为2
11
=2048
? (4)虚实地址转换示意图4.31所示：
虚
地
址
页
面
号
页
内
地
址
页表起址寄存器
0 0 5 H 1 5 0 H 1 0 0 0 H
虚页面号
物理页号
特征位
其它位
0 0 0 H 0
0 0 1 H 5 0 H 1
0 0 5 H 4 5 H 1
7 F E H 0
7 F F H 7 0 H 1
4 5 H 1
其它位
左移
9
位
实地址
8B50H
? (3)段页式虚拟存储器见P246
?
? Cache技术指标的计算
? 1,CPU执行一段程序时，Cache完成存取的次数为5000次，主存完成存取的次数为200次。
已知Cache存取周期为40ns，主存存取周期为
160ns。求：
? (1)Cache 命中率H。
? (2)Cache／主存系统的访问效率e。
? (3)平均访问时间Ta。
?解：(1)命中率H＝N
c
／(N
c
＋N
m
) ＝5000／
(5000＋200)＝0.96
? (2)平均访问时间：T
a
＝T
c
＋(1 – H)×T
m
＝
40ns＋(1 – 0.96)×160ns＝46.4ns
? (1)访问效率：e＝T
c
／T
a
＝40ns／
46.4ns×100%＝86.2%
?2．以知cache 命中率H=0.98，主存比cache
慢四倍，以知主存存取周期为200ns，求
cache/主存的效率和平均访问时间。
?解：R=Tm/Tc=4；Tc=Tm/4=50ns
?平均访问时间：T
a
=H×T
c
+ (1 – H)
×T
m
=0.98×50ns + (1 – 0.98)×200ns=53ns
?访问效率：e = T
c
/
T
a
=50ns/53ns×100%=94.3%
?3．已知cache/主存系统效率为85%，平均访问时间为60ns，cache比主存快4倍，
求主存存储器周期是多少？cache 命中率是多少？
?解：因为Ta=Tc/e 所以Tc=Ta×e
=60ns×0.85=51ns (cache存取周期)
? r=4,Tm=Tc×r =51×4 =204ns (主存存取周期)
?因为：T
a
=H×T
c
+ (1 – H)
×T
m
=H×51ns + (1 – H)×204ns=60ns
?所以：命中率H=144/153=94%
