1． 有一个两层的存储器层次结构：M1和M2。M1的命中率用h表示，并分别令c1和c2为每千字节的成本，s1和s2为存储器容量，t1和t2为存取时间。

（a）在什么条件下，整个存储器系统的平均成本会接近于c2？

（b）该层次结构的存储器有效存取时间Ta是多少？

（c）令两层存储器的速度比r=t2/t1，并令E=t1/Ta为存储系统的存取效率。试以r和h来表示E。

（d）如果r=100，为使 E>0.95，要求的命中率h是多少？

解：（a）总成本Tc=s1*c1+s2*c2；

平均成本Ac=Tc/(s1+s2)=(s1*c1+s2*c2)/(s1+s2)；

所以，当s1<，且s1*c1<时，Ac－>s2*c2/s2=c2。

（b）Ta=h*t1+(1－h)*t2。

（c）E=t1/Ta=t1/[h*t1+(1－h)*t2]=1/[h+(1－h)*r]。

（d）r=100，即要求1/(100－99h)>0.95

得h>0.9995。

2．有关标量RISC或超标量RISC处理机设计的问题：什么是大型寄存器堆和大型D高速缓存之间的折衷设计方案？为什么在超标量处理机中需要有保存站或排序缓冲器？

解：折衷方案可以采用同时使用一个大寄存器堆和分开的I和D高速缓存，这样有利于内部数据定向，而且可以省去多余的中间结果的不必要的存储。

保存站和重排序缓冲器可用于建立指令窗口，目的是为了支持指令先行和内部数据定向，这对于调度多条指令同时通过多条流水线是必须的。

3．求完成一个两层存储系统的容量设计。第一层M1是高速缓存，其容量有三种选择：64K字节、128K字节和256K字节。第二层M2是主存储器，其容量为4M字节。分别令c1和c2是每个字节的成本，t1和t2是M1和M2的存取时间。假定c1=20c2和t2=10t1，三种容量高速缓存的命中率分别为0.7，0.9和0.98。

（a）在t1=20ns的条件下，三种高速缓存的平均存取时间Ta是多少？（注意：t1是从CPU到M1的时间。t2是从CPU到M2的时间，不是从M1到M2的时间）。

（b）如果c2=0.2美元/K字节，试说明整个存储器层次结构的平均字节成本。

（c）对三种存储器的设计作一比较，并分别按平均成本和平均存取时间指出它们性能的排列次序。再根据平均成本和平均存取时间的乘积，选择最佳设计。

解：（a）t1=20ns，t2=10t1=200ns；

M1=64K，　h=0.7， Ta=h*t1+(1－h)*t2=74ns

M2=128K， h=0.9， Ta=h*t1+(1－h)*t2=38ns

M3=256K， h=0.98，Ta=h*t1+(1－h)*t2=23.6ns

（b）c2=0.2美元，c1=20c2=4美元/K字节；

M1=64K， c=(c1*s1+c2*s2)/(s1+s2)=0.26美元/K字节

M2=128K， c=(c1*s1+c2*s2)/(s1+s2)=0.32美元/K字节

M3=256K， c=(c1*s1+c2*s2)/(s1+s2)=0.42美元/K字节

（c）按平均成本：64K―>128K―>256K 成本增加

按存取时间：256K―>128K―>64K 存取时间增加

乘积：mul1=19.24，mul2=12.16，mul3=9.912

所以最佳设计应该是256K方案

4．解释有关术语：虚拟地址空间、物理地址空间、地址映象、高速缓存块、多级页表

解、虚拟地址空间：也称虚存空间或虚拟存储器空间，它是应用程序员用来编写程序所使用的地址空间，这个地址空间一般比较大。

物理地址空间：主存储器中的所有存储字构成存储空间。

地址映象：在不同地址空间进行转换的方式。比如把虚拟地址空间映象到主存地址空间，具体地说，就是把用户用虚拟地址编写的程序按照某种规则装入到主存储器中，并建立多用户虚地址与主存实地址之间的对应关系。

高速缓存块：高速缓存被分成高速缓存块，又称高速缓存行，是高速缓存和主存储器间数据传送的单位。

