计算机系统结构期末重点题目及考点

计算机系统结构期末重点题目及考点：1.2.如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释，若执行第一级的一条指令需kns，那执行第2级、第3级、第4级的指令需要多少时间？第1级1条1级指令kns第2级1条2级指令N条1级指令1·N·kns=Nkns第3级1条3级指令N条2级指令1·N·N·kns=N2kns第4级1条4级指令N条3级指令1·N·N·N·kns=N3kns1.8.从机器（汇编）语言程序员看，以下哪些是透明的？指令地址寄存器；指令缓冲器；时标发生器；条件码寄存器；乘法器；主存地址寄存器；磁盘外设；先行进位链；移位器；通用寄存器；中断字寄存器。第一组区别，加3位编码），编码性能如下表；(4)3/7扩展编码是15/15/15法的变种，第一组3条指令，码长为2（共有4种组合，其中3种组合分别代表3条指令，留1种组合作为扩展前缀标志）,第二组7条指令，码长为5（2位固定的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合），编码性能如下表。Huffman编码2/8扩展编码3/7扩展编码平均码长L2.993.13.2信息冗余量R1.10%4.61%7.59%2.14一台模型机共有7条指令，各指令的使用频率分别为35%，25%，20%，10%，5%，3%和2%，有8个通用数据寄存器，2个变址寄存器。(1)要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。(2)设计8字长的寄存器-寄存器型指令3条，16位字长的寄存器-存储器型变址寻址方式指令4条，变址范围不小于±127。请设计指令格式，并给出各字段的长度和操作码的编码。解：(1)要使得到的操作码长度最短，应采用Huffman编码，构造Huffman树如下：由此可以得到7条指令的编码分别如下：这样，采用Huffman编码法得到的操作码的平均长度为：H=2×(0.35+0.25+0.20)+3×0.10+4×0.05+5×(0.03+0.02)=1.6+0.3+0.2+0.25=2.35(2)设计8位字长的寄存器-寄存器型变址寻址方式指令如下，因为只有8个通用寄存器，所以寄存器地址需3位，操作码只有两位，设计格式如下：三条指令的操作码分别为00，01，10设计16位字长的寄存器-存储器型变址寻址方式指令如下：四条指令的操作码分别为1100，1101，1110，11112.15某处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令三类，并假设每个地址字段的长度均为6位。(1)如果双地址指令有15条，单地址指令和零地址指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。(2)如果要求三类指令的比例大致为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。解：(1)15条/63条/64条(2)14条/126条/128条(1)根据指令地址的数量来决定各种指令在指令空间上的分布：如果我们按照从小到大的顺序分配操作码，这样，按照指令数值从小到大的顺序，分别为双地址指令、单地址指令和零地址指令。其次可以根据指令的条数来大致的估计操作码的长度：双指令15条，需要4位操作码来区分，剩下的12位操作码平均分给单地址和零地址指令，每种指令可以用6位操作码来区分，这样，各指令的条数为：双地址指令15条，操作码：0000~1110；单地址指令2^6-1=63条，操作码：1111000000~1111111110；零地址指令64条，操作码：1111111111000000~1111111111111111。(2)与上面的分析相同，可以得出答案：双地址指令14条，操作码：0000~1101；单地址指令2^6x2-2=126条，1110000000~1110111110，1111000000~1111111110；零地址指令128条1110111111000000~1110111111111111,1111111111000000~1111111111111111(2)B双地址指令同上,14条，操作码：0000~1101；单地址指令64+62=126条，64条单地址指令操作码1110000000~1110111111，62条单地址指令操作码1111000000~1111111101；零地址指令128条1111111110000000~1110111110111111,1111111111000000~1111111111111111：3.9：一个页式虚拟存储器的虚存空间大小为4Gb，页面大小为4KB，每个页表存储子要占用4个字节。计算这个页式虚拟存储器需要采用几级页表？答：Log2（4G/4K）/Log2（4K/4）=2.0.取整得2，所以需要2级页表如果要求页表所占用的总主存页面数最小，请分配每一级页表的实际存储容量各为多少字节？答：第一季页表为一个页面大小，为4kb，第二级页表被占用1k个页面，为4mb页表的哪些部分必须存放在主存中？哪些可以放在辅存中？答：第一级页表必须放在主存中，二级页表只需将正在运行的程序的相关页表放在主存中，其他都可以放在辅存中。3.12一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。

