《计算机系统结构期末复习资料》由会员分享，可在线阅读，更多相关《计算机系统结构期末复习资料（16页珍藏版）》请在金锄头文库上搜索。
1、福建农林大学计算机系统结构共 16 页第 1 页计算机系统结构期末复习资料计算机系统结构期末复习资料计算机系统结构期末复习资料计算机系统结构期末复习资料应用题应用题应用题应用题【题型 1】经统计，某机器 14 条指令的使用频度分别为： 0.01,0.15,0.12,0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14,0.11,0.03。分别求出用等长码、Huffman 码、只有两种码长的扩展操作码 3 种编码方式的操作码平均码长。解答14 条指令的等长操作码的平均码长是14log2位，即 4 位。哈夫曼编码可先用哈夫曼算法构造哈夫曼树，本题的哈夫曼树如图
2、1 所示。在图 1 中，叶子上用圆括号所括起来的数字表示该频度指令所用的二进位编码的码位数，所以哈夫曼编码的操作码平均码长为38. 3141= =iiilp位。采用只有两种码长的扩展操作码，可根据 14 条指令所给出的使用频度值分成两群，让使用频度较高的 6 种指令用 3 位操作码编码表示，留下两个 3 位码作为长码的扩展标志，扩展出 2 位，共有 8 条使用低频的指令的操作码，这样，操作码的平均码长为 =+=1414 . 320. 0580. 03iiilp 位【题型 2.1】设中断级屏蔽位“1”对应于开放， “0”对应于屏蔽，各级中断处理程序的中断级屏蔽位设置如表所示。福建农林大学计算机系
3、统结构共 16 页第 2 页表 1 中断级屏蔽位设置中断处理程序级别中断级屏蔽位 第 1 级第 2 级第 3 级第 4 级 第 1 级0000 第 2 级1011 第 3 级1000 第 4 级1010 （1）当中断响应应优先次序4321时，其中断处理次序是什么？ （2）如果所有的中断处理都各需 3 个单位时间，中断响应和中断返回时间相对中断处理时间少得多。当 机器正在运行用户程序时，同时发生第 2、3 级中断请求，过两个单位时间后，又同时发生第 1、4 级中断 请求，试画出程序运行过程示意图。分析为了领会中断响应排队器对中断响应的优先次序是用硬件固定的，以及通过由操作系统给各中断级服务程序现
4、行程序状态字中的中断级屏蔽位设置不同的状态，可以改变中断处理（完）的次序这两个要点，图1 给出了一个中断响应硬件部分的简单逻辑原理示意图。图中略去了某些实现上的具体细节，因为这些已不是本课程要讨论的内容。中断级屏蔽位是程序状态字中的一个组成部分。程序状态字是将散布于系统各部分，反映程序工作时某些关键性硬件的状态，组合在一起所构成的字，有的计算机也称其为处理器状态字或程序换道区。每类程序均在主存中指定一个区域来放置其程序状态字。运行一个程序或进程时，就会将其程序状态字从主存指定单元或区域取出送到分散于系统各部分的寄存器或计数器中，建立起运行此程序或进程的环境。一个程序或进程在退出运行时，也会将反
5、映该程序状态的这些寄存器或计数器内容组拼成程序状态字，存回该程序或进程在主存中的指定单元或区域里因此，程序或进程的切换，只需要通过硬件启动的交换新旧程序状态字的内容即可快速完成。例如在 IBM 370 系列机上，程序状态字为 64 位，等于它的长字，交换程序状态字只需硬件启动经写长字和读长宇二次访存即可完成。尽管中断请求是随机发出的，为了便于精确保存中断的断点以及在中断处理完后又能返回到原中断处，中断响应排队器总是在每条指令执行到最后一个机器周期的最后一个时钟周期时，对目前到达中断响应排队器入口的所有中断请求排一次队， 择优进行响应。 在中断响应排队器相应的输出端产生出响应信号，福建农林大学计
6、算机系统结构共 16 页第 3 页此信号经中断级服务程序入口地址形成硬件，生成该级中断服务程序的程序状态字在内存区中所存放的地址。同时，经中断响应控制信号启动，进行新旧程序状态字的交换，完成程序的切换被中断的程序的断点地址（即程序计数器的内容） ，由硬件自动压入返回地址堆栈，予以保存。系统切换到新的程序或进程后，继续运行下去，如果新的程序或进程是一个中断服务程序，在运行结束，执行到中断返回指令时，就会从堆栈中弹出所保存的返回地址再次交换程序状态字，系统又重新返回到原先被中断的程序，恢复运行。当然，低级的中断服务程序在处理过程中又遇到了比其更高级的中断请求时，应允许其被中断，以实现多级中断的嵌套
7、。利用返回地址堆栈的后进先出工作方式，就可以完成中断嵌套时的正确返回。可以看出， 只要某道程序运行时， 由操作系统在现行程序的程序状态字中， 根据对各中断级的中断请求是否屏蔽，设置好中断级屏蔽位的状态，就可以控制这些级别的中断请求是否进入中断响应排队器去参加排队。只有能进入中断响应排队器的中断级请求，才有机会得到响应，从而就可改变中断实际处理完的次序。应当注意的是，用户程序是不能屏蔽任何中断的。因此，用户程序的现行程序状态字中，对各级中断级的屏蔽位，均应让其处于“开放”状态。根据本题所给出的各级中断处理程序对中断级屏蔽位设置的状况，很容易得出其中断处理(完)的次序应当是 1342。因为正处理
8、l 级的中断处理程序时，现行程序状态字中的中断级屏蔽位为 0000，在其执行期间，任何新的同级和低级的中断请求都不可能进入中断响应排队器进行排队，所以，1 级中断处理程序一定会先处理完。当执行 3 级中断服务程序时，由于现行程序状态字中的中断级屏蔽位为 1000，即对 l 级中断请求是“开放”的，而对其它各级中断请求则处于“屏蔽”状态，所以，只要此时发生 1 级中断请求，它就能进入中断响应排队器去排队。从而在中断请求排队的微操作发出时，就可打断 3 级中断服务程序的执行，交换程序状态字。转去执行 1 级中断处理程序，使之被优先处理完。而在执行 3 级中断服务程序时，由于现行程序状态字对 2、3
9、、4 级的中断请求处于被“屏蔽”的状态，所以，它们都不能打断正在执行的 3 级中断处理程序。其它的情况也就可以依此类推得到。 解答（1）中断处理（完）的次序为2431。 （2） CPU 运行程序的过程示意图如下图所示。 在该图中， 粗短线部分代表进行交换程序状态字的时间， t为 1 个单位时间。【题型 2.2】若机器共有 5 级中断，中断响应优先次序为 l2345，现要求其实际的中断处理次序 为 l4523。 (1) 设计各级中断处理程序的中断级屏蔽位(令“1”对应于屏蔽，“0”对应于开放)； (2) 若在运行用户程序时，同时出现第 4、2 级中断请求，而在处理第 2 级中断未完成时，又同时出
10、现第 l、 3、5 级中断请求，请画出此程序运行过程示意图。分析根据题意，中断级屏蔽位“l”对应于屏蔽， “0”对应于开放，实际上就是在图 31 中，控制各级中断请求进入中断响应排队器入口端的与门控制端是接在各中断级屏蔽位触发器的“0”输出端而已，并无实质上的不同。此外，正在处理某级中断服务程序时，与其同级的新的中断请求是不能被响应的，应当予以屏蔽， 这是因为两者既然是属于同一优先级的， 则先来的中断请求理所应当先得到响应并被处理完。福建农林大学计算机系统结构共 16 页第 4 页KTnTP=所以，根据所要求的中断处；理(完)的次序，各级中断处理程序现行状态字中各中断级屏蔽位的状态就很容易被设
11、置出来。解答(1) 各级中断处理程序中的中断级屏蔽位的设置，如表 2 所示。表 2 中断级屏蔽位的设置中断处理程序级别中断级屏蔽位51111101000100111501100(2) 由已知条件可得程序运行过程的示意图如图 3.3 所示。图中，粗短线表示交换程序状态宇的时间。【题型 3】吞吐率衡量流水线性能的主要指标有吞吐率、加速比和效率。解决流水线瓶颈问题的常用方法：细分瓶颈段、重复设置瓶颈段。最大吞吐率 Tpmax： 指流水线达到稳定状态后可获得的吞吐率。实际吞吐率Tp：是指单位时间内能处理的任务数或输出结果的数量，它总是小于最大吞吐率。因为流水线有建立阶段和排空阶段，以及其他因素会影响流
12、水线的连续流动。（1）吞吐率Tp：流水线单位时间里能流出的任务数或结果数。各段时间均相等的流水线：实际吞吐率：最大吞吐率：tnknTP+=) 1()ttnknTP n=+= 1 1limmax福建农林大学计算机系统结构共 16 页第 5 页各段时间不完全相等的流水线：实际吞吐率：最大吞吐率：（2）效率：流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率。各段时间均相等的流水线：E=TPt各段时间不完全相等的流水线：流水线中经过时间最长的子过程称为瓶颈子过程。例如，有一个 4 段的指令流水线如图 2 所示，其中，1、3、4 段的经过时间均为0t，只有 2 段的经过时间为03t，
13、因此瓶颈在 2 段，使整个流水线最大吞吐率只有)3/(10t，其时-空图如图 3 所示。即使流水线每隔0t流入一条指令，也会因来不及处理被堆积于 2 段，致使流水线仍只能以03t才流出一条指令。为了提高流水线的最大吞吐率，首先要找出瓶颈，然后设法消除此瓶颈。消除瓶颈的一种办法是将瓶颈子过程再细分。例如将 2 段再细分成 21、22、23 三个字段，如图 4 所示。让各子段经过时间都减少到0t，这样，最大吞吐率就可提高到0/1t。图 5 是将瓶颈子过程再细分后的时-空图。然而，并不是所有的子过程都能再细分的。假如 2 段已经不能再细分了，则可以通过重复设置多套（如此例用 3 套）瓶颈段并联，让它
14、们交叉并行，如图 6 所示。每隔0t轮流给其中一个瓶颈段分配任务，使它们仍可每隔0t解释完一条指令，时-空图见图 7 所示。这种办法需要解决好在各并行子过程之间的任务分配和同步控制，比瓶颈子过程再细分控制要复杂、设备量要多。 =+=kikitttntnTP121),max() 1(L),max(121max ktttTP=L + = = kikikiitttntktn E1211),max() 1(L福建农林大学计算机系统结构共 16 页第 6 页以上讲的都是流水线连续流动时能达到的最大吞吐量。由于流水开始时总要有一段建立时间，加上各 种原因使流水线不能连续流动，经常是流一段时间，停一段时间，
15、因此流水线的实际吞吐率pT总比最大吞 吐率maxpT要小。 【例题】为提高流水线效率可采用哪两种主要途径来克服速度瓶颈？现有 3 段流水线，各段经过时间依次 为t、3t、t， (1)分别计算在连续输入 3 条指令时和 30 条指令时的吞吐率和效率。 (2)按两种途径之一改进，画出你的流水线结构示意图，同时计算连续输入 3 条指令和 30 条指令时的吞吐 率。 (3)通过对(1)、(2)两小题的计算比较可得出什么结论？ 解答:提高流水线效率,消除速度瓶颈主要有将瓶颈段再细分以及重复设置多个瓶颈段并联工作， 给其轮流 分配任务的两种途径。 （1）在 3 段流水线，各段经过时间依次是t，t3，t的情
16、况下，连续流入 3 条指令时，将 ttttttttmnj=3,3, 3, 2321代入，可得吞吐率pT和效率为：ttntnTmijip= += =113) 1(1福建农林大学计算机系统结构共 16 页第 7 页而连续流入 30 条指令时，只需将上式之 n 改为 30，其他参数不变，得（2）若采取将 2 段细分成 3 个字段，每个字段均为t，构成的流水线结构如下图所示。连续流入 3 条指令时，将tmnji=, 5, 3代入，得连续流入 30 条指令时，将30=n代入，其它参数不变，有若采取将 3 个 2 段并联构成的流水线，其构成如下图所示。115) 1(11= + = = mijimiitntmtn ttntnTmijip= += =4615) 1(14625)