多级页表：页表是用于虚拟地址转换为主存地址而使用的存储结构，由于虚拟地址空间很大，单级页表往往很长，占去了很大部分主存空间。多级页表就是为了减小页表在主存中的空间而设置的。但多级页表生成所需的物理地址要站占用较长的时间，这是因为要访问一系列页表，需要做多次存储器访问。

5．讨论采用指令与数据合一的高速缓存和分开的高速缓存的优缺点。

解：指令与数据合一的高速缓存必须共享同一条数据/指令通路，它简化了硬件系统，但在流水线操作中会造成读写和写读冲突，降低了流水线的效率。

指令与数据分开的高速缓存，又称哈佛结构，这样对高速缓存的访问可以使用不同的存取通路，提高了流水线的效率，同时增加了硬件设计的难度。

6．解释有关术语：命中率、缺页、散列函数、倒置页表和存储器访问策略、高速缓存冲洗策略、影响高速缓存命中率的因素。

解：命中率：命中率是为存储器层次结构中从某一层存储器中能访问到所需信息的概率，当在Mi中找到一个信息项时，称之为命中，反之称之为缺失。

缺页：如果所要访问的页在PT（页表）中找不到，也就是说该页面没有调入主存中，则称为缺页。

散列函数：是用较少位数把长页号转换为短页号，以建立起主存页号和虚拟存储器页号间的对应关系的函数关系。

倒置页表：倒置页表只包括当前驻留在物理存储器的虚拟页面，有效减少了页表的大小，地址转换映象用倒置映象实现，且其大小是由物理空间的大小决定的。

存储器替换策略：存储器替换策略指的是为活动进程分配与再分配存储器页面以及如何对存储器中的页面进行替换。

高速缓存冲洗策略：多个进程可能会使用同一个虚拟地址范围，如果两个或多个进程访问高速缓存同一个物理单元时，那么这种别名问题可能会造成混乱，解决别名问题的一种办法是每当发生别名使用时，将整个高速缓存冲洗一遍。

影响高速缓存命中率的因素：高速缓存的命中率将以不同的方式受到高速缓存容量与块大小的影响。在组联想高速缓存中，组数的影响也是明显的。

7．试说明多层次存储器层次结构的包含性和存储器一致性要求，以及写直达和写回策略在保持相邻层一致性方面的区别。

解：设Mi为第i 层存储器。包含性表示为在Mi中能够找到的数据，在Mi+1不一定能找到，但在Mi+1中能够找到的数据，在Mi一定能找到。也就是说所有信息项最初是存放在最外层M1的。

一致性要求指的是同一个信息项在各个存储器层次上的副本是相同的。

写直达是指：如果在Mi+1修改了一个字，则在Mi中需要立即修改。

写回是指：数据在Mi+1中修改后，并不立即修改Mi中的原本，而是等到Mi+1中的该数据项被替换时，才对Mi中的原本进行修改。

8．试说明分页与分段在层次结构中管理物理与虚拟存储器的基本概念。

解：分页：是一种把物理存储器和虚拟存储器都划分为固定大小页面的技术。它们之间的信息交换的单位是页。页表用于主存页号和虚拟存储器页号之间的映象，它们是应用程序创建用户进程时在主存储器内实现的。

分段：段是为了便于用户共享程序段而设置的，它是用户定义的虚拟地址空间的一部分。一个段可以由若干个页面组成，也可以由一个页面组成，也可以是多个段组成一个页面。分段往往会带来许多页面不能充分使用，留下许多碎片。

9．试说明在存储器层次结构中与程序/数据存取有关的时间局部性、空间局部性和顺序局部性。

解：时间局部性：最近的访问项（指令或数据）很可能在不久的将来再次被访问。这种情况一般是由特殊的程序结构诸如迭代循环、进程堆栈、暂时变量或子程序引起的。一旦进入循环或调用了子程序，一个短代码段将被重复访问许多次。因此，时间局部性往往会引起对最近使用区域的集中访问。

空间局部性：指的是一个进程访问的各项其地址彼此很近，也就是说刚访问的数据块邻近的数据块很快会被访问。例如，表操作或数组操作就会对地址空间中某一区域集中进行访问。

顺序局部性：指的是在程序中，接连排列的指令会按排列次序访问。在典型程序中，除非转移指令和子程序调用指令产生不按次序的转移外，指令都是顺序（或程序顺序）执行的。