（1）写出多用户虚地址的格式，并标出各字段的长度。

（2）写出主存地址的格式，并标出各字段的长度。

（3）快表的字长为多少位？分几个字段？各字段的长度为多少位？

（4）慢表的容量是多少个存储字？每个存储字的长度为多少位？

答：用户号：64＝26，虚页号：1024＝210，页内地址：4K＝212，主存页数：8M/4K＝211

（1）多用户虚地址：

用户号（6位）＋虚页号（10位）＋页内地址（12位）

共28位

（2）主存地址：

主存实页号（11位）＋页内地址（12位）

共23位

快表字长27位；分3个字段：用户号6位，虚页号10位，实页号11位

（4）慢表容量为2(6+10)，每个存储字长为：主存页号＋1＝12位。3.143.14在页式虚拟存储器中，一个程序由P1~P5共5个虚页组成。在程序执行过程中依次访问到的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LRU和OPT三种替换算法对这三页主存进行调度。（1） 画出主存页面调入、替换和命中的情况表。（2） 统计三种页面替换算法的页命中率。答案：解：三种替换算法的替换过程：页地址流232152453252FIFO222255553333命中3次33332222255111444442调调命调替替替命替命替替进进中进换换换中换中换换222152453252LRU33215245325命中5次321524533调调命调替命替命替替命命进进中进换中换中换换中中OPT222222444222命中6次333333333331555555555调调命调替命替命命替命命进进中进换中换中中换中中3.15.一个程序由五个虚页组成，采用lfu替换算法，在程序中依次访问的页地址流如下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3可能的最高页命中率是多少？至少要分配给该程序多少个主存页面才能获得最高的命中率?如果在程序中每访问一个页面，平均要对该页面内的存储单元访问1024次，求访问单元的命中率？答案：（1）在分配的主存页面数目大于等于5的情况下，这时，除了第一次调入不命中，以后的访问均命中，可以达到最高的页面命中率：实际命中的次数为7次，所以可能达到的最高页面命中率为：（2）由于在页面数大于等于5的情况下，肯定可以达到最高命中率，所以我们来看页面数小于5时能否达到该命中率：分配的主存页面数等于4时，调度过程如下：LFULFU算法44444*11111*11命中7次

555*55555*555

3333*33*333*3

2222*22222调入调入调入调入命中调入命中命中命中命中命中命中此时也可以达到最高命中率；分配的主存页面等于3时，调度过程如下：LFULFU算法444*222*33*333*3命中3次

555*555*222*11

333*1111*555调入调入调入调入命中调入调入调入命中调入调入命中此时不能达到最高命中率。所以至少应该分配4个主存页面。（3)我们假设程序每次只访问一个存储单元，这样，对每一个特定页面的访问过程可以描述如下：因为第一次总是不命中的，而平均起来，随后的1023次总是命中的，然后再次被调出主存，并再次重复先前的过程。所以访问存储单元的命中率为：欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。P=453251323513命中次数4532513235134532513235145325112354432551224444444n=10n=2√1n=3√√√3n=4√√√√√√√7n=5√√√√√√√7(1)Hmax=7/12≈58.3%(2)n=4(3)当1次页面访问代表连续1024次该页内存储单元访问时，后1023次单元访问肯定是命中的，而第1次单元访问的命中情况与这1次页面访问的命中情况相同。根据上图中最高命中情况，共有7次页命中（折算为7×1024次单元命中），5次页不命中（折算为5×1023次单元命中，也可写为5×1024-5），单元访问总次数为12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96%3.16.一个程序由1200条指令组成，每条指令的字长均为4B。假设这个程访问虚拟存储器的字地址流为：12，40，260，280，180，800，500，560，600，1100，1200，1000。采用FIFO替换算法，分配给这个程序的主存容量为2048B。

