以下习题来自计算机系统结构存储体系

以下习题来自《计算机系统结构》第七章 存储体系。

7．1解释下列术语

直接映像：每个主存地址映像到Cache中的一个指定地质的方式称为直接映像。 全相联映像：任何主存地址可映像到任何Cache地址的方式称为全相联映像。

组相联映像：组相联映像指的是将存储空间的页面分成若干组，各组之间是直接映像，而组内各块之间是全相联映像。

全写法：全写法也称直达法，即写操作将数据同时写入Cache和缓存。

写回法：写Cache时不写主存，仅当被写Cache数据块要被替换出去时才写回主存。 虚拟存储器：虚拟存储器是主存的扩展，当主存的容量不能满足要求时，数据可存放在外存中，在程序中仍然按地址访问外存空间。大小取决于计算机的访存能力。 段式管理：把主存按段分配的存储管理方式称为段式管理。 页式管理：把虚拟存储空间和实际存储空间等分成固定大小的页，各虚拟页可装入主存中不同的实际页面位置。 段页式管理：段页式管理式段式管理和页式管理的结合，他将存储空间按逻辑模块分成段，每段又分成若干个页，访存通过一个段表和若干个页表进行。段的长度必须是页的长度的整数倍，段的起点必须是某一页的起点。 快表：为了提高页表中常用项的访问速度，采用快速硬件构成的比全表小的多的部分表格。 慢表：存放在主存中的整个页表。 高速缓存：高速缓冲存储器是位于CPU和主存之间的高层存储子系统。 时间局部性：如果一个存储项被访问，则可能该项会很快再次被访问。 空间局部性：如果一个存储项被访问，则该项及其邻近的相也可能很快被访问。 段表：在对虚拟内存进行管理时，系统中用于指明各段在主存中的位置的表，表中包括段名或段号、段起点、装入位和段长等。 页表：在对虚拟内存进行管理时，系统中用于指明各页在主存中的位置的表，表中包括页号、每页在主存中的起始位置、表示该页是否已装入主存的装入位等。 块表：存储系统中的一个用于解决块和页的定位、标志、和寻址问题的表。 7.2 有人认为,随着存储器芯片集成度的提高，主存的容量将越来越大，虚拟存贮器将被淘汰，未来的计算机中将不采用虚拟存储器。你是否同意这种观点，为什么? 答：我不同意这种观点，尽管主存的容量越来越大，但是，随着计算机技术的不断发展，应用程序所需要的存储空间也会不断地增大，而且由于计算机的成本等问题，注定主存的容量不可能完全满足应用程序的所用需要，所以虚拟存储器作为主存的一个重要补充，仍然将是计算机中不可或缺的一部分，不会被淘汰。 7.3编译程序怎样利用系统中的Cache进行代码优化以提高系统的性能？ 答：应该将常用到的指令、变量尽量地存放在主存的相邻单元，这样可以使他们一次被读入Cache，从而提高读Cache的命中率来提高系统的性能。另外，应该将对同一变量的操作尽可能地集中起来完成，以免该变量因为反复地被读入和读出而增加执行额外的时间。 7.4试写出两层和三层Cache的平均访问时间公式。

解：

（I）两层Cache的情况：

设Cache的命中时间是TC，命中率是HC，失效时间为TM。则平均访存时间

TA=TC*HC+(1-HC)(HC*TC+(1-HC)*TM)

（II）三层Cache的情况：

TA=TC*HC+(1-HC)(HC*TC+(1-HC)(HC*TC+(1-HC)*TM)) 1

少年易学老难成，一寸光阴不可轻 -

7.5 VAX-11/780在Cache命中时的指令平均执行时间是8.5时钟周期，Cache失效时间是6个时钟周期，假设不命中率是11%，每条指令平均访存3次。试计算在考虑了Cache的不命中时的指令平均执行时间。它比Cache命中时的平均指令执行周期延长了百分之几？

解：由题设可知：考虑了Cache的不命中时的指令平均值执行时间

TA=%*8.5+11%*(8.5+6)=9.16(时钟周期)，

与Cache命中时的平均指令执行周期延长了

（9.16-8.5）/8.5*100%=7.76%

7.6上题中若CPU在Cache命中时的指令平均执行时间是1.5个时钟周期，如RISC计算机中的那样，其它条件一样，结果如何？从中可看出什么问题?