10．一个两层存储器系统有8个磁盘上的虚拟页面已被影射到主存储器的4个页面框架（PF）中。某程序产生以下的页面踪迹：1，0，2，2，1，7，6，7，0，1，2，0，3，0，4，5，1，5，2，4，5，6，7，6，7，2，4，2，7，3，3，2，3

（a）根据上述页面踪迹采用LRU替换策略指出驻留在4K页面框架中的相继虚拟页面。计算在主存储器中的命中率。假定PF最初是空的。

（b）采用环形FIFO页面替换策略，重复（a）。计算在主存储器中的命中率。

（c）比较（a）和（b）中的命中率并根据这一特定的页面踪迹对环形FIFO策略的效果比较接近LRU策略作一评论。

解：（a）（b）

（c）对本题中的特定页面序号来说，两种替换策略的命中率相同。环形FIFO策略近似于用简单环形队列来实现LRU，其性能介于LRU和FIFO之间。但是，任何策略与其他策略相比，由于其性能还与程序本身和页面框架的运行状态有关，因而都没有绝对的优势。

11．什么是工作集？试评述观察窗口大小对工作集大小的灵敏度。这对主存储器命中率将有什么影响？

解：工作集：在一个给定的时间段（窗口）内被访问的地址（或页面）子集称为工作集。当窗口到达一定大小，工作集不会有显著的变化；但由于存在着访问局部性，因而不会产生大量的缺失，提高了主存储器的命中率。

12．什么是90－10规则？它和访问局部性的关系如何？

解：90－10规则就是指典型程序在其90%的时间上用于执行10%的代码，例如嵌套循环操作的最内层循环就是这种代码。这个规则从程序执行的角度描述了访问的局部性，即存储器的存取在时间、空间和次序上往往都集中在一定范围内进行。

13．设有一个两层存储器层次结构M1和M2，存取时间、每个字成本和容量分别是t1和t2、c1和c2以及s1和s2。在第一层，高速缓存的命中率h1=0.95（注意，t2是CPU和M2之间的存取时间，而不是M1和M2之间的存取时间）。

（a）推导表示该存储器有效存取时间T的公式。

（b）推导表示该存储器总成本的公式。

（c）假设t1=20ns，t2是未知数，s1=512字节，s2是未知数，c1=0.01美元/字节，c2=0.0005美元/字节。高速缓存和主存储器总成本的上限是15000美元。

（i）在不超过预算限制的范围内，可能得到M2的容量有多大（s2=？）？

（ii）在上述命中率假设的条件下，为使整个存储器系统的有效存取时间T=40ns，主存储器应该有多快（t2=？）？

解：（a）有效存取时间Ta=h1*t1+(1－h1)*t2=0.95*t1+0.05*t2

（b）总成本TC=c1*s1+c2*s2

（c）（i）Cost=c1*s1+c2*s2=0.01*512+0.0005*s2≤15000

得 s2≤28.6M

（ii）T=0.95*t1+0.05*t2=0.95*20+0.05*t2=40

得 t2=420ns

14．试比较以下和高速缓存结构有关的术语：低位交叉存储与高位交叉存储、物理地址与虚拟地址高速缓存。

解：低位存储器交叉存取：是一种存储器地址分配方式，存储器地址的低a位用来指明存储器模块，高b位则是每个模块内的字地址。高位交叉存储器存取：也是一种存储器地址分配方式，存储器地址的高b位用来指明存储器模块，低a位则是每个模块内的字地址。

物理地址与虚拟地址高速缓存的比较：当可用物理地址对高速缓存进行访问时，则称其为物理物理地址高速缓存。当高速缓存的索引或标记用虚拟地址表示时，则称其为虚拟地址高速缓存。

15．试比较以下和高速缓存设计有关的术语：写直达与写回策略、可高速缓存与不可高速缓存数据、私用高速缓存与共享高速缓存。

解：写直达与写回高速缓存的比较：写直达策略是指对高速缓存的数据块修改后，立即更新主存储器中的原本。写回策略则是等到高速缓存中的该数据块替换时，才将数据写入主存储器。

可高速缓存与不可高速缓存数据的比较：可写的共享数据不存放在本地高速缓存中，这称为共享数据是不可高速缓存数据，只有指令和私有数据可以存放在本地高速缓存中。共享数据包括锁、进程队和由临界区保护的任何其它数据结构。编译器必须将数据标记成为可以存放在高速缓存和不可高速缓存两种，而且还必须使用专门的硬件标记来加以区别。

