编译原理复习题 (1)

一、 选择题：

1、虚拟存储器地址变换是指（ B） A 多用户虚地址与实地址如何一一对应 B 程序的逻辑地址变换成主存实地址 C 程序执行时将虚地址变换成对应的实存地址 D 指令的符号地址变换成二进制地址

2、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（ B ）

A 汇编语言机器级，操作系统机器级，高级语言机器级 B 微程序机器级，传统机器语言机器级，汇编语言机器级 C 传统机器语言机器级，高级语言机器级，汇编语言机器级 D 汇编语言机器级、应用语言机器级、高级语言机器级 3、操作码优化的主要目的是（ D ）

A 缩短指令字长 B减少程序总位数 C增加指令字表示的信息D A和B和C

4、为实现“执行K”与“分析k+1”的重叠，必须( C )。 A. 操作数和指令分别存放在两个独立编址的存储器中 B．采用多体交叉主存结构，且不共存于一个体中 C．有独立的指令分析部件和指令执行部件 D．增设指令缓冲寄存器 5、计算机系统中主存一辅存存储层次或Cache一主存存储层

1

次常用的替换算法是( B ) A 随机算法 B 近期最少使用算法 C 先进后出算法 D OPT算法 6、数据表示的意义是：（ B ） A 它是计算机系统能表示的数据类型 B 它是计算机硬件能直接识别的数据类型 C 它是计算机硬件能直接识别的数据结构 D 它是数据结构的一个子集

7、如果一台计算机的输入输出由一个独立的处理机来完成，它应该是：（ C ）

A 采用DMA的计算机系统 B 采用通道处理机的系统 C 采用I/O处理机的系统 D 采用程序传送方式进行I/O的系统

8、假设禁止向量为（1，5，6，8），则8位的初始冲突向量为（10110001）。若选择第二个任务在2拍后送入流水线，则新的冲突向量为（ C ）00101100

A 10101010 B 01011111 C 10111101 D 10111011 9、系列机软件兼容必须有的基本要求是：应能保证做到( D )。

A 向上兼容 B 向下兼容 C 向前兼容 D 向后

2

兼容

10、对计算机系统结构，下列哪个是透明的：（ B ） A 操作系统程序员 B 应用程序员 C 系统结构设计人员 D 机器语言程序设计人员 2、2－4扩展编码最多可以得到的码点数是（ D）???? A、6 B、7 C、10 D、13 4、静态流水线是指（ C ）

A、功能不能改变的流水线 B、可同时执行多种功能的流水线

C、同时只能完成一种功能的多功能流水线 D、各段之间的连接是固定不变的流水线 5、虚拟存储器主要是为了解决（ A ）

A、扩大存储系统的容量 B、Cache提高存储系统的速度

C、扩大存储系统的容量和速度 D、便于程序的访存操作

6、输入输出数据不经过CPU内部寄存器的输入输出方式是（ B ）

A、中断方式 B、DMA方式 C、程序查询方式 D、上述3种方式

3

8、RISC执行程序的速度比CISC要快的原因是（ D ） A、RISC的指令系统的指令数少

B、程序在RISC上编译生成的目标程序较短 C、RISC只允许load指令和store指令访存 D、RISC的指令平均周期数较少 10、字节多路通道的实际流量是（ C ）

A、 连接在这个通道上所有外设的最大数据传输速率 B、 连接在这个通道上所有外设的最小数据传输速率 C、 连接在这个通道上的所有设备的数据传输速率之和 D、

以上3者都不是

1、在计算机的系统结构设计中，提高硬件功能实现的比例会（ B ）????

A、 提高硬件利用率 B、提高系统的运行速度 C、减少需要的存储器容量 D、提高系统的性能价格比 2、平均码长最短的编码是（ D ）

A、定长码 B、2－4扩展码 C、3－6扩展码 D、哈夫曼编码

4、与线性流水线最大吞吐率有关的是（ C ）

A、各个子过程的执行时间 B、最快子过程的执行时间

4

C、最慢子过程的执行时间 D、最后子过程的执行时间

5、与全相联映象相比，组相联映象的优点是（ A ）???? A、目录表小 B、块冲突概率低 C、命中率高 D、主存利用率高 6、程序员编写程序时使用的访存地址是（ D ）

