高等计算机体系结构

1、高等计算机体系结构习题高等计算机体系结构存储器习题（共47题）选书一计算机系统结构，郑纬民，清华大学出版社，第二版。共14题。二高等计算机体系结构，KaiHuang,郑纬民等译，清华大学出版社。共7题。三操作系统：设计与实现（上册），andrews. Tanenebum 著。王鹏等译。电子工业出版社。共19题。四计算机组成与结构，第二版，王爱英，清华大学出版社。共7题。班级：计研六姓名：李旭东学号：0056162000/1/8一计算机系统结构，共15题。3.1答：存储系统是是由两个或者两个以上速度，容量，价格各不相同的存储器用硬件，软件，或者项结合的办法连接起来的一个系统。这个系统对程序员是透

2、明的。它的速度与最快的接近，容量与最大的接近，价格与最便宜的接近。（1）当M1所占的比例较小时，平均价格会接近C2.（2）TA=H*T1+(1-H)*T2.（3）E=T1/TA=T1/( H*T1+(1-H)*T2)=1/(H+(1-H)R).（5）由1/(H+(1-H)100)>0.95得：H>99.94%.（6）假设大小为N，则有：0 96（0.9994+5*n-1）/5*n所以n=(1-0.96)/(1-0.9994)=66.73.2答：(1)假设命中率分别时H1,H2,H3,则有：T=H1*T1+(1-H1)*H2*T2+(1-H1)*(1-H2)*T3.S=S3C=(S1

3、*C1+S2*C2+S3*C3)/(S1+S2+S3)(2)当S3的比例非常大时，平均价格C接近与C3.3.3答：（1） 等效访问时间：TAh1*t1+(1-h1)*t2Ta1=0.7*20+0.3*200=74 nsTa2=0.9*20+0.1*200=38 nsTa3=0.98*20+0.02*200=23.6 ns（2） 平均价格：c1=(64*4+4*1024*0.2)/(64+4*1024)=0.258c2=(128*4+4*1024*0.2)/(128+4*1024)=0.315c3=(256*4+4*1024*0.2)/(256+4*1024)=0.424（3）等效访问时间：1&

4、gt;2>3平均价格：1<2<3（4） 效访问时间与价格的乘积：1.19.0922. 11.973. 10.0最优设计：33.4答：(1) 主存的最大容量：15000-512*0.01/0.5=29989k(2) 因为40=0.95*20+0.05*t2，所以t2=420 3.6答：采用CACHE来弥补他们之间的差距。如果CACHE的读写周期是10ns的话，那么可以提高10倍以上。3.7答：每块存储器：1M容量。20位。（1）地址格式：高位交叉：420并行：16低位交叉：2042路高位8路低位：12034路高位4路低位：22024路并行4路低位：202（2）优缺点高位交叉：便

5、于扩大容量并行：字长增加，一个周期里可以访问多个字低位交叉：提高存储器访问速度。（3）频带宽度（相对量）高位交叉：1并行：16低位交叉：约162路高位8路低位：约84路高位4路低位：约44路并行4路低位：约16（4）逻辑图略。3.9答：（1） 页表项数：1M，每个页面能容的页表项为：128所以应需要二级页表。（2）第一级：1个页面，共1024个表项。第二级，1024个页面，共1M个表项。（3）第一级页表应该放在主存中。第二级页表的常用部分应放在主存中。3.10答：（1）等效访问时间：10.01*10+0.0001*10000=2.1（2） 访问效率：1/2.1=47.6%3.12答：（1） 虚

6、拟地址格式：61012（2） 主存地址格式：1112（3） 快表中如果只保存页号，不算标志位，则有虚页号16位，实页号11位，格式为：61011。（4） 慢表容量是64K个存贮字。每个存贮字格式与快表类似。（5） 图略。3.14答：访问顺序：232152453252（1）FIFO算法内存页面下个访问命中（0不命中）000202003023021230102315031520152405245152430243212435043520352LFU算法内存页面下个访问命中（0不命中）0002020030230212301023150215212154025451524304532035251352