私用高速缓存与共享高速缓存的比较：私用高速缓存为本地处理机所独有。共享高速缓存为各处理机所共享，有利于彻底解决高速缓存的一致性。

16．假定一个高速缓存（M1）和存储器（M2）的层次结构有以下性能：

M1：16K字，存取时间为50ns。 M2：1M字，存取时间为400ns。高速缓存块为8个字，组的大小为256个字，采用组联想映射；

（a）表示出M2与M1之间的映射关系；

（b）计算高速缓存命中率h=0.95时的有效存储器存取时间。

解：（a）M1：块数B=16K/8=2K，组数G=16K/256=64，路数k=256/8=32

M2：块数B=1M/8=128K，区数A=1M/16K=64，块号为b的主存储器在高速缓存中的地址为：(b%2k)/64组中32块的其中一块。

（b）Ta=t1*h+t2*(1－h)=50*0.95+400*0.05=67.5ns

17．一个单处理机系统使用分开的指令高速缓存和数据高速缓存，它们的命中率分别是hi与hd。从处理机到每个高速缓存的存取时间是c个时钟周期，高速缓存与主存储器之间块的传送时间是b个时钟周期。

在CPU进行的所有访存操作中，fi是访问指令的百分比，在高速缓存内所有的替换块中，fdir是页面重写块的百分比（页面重写是指高速缓存的副本与存储器的副本不同）。

假定用写回策略，试根据本存储器系统的hi，hd，c，b，fi及fdir确定有效存储器存取时间。

解：Ta=fi*[hi*c+(1―hi)*(c+b)]+

(1―fi)*[hd*c+(1―hd)*(c+b)(1－fdir)+(1―hd)*fdir*(2b+c)]

18．利用17题中所讨论的处理机存储器系统，构造一个基于总线的共享存储器多处理机。假定命中率与存取时间保持与17题相同。但是，由于每台处理机现在必须处理除读与写之外的高速缓存无效问题，因此有效存储器存取时间将是不一样的。

设finv是造成无效信号向其他高速缓存发送的数据访问的百分率。处理机发送无效信号并需要i个时钟周期去完成无效操作。其他处理机则与无效过程无关。假定仍然使用写回策略，试确定该处理机的有效存储器存取时间。

解：T= fi*[hi*c+(1―hi)*(c+b)]+

(1―fi)*[hd*c+(1―hd)*(c+b)(1－fdir)+(1―hd)*fdir*(2b+c)]

T’=T+(1－fi)*finv*i

19．设有一个主存储器，它包含4个存储器模块，每个模块有256个字。再假定每个高速缓存块中有16个字，高速缓存的总容量是256个字。使用组联想映射将高速缓存块定位到块框中。高速缓存被分成4组。

（a）说明在主存储器的4路低位交叉存取结构中全部1024个字的地址分配。

（b）主存储器有多少块？高速缓存有多少块框？

（c）说明在两层存储器系统中对每个字进行寻址所需的位字段。

（d）表示出从主存储器的块到高速缓存的组的映射关系，并解释如何利用标记字段在每组范围内定位一个块框。

解：（a）设主存地址为Addr，则其在第（Addr%4）个模块中，模块内的偏移地址为（Addr/4）。

（b）主存储器有64块，高速缓存有16块框。

（c）主存储器地址为：标记为高4位，2位组地址，4位字地址

（d）设主存地址为addr，则其在高速缓存的第（（addr/16）%4）组，将标记字段与本组的4个标记进行比较，有一致的，则命中此块框。

20．假定有一个处理机台数为p的共享存储器多处理机系统。设m为典型处理机每条指令执行时对全局存储器进行访问的平均次数。

设t为共享存储器的平均存取时间，x为使用本地存储器的单处理机MIPS速率。再假定在多处理机的每台处理机上执行n条指令。

（a）根据参数m，t，x，n和p，确定多处理机的有效MIPS速率。

（b）假设一台多处理机有p=32台RISC处理机，m=0.4，t=1us，要使多处理机的有效性能达到56MIPS，需要每台处理机的MIPS速率是多少（即x=？）？

（c）假设有p=32台CISC处理机用在上述多处理机系统中，每台处理机的x=2MIPS、m=1.6、t=1us，试问多处理机系统的有效MIPS速率是多少？

