《计算机系统结构课堂习习题答案》由会员分享，可在线阅读，更多相关《计算机系统结构课堂习习题答案（9页珍藏版）》请在金锄头文库上搜索。
1、1. 经统计，某机器14条指令的使用频度分别为：，.分别求出用等长码、哈夫曼码、只有两种码长的扩展操作码等3种编码方式的操作码平均码长.答：分析 等长操作码的意思是不管其指令的频度如何，都用同样长度的二进制码位数 来对指令操作码编码。显然，当指令系统中的指令条数为n时，等长操作码的二进制码位 数应当是 。 Huffman编码是用Huffman算法构造出Huffman树来得到的。它的平均码长是用l计算求得的。 只有两种码长的扩展操作码编码，则需要对指令使用频度进行按大小分群。将高频的指令分在同一群中，对其用短的操作码编码，而将低频的指令分在另一群中，使用长操作码编码。每一群都各自用等长操作码编码
2、。这时，为能唯一解码和立即解码，在短操作码中还要使用某些码来作为扩展成长操作码的扩展标志码。经过综合权衡，使平均码长尽可能短，来定好长、短码的码长组配关系。从而，再用l来求得其平均码长。 解答 14条指令的等长操作码的平均码长是位，即4位。 Huffman编码可先用Huffman算法构造出Huffman树。本题的Huffman树如图所示。 图中，叶子上用圆括号所括起的数字是表示该频度指令所用的二进位编码的码位数， 所以Huffman编码的操作码平均码长为l=位。 采用只有两种码长的扩展操作码，可根据14条指令所给出的使用频度值分成两群。让使用频度较高的6种指令用3位操作码编码表示。例如，用00
3、0101分别表示使用频度为、的指令的操作码。留下110和111两个3位码作为长码的扩展标志，扩展出2位码。从而用5位码就可以各扩展出4条使用频度较低的指令，这样，共有8条使用频度较低的指令符合题目的要求。由此可求得操作码的平均码长为 l=3位3. 设中断级屏蔽位”1”对应于开放，”0”对应于屏蔽，各级中断处理程序的中断级屏蔽位设置如表3-4所示。表3-4 习题3-5中的中断级屏蔽位位置中断处理程序级别中断级屏蔽位第1级第2级第3级第4级第1级0000第2级1011第3级1000第4级1010(1) 当中断响应优先次序为1-2-3-4时，其中断处理次序是什么(2) 如果所有的中断处理都各需3个单
4、位时间，中断响应和中断返回时间相对中断处理时间少很多。当机器正在运行用户程序时，同时发生第2、3级中断请求，过两个单位时间后，又同时发生第1、4级中断请求，试画出程序运行过程示意图。答：(1) 中断处理(完)的次序为1342。(2) 由题目所给出的条件，其CPU运行程序的过程示意田如图32所示。图中，粗短 线部分代表进行交换程序状态字的时间，t为1个单位时间。4. 若机器共有5级中断，中断响应优先次序为1-2-3-4-5，现要求其实际的中断处理次序为1-4-5-2-3，回答下面问题：(1) 设计各级中断处理程序的中断级屏蔽位(令”1”对应于屏蔽，”0”对应于开放)；(2)若在运行用户程序时，同
5、时出现第4、2级中断请求，而在处理第2级中断未完成时，又同时出现第1、3、5级中断请求，请画出此程序运行过程示意图。答：(1) 各级中断处理程序中的中断级屏蔽位的设置，如表32所示。(2) 由已知条件可得程序运行过程的示意图如图33所示。图中，粗短线表示交换程序状态宇的时间。表32 中断级屏蔽位的位置中断处理程序级别中断级屏蔽位5111110100001000111501100 5.设某程序包含5个虚页，其页地址为4，5，3，2，5，1，3，2，2，5，1，3。当使用LRU算法替换时，为获得最高的命中率，至少应分配给该程序几个实页其可能的最高命中率为多少答：用堆栈对页地址流处理一次的过程如附表
6、7所示，其中H表示命中。附表7用堆栈对页地址流处理一次的过程页地址流453251322513堆栈内容S(1)453251322251S(2)45325133325S(3)4532511132S(4)443255513S(5)4444444S(6)实页数n=1Hn=2Hn=3HHn=4HHHHHHHn5HHHHHHH模拟结果表明，使用LRU替换算法进行替换，对该程序至少应分配4个实页。如果只分配3个实页，其页命中率只有2/12，太低；而分配实页数多于4页后，其页命中率不会再有提高。所以，分配给该程序4个实页即可，其可能的最高命中率为H7/12。6.有一个Cache存储器。主存共分8个块(07)，
7、Cache为4个块(03)，采用组相联映像，组内块数为2块，替换算法为近期最久未用过的算法(LRU)。(1) 画出主存、Cache地址的各字段对应关系(标出位数)图；(2) 画出主存、Cache空间块的映像对应关系示意图；(3) 对应如下主存块地址流：1，2，4，1，3，7，0，1，2，5，4，6，4，7，2，如主存中内容一开始未装入Cache中，请列出Cache中各块随时间的使用状况；(4) 对于(3)，指出块失效又发生块争用的时刻；(5) 对于(3)，求出此期间Cache之命中率。答：(1) 主存、Cache地址中各个字段的含义、位数及其映像的对应关系如附图14所示。(2) 主存、Cach
8、e空间块的映像对应关系如附图15所示。主存的第0、1、4、5块只可映像装入或替换掉物理Cache中的第0、1块的内容。主存的第2、3、6、7块只可映像装入或替换物理Cache中的第2、3块的内容。(3) 程序运行时，由给出的主存块地址流可得到Cache中的各个块的使用状况，如附表13所示，表中标”*”的是候选替换块的块号。附表13Cache中的各个块的使用情况时间t123456789101112131415主存块地址124137012546472Cache块0111*1111*111*44444144*4*4*00*0*55*5*5*5*5*22222*7777*7*7*666*2333*3*
9、3*2222*2*77*命中情况失失失H失替替H替替替替H替替(4) 发生Cache块失效又发生块争用的时刻有6、7、9、10、11、12、14、15。(5) Cache的块命中率为Hc=3/15=.7.假设指令的解释分取指、分析与执行3步，每步的时间相应为t取值、t分析、t执行，(1) 分别计算下列几种情况下，执行完100条指令所需时间的一般关系式： 顺序方式； 仅”执行k”与”取值k+1”重叠； 仅”执行k”、”分析k+1”与”取值k+2”。(2) 分别在t取值=t分析=2、t执行=1和t取值=t分析=5、t执行=2两种情况下，计算出上述各结果。答：分析 可先按指令间所要求的时间关系画出指
10、令间的时间重叠关系图，由图就可以列出各种情况下，计算100条指令所需时间的一般关系式。再将给出的时间值代入，实际完成100条指令所需的时间就可以求得。 顺序方式工作的时间关系如图51所示。 图 顺序方式工作的时间关系图仅“ ”与“”、重叠方式工作的时间关系如图52所示 图52 仅“”，与“”重叠方式工作的时间关系图仅“”、“”、“”重叠方式工作的时间关系如图53所示 图53 仅“”、“”、“”重叠方式工作的时间关系图(1)计算执行完100条指令所需要的时间：(i)顺序方式工作时为 (ii)仅“”，与“”重叠方式工作时为 (iii)仅“”、“”、“”重叠方式工作时为 (2)当2、l时，代入上面的
11、各式，可求得100条指令执行所需要的时间是： 顺序方式工作时为500。 仅“”，与“”重叠方式工作时为401。仅“”、“”、“”重叠方式工作时为203。 当 5， =2，代入上面的各式，可求得100条指令执行所需要的时间是： 顺序方式工作时为1200。 仅“”，与“”重叠方式工作时为705。 仅“”、“”、“”重叠方式工作时为510。8.在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如表54所示。表54 9拍才能完成一个任务的预约表时间段t0t1t2t3t4t5t6t7t8S1S2S3S4S5分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞
12、吐率及其调用方案。按此流水调度方案输入6个任务，求实际吞吐率。答：对预约表中各个行中打” ”的拍数求出差值，并将这些差值汇集在一起，就可得到延迟禁止表：F=1，3，4，8由延迟禁止表F可转换得初始冲突向量C=()根据初始冲突向量可画出状态转移图如附图32所示。各种周期性调度方案列于附表16。由附表16可知最小平均延迟为拍。附表16周期性调度方案调度方案平均延迟/拍调度方案平均延迟/拍(2,5)(6,7)(2,7)(7)7(5)5(5,2)(6,5).(6)6此时，Tpmax=1/(任务/拍)。最佳调度方案为(2，5)。按(2，5)调度方案实际输入6gve任务的时空间如附图33所示。实际吞吐率Tp6/25(任务/拍)。9