A、主存地址 B、物理地址 C、有效地址 D、逻辑地址

7、在顺序流动的指令流水线中，可能发生的相关有（ C ）？？？？

A、 同一条指令的读操作和写操作之间的先写后读相关 B、 先流入的指令的写操作与后流入的指令的读操作之间的先写后读相关

C、 后流入的指令的写操作与先流入的指令的读操作之间的先读后写相关

D、 两条指令的写操作之间的写－写相关 8、设置中断屏蔽码可以改变（ D ）????

A、多个中断源的中断请求优先级 B、多个中断服务程序被开始执行的次序

C、CPU对多个中断响应的优先次序 D、多个中断服务程序

5

执行完的次序

9、流水线的技术指标不包括( A )

A、响应比 B、吞吐率 C、加速比 D、效率

10、通道最大流量等于通道实际流量时，有可能发生局部的数据丢失，这是因为（ D ） A通道流量匹配的要求不合理

B多个外设的数据传输速率之和大于通道最大流量 C通道没有空闲的工作周期及时响应优先级低的外设的个别数据传送请求

D通道在数据传送过程中丢失数据

1、不同系列的机器之间，实现软件移植的途径不包括（ B ） A、采用统一的高级语言 B、采用统一的汇编语言 C、模拟 D、仿真

2、多处理机上两个程序之间若有先写后读的数据相关，则（ b）？？？？

A 、 可以并行执行 B 、不可能并行 C 任何情况均可交换串行 D、 必须并行执行 3、采用先行控制技术必须增设( D )。

A、指令缓冲栈 B、先行操作栈 C、数据缓冲栈 D、

6

以上都需要

6、指令流水线属于（ C ）

A、操作流水线 B、部件级流水线 C、系统级流水线 D、处理机级流水线

7、按Cache地址映像的块冲突概率从高到低的顺序是（A） A、 直接映像、组相联映像、全相联映像 B、 全相联映像、组相联映像、直接映像 C、 组相联映像、直接映像、全相联映像 D、 全相联映像、直接映像、组相联映像 1、系列机在软件兼容上应做到（ B ） A、

向前兼容，并向上兼容

B、 向后兼容，力争向上兼容

C、向前兼容，并向下兼容 D、向后兼容，力争向下兼容

7、指令的二次交叉执行方式是指（ B ）???? A、 同时解释执行相邻的2条指令

B、 把指令的解释执行过程分为指令分析和指令执行2个子过程交叉执行

C、 一条指令的取指、分析与执行同时解释执行 D、 取指K，分析K＋1与执行K＋2同时解释执行

7

8、虚拟存储器常用的地址映像是（ ） A全相联映像 B、组相联映像 C、直接映像 D、以上三种

9、直接存储器访问方式的并行性是指( C )???? A、

多个外设可同时并行地通过DMA控制器进行数据传

送

B、 外设和主存储器并行工作 C、 CPU和DMA控制器并行工作 D、 CPU和主存储器并行工作

5．浮点数表示的尾数的基Rm＝16，尾数的长度P＝8，可表示的规格化最大正尾数的值是（ ）???? A．0.5 B.0.125 C.0.25 D.1/64 3、非线性流水线的特征是（ B ）

A、一次运算中使用流水线中的多个功能段 B、一次运算中要多次使用流水线中的某些功能段 C、流水线中某些功能段在各次运算中的作用不同 D、流水线的各功能段在不同运算中可以有不同连接 二、填空题：

1、计算机实现是指计算机组成的 物理 实现,而计算机组成则是计算机系统结构的

8

逻辑 实现.

2、按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以把非线性流水线分为 动态非线性流水线 和 静态非线性流水线 。

3、地址映象是指将每个虚存单元按一定规则装入 主存储器 ；地址变换是指程序执行中，如何将多用户虚地址变换成对应的 主存实地址 。

4、 CPI表示执行每条指令所需的_ 平均时钟周期数 。 5、 按照Flynn分类法,根据指令流和数据流的不同组织方式,计算机系统的结构可以分为SISD(单指令流单数据流)、MISD（多指令流单数据流）、SIMD 和 MIＭＤ 。 6、数组多路通道与设备之间的数据传送的基本单位是_ 数据块 ___。