在下列不同的页面大小情况下，分别写出该程序执行过程中访存的虚页地址流，并分别计算主存命中率。

(1)

页的大小为1024B。

(2)

页的大小为512B。

(3)

页的大小为2048B。

解：(1)

（6分）页的大小为1

024B，即页面大小为256字；主存容量为2048B，即分配n=2个实页。给定的程序访存字地址流对主存空间的使用过程如图所示。主存命中率H1=6／12

=

0．50

（8分）页的大小为512B，即页面大小为128字；主存容量为2

048B，即分配n=4个实页。给定的程序访存字地址流对主存空间的使用过程如图所示。主存命中率为H2

=

3／12

=

0．25

页的大小为2048B，即页面大小为512字，主存容量为2048B，即分配n=1个实页。给定的程序访存字地址流对主存空间的使用过程如图所示。主存命中率为H3

=

6／12

=

0．503.19

在一个采用组相联映象方式的Cache存储系统中，主存由B0～B7共8块组成，Cache有2组，每组2块，每块大小为16B。在一个程序执行过程中，访存的主存块地址流为：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3。

(1)写出主存地址的格式，并标出各字段的长度。

(2)写出Cache地址的格式，并标出各字段的长度。

(3)指出主存与Cache之间各个块的映象关系。

(4)若Cache的4个块号为C0、C1、C2和C3，列出程序执行过程中的Cache块地址流。

(5)若采用FIFO替换算法，计算Cache的块命中率。

(6)若采用LRU替换算法，计算Cache的块命中率。

(7)若改为全相联映象方式，再做(5)和(6)。

(8)若在程序执行过程中，每从主存装入一块到Cache，平均要对这个块访问16次，计算在这种情况下的Cache命中率。答案：解：（1）（2）采用组相联映象时，主存和Cache地址的格式分别为：

主存按Cache的大小分区，现主存有8个块，Cache有2×2=4个块，则主存分为8/4=2个区，区号E的长度为1位。又每区有2个组，则组号G、g的长度都为1位。而每组有2个块，则块号B、b的长度又都为1位。每块大小为16个存储字，故块内地址W、w的长度都为4位。

（3）根据组相联映象的规则，主存块0～7与Cache块0～3之间的映象关系为：主存块0、1、4、5与Cache块0、1之间全相联，主存块2、3、6、7与Cache块2、3之间全相联。

（4）根据组相联映象的规则，该主存块地址流相应的一种Cache块地址流如下表所示（组内替换算法为FIFO）。

时间：

1

2

3

4

5

6

7

8

9

10

11

12

主存块地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache块地址流：

C2

C3

C0

C1

C0

C2

C2

C0

C0

C0

C3

C（5）组内替换算法采用FIFO时，Cache块0～3的使用过程如下表所示。

时间：

1

2

3

4

5

6

7

8

9

10

11

12

主存块地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache块0

Cache块1

Cache块2

Cache块3

命中

命中

命中

可见命中三次，Cache块命中率为Hi

=

3/12

=

0.25。

组内替换算法采用LRU时，Cache块0～3的使用过程如下表所示。时间：

1

2

3

4

5

6

7

8

9

10

11

12

主存块地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache块0

Cache块1

Cache块2

Cache块3

命中

命中

命中

命中

可见命中四次，Cache块命中率为Hi

=

4/12

=

0.33。

全相联映象的规则是主存块0～7可装入Cache块0～3的任一块上。

当替换算法采用FIFO时，Cache块0～3的使用过程如下表所示。时间：

1

2

3

4

5

6

7

8

9

10

11

12

主存块地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache块0

Cache块1

Cache块2

Cache块3

命中

命中

命中

命中

可见命中四次，Cache块命中率为Hi

=

4/12

=

0.33。

当替换算法采用LRU时，Cache块0～3的使用过程如下表所示。

时间：

1

2

3

4

5

6

7

8

9

10

11

12

主存块地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B块0

Cache块1

Cache块2

Cache块3

命中

命中

命中

可见命中三次，Cache块命中率为Hi

=

3/12

=