解： TA=%*1.5+11%*(1.5+6)=2.16 与Cache命中时的平均指令执行周期延长了 (2.16-1.5)/1.5*100%=44% 可以看出：当CPU的速度较快时，Cache的速度将成为影响系统速度的主要因素，也就是成为速度的瓶颈。 7.7有一个“Cache-主存”存储层次。主存共分8个块（0~7），Cache为4个块（0~3），采用组相联影像，组内块数为2块，替换算法为近期最少使用法（LRU）。 （1） 画出主存、Cache空间块的影像对应关系的示意图； （2） 对于如下主存块地址流：1、2、4、1、3、7、0、1、2、5、4、6、4、7、2，如主存中内容一开始未装入Cache中，请列出随时间变化的Cache中各块的使用状况； （3） 对于（2），指出块失效又发生块争用的时刻； （4） 对于（2），求出此期间Cache的命中率。 解： （1） 主存、Cache空间块的映象对应关系示意图如下： 2

少年易学老难成，一寸光阴不可轻 -

0 1 I组 0 2 I组 1 3 II组 2 4 II组 3 5 I组 6 7 II组

（2） 地址流入体所示时，主存中内容如下表： 2 4 1 3 7 0 1 2 5 4 6 4 7 2 寄1 存器号 0 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 1 - - 4 4 4 4 0 0 0 5 5 5 5 5 5 2 - 2 2 2 2 7 7 7 7 7 7 6 6 6 2 3 - - - - 3 3 3 3 2 2 2 2 2 7 7 （3） 在（2）中，时刻1、2、3、5、6、7、9、10、11、12、14、15发生块失效， 时刻6、7、9、10、11、12、14、15发生块争用。 （4） 此间，共有15个时刻，命中了4、 8、13这3个时刻，所以命中率为20%。 7.8在页式管理虚拟存储器中，假定各页面按以下的顺序请求访问： 12、14、2、34、56、23、14、56、12、12 并且主存中只能容纳4个页面，列出使用下列各种算法时，每一个页面调度操作后在主存中的页面： （1） 先进先出替换算法； （2） 最近最少使用替换算法； （3） LRU的计数法替换算法。 并指出什么时刻发生页面失效。 解：（1）主存中的内容如下图所示： 12 14 2 34 56 23 14 56 12 12 0 12 12 12 12 56 56 56 56 56 56 1 - 14 14 14 14 23 23 23 23 23 2 - - 2 2 2 2 14 14 14 14 3 - - - 34 34 34 34 34 12 12 2 3 4 5 6 7 8 9 10 时刻 1 在时刻1、2、3、4、5、6、7、9发生页面失效。

（2） 存中的内容如下图所示： 12 14 2 34 56 23 0 12 12 12 12 56 56 1 - 14 14 14 14 23 1 - - 2 2 2 2 3 - - - 34 34 34 2 3 4 5 6 时刻 1 在时刻1、2、3、4、5、6、7、9发生页面失效。 3

14 56 23 14 34 7 56 56 23 14 34 8 12 56 23 14 12 9 12 56 23 14 12 10 少年易学老难成，一寸光阴不可轻 -

（3）主存中的内容如下图所示： 12 14 2 34 0 12 12 12 12 1 - 14 14 14 1 - - 2 2 3 - - - 34 2 3 4 时刻 1 56 56 14 2 34 5 23 56 23 2 34 6 14 56 23 14 34 7 56 56 23 14 34 8 12 56 23 14 12 9 12 56 23 14 12 10 在时刻1、2、3、4、5、6、7、9发生页面失效。

7.10当访问页面已知时，怎样实现最佳替换算法，请提出你的建议。

答：我认为应该将访问序列中访问较多的块在主存种分配以固定的位置，不调出主存。其余那些在整个访问过程中只被访问一两次的块才进行替换。这样可使访问的命中率有显著提高。 7.12 Cache C1是直接映射的，有16个长度为1字的快；Cache C2是直接映射的，有4个长度为4的块，假设C1的不命中的访问时间为8个时钟周期；C2的不命中的访问时间11个时钟周期，初始时Cache为空，举出一种使C2命中率较高，但访问周期较长的字地址序列。 解：序列1、5、9、2、3、4、6、7、8、10、11、12、17、25、18、19、20、33、26、27、28、34、35、36满足上述条件，因为，C2在访问2、3、4、6、7、8、10、11、12、18、19、20、26、27、28、34、35、36时不必从主存中调入。 7.14对于以下三种Cache组织： Cache1：直接映射，块长为1字 Cache2：直接映射，块长为4字 Cache3：两路组相联映射，块长位4字 假设一下失效率： Cache1：指令失效率4%，数据失效率为8% Cache2：指令失效率2%，数据失效率为5% Cache3：指令失效率2%，数据失效率为4% 对于这几种机器，一般的指令包含一个数据访问。假定Cache不命中访问时间为6加上块的字节数，指出哪一种机器在Cache失效上花费的时间最多？ 解：对于Cache1失效一次花费时间为6+1=7； 对于Cache2和Cache3失效一次花费时间为6+4=10； 又因为它们的失效率为8：4：5，所以它们的失效花费时间为（4+2*8%）*7；（2+1*5%）*10；（2+1*4%）*10，花费时间比为29.12：20.05：20.04，可见第一种机器在Cache失效花费时间最多。 7.15假设机器的时钟周期位10豪微秒，Cache失效时的访存时间为20个时钟周期 （1） 设失效率为0。05，忽略写操作时的其它延迟，求机器的平均访存时间 （2） 假设通过增加Cache的容量一倍而使时效率降低到0.03，但使得Cache命中时的访