7、21352OPT算法内存页面下个访问命中（0不命中）000202003023021230102315023521235403545135431354202545125421254（2）命中率(调入算命中)：FIFO: 6/12=50%LFU: 8/12=66.7%OPT: 9/12=75%3.15答：（1） 可能的最高命中率是7/12=58.3，不算调入。（2） 至少要分配5个主存页面才能满足要求。（3） (1024*12-5)/1024*12=100%3.17答：虚拟存储器主要目的是解决主存不足，CACHE是为了弥补在处理机和主存之间的速度诧异。他们之间的差别有：1 虚拟存储器由主存和外存共

8、同实现。CACHE一般是高速存储器。2 虚拟存储器使用页表来查看该页是否在主存中，CACHE一般使用标志位。3 虚拟存储器一般使用全相联，而CACHE一般使用组相联。4 虚拟存储器一般使用软件调页，CACHE一般使用硬件完成。3.19答：(1)主存地址格式：块号3块内地址偏移4。(2)CACHE地址格式：块号2块内地址偏移4。(3)主存分成4组，1，3组与CACHE的一组对应，2，4组与CACHE2组对应，组内全相联。(4)C0C1C2C3B6 B2B4 B1 B4 B6 B3 B0 B4 B5 B7 B3(5)fifo算法：CACHE中地址 下个地址 是否命中0000 6 00060 200

9、062 4 04062 1 0 4162 4 1 4162 6 1 4162 3 0 4132 0 0 0132 4 0 0432 5 0 5432 7 0 5437 3 0命中率：2/1217（6）LFU算法：CACHE中地址 下个地址 是否命中0000 6 00060 200062 4 04062 1 0 4162 4 1 4162 6 1 4162 3 0 4163 0 0 4063 4 1 4063 5 0 4563 7 0 5473 3 1命中率：4/1233.3(7)采用全相联后；fifo算法：CACHE中地址 下个地址 是否命中0000 6 06000 206200 4 0624

10、0 1 0 6241 4 1 6241 6 1 6241 3 0 2413 0 0 4130 4 1 4130 5 0 1305 7 0 3057 3 1命中率：4/1233.3LFU算法：CACHE中地址 下个地址 是否命中0000 6 06000 206200 4 06240 1 0 6241 4 1 6241 6 1 6241 3 0 6413 0 0 6430 4 1 6430 5 0 4305 7 0 4057 3 0命中率：3/1225(8)针对最后一个计算：16×3/(16*3+9)=84.2% 3.23答：对减少等效访问时间，并按影响程度排序：3，2，8，4，6，5二

11、高等计算机体系结构，共7题。1 设有一个两层的存储器层次结构：M1，和M2。M1的命中率用h表示，并分别令c1和c2为每千个字节的成本，s1和s2为存储器的容量，t1和t2为存储时间。（a）.在什么条件下，整个存储器系统的平均成本接近c2? (b).该层次结构的存储器有效存取时间ta是多少？ (c).令两层存储器的速度rt2/t1，并令E=t1/ta为存储系统的存取效率，试以速度比r和命中率h来表示E. (d).如果r=100,为使 E>0.95,要求的命中率是多少？答：（a）当s1>>s2时，整个存储器系统的平均成本接近c2。 （b）ta=t1*h+t2*(1-h).(c)