0.25。

（8）当命中三次时，Cache的命中率为Hi

=

（12×16-9）/（12×16）≈1，当命中四次时，Cache的命中率为Hi

=

（12×16-8）/（12×16）≈1。3.203.23对于一个采用组相联映象方式和FIFO替换算法的Cache，发现它的等效访问时间太长，为此，提出如下建议：

增大主存的容量。答案：基本无关

（2）

提高主存的速度。

答案：能够减小等效访问时间，T=TcH+Tm(1-H),通过减小Tm能够减小T。（3）

增大Cache的容量

答案：当cache比较小时，增大cache对减少等效访问时间效果明显；当cache容量达到一定程度时效果逐渐不明显。（4）

提高Cache的速度。

Cache的总容量和组大小不变，增大块的大小。

（6）

Cache的总容量和块大小不变，增大组的大小。答案：有一个极大值，在这个极大值点，等效访问时间最小。

（7）

Cache的总容量和块大小不变，增加组数。

（8）

替换算法由FIFO改为LFU

：4.4有5个中断源D1、D2、D3、D4和D5，它们的中断优先级从高到低依次是1-5级别。这些中断源的中断优先级、正常情况下的中断屏蔽码和改变后的中断屏蔽码如下表所示。每个中断源有5位中断屏蔽码，其中0表示该中断源开放，1表示该中断源被屏蔽。(1)当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实际上中断处理的先后次序是什么？

(2)当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实际上中断处理的先后次序是什么？

(3)如果采用改变后的中断屏蔽码，

D1、D2、D3、D4和D5同时请求中断时，画出处理器响应各中断源的中断请求和实际运行中断服务程序过程的示意图。答案：(1)

当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是D1、D2、D3、D4、D5。

实际上中断处理的先后次序是D1、D2、D3、D4、D5。

(2)

当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是D1、D2、D3、D4、D5。

实际上中断处理的先后次序是D4、D5、D3、D2、D1。

如果采用改变后的中断屏蔽码，

D1、D2、D3、D4和D5同时请求中断时，处理器响应各中断源的中断请求和实际运行中断服务程序过程如下图所示：4.5某处理机共有4个中断源，分别为D1、D2、D3、D4,要求处理机响应中断源的中断服务请求的次序从高到低分别是D1、D2、D3、D4，而处理机实际为各中断源服务的先后次序为D3，D3，D4，D1.每个中断源有4位中断屏蔽码，其中，0表示该中断源被屏蔽，1表示该中断源开放。已知中断服务次序为3-2-4-1，。(1)中断屏蔽字表如下图；D1D2D3D4D10111D20010D30000D40110(2)中断过程示意图如右图。时间中断请求 主程序 1级2级3级4级D1，D2D3，D44.74.8一个字节多路通道连接有4台外围设备，每台设备发出输入输出服务请求的时间间隔，他们的服务优先级和发出第一次服务请求的时刻表如下：设备名称

D1

D2

D3

D4

发服务请求间隔

10µs

75

µs

15

µs

50

µs

服务优先级

1

4

2

3

发第一次请求时刻

0

µs

70

µs

10

µs

20

µs

（1）计算这个字节多路通道的实际流量和工作周期

（2）在数据传送期间，如果通道选择一次设备的时间为3

µs，传送一个字节的时间为2

µs，画出这个字节多路通道响应各设备请求和为设备服务的时间关系图。(1)f=2×105字节/秒，T=5us(2)Ts+Td=5us，通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现，才能确定是否丢失数据（因为响应优先级低的设备较易丢失数据）。(3)5，160，20，40；(4)D2丢失第一次请求的数据；(5)参见P245。：5.8用一条5个功能段的浮点加法器流水线计算每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。[解答]首先需要考虑的是，10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：I1： R1←A1+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←A9+A10I6： R6←R1+R2I7： R7←R3+R4I8： R8←R5+R6I9： F←R7+R8这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图如下，图中的数字是指令号。整个计算过程需要21Δt，所以吞吐率为：加速比为：效率为：5.9一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这条流水线计算：画出流水线时空图，并计算流水