问时间增到了1.2时钟周期，指出这样的改动设计是否合适。

（3） 如果时钟周期取决于Cache的访问时间（也就是用延长时钟周期的方法），上述改

动设计是否合理 解：

（1）机器的平均访存时间为10*（1*0.95+20*0.05）=19.5毫微秒；

（2）改动以后机器的平均访存时间为10*（1.2*0.97+20*0.03）=17.毫微秒，可见改动是合理的。

（3）如果采用延长时钟周期的方法，平均访存时间为10*1.2*(1*0.97+20*0.03)=18.844

少年易学老难成，一寸光阴不可轻 -

毫微秒。也是合理的。

7.16假设存储器系统采用50MHZ时钟，存储器以每周其一个字的速率，传输8个字的访问请求，以支持块长为8个字的Cache， 对于读操作，访问顺序是：

1个周期接收地址 3个周期延迟

8个周期用于传输8个字 对于写操作，访问顺序是：

1个周期接收地址 2个周期延迟 8个周期用于传输8个字 对于以下访问模式： 全部访问为读操作 全部访问为写操作 65%的访问为读操作，35%的访问为写操作 求出该存储器的最大带宽（以每秒字节数表示）。 解：假如访问模式为全读操作： 每秒可进行50M/12=4166667次操作。传输字节数为33333333，最大带宽为33333333字节/秒。 假如访问模式为全写操作： 每秒可进行50M/11=4545455次操作。传输字节数为36363636，最大带宽为36363636字节/秒。 假如访问模式为65%读操作和35%写操作。每秒进行27699次读操作和1502145次写操作，传输字节数为34334763，最大带宽为34334763字节/秒。

以下习题来自《计算机组成原理教程》第3章 存储体系。 3.1试说明存储器的存取时间与存取周期的区别。 答：存取时间分为读出时间和写入时间，读出时间是从开始送入地址到这个存储器产生有效数据输出所花费的时间；写入时间是从送入地址开始并把有效数据保持一定时间所花费的时间。存取周期是指先读出一个单元的数据，随后又将一个数据写入该存储地址单元操作所需的最小时间。

3.2存储器的带宽有何物理意义？设存储器数据总线宽度为32位，存取周期为250ns，5

少年易学老难成，一寸光阴不可轻 -

这个存储器的带宽是多少？ 解：存储器的带宽是指每秒中访问的二进制的位的数目。题中的存储器每秒可访问的二进制数为32×（1000000÷250）＝128000bps。

3.3存储系统的层次结构的存储系统可以解决什么问题？实现存储器层次结构的先决条件是什么？如何度量？

答：层次结构的存储器可以解决价格、容量、速度这三者之间的矛盾。上层存储器的速度快但是价格高，容量小；下层存储器的速度相对较慢，但是成本低，容量大。而层次结构的存储器的存储速度接近于最上层，容量及其成本却是接近于最下层的。

实现存储器层次结构的先决条件是平均存取时间应该能满足程序的需要，可以根据上、下层存储器的存取时间和上层存储器的命中率计算出平均存取时间来进行度量。 3.5设计一个用K×1位的芯片构成256K×16位的存储器，画出组织结构图。 解：如下图所示：先用K×1位的芯片构成K×16位的存储器，再用K×16位的存储器构成256K×16位的存储器。 6

少年易学老难成，一寸光阴不可轻 -

地址总线

CS

。。。。。。。。。。。。。。。 R/W 数据总线