7、目前常用的基本输入输出方式有如下三种 I/0处理机方式 ,直接存储器访问 和 程序控制输入出 （程序查询方式和程序中断方式） 。

8、 为了满足向量计算机中运算器带宽的要求，通常有两种向量处理机结构，它们是P190 横向处理方式 和 纵向处理方式 。？？？？

3、流水线消除速度瓶颈的方法是 将瓶颈子过程进一步细分9

成若干个子子过程，使每一个子子过程与其他子过程时间相等；在瓶颈段设置多套功能段部件，使它们轮流工作 如 P169 。

4、就其本质而言，局部性原理包括 时间局部性 和空间局部性 两部分。

5、CPU响应中断后，硬件自动 关中断？？？？ 是为了使CPU不再响应其他中断请求，使保存断点及现场信息的工作不受干扰。在保存现场之后和执行中断服务功能之前，应使CPU 开中断 ，是为了能实现多重中断。P73—75 2、CISC中,各种指令的使用频率相差很悬殊，大量的统计数字表明，大约有 20% 的指令使用频率比较高，占据了 80% 的处理机时间。

3、根据所采用的地址映象和地址变换方法的不同，有多种类型的Cache，如全相联映象直接相联映像 和 组相联映像 。 5、按照流水线的各个功能段之间是否有反馈信号，可以把流水线分为 线性流水线和 非线性流水线 。

1、 当两个虚页要求装入同一主存页面的位置时，称为 页面冲突 ；当发生页面失效，同时又发生页面冲突时，需要进行 置换 。？？？？

2、若通道连接的外设台数为p，外设 i 的数据传输速率为fi，

10

那么，字节多路通道的实际流量fbyte＝ 所有通道流量之和∑fi，选择通道的实际流量fselect＝ 通道的最大流量max fi ，数组多路通道的实际流量fblock＝ 通道的最大流量max fi。 3、假设高速缓存Cache工作速度是主存的5倍，且cache被访问命中的概率为90％，则采用Cache后，能使整个存储系统获得的加速比3.57 Sn=T0/Tn=1/(1-Fe+Fe/Se)。 5、先行控制技术的关键是 缓冲技术 和 预处理技术 。 1、实现程序移植的主要途径有系列机、采用统一的高级语言、模拟和仿真。

2、假设将某系统某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40％，则采用加快措施后能使整个系统的性能提高 1.56 倍。 3、Cache存储器采用组相联映像是指组间采用 直接相联 映像，组内各块采用 全相联 映像方式。

1、数据存储空间的编址单位有 字 编址、字节 编址和 位 编址。P43

2、只需要通过该层的语言就可以使用机器，而不必关心其下层的机器级是如何工作和如何实现各自功能的，这一性质

称为 透明性 。？？？？ 3、在Cache存储器中，CPU每次可在写Cache的同时也写入

11

主存，也可以在发生块替换的时候才写回主存，这2种保持Cache一致性的方法中，前者称为 写直达法 ， 后者称为 写回法 。

4、在程序控制输入输出方式中，由CPU执行用户程序来完成输入输出工作；在中断输入输出方式中，由 CPU 执行 中断服务 程序来完成输入输出工作；在通道输入输出方式中，由 CPU 通道 执行 通道指令控制设备控制器 来完成输入输出工作。 三、名词解释： 1、

RISC :是在20世纪80年代发展起来的，尽量简化指令

功能，只保留那些指令功能简单，能在一个节拍内执行完成的指令，较复杂的功能用一段子程序来实现的计算机系统。 2、

虚拟存储器：是主存储器—联机外部存储器（辅存）层

次结构的进一步发展和完善，主要是为了克服主存容量满足不了要求而提出来的。（Cache与虚拟存储器的区别） 存储系统 Cache 虚拟存储器 要达到的目标 提高主存速度 扩大主存容量 实现方法 全部硬件 软件为主，硬件为辅 两级存储器速度比 3—10倍 100倍 页（块）大小 1—16字 1—16KB

12