12、.E=t1/ta=t1/(t1*h+t2*(1-h)=1/(h+r(1-h). (d).E>0.95即1/(h+r(1-h)>0.951/(h+100(1-h)>0.95h> (100-1/0.95)/99h > 0.999468.2.(4.12)答：令h1=0.7,h2=0.9,h3=0.98.(a).ta1=t1*h1+t2*(1-h1)=20*0.7+200*(1-0.7)=74nsta2=t1*h2+t2*(1-h2)=20*0.9+200*(1-0.9)=38nsta3=t1*h3+t2*(1-h3)=20*0.98+200*(1-0.98)=23.6n

13、s(b)c1=4美元/K字节Ca1=(s64*c1+s2*c2)/(s64+s2)=(64*4+4096*0.2)/(64+4096)=0.2584美元/K字节Ca2=(s128*c1+s2*c2)/(s128+s2)=(128*4+4096*0.2)/(128+4096)=0.31515美元/K字节Ca3=(s256*c1+s2*c2)/(s256+s2)=(256*4+4096*0.2)/(256+4096)=0.4235美元/K字节(c).按平均成本比较，64K最优，128K次之，256K最差。按平均存取时间比较，256K最优，128K次之，64K最差。平均成本和平均存取时间的乘积分别为

14、64K是19.1216美元*ns/K字节，128K是11.9757美元*ns/K字节，256K是9.9946美元*ns/K字节. 所以256K是最佳设计。3.(4.13)答：等待时间：全局共享存储器的等待时间较长，因为存贮器的带宽有限，而多个处理器要同时访问主存时会发生冲突，引起等待时间的增加。而私有虚拟存储器系统中，每一个处理器都有自己的虚拟存储器，没有访问冲突，等待时间较短。一致性：全局共享虚拟存储器较好实现一致性，因为主存数据只有一份，没有不一致的情况，而私有虚拟存储系统中，每个处理器对应的存储器会出现不一致的现象，需要一致性处理。页面迁移：共享存储器系统中，数据通信可以直接在共享主存中

15、进行，不需要进行页面的交换，而私有虚拟存储器系统中，各处理器的通讯需要页面的迁移。保护：私有虚拟存储器系统较容易实现保护。实现：各有优缺点，因为全局共享存储器系统对存储器的要求很高，而私有系统要进行一致性处理。可扩充性：私有虚拟存储器系统有更好的可扩充性，在共享存储器时，随着系统规模的增大，对存储器的要求越高，而存储器的带宽是有限的，存储器就成了系统的瓶颈。而在私有系统中，存储器对系统规模的扩大影响要小。4.(4.13)答：包含性：速度较快而容量较小的存储器中的数据在速度较慢而容量较大的一层存储器中都因该有拷贝。一致性：由于有些数据在多层中都有拷贝（包含性），系统中这些数据的不同拷贝在一定条件

16、下应该保持一致。写通过(写直达):当某个处理器修改高层存储器中的某个数据时同时修改低层存储器中的相对应的数据。这样做可以保证低层存储器中的数据始终是有效的，但是效率可能不高，因为每一次写数据时都要写低层的慢速的存储器，达不到多层存储器系统的速度与最高层存储器相近的要求。写回：当某个处理器修改高层存储器中的某个数据时，不会马上修改低层存储器中的数据，而是在当这个数据迁移到其他较高层的存储器时才修改这个低层处理器中的数据。他可以减少写入低层存储器的次数，但是没有保证低层数据的有效性。分页，分段是把低层存储器与高层存储器的按一定的长度分成多个取，他们之间交换数据时的基本单位就是这种区，由局部性原理，

17、交换这样一块数据能保证很高的效率。5（4.15）答：(a). 1022176701203045151022176701203045151002176701203045111021167012230440221677112300mmmhhmmhmhmhmhmmmh245676724273323245676724273323524567672427732152455567742277411244456664444mhhmmhhmmhhmhhh所以miss=17,hit=16 命中率为16/33=0.4848.(b). 1022176701203045151022276661103345111000

18、277766100345511102227761103441000227661033mmmhhmmhhmhmmhmmmh245676724273323222677774443322111266667774433555122226667744444511112226677mhhmmhhhmhhmhmh所以miss=17,hit= 16 命中率为16/33=0.4848.（c）.两种情况下命中率相等，这与PF的大小以及程序的特性有关，本来LRU应该有更好的表现，因为他利用程序的局部性原理，但是在程序的局部性参数（工作集）与PF的大小不匹配时，LRU的优势就没有了。因此给程序分配适当的页面数（PF的

19、大小）对系统的性能有很大的影响。6.（a）.时间局部性：最近访问的指令和数据很可能在不久的将来再次被访问。空间局部性：表示一种趋势，指的是一个进程访问的各项其地址彼此很近，即下一个要访问的项很可能就是这次访问项的邻进项。顺序局部性：在典型的程序中，除非转移指令产生不按次序的转移外，指令都是顺序执行的，按序执行的和不按序执行的比例大概是5比1。(b).给定时间间隔内程序访问的地址的子集叫工作集。显然观察窗口越大，工作集就越大，各工作集的交集就越大，页面的命中率就越高，当观察窗口很小时，各工作集的交集就很小，缺页率就会上升。（c）.90-10规则是指程序在用90的时间多次执行10的指令，而用只有1

20、0的时间在执行另外90的指令。这个规则从全局说明了指令的执行情况，对于程序的优化有指导意义，而局部性原理是在某一个时刻说明了程序的执行规律，对于实现虚拟存储器有指导意义。7（4.17）（a）.把对整个存储的访问分成两部分，在M1中命中的和没有命中的，命中M1的访问所花的时间为t1其概率为h1，不命中M1所花的时间是t2，其概率是（1-h1），所以该存储系统的有效存取时间teff=t1*h1+t2*(1-h1).(b).总的每字节成本所有的所有存储器的成本比上所有的容量，所有的成本是（c1*s1+c2*s2）,所有的容量是（s1+s2）,所以总的每字节成本是（c1*s1+c2*s2）/（s1+s

21、2）.(c).（i）c1*s1+c2*s2=150000.01*512+0.0005*s2=15000s2=29989760字节。(ii).40=20*0.95+t2*0.05t2=420ns。所以主存存取时间最慢是420ns.三操作系统：设计与实现（上册），共19题1. 一个计算机系统有足够的空间在它的主存中放4个程序，这些程序有一半的时间在等待I/O操作。问多大比例的CPU时间被浪费掉了？答：如果是单道的操作系统，则有一半的时间浪费；如果是多道分时操作系统，则没有时间浪费。2. 在一个使用交换的系统中，按地址排列的内存中的空洞大小是10K，4K，20K，18K，7K，9K，12K，15K。

22、对于连续的段请求：（A）12K；（B）10K；（C）9K使用首次适配算法，哪个空洞将被取出？对最佳适配，最差适配，下次适配回答同样的问题。答：首次适配法：20K，10K，18K最佳适配法：12K，10K，9K最差适配法：20K，18K，15K下次适配法：3. 物理地址和虚拟地址之间的区别是什么？答：物理地址：内存的实际地址。虚拟地址：进程和操作系统使用的地址，只是逻辑上的地址，使用时被转换成物理地址。4. 使用4-8（P240）的页表，指出对应与下列虚地址的物理地址：（A）20；（B）4100；（C）8300；答：20：虚拟页面：0；对应物理页面2；物理地址：8*1024+20=8212； 4

23、100：虚拟页面：4100/4/1024=1；对应物理页面1；物理地址：4100；8300：虚拟页面：8300/4/1024=2。108；对应物理页面6；物理地址：6*4*1024+108=24684；5. INTEL 8086处理器不支持虚拟存储器，然而一些公司曾经出售过含有没做任何改动的8086CPU的分页系统。他们是怎么做的？答：在CPU与内存之间做一个虚拟分页调度单元MMU。6. 如果一条指令需要1US，一个页面故障需要另外NUS，给出在页面故障每K条指令发生一次时指令的实际执行时间。答：平均实际每条指令执行时间：（K+N）/K ns7. 一个机器有32位地址空间和8K页表，页表完全由

24、硬件实现，每个入口一个32位字。在进程启动时，页表被以每个100NS的速度从内存拷贝到硬件中。如果每个进程运行100MS（包含装入页表的时间），多少比例的CPU时间被用来装入页表？答：（8*1024*100）/（100*106）=0.8%8. 一个32位地址的计算机使用两极页表。虚地址被分为9位的顶级页表域，11位的二级页表域和偏移。页面长度时多少？地址空间中一共有多少页？答：页面长度：212=4K。地址空间页总数：2(11+9)=2M.9. 假设一个32位的虚地址空间被分成A，B ，C ，D四个域。前三个用于一个三级页表系统，第四个时偏移，页面数与这四个与的大小都有关系吗？如果不是，与那些有

25、关，那些无关？答：是的。10. 一台计算机的处理器的地址空间有1024个页面，页表保存在内存中。从页表中读取一个字的开销时500NS，TLB有32个虚地址物理地址对，能在100NS 内完成查找。把平均开销降低到200NS需要的命中率时多少？答：假设N次中有X次命中。则有：X*100+（N-X）*（100+500）=N*200-> X/N=80%所以命中率为80%。11. 一台计算机有48位的虚拟地址和32位物理地址，页面的8K，在页表中需要多少个入口？答：虚拟页数：248/(8*1024)=235。12. 一台计算机有4个物理页，使用情况如下图：页装入时间上次引用时间R（访问）M（修改）

26、012627900123026010212027211316028011（A）NRU（最近未使用）将替换哪个页面？（B）FIFO将替换哪个页？（C）LRU（最久未使用）将替换哪个页？（D）第二次机会将替换哪个页？答：NRU：0FIFO：2LRU：113. 如果FIFO页面替换算法被用到4个物理页和8个页面上，当物理页初始为空，引用序列为0172327103时会发生多少次页面故障？如果使用LRU呢？答：FIFO：页面下次引用页面未命中017231172320172370172310172301723030总共未命中次数：2次。LRU：页面下次引用页面未命中01723117232017237017

27、2310172301172031170330总共未命中次数：3次。14. 把一个64K的程序从平均寻道时间30MS，旋转时间20MS，每道32K的磁盘上装入，需要多少时间？（A） 页长2K（B） 页长4K页随机分布。答：2K：需要读32次。时间：32*(30+20)15. PDP-1是最早的分时计算机之一。有4K18位的内存。在每个时刻它在内存中保持一个进程。掉出时内存中的进程将被写到一个换页鼓上。鼓表面有4K18位字。鼓可以从任何地址开始读写，你认为为什么要选这个鼓？答：保证内存中的数据全部保存，不被覆盖。16. 一台计算机为每个进程提供65535字节的地址空间划分为4K的页。一个特定的程序

28、有32768字节的正文，16386字节数据和15870字节的堆栈。这个程序能装入吗？如果页面长度512字节时呢？答：页面总页数 正文需要页数数据需要 堆栈需要4k16844512128643231所以在4K的页面下，不能一次装入。所以在512的页面下，能一次装入。17. 假设一条普通指令需要1US，但是如果发生了页面故障需要2001US，如果一个程序运行了60S，期间发生了15000次页面故障。如果可用内存时原来两倍，这个程序运行需要多少时间。答：这个程序的指令数是：（60*100000-15000*2000）=3*107; 内存加倍后，发生未命中次数变成7500;运行时间是：60-7500*

29、2000/1000000=45s.18. 在段页式中，必须先查找段描述符，然后是页描述符，TLB也是这样以两极查找的方式工作的吗？答：不是。TLB不分段描述符和页描述符。直接从虚拟页面映射实际页面。19. 解释内零头和外零头。哪个发生在分页系统中？哪个发生在使用纯的分段的系统中？答：内零头：页面内没有使用的空间。发生在分页系统中。 外零头：夹在使用了的空间中的少数未使用页面或者空间。发生在分页系统和纯的分段的系统中。四计算机组成与结构，共7题。5有一个512K*16的存储器，由64K*1的芯片构成（4个128×128结构）问：1） 总共需要多少个？2） 采用分散刷新方式，如果单元刷新

30、间隔不超过2MS,则刷新周期是多少？3） 采用集中刷新方式，设读写周期T0.1US,则刷新一遍需要多久？答： 1需要8×16128片。22MS.3. 4*128*8*0.1=409.6US.7设某计算机CACHE采用4路组相联映象，已知CACHE容量为16KB,主存容量为2MB,每个字块有8个字，每个字32位。请回答：1） 主存地址多少位？（按字节编址）各字段怎么划分？2） 设CACHE起始空，CPU从主存0，1，。100依次读出101各字。并重复此顺序读11次。问命中率。如CACHE速度是主存的5倍，问采用CACHE比无CACHE速度提高多少倍？答：1。主存地址21位。前16位选字块，后5位选字节。 2CACHE块数是：16k/8/4=512.所以命中率是：10/1191。与没有采用CACHE相比，速度提高：11×5/（101×5）3.67倍。8某计算机采用直接映象CACHE,已知容量4096B1) 如果CPU依次从主存单元0，1，。99和4096，4097，。4195交替去指令，循环10次，问命中率。2) 如果CACHE存取时间为50NS,主存存取时间为500NS.CACHE命中率为95，求平均存取时间。答：（1）假设调入算命中。4196&#