上图为16K×16的存储器框图。 A17 片选译码器 A16 A0~A15 地址总线 CS CS CS CS CPU K×16 K×16 K×16 K×16 R/W R/W R/W R/W RD 控制总线 双向数据总线 上图是256K×16位的存储器框图。 3.11 在8体交叉主存系统中，若每体并行读出两个字，每字长两字节，主存周期为T，求改该存储器的最大带宽。 解：最大带宽为：2×8×8÷T=128/T（比特/秒）。 3.13主存储器容量为4MB，虚拟存储器容量为1GB，则虚拟地址和物理地址各为多少位？根据寻址方式计算出来的有效地址实虚拟地址该是物理地址？ 解：虚拟地址为30位，物理地址为22位，根据寻址方式计算出来的是物理地址。 3.14假设可供用户程序使用的主存容量为100KB，而某用户的程序和数据所占的主存容量超过100KB，但小于逻辑地址所表示的范围，请问具有虚拟存储器与不具有虚拟存储器对用户有何影响？

答：如果用户具有虚拟存储器，则该用户仍然可以使用这个程序，否则由于存储器的容量不够，用户将无法使用该程序。

3.15在上题中如果页面大小为4KB，页表长为多少？ 解：页表长度为：100÷4＝25字节。

3.16术语：存储元、存储单元、存储体、存储单元地址，有何区别与联系？ 答：存储元指的是存储器中用于存储信息的一个一个的小磁环，它是一个物理范畴中的概念；存储单元指的是存储器中被当作一个整体对待的一些存储元；存储体指的是整个存储7

少年易学老难成，一寸光阴不可轻 -

器；存储单元地址则指的是在存储体中用于寻找存储单元的信息。

3.17在虚拟存储器中，术语物理空间、逻辑空间有何区别与联系？ 答：在采用虚拟存储器的计算机中，在访问存储器时都不是直接根据程序员制定的地址进行的。CPU根据程序指令生成的地址是虚拟地址有成逻辑地址，它指向的空间称为逻辑空间，经过转换后的地址是实际地址，指向的是实际物理空间；虚拟地址空间是程序员所看到的地址空间，实际地址空间则是程序虚拟地址空间在存储器中的实际物理映射。

以下习题来自《计算机组成和系统结构》第3章 存储体系。

1．一台计算机的主存容量为1MB，字长为32位，cache的容量为512字。确定下列情况下的地址格式。 （1） 直接映像的cache，块长为1字； （2） 直接映像的cache，块长为8字； （3） 组相联映像的cache，块长为1字，组内4块。 解：（1）cache地址如下： 块号 因为块长为1字，所以不需要块内地址。 主存地址如下： 块号 （2）cache地址如下： 主存块号 块内地址 Cache中有16个块，所以块号为4位，块内地址为3位，指出是8块中的哪一块。 主存地址如下： 主存块号 块内地址 （3）cache地址如下： 组号 块号 因为块长为1字，所以不需要块内地址只需有组号和块号就足够了，共有128个组，所以组号为7位，块号有2位 主存地址如下： 区号 组号 主存块号 4.一个组相连映象cache由个存储块构成，每组包含4个存储块。主存包含4096个存储块，每块有128字组成。访存地址为字地址。 （1） 求一个主存地址有多少位？一个cache地址有多少位？ （2） 计算机主存地址格式中，区号，组号，块号和块内地址字段的位数。 解：由题可知：主存地址一共包括6位区号，4位组号，2位块号，7位块内地址，共19位，cache地址一共包括4位组号，2位块号，7位块内地址，共13位。

5．考虑一个具有16KB 4路组相连cache的32位微处理器，假定该cache的块为4个32位的字。

（1） 画出该cache的结构逻辑图，指出主存地址的不同字段的作用。 （2） 主存地址为ABCDE8F8的单元在cache中的什么位置？ 解：cache结构逻辑图如下所示：

8

少年易学老难成，一寸光阴不可轻 -

含有4个32位字的块 第0组 。 。 。 。 第十五组 主存地址为ABCDE8F8，可知区号有10位，组号4位，主存块地址16位，块内字地址2位，所以主存地址为ABCDE8F8的单元在cache 中位第3组中某一块的第0个字。 9．假设cache的工作速度为主存的5倍，且cache被访问命中的概率为90％，则采用cache后存储器性能提高了多少？ 解：设cache的访存时间位T1,则不用cache 的平均访存时间为： 5×T1 而采用cache的平均访存时间为： 90％×T1+10%×5×T1=1.4T1 性能提高了（5－1.4）/5×100％=72% 16．试分别写出简单写回法cache 在按写分配法和不按写分配法的情况下的平均访问时间表达式 。 解：设 cache的命中率为H1,写 cache时间为T1 ,cache失效时间为T3,写主存时间为T2, 在按写分配法情况下，平均访问时间为： H1×T1+(1-H1)×(T3+T1) 在不按写分配法情况下，平均访问时间为： H1×T1+(1-H1)×T2 9