解：（a）有效MIPS速率=p*x/(1+m*x*t)

（b）32*x/(1－0.4*x*1)=56，得x=5.83

（c）有效MIPS速率=p*x/(1+m*x*t)=32*2/(1+1.6*2*1)=15.24

21．解释以下术语：原子与非原子存储器存取、存储器带宽与容错。

解：原子存储器存取：如果存储器更新时为所有处理机所知道，那么这就是原子共享存储器访问。非原子存储器存取：在基于高速缓存/网络的多处理机中，如果一个更新操作不能同时到达所有的处理机，那么就是非原子的。

存储器带宽：存储器模块每个存储周期可以提供的存储字数。存储器容错：在一个存储体中，当检测出一个模块故障时，可以将发生故障的存储器模块隔离开，剩下的模块仍然可以在地址空间中使用。

22．试比较四种高速缓存组织的优缺点：

（1）直接映射高速缓存 （2）全联想高速缓存

（3）组联想高速缓存 （4）区段映射高速缓存

解：（1）直接映射的优点在于硬件比较简单，不需要联想查找，不需要页面替换算法，因而成本较低且速度较高。缺点是命中率较低，而且它还禁止并行虚拟地址转换。

（2）全联想的优点是提供最大的灵活性，可以实现较好的块替换策略，以减少块的冲突。缺点是检索过程昂贵，需要的硬件成本比较高。

（3）组联想可以提供较好的性能价格比，替换策略可以更加经济地实现，联想检索实现容易，设计灵活可以获得更高的高速缓存的命中率。

（4）区段映射的优点在于，实现各种块替换算法比较灵活和对有限数量区段标记完成全联想检索比较经济。

23．试解释下列有关存储管理的术语：OS内核中存储管理程序的作用、抢先和非抢先存储器分配策略。

解：存储管理程序监控主存储器可用部分的数量，并且决定哪些进程应该留在主存储器中以及主存储器达到极限时哪些进程应该放回到磁盘上去。

抢先分配策略可把一个输入块放到目前已被其他进程所占用的区域内，提供较大的灵活性，但要更为复杂一些，实现时要花更大的代价。

非抢先分配策略，输入块只能放在主存储器的一个空的区域内，实现比较容易，但它不能使存储器得到最好的利用。

24．试根据硬件复杂性和实现的成本排出四种高速缓存组织的次序并说明理由。

解：按直接映射高速缓存——>区段映射高速缓存——>组联想高速缓存——>全联想高速缓存的顺序，依次升高。直接映射不需要联想查找，不需要页面替换算法；区段映射只对有限数量区段标记，所以完成全联想检索比较经济；组联想在做k路联想检索中，由于k实际上是相当小的，因此比全联想要经济得多；全联想标记长度大，检索耗时。

25．假定一个由16个存储器模块构成的主存储器系统有下列三种交叉存储器设计方案。每个模块的容量为1M字节，机器按字节寻址。

设计1：用1个存储体16路交叉。

设计2：用2个存储体8路交叉。

设计3：用4个存储体4路交叉。

（a）确定上述每种存储器组织的地址格式。

（b）在上述每种存储器组织中，假定只有一个存储器模块失效，确定能获得的最大存储器带宽。

（c）比较说明三种交叉存储器组织的优缺点。

解：（a）设计1：低4位是模块地址，高位是字地址

设计2：低3位是模块地址，最高1位是体地址，中间是字地址

设计3：低2位是模块地址，最高2位是体地址，中间是字地址

（b）当有一个存储器模块失效时，设计1带宽为0，设计2带宽为4，设计3带宽为6

（c）设计1支持邻接单元的成块存取，带宽很好，但不能容错

设计2带宽稍差，但可以容错

设计3带宽更差一些，但容错性能很好

26．在页式虚拟存储器中，一个程序由P1~P5共5个页面组成。在程序执行过程中依次访问到的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2。假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LFU和OPT三种页面替换算法对这3页主存进行调度。画出主存页面调入、替换和命中的情况表。（2）统计三种算法的页命中率。

解：

27．一个程序由5个虚页组成，采用LFU替换算法，在程序执行过程中依次访问的页地址流如下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3

（1） 可能的最高页命中率是多少？

（2） 至少要分配给该程序多少个主存页面才能获得最高的命中率？

