第4章 部分习题参考答案
4.1 解释下列术语
? 存储器最大频宽－存储器连续工作时所能达到的频宽。
? 存储器实际频宽－存储器实际工作时达到的频宽，它一般小于存储器最大频宽。 ? 模m交叉编址－交叉访问存储器由多个存储体（m个存储模块）组成一个大容量
的存储器，对多个存储体的存储单元采用交叉编址方式，组成交叉访问存储器。通常有两种交叉编址方式，一是地址的高位交叉编址，一般使用较少转型是低位交叉编址，即由m个存储体组成的低位交叉存储器的存储单元地址的低log2m位称为体号k，高log2n位称为体内地址j，存储单元地址A的计算公式为：A＝m×j×k。若已知地址A，可计算出对应的体号k=A mod m，体内j=[A/m]地址。高位交叉编址主要用于扩展常规主存的容量，而低位交叉编址主要用于提高常规主存的访问速度。
? 程序局部性－程序中对于存储空间90％的访问局限于存储空间的10％的区域中，
而另外10的访问则分布在存储空间的其余90％的区域中。这就是通常说的程序局部性原理。访存的局部性规律包括两个方面，一是时间局部性：如果一个存储项被访问，则可能该项会很快被再次访问；二是空间局部性：如果一个存储项被访问，则该项及其邻近的项也可能很快被访问。
? 虚拟存储器－即“主存－辅存”存储层次，主要目的是为了弥补主存容量的不足，
可以为程序员提供大量的程序空间。其部分功能采用硬件，其余则由操作系统的存储管理软件来实现，对于系统程序员不透明。
? 段式管理－把主存按段分配的存储管理方式。它是一促模块化的存储管理方式，
每个用户程序模块可分到一个段，该程序模块博只能访问分配给该模块的段所对应的主存空间。段长可以任意设定，并可放大和缩小。系统中通过一个段表指明保段在主存中的位置。段表中包括段名（段号）、段起点、装入位和段长等。段表本身也是一个段。段一般是程序模块划分的。
? 页式管理－把虚拟存储空间和实际存储空间等分成固定大小的页，各虚拟页可装
入主存中的不同实际页面位置。页式存储中，处理机逻辑地址由虚页号和页内地址两部分组成，实际地址也分成页号和页内地址两部分，由地址映像机构将虚页号转换成主存的实页号。页式管理用一个页表，包括页号、每页在主存的起始位
置、装入位等。页表是虚页号与物理页号的映射表。页式管理由操作系统进行，对应用程序员是透明的。
? 段页式管理－是段式管理和页式管理的结合，它将存储空间按逻辑模块分成段，
每段又分成若干个页，访问通过一个段表和若干个页表进行。目前大多数操作系统采用段页式对存储器进行管理。
? 地址的映像－对虚拟存储器而言，指多用户程序的虚拟地址与主存地址之间的对
应关系。对于Cache存储器而言，指主存地址与Cache地址之间的对应关系。 ? 地址的变换－对虚拟存储器而言，指按照地址映像规则将多用户程序的虚拟地址
转变为主存地址的过程，包括把多用户的虚拟地址变换成主存实地址（内部地址变换）或磁盘存储器地址（外部地址变换）。对于Cache存储器而言，指按照地址映像规则将主存地址转变为Cache地址的过程。
? 堆栈型替换算法－以任意一个程序的页地址流作为两次主存页面数分配，分另分
配m个主存页面和n个主存页面，并且有mn。如果在任何时刻t，主存页面数集合Bt都满足关系：，则这类算法称为堆栈型替换算法。简单地说，堆栈型替换算法的基本思想是：随着分配给程序的主存页面数增加，主存命中率也提高，至少不下降。
? Cache存储器－即“Cache－主存”存储层次，主要目的是为了弥补主存速度的不
足，通过在CUP和主存之间增加速度快、容量小、价格较高的Cache，它与主存的构成有机整体，来提高访存速度。其功能主要采用硬件来实现，对于系统程序员是透明的。
? 直接映像－主存中的每一块只能被放置到Cache中唯一的一个地方。计算公式
为：，其中，b为Cache块号，B是主存块号，C是Cache的块数。整个Cache地址与主存地址的低位部分完全一样。
? 组相联映像－主存与Cache按同样大小划分成块，还按同样大小划分成组。从主
存的组到Cache的组之间采用直接映像，在两个对应的组内部采用全相联映像方式。
? 写回法－当CPU对Cache写命中时，只修改Cache的内容，而不立即写入主存，
只有当此行被换出时才写回主存。
? 写直达法－当Cache写命中时，Cache与主存同时发生写修改。
? 恒预取法－当CPU访问主存时，无论Cache是否命中，都把紧接着访问字所在块
的下一块从主存中取到Cache中。
? 不命中预取法－当CPU访问存储器时，如果Cache不命中，在把包含访问字的块
取到Cache之后，还把紧接着的下一块也取到Cache中。
? 环保护－将系统程序和用户程序按访问权限分层。最内的几层是系统程序层，其
外的几层为用户程序层，级别由里向外逐层降低。程序各页的环号由操作系统给定，并置入页表，每个程序都规定了一个上限环号，即可访问的最内层的环号。环式保护既能保护用户程序的出错而不破坏系统程序的工作，又能使同一用户程序的外层部分的出错不破坏其内层部分。
? 访问方式保护－对主存信息的使用可以另上读、写和执行3种方式。
4.2 （题目略）
【解】由访问效率计算公式：e?TA1TA11，有??THTA!?(1?H)TA2H?(1?H)TA2/TA10.8?1，得H＝0.9999974999?≈0.9999975。 5H?(1?H)?10显然，这样高的命中率是很难达到的，为了不对H提出过高的要求，可能通过减少相邻两级存储器的访问速度差异，或是减少相邻两级存储器的容量差距来解决，也可以在两级间增加一个中间级来实现。
4.10 （题目略）
【解】（1）（2）采用组相联映像，主存地址和C地址的格式分别如下图所示： 区号E（1位） 组号G（1位） 块号B（1位） 块内地址W(4位) 主存地址格式 组号g（1位） 块号b（1位） 块内地址w(4位) Cache地址格式
Cache有2组，每组2块，Cache容量为4，组号G和g长度为1位，组内块号B和b的长度为1位。
每块大小为16B，如果访存是以字节为寻址单位，块内地址W和w的长度为4位。 主存按Cache大小划分为区，主存容量为8，Cache容量为4，故主存分2个区，区号E的长度为1位。
（3）根据组相联映像规则，主存的组到Cache的组是直接映像，对应的组内块和块之间的全相联映像。因此，主存和Cache空间块的映像对应关系以及对应关系表（√为有关系）分别如下表所示。
第0组 第0区
第1组 第0组 第1区
第1组 B0 B1 B2 B3 B4 B5 B6 B7 C0 C1 C2 C3 实块 0 1 C0 √ √ √ √ C1 √ √ √ √ C2 √ √ √ √ C3 √ √ √ √ 第0组 第1组
主存块 2 3 4 5 6 7 主存块B0, B1, B4, B5只能映射到Cache块C0, C1任意1块上。 主存块B2, B3, B6, B7只能映射到Cache块C2, C3任意1块上。
（4）组相联映像方式，采用LFU替换算法，Cache的块地址流序列如下： P= C0 C1 C2 C3
6 6 入
2 6 2 入
4 4 6 2 入
1 4 1 6 2 入
4 4 1 6 2 中
6 4 1 6 2 中
3 4 1 6 3 替
0 4 0 6 3 替
4 4 0 6 3 中
5 4 5 6 3 替
7 4 5 7 3 替
3 4 5 7 3 中
Cache块命中率H=4/12=1/3
（5）组相联映像方式，采用FIFO替换算法，Cache的块地址流序列如下： P= C0 C1 C2 C3
6 6 入
2 6 2 入
4 4 6 2 入
1 4 1 6 2 入
4 4 1 6 2 中
6 4 1 6 2 中
3 4 1 3 2 替
0 0 1 3 2 替
4 0 0 3 2 中
5 5 4 3 2 替
7 5 4 3 7 替
3 5 4 3 7 中
Cache块命中率H=3/12=0.25
（6）组相联映像方式，采用LRU替换算法，Cache的块地址流序列如下： P= C0 C1 C2 C3
6 6 入
2 6 2 入
4 4 6 2 入
1 4 1 6 2 入
4 4 1 6 2 中
6 4 1 6 2 中
3 4 1 6 3 替
0 4 0 6 3 替
4 4 0 6 3 中
5 4 5 6 3 替
7 4 5 7 3 替
3 4 5 7 3 中
Cache块命中率H=4/12=1/3
（7）全相联映像方式，采用FIFO替换算法，Cache的块地址流序列如下： P= C0 C1 C2 C3
6 6 入
2 6 2 入
4 6 2 4 入
1 6 2 4 1 入
4 6 2 4 1 中
6 6 2 4 1 中
3 3 2 4 1 替
0 3 0 4 1 替
4 3 0 4 1 中
5 3 0 5 1 替
7 3 0 5 7 替
3 3 0 5 7 中
Cache块命中率H=4/12=1/3
全相联映像方式，采用LRU替换算法，Cache的块地址流序列如下： P= C0 C1 C2 C3
6 6 入
2 6 2 入
4 6 2 4 入
1 6 2 4 1 入
4 6 2 4 1 中
6 6 2 4 1 中
3 6 3 4 1 替
0 6 3 4 0 替
4 6 3 4 0 中
5 5 3 4 0 替
7 5 7 4 0 替
3 5 7 4 3 替
Cache块命中率H=3/12=0.25。
（8）若在程序执行过程中，每从主存装入一块到Cache，平均要对这个块访问16次。总的访问次数为：12*16=192，而其中有8次是不命中Cache的，其余则为命中Cache的。所以Cache存储单元命中率为H=（12*16-8）/（12*16）≈95.8%
4.17 （题目略）
【解】（1）增大主存容量对Cache的访问时间基本不影响，从而对Cache的等效访问速度基本不影响。
（2）增大Cache的块数（块的大小不变）一般使Cache的命中率上升，从而使下降，并提高Cache的等效访问速度。
（3）增大组组相联的大小（块的大小不变）一般使Cache的命中率上升，从而使下降，并提高Cache的等效访问速度。
（4）增大块的大小（组的大小和Cache总容量不变）一般将使下降，从而提高Cache的等效访问速度。
（5）提高Cache本身器件的访问速度一般将缩短，从而提高Cache的等效访问速度。