计算机系统结构课堂习题答案

1、1.经统计，某机器14条指令的使用频度分别为：，.分别求出用等长码、 哈夫曼码、只有两种码长的扩展操作码等3种编码方式的操作码平均码长.答：分析等长操作码的意思是不管其指令的频度如何，都用同样长度的二进制码位 数来对指令操作码编码。 显然，当指令系统中的指令条数为n时，等长操作码的二进制码位数应当是 10g 2 n 。Huffman编码是用 Huffman算法构造出 Huffman树来得到的。它的平均码长是用 nPi 1计算求得的。i 1只有两种码长的扩展操作码编码，则需要对指令使用频度进行按大小分群。将高频的指令分在同一群中，对其用短的操作码编码，而将低频的指令分在另一群中，使用长 操作码编

2、码。每一群都各自用等长操作码编码。这时，为能唯一解码和立即解码，在短 操作码中还要使用某些码来作为扩展成长操作码的扩展标志码。经过综合权衡，使平均n码长尽可能短，来定好长、短码的码长组配关系。从而，再用Pi li来求得其平均码i1长。解答14条指令的等长操作码的平均码长是log 214位，即4位。Huffman编码可先用 Huffman算法构造出 Huffman树。本题的Huffman树如图所示。 图中，叶子上用圆括号所括起的数字是表示该频度指令所用的二进位编码的码位14数，所以Huffman编码的操作码平均码长为Pi h 二位。i1（曲）0 2. 1 2* 10 的 Huffman 用采用只

3、有两种码长的扩展操作码，可根据14条指令所给出的使用频度值分成两群。让使用频度较高的 6种指令用3位操作码编码表示。例如，用 000101分别表示 使用频度为的指令的操作码。留下 110和111两个3位码作为长码的扩展标志，扩展出2位码。从而用5位码就可以各扩展出4条使用频度较低的指令，这样，共有 8 条使用频度较低的指令符合题目的要求。由此可求得操作码的平均码长为14Pi i 1li=30.80 5 0.203.4位.设中断级屏蔽位” 1对应于开放，”网应于屏蔽，各级中断处理程序的中断级屏蔽位 设置如表3-4所示。表3-4习题3-5中的中断级屏蔽位位置中断处理程序级别中断级屏蔽位第1级第2级

4、第3级第4级第1级0000第2级1011第3级1000第4级1010(1)当中断响应优先次序为 1-2-3-4时，其中断处理次序是什么(2)如果所有的中断处理都各需 3个单位时间，中断响应和中断返回时间相对中断处理时间少很多。当机器正在运行用户程序时，同时发生第2、3级中断请求，过两个单位时间后，又同时发生第 1、4级中断请求，试画出程序运行过程示意图。答:(1)中断处理(完)的次序为1 一 3一 4一Z(2)由题目所给出的条件，其 CPU运行程序的过程示意田如图3. 2所示。图中，粗短 线部分代表进行交换程序状态字的时间，t为1个单位时间。中厮处理狎序幽I求用”序 J_ _2_ 2_4图露

5、遇3的程中足忏过程加息图.若机器共有5级中断，中断响应优先次序为1-2-3-4-5,现要求其实际的中断处理次序为1-4-5-2-3,回答下面问题：(1)设计各级中断处理程序的中断级屏蔽位(令”例应于屏蔽，”网应于开放)；(2)若在运行用户程序时，同时出现第4、2级中断请求，而在处理第 2级中断未完成时，又同时出现第1、3、5级中断请求，请画出此程序运行过程示意图。答：(1)各级中断处理程序中的中断级屏蔽位的设置，如表3. 2所示。(2)由已知条件可得程序运行过程的示意图如图3. 3所示。图中，粗短线表示交换程序状态宇的时间。表3. 2中断级屏蔽位的位置中断处理程序级别中断级屏敝位1234511

6、1111201100300100401111501100中所请求用户飘幅处理期_2_ _3_ _4_ _5_H3.3蜃&3的程朋g行过程示意图.设某程序包含5个虚页，其页地址为4,5,3,2,5, 1, 3,2,2,5,1 ,3。当使用LRU算法替换时，为获得最高的命中率，至少应分配给该程序几个实页其可能的最高命 中率为多少答：用堆栈对页地址流处理一次的过程如附表7所示，其中H表示命中。附表7用堆栈对页地址流处理一次的过程页地址流453251322513堆 S(1)453251322251栈 S(2)45325133325内 S(3)4532511132容 S(4)443255513S(5)4

7、444444S(6)实 n=1H页 n=2H数 n=3HHn=4HHHHHHHn5HHHHHHH模拟结果表明，使用LRU替换算法进行替换，对该程序至少应分配 4个实页。如果只分 配3个实页，其页命中率只有 2/12,太低；而分配实页数多于 4页后，其页命中率不会 再有提高。所以，分配给该程序 4个实页即可，其可能的最高命中率为H=7/12o.有一个Cache存储器。主存共分 8个块(07), Cache为4个块(03),采用组相联映像，组内块数为2块，替换算法为近期最久未用过的算法(LRU)(1)画出主存、Cache地址的各字段对应关系(标出位数)图； 画出主存、Cache空间块的映像对应关系