（3） 如果在程序执行过程中每访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。

解：（1）可能的最高页命中率=7/12。

（4） 至少要分配给程序4个主存页面。

（5） 可知总的访问次数为1024*12=12288，其中缺失5次

存储单元的命中率=（12288－5）/12288=99.96%

28．试就块替换算法的实现灵活性排出四种高速缓存组织的次序并说明理由。

解：按直接映射高速缓存——组联想高速缓存——全联想高速缓存——区段映射高速缓存的顺序，灵活性增加。直接映射不需要块替换算法；组联想替换算法得选择有限；全联想可以实现较好得替换算法；区段映射实现替换算法经济、灵活。

29．试解释每种高速缓存组织的块映射策略对命中率问题的影响。

解：直接映射高速缓存的结构十分简单，直接映射非常严格，命中率比较低；全联想高速缓存提供最大的自由度，可以获得较好得命中率，减少块的冲突；组联想高速缓存，可以考虑许多设计上折衷方案，获得更高的命中率，性能价格比较好；区段映射高速缓存替换算法比较灵活，可以提供不错的高速缓存命中率。

30．试解释组联想高速缓存组织的块大小、组数、联想特性和高速缓存的大小对性能的影响。

解：（1）高速缓存的容量越大，命中率越高，但其价格比较昂贵，容量总是受预算限制的。

（2）当容量固定，性能对块大小十分敏感，存在着一个最佳块大小，命中率在此处达到峰值。当块变得非常大时，取进高速缓存得许多字可能永远不会使用，而且随着块大小的加大，会逐渐失去时间局部性的作用。

（3）组数的影响是十分明显的，对一个大小固定的高速缓存来说，其命中率会随着组数的增加而降低。

（4）联想特性，对固定大小的高速缓存来说，存在着联想特性和组数的折衷问题。

31．试解释下列有关存储器的术语：交换存储器系统及举例、请求式页面存储器系统及举例、混合式存储器系统及举例。

解：指的是交换只允许在整个进程级进行的存储器系统，交换设备是磁盘的可配置部分，用来暂存从主存储器换出的信息，留作交换设备的这部分磁盘存储器空间称为交换空间。交换系统曾用于PDP-11和早期的UNIX系统中。

请求式页面存储器系统只允许页面（不是进程）在主存储器与交换设备之间进行传送，进程的各个页面可以独立地换入与换出，它允许进程地址空间比物理地址空间更大一些。优点是可以动态地容纳大量进程。

VAX/VMS和UNIX系统V将交换与请求式页面调度的优点结合在一起，实现了混合式存储器系统。当几个进程同时处于就绪-运行但要交换的状态时，交换器可以完整地将这几个进程交换出去，以便腾出所需的空间。这种方案的页面故障率可能较低并可减少颠簸现象。

32．试分析Lamport（1979）、Dubois等（1986）和Sindhu等（1992）对各自的顺序一致性所用条件的相似之处以及细微的差别。

解：相似之处是：所有处理机的取、存和交换操作都可以看作是按一种单一的全局存储次序在顺序地执行，这种存储次序与处理机各自的程序次序是相符合的。

Lamport的定义建立了顺序一直性的基本原则。Lamport的原子性定义对Dubois等施加给存储器访问的限制也有所缓解。Sindhu等指出的顺序一致性条件对偏序关系又有了进一步的改善。

33．试分析弱一致性存储器系统的DSB模型和TSO模型，对各自的顺序一致性所用条件的相似之处以及细微的差别。

解：相似之处就是他们都实现了对存储器访问的弱次序。

DSB和TSO是两种不同的弱一致性存储器模型。DSB模型的弱化表现在同步点强制实施顺序一致性上。TSO模型的弱化表现在用FIFO存缓冲器对读、存和交换操作实行不同的处理上。TSO模型已经在实际系统中实现，而DSB模型则还没有。

34．在计算机系统中设置虚拟存储器和Cache的主要目的各是什么？试列举出这两种存储系统在具体实现时至少4个方面的差别，并说明主要理由。

解：Cache存储系统的主要目的是为了提高存储器的速度；虚拟存储系统的主要目的是为了增加存储器的存储容量。