等效存储容量 主存储器 虚拟存储器 透明性 对系统和应用程序员 仅对应用程序员 不命中是的处理方式 等待主存储器 任务切换 3、

向量处理：P189由于向量内部各个元素（分量）之间很

少相关，且对这些元素一般是执行同一种操作，比较容易发挥出流水线的效能，所以一般是将向量数据表示和流水线技术结合起来，构成向量流水处理机，以提高主要米昂想向量数组计算类应用的计算机的速度性能。 4、

流水线的吞吐率：流水线单位时间里能处理的任务数或

输出的结果数。

1、Amdahl定律 ：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高取决于这种执行方式的使用频率或占总执行时间的比例。实际上定义了加快某部分功能处理后，整个系统所获得的性能改进或执行时间的加速比的大小。加速比与两个因素有关：一是计算机执行某个人物的总时间中可被改进部分的时间所占的百分比，Fe=可改进部分占用的时间/改进前整个任务的执行时间，它总小于1；二是改进部分采用改进措施后比没有采用改进措施前性能提高倍数，Se=改进前改进部分的执行时间/改进后改进部分的执行时间，它总大于1。

13

（1）改进后整个任务的执行时间：Tn=T0(1-Fe+Fe/Se)，T0是改进前整个任务的执行时间。

（2）改进后整个系统的加速比：Sn=T0/Tn=1/(1-Fe+Fe/Se)。 （1-Fe）表示不可改进部分，当Fe=0，既没有改进部分，Sn为1，所以性能的提高幅度受改进部分所占比例的限制。当Se→∞，则Sn=1/1-Fe，因此，可获取性能改善极限受Fe值的约束。

2、透明性：一种本来存在的有差异的事物或属性，从某种角度来看似乎不再存在。

3、数据相关：P161由于重叠方式中“执行K”和“分析K+1”同时进行，而“执行K”写结果数据的空间和“分析K+1”的数据所在空间刚好相同，从而造成K指令和K+1指令的数据在空间上相关联。

4、地址映像：在Cache中，它是把主存空间地址映像到Cache地址空间，具体地说及时把存放在主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系。（虚拟：虚拟空间地址映像到主存地址空间，把虚拟地址编写的程序按照某种规则装入到主存储器中，并建立多用户虚地址与主存实地址之间的对应关系）

5、地址变换：指当程序已经装入到Cache之后， 在实际运行

14

过程中，把主存地址变换成Cache地址。（程序被装入主存储器后在程序执行时进行，多用户虚地址变换成主存是地址称为内部地址变换；多用户虚地址变换成此怕存储器地址称为外部地址变换）

6、中断源 ：引起中断请求的各种事件。

7、中断响应时间：允许该中断请求中断CPU现行程序的运行，转而去处理该请求的过程的时间。

8、局部性原理：从大量的统计中得到的一个规律。（程序对存储空间的90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在存储空间的90%的区域中）

9、流水线的链接 ：按其分为线性流水线和非线性流水线。 3、非线性流水线 ：存在反馈回路，从输入到处处过程中，流水线经反馈回路和多路开关时某些段可能要多次通过，而有些段可能被跳过。

4、链接技术：P194实质上是吧“相关通路”的思想引入到向量指令的执行过程之中。只有在前一条指令的第1个结果分量送入结果向量寄存器组的那一个时钟周期为允许连接时间才行。

5、静态流水线：同一时间内它时能以一种工作方式工作的多功能流水线。（可是是单功能的）

15

发生块失效且块争用的时刻？？？？，计算Cache命中率。3/15=20%

3、有5个中断源D1、D2、D3、D4、D5，优先级从高到低1、2、3、4、5，已知各种中断处理程序的中断屏蔽码设置如下表所示，中断屏蔽位为“0”表示该中断源被屏蔽；“1”对应开放。

中断中断屏蔽码 源 D1 D2 D3 D4 D5

（1） 5个中断源同时请求中断服务时，处理机响应次序是

什么D5—D4—D3—D2—D1？实际中断处理次序是什么D1—D2—D3—D5—D4？

（2） 假设从处理机响应中断源的请求到第一次开中断所

用时间为1个单位时间，处理机运行中断服务程序的

21