8、示意图；(3)对应如下主存块地址流：1, 2, 4, 1 ,3,7,0,1,2,5, 4, 6,4,7, 2,如主存中内容一开始未装入 Cache中，请列出Cache中各块随时间的使用状况；(4)对于(3),指出块失效又发生块争用的时刻； 对于(3),求出此期间Cache之命中率。答：(1)主存、Cache地址中各个字段的含义、位数及其映像的对应关系如附图14所示。 主存、Cache空间块的映像对应关系如附图15所示。主存的第0、1、4、5块只可映像装入或替换掉物理Cache中的第0、1块的内容。主存的第2、3、6、7块只可映像装入或替换物理Cache中的第2、3块的内容。(3)程序运行时，由

9、给出的主存块地址流可得到Cache中的各个块的使用状况，如附表13所示，表中标”*的是候选替换块的块号。附表13 Cache中的各个块的使用情况时间t123456789101112131415主存块地址124137012546472Cache块0111*1111*111*44444144*4*4*00*0*55*5*5*5*5*22222*7777*7*7*666*2333*3*3*2222*2*77*命中情况失失失H失替替H替替替替H替替(4)发生Cache块失效又发生块争用的时刻有 6、7、9、10、11、12、14、15Cache的块命中率为Hc=3/15=.假设指令的解释分取指、分析与

10、执行3步，每步的时间相应为t取值、t分析、t执行,(1)分别计算下列几种情况下，执行完100条指令所需时间的一般关系式：顺序方式；仅”执行k与”取值k+1”重叠；仅“执行k”、”分析k+1与”取值k+2”。(2)分另1在t取值=t分析=2、t执行=1和t取值=t分析=5、t执行=2两种情况下，计算出上述各结果。答：分析可先按指令间所要求的时间关系画出指令间的时间重叠关系图，由图就可以列 出各种情况下，计算100条指令所需时间的一般关系式。再将给出的时间值代入，实际 完成100条指令所需的时间就可以求得。顺序方式工作的时间关系如图 5. 1所示。取指k i分析k :执行k ；取指k+1 ;分析k

11、+1 :执行k+1；取指k+2分析k+2 ；执行k+2 IIIIIIIII图 顺序方式工作的时间关系图仅，执行k ”与 取指k+1 ”、重叠方式工作的时间关系如图 5. 2所示.取指k 1分析k 1执行k取指k+1 ：分析k+1 ；执行k+1取指k+2 ；分析k+2；执行k+2图5. 2 仅“执彳Tk ”，与“取指k+1 ”重叠方式工作的时间关系图仅 啾行k ”、 “分析k+1 ”、 “取指k+2 ”重叠方式工作的时间关系如图5. 3所示.取指k+1 ；分析k+1 ；执行k+1取指k+2 :分析k+2 :执行k+2图5. 3 仅执彳k ”、 吩析k+1 ”、 “取指k+2 ”重叠方式工作的时间

12、关系图(1)计算执行完100条指令所需要的时间：(i)顺序方式工作时为100 (t取指t分析t执行)(ii)仅“执行k ”，与“取指k+1 ”重叠方式工作时为t取指100t分析99 max t取指，t执行t执行(iii)仅执行k 、吩析k+1 ”、 “取指k+2 ”重叠方式工作时为t取指max t分析,t取指 98 max t取指,t分析,t执行max t执行，t分析t执行当,取指=t分析=2、t执行=l时，代入上面的各式，可求得 100条指令执行所 需要的时间是：顺序方式工作时为500。仅“执行k ”，与“取指k+1 ”重叠方式工作时为401。仅“执行k ”、“分析k+1 ”、取指k+2 ”

13、重叠方式工作时为203。当t取指=t执行=5, t分析 =2,代入上面的各式，可求得100条指令执行所需 要的时间是：顺序方式工作时为1200。仅“执行k ”，与“取指k+1 ”重叠方式工作时为 705。仅“执行k ”、 吩析k+1 ”、 “取指k+2 ”重叠方式工作时为510。.在一个5段的流水线处理机上需经 9拍才能完成一个任务，其预约表如表 54所示。 表5 49拍才能完成一个任务的预约表间段、t。t1t2t3t4t5t6t7t8S1SS3与S分别写出延迟禁止表 F、冲突向量C;画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调用方案。按此流水调度方案输入6个任务，求实际吞吐率。答：对预约表中各个行中打”的拍数求出差值，并将这些差值汇集在一起， 就可得到延迟禁止表：F=1, 3, 4, 8由延迟禁止表F可转换得初始冲突向量 C=