差别：（i）Cache的价格高；虚拟存储器由主存储器与联机的外部存储器构成，价格较低；（ii）Cache在实现上对程序员是透明的；虚拟存储器对系统程序员是透明的；（iii）Cache存储速度快；虚拟存储器则速度相对慢；（iv）Cache采用相联方式访问，对程序员来说，不需要编址。

35．在一个采用快、慢表的虚拟存储器中，访问主存的命中率为99.99%，访问快表的命中率为99%，经快表进行地址变换所需要的时间仅是经过查页表进行地址变换时间的十分之一，磁盘存储器的访问速度仅是主存储器速度的万分之一。

（1） 计算这个虚拟存储器的等效访问时间。

（2） 计算这个虚拟存储器的访问效率。

解：（1）设为访问快表所需的时间，则访问页表、磁盘存储器的时间分别为10t， t

等效访问时间Ta=0.99*t+0.01*0.9999*10t+0.01*0.0001*t =1.18999t

（2）访问效率e==84%

36．对于一个采用组相联映象方式和FIFO替换算法的Cache，发现它的等效访问时间太长，为此，提出如下改进建议：

（1） 增大主存的容量。

（2） 提高主存的速度。

（3） 增大Cache的容量。

（4） 提高Cache的速度。

（5）Cache的总容量和组大小不变，增大块的大小。

（6）Cache的总容量和块大小不变，增大组的大小。

（7）Cache的总容量和块大小不变，增加组数。

（8）替换算法由FIFO改为LFU。

请分析以上改进建议对等效访问时间有何影响，其影响的程度如何？

解：（1）增加等效访问时间；（2）减少等效访问时间，提高较多；（3）会改善性能，存在一个值，当超过此大小，性能改善十分有限；（4）会改善性能，但受限于缺失率；（5）存在一个最佳大小，小于此值时，块大小增加，命中率增加，当大于此值时，块大小增加，命中率反而会下降；（6）当组大小很大时，会降低性能；（7）会降低性能，当组数超过一定数量，下降非常快；（8）会改善性能，但和页面访问踪迹有关系。

37．假设程序中出现转移指令且转移成功的概率为0.1，设计一个采用低位交叉方式访问的多体存储器，要求每增加一个存储体在一个存储周期中能够访问到的平均指令条数增加0.2条以上，请计算最多的并行存储体的个数。

解：加速倍数S(n)=[1― (1―g)]/g； 代入g=0.1

解方程S(n+1)－S(n)≥0.2 得n≤15

38．一台处理机的运算速度为1GIPS，每执行一条指令平均需要取指令一条和读/写数据两个，输入输出系统对存储器的访问可以忽略不计。主存储器采用DRAM芯片，工作周期为150ns，请设计存储系统方案，可以采取哪些措施来匹配存储器与CPU之间的速度差距？

解：CPU取指令：1GW/s CPU读/写数据：2GW/s

所以要求存储器的频带宽度不低于3GW/s，要求存储器的访问周期不大于0.33ns

可以采取三种方法匹配速度差距：

（i） 多个存储器并行工作，并且用并行访问和交叉访问等方法提高存储器的访问速度；（ii）采用层次结构存储系统，特别是Cache存储系统；（iii）设置各种缓冲存储器。

39．一个页式虚拟存储器的虚存空间大小为4GB，页面大小为4KB，每个页表存储字要占用4个字节。

（1） 计算这个页式虚拟存储器需要采用几级页表？

（2） 如果要求页表所占总的主存页面数最小，请分配每一级页表的实际存储容量各为多少字节？

（3） 页表的哪些部分必须存放在主存中？哪些可以放在辅存中？

解：（1）㏒=32，㏒=12，㏒=12，㏒=2，页表级数g=（32－12）/（12－2）=2

（2）第一级页表为1页，实际存储容量为1K字，即4K字节；第二级页表为1K页，实际存储容量为1M字，即4M字节

（3）第一级页表必须驻留在主存储器中，二级页表只需驻留一小部分，其余二级页表可以放在辅存中。

40．一个16X16的矩阵，要求在一个存储器周期内实现按行、按列、按对角线和按反对角线的无冲突访问。至少需要多少个存储体？写出矩阵的各元素在各个存储体中存放的位置。

解：至少需要16个存储体。矩阵元素a，表格中用ij来代表之，0≤i,j≤F

有一个两层的存储器层次结构M1和M2M1的命中率用h表示