D1 1 0 1 1 1 D2 0 1 0 1 1 D3 0 0 1 0 1 D4 0 0 0 1 0 D5 0 0 0 1 1

其他部分所用时间为4个单位时间。在执行用户程序时，同时发生第3、4级和第5级中断请求；过了3个单位时间之后，又同时发生第1、2级中断请求。请画出中断处理程序的运行过程示意图，说明中断处理次序。

执行完1，2返回用户程序，开中断1个单位时间，再到D3。

4、有一个5段流水线，各段执行时间均为△t，其预约表如下表所示：

S1 S2 S3 S4 S5

(1) 画出流水线调度的状态有向图。 禁止启动距离（1,3,6）

(2) 分别求出允许不等时间间隔调度和等时间间隔调

22

T1 √ T2 √ T3 √ T4 √ √ T5 √ √ T6 √ T7 √ √ 度？？？？的两种最优调度策略（确定启动距离，最多的3），以及这两种调度策略的流水线最大吞吐率 (3) 若连续输入10个任务，求等时间间隔调度的流水线实际吞吐率和加速比。

1、某个处理机的时钟频率为15MHz,执行测试程序的速率为10MIPS，假设每次存储器存取需1个时钟周期的时间，试问： （2） 处理机的CPI值是多少？MIPS=时钟f/CPI*106，

CPI=15*106/107=1.5

（3） 假设将处理机的时钟频率提高到30MHz，但存储器的工

作速率不变，这使得每次存储器存取需2个时钟周期。如果测试程序得30％指令需要1次访存，5％指令需要2次访存，其他指令不需要访存，试求测试程序在改进后得处理机上执行得 MIPS=30*106/CPI*106,=37.5。CPI=30%*2+5%*4+65%*0=0.8

2、在CRAY-1机上，Vi为向量寄存器，设向量长度为64，s为标量寄存器，所有浮点功能执行部件的执行时间分别为：加法需6拍，相乘需7拍，从存储器读数需6拍，结果打入寄存器和启动功能部件（包括存储器）各需1拍，计算下列指令序列全部完成所需要的拍数。（需划出流水线链接图）

23

V3←存储器 V2←V0＋V1 V4←V2＊V3 存储器←V4

1+6+1+1+7+1+1+6+63=87

3、有5级中断源D1、D2、D3、D4、D5，优先级从高到低1、2、3、4、5，已知各种中断处理程序的中断屏蔽码设置如下表所示，中断屏蔽位为“1”表示该中断源被屏蔽；“0”对应开放。

中断中断屏蔽码 源 D1 D2 D3 D4 D5

（3） 5个中断源同时请求中断服务时，处理机响应次序是

什么D5→D4→D3→D2→D1？实际中断处理次序是什么D3→D2→D5→D4→D1？

（4） 若在运行用户程序时，同时出现第2、4级中断请求，

24

D1 1 0 0 0 0 D2 1 1 0 1 1 D3 1 1 1 1 1 D4 1 0 0 1 0 D5 1 0 0 1 1

而在第2级中断已经开始处理却处理未完成时又出现第1，3，5级中断请求。请画出中断处理程序的运行过程示意图，说明中断处理次序。

2、在CRAY1机上，V为向量寄存器，设向量长度均为32，S为标量寄存

器，所用浮点功能执行部件的执行时间分别为：加法需要6拍，相乘需要7拍，从存储器读数需要6拍，打入寄存器及启动功能部件（包括存储器）各需要1拍。问下列各指令组中哪些指令可以链接，哪些可以并行执行，试说明原理并分别计算出各指令组合全部完成所需的拍数。

（1）V0 存储器 （2）V2

V1 V0+V1

V2＋V3 V3 存储器

V4 V5*V6 V4 V2*V3 （1）第一条指令和第二条指令可以并行执行，V5和V6的读取可以并行执行。无连接， 拍数=1+6+1+N-1+1+7+1+N-1=79

（2）第一条指令和第二条指令可以连接和并行执行， 拍数=1+6+1+1+7+1+31=48

4、一条3个功能段的非线性流水线及其预约表如下： 输出

25

本文来源：https://www.bwwdw.com/article/cnxg.html