计算机组织与系统结构第四章习题答案

第 4 章 习 题 答 案

3. 已知某机主存空间大小为64KB，按字节编址。要求： （1）若用1K×4位的SRAM芯片构成该主存储器，需要多少个芯片？ （2）主存地址共多少位？几位用于选片？几位用于片内选址？ （3）画出该存储器的逻辑框图。 参考答案： （1）64KB / 1K×4位 = 64×2 = 128片。

（2）因为是按字节编址，所以主存地址共16位，6位选片，10位片内选址。

（3）显然，位方向上扩展了2倍，字方向扩展了64倍。下图中片选信号CS为高电平有效。

Y0A15………A10A9…Y63A0…1K*4SRAMCSWR1K*4SRAMCSWR……1K*4SRAMCSWR1K*4SRAMCSWRD7…D0WE 4. 用64K×1位的DRAM芯片构成256K×8位的存储器。要求： （1） 计算所需芯片数，并画出该存储器的逻辑框图。

（2） 若采用异步刷新方式，每单元刷新间隔不超过2ms，则产生刷新信号的间隔是多少时间？若采

用集中刷新方式，则存储器刷新一遍最少用多少读写周期？ 参考答案：

（1）256KB / 64K×1位 = 4×8 = 32片。存储器逻辑框图见下页（图中片选信号CS为高电平有效）。 （2）因为每个单元的刷新间隔为2ms，所以，采用异步刷新时，在2ms内每行必须被刷新一次，且

仅被刷新一次。因为DRAM芯片存储阵列为64K=256×256，所以一共有256行。因此，存储器控制器必须每隔2ms/256=7.8μs产生一次刷新信号。采用集中刷新方式时，整个存储器刷新一遍需要256个存储（读写）周期，在这个过程中，存储器不能进行读写操作。

A17Y0……A16A15……Y3A0CSCSCSCSCSCSDRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1CSDRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1CSCSCSCSCSCSCSCSCS……DRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1D7…D0

5. 用8K×8位的EPROM芯片组成32K×16位的只读存储器，试问：

（1）数据寄存器最少应有多少位？ （2） 地址寄存器最少应有多少位？ （3） 共需多少个EPROM芯片？ （4） 画出该只读存储器的逻辑框图。 参考答案：

（1）数据寄存器最少有16位。

（2）地址寄存器最少有：15位（若按16位的字编址）；16位（若按字节编址）。 （3）共需要 32K×16位 / 8K×8位= 4×2 = 8片。

（4）该只读存储器的逻辑框图如下（假定按字编址，图中片选信号CS为高电平有效）。

Y0A14A13A12………………CSWR……CS…………CSWR……Y3A08K*8EPROM8K*8EPROMWR8K*8EPROM8K*8EPROMWRCSD15……D8D7……D0

6. 某计算机中已配有0000H～7FFFH的ROM区域，现在再用8K×4位的RAM芯片形成32K×8位的存

储区域，CPU地址总线为A0-A15，数据总线为D0-D7，控制信号为R/W#（读/写）、MREQ#（访存）。要求说明地址译码方案，并画出ROM芯片、RAM芯片与CPU之间的连接图。假定上述其他条件不变，只是CPU地址线改为24根，地址范围000000H～007FFFH为ROM区，剩下的所有地址空间都用8K×4位的RAM芯片配置，则需要多少个这样的RAM芯片？ 参考答案：

CPU地址线共16位，故存储器地址空间为0000H～FFFFH，其中，8000H～FFFFH为RAM区，

WE共215=32K个单元，其空间大小为32KB，故需8K×4位的芯片数为32KB/8K×4位= 4×2 = 8片。

因为ROM区在0000H～7FFFH，RAM区在8000H～FFFFH，所以可通过最高位地址A15来区分，当A15为0时选中ROM芯片；为1时选中RAM芯片，此时，根据A14和A13进行译码，得到4个译码信号，分别用于4组字扩展芯片的片选信号。（图略，可参照图4.15）

若CPU地址线为24位，ROM区为000000H～007FFFH，则ROM区大小为32KB，总大小为16MB=214KB=512×32KB，所以RAM区大小为511×32KB，共需使用RAM芯片数为511×32KB/8K×4位=511×4×2个芯片。

7. 假定一个存储器系统支持4体交叉存取，某程序执行过程中访问地址序列为3, 9, 17, 2, 51, 37, 13, 4, 8, 41,

67, 10，则哪些地址访问会发生体冲突？ 参考答案：

对于4体交叉访问的存储系统，每个存储模块的地址分布为： Bank0: 0、4、8、12、16 … …

Bank1: 1、5、9、13、17 …37 …41… Bank2: 2、6、10、14、18 … … Bank3: 3、7、11、15、19…51…67

如果给定的访存地址在相邻的4次访问中出现在同一个Bank内，就会发生访存冲突。所以，17和9、37和17、13和37、8和4发生冲突。

8. 现代计算机中，SRAM一般用于实现快速小容量的cache，而DRAM用于实现慢速大容量的主存。以

前超级计算机通常不提供cache，而是用SRAM来实现主存（如，Cray巨型机），请问：如果不考虑成本，你还这样设计高性能计算机吗？为什么？ 参考答案：

不这样做的理由主要有以下两个方面：

① 主存越大越好，主存大，缺页率降低，因而减少了访问磁盘所需的时间。显然用DRAM芯片比用SRAM芯片构成的主存容量大的多。

② 程序访问的局部性特点使得cache的命中率很高，因而，即使主存没有用快速的SRAM芯片而是用DRAM芯片，也不会影响到访问速度。

9. 分别给出具有下列要求的程序或程序段的示例：

（1）对于数据的访问，几乎没有时间局部性和空间局部性。

（2）对于数据的访问，有很好的时间局部性，但几乎没有空间局部性。 （3）对于数据的访问，有很好的空间局部性，但几乎没有时间局部性。 （4）对于数据的访问，空间局部性和时间局部性都好。 参考答案（略）：

可以给出许多类似的示例。例如，对于按行优先存放在内存的多维数组，如果按列优先访问数组元素，则空间局部性就差，如果在一个循环体中某个数组元素只被访问一次，则时间局部性就差。

10. 假定某机主存空间大小1GB，按字节编址。cache的数据区（即不包括标记、有效位等存储区）有64KB，

块大小为128字节，采用直接映射和全写（write-through）方式。请问：

（1）主存地址如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。 （2）cache的总容量为多少位？ 参考答案：

（1）主存空间大小为1GB，按字节编址，说明主存地址为30位。cache共有64KB/128B=512行，因

此，行索引（行号）为9位；块大小128字节，说明块内地址为7位。因此，30位主存地址中，高14位为标志（Tag）；中间9位为行索引；低7位为块内地址。

（2）因为采用直接映射，所以cache中无需替换算法所需控制位，全写方式下也无需修改（dirty）位，

而标志位和有效位总是必须有的，所以，cache总容量为512×(128×8+14+1)=519.5K位。

11. 假定某计算机的cache共16行，开始为空，块大小为1个字，采用直接映射方式。CPU执行某程序时，

依次访问以下地址序列：2，3，11，16，21，13，64，48，19，11，3，22，4，27，6和11。要求： （1）说明每次访问是命中还是缺失，试计算访问上述地址序列的命中率。

（2）若cache数据区容量不变，而块大小改为4个字，则上述地址序列的命中情况又如何？ 参考答案 （1） cache采用直接映射方式，其数据区容量为16行×1字/行=16字；主存被划分成1字/块，所以，

主存块号 = 字号。因此，映射公式为：cache行号 = 主存块号 mod 16 = 字号 mod 16。 开始cache为空，所以第一次都是miss，以下是映射关系（字号-cache行号）和命中情况。 2-2: miss，3-3: miss，11-11: miss，16-0: miss, 21-5: miss，13-13: miss，64-0: miss、replace， 48-0: miss、replace，19-3: miss、replace，11-11: hit, 3-3: miss、replace，22-6: miss， 4-4: miss，27-11: miss、replace，6-6: miss、replace，11-11: miss、replace。 只有一次命中！

（2）cache采用直接映射方式，数据区容量不变，为16个字，每块大小为4个字，所以，cache共有

4行；主存被划分为4个字/块，所以，主存块号 = [字号/4]。因此，映射公式为：cache行号 = 主存块号 mod 4 = [字号/4] mod 4。

以下是映射关系（字号-主存块号-cache行号）和命中情况。

2-0-0: miss，3-0-0: hit，11-2-2: miss，16-4-0: miss、replace，21-5-1、13-3-3: miss， 64-16-0、48-12-0、19-4-0: miss, replace，11-2-2: hit，3-0-0: miss、replace，

22-5-1: hit，4-1-1: miss、replace，27-6-2: miss、replace，6-1-1: hit，11-2-2: miss、replace。

命中4次。

由此可见，块变大后，能有效利用访问的空间局部性，从而使命中率提高！

12. 假定数组元素在主存按从左到右的下标顺序存放。试改变下列函数中循环的顺序，使得其数组元素的

访问与排列顺序一致，并说明为什么修改后的程序比原来的程序执行时间短。 int sum_array ( int a[N][N][N]) { int i, j, k, sum=0; for (i=0; i < N; i++) for (j=0; j < N; j++) for (k=0; k < N; k++) sum+=a[k][i][j];

return sum; }

参考答案：

int sum_array ( int a[N][N][N]) { int i, j, k, sum=0; for (k=0; k < N; k++) for (i=0; i < N; i++) for (j=0; j < N; j++) sum+=a[k][i][j];

return sum;

}

修改后程序的数组元素的访问与排列顺序一致，使得空间局部性比原程序好，故执行时间更短。

13. 分析比较以下三个函数的空间局部性，并指出哪个最好，哪个最差？

# define N 1000 typedef struct { int vel[3]; int acc[3]; } point; point p[N]; void clear1(point *p, int n) { int i, j; for (i = 0; i < n; i++) { for (j = 0; j<3; j++) p[i].vel[j] = 0; for (j = 0; i<3; j++) p[i].acc[j] = 0; } } # define N 1000 typedef struct { int vel[3]; int acc[3]; } point; point p[N]; void clear2(point *p, int n) { int i, j; for (i=0; i

参考答案：

对于函数clear1，其数组访问顺序与在内存的存放顺序完全一致，因此，空间局部性最好。

对于函数clear2，其数组访问顺序在每个数组元素内跳越式访问，相邻两次访问的单元最大相差3个int型变量（假定sizeof(int)=4，则相当于12B），因此空间局部性比clear1差。若主存块大小比12B小的话，则大大影响命中率。

对于函数clear3，其数组访问顺序与在内存的存放顺序不一致，相邻两次访问的单元都相差6个int型变量（假定sizeof(int)=4，则相当于24B）因此，空间局部性比clear2还差。若主存块大小比24B小的话，则大大影响命中率。

14. 以下是计算两个向量点积的程序段：

float dotproduct (float x[8], float y[8]) {

float sum = 0.0; int i,;

for (i = 0; i < 8; i++) sum += x[i] * y[i]; return sum; }

要求：

（1）试分析该段代码中数组x和y的时间局部性和空间局部性，并推断命中率的高低。

（2）假定该段程序运行的计算机的数据cache采用直接映射方式，其数据区容量为32字节，每个主

对于以下的访问地址序列：0，3，4，8，12，16，20，cache1缺失7次，而cache2缺失6次； 如此等等，可以找出很多。

20. 提高关联度通常会降低缺失率，但并不总是这样。请给出一个地址访问序列，使得采用LRU替换算法

的2-路组相联映射cache比具有同样大小的直接映射cache的缺失率更高。 参考答案：

2-路组相联cache的组数是直接映射cache的行数的一半，所以，可以找到一个地址序列A、B、C，使得：A映射到某一个cache行，B和C同时映射到另一个cache行，并且A、B、C映射到同一个cache组。这样，如果访存的地址序列为A、B、C、A、B、C、A、B、C …，则对于直接映射cache，其命中情况为：miss/miss/miss /hit/miss/miss /hit/miss/miss/… 命中率可达33.3%。

对于组相联cache，因为A、B、C映射到同一个组，每组只有2行，采用LRU替换算法，所以，每个地址处的数据刚调出cache就又被访问到，每次都是miss，命中率为0。 例如：假定直接映射cache为4行×1字/行，同样大小的2-路组相联cache为2组×2行/组×1字/行 当访问序列为：0、2、4、0、2、4、0、2、4、 …（局部块大小为3）时，则出现上述情况。

当访问的局部块大于组的大小时，可能会发生“颠簸”现象：刚被替换出去的数据又被访问，导致缺失率为100%！

21. 假定有三个处理器，分别带有以下不同的cache：

cache1：采用直接映射方式，块大小为1个字，指令和数据的缺失率分别为4%和6%； cache2：采用直接映射方式，块大小为4个字，指令和数据的缺失率分别为2%和4%；

cache3：采用2-路组相联映射方式，块大小为4个字，指令和数据的缺失率分别为2%和3%。

在这些处理器上运行相同的程序，该程序的CPI为2.0，其中有一半是访存指令。若缺失损失为（块大小+6）个时钟周期，处理器1和处理器2的时钟周期都为420ps，带有cache3的处理器3的时钟周期为450ps。请问：哪个处理器因cache缺失而引起的额外开销最大？哪个处理器执行速度最快？ 参考答案：

假设所运行的程序共执行N条指令，每条访存指令仅读写一次内存数据，则在该程序执行过程中各处理器因cache缺失而引起的额外开销和执行时间计算如下。 对于处理器1： 额外开销为：N×(4% + 6%×50%)×(1+6) = 0.49 N个时钟周期 执行程序所需时间为：(N×2.0 +0.49N)×420ps = 1045.8N ps 对于处理器2： 额外开销为：N×(2%+4%×50%)×(4+6) = 0.40N个时钟周期 执行程序所需时间为：(N×2.0+0.40N)×420ps=1008N ps 对于处理器3： 额外开销为：N×(2%+3%×50%)×(4+6) = 0.35N个时钟周期 执行程序所需时间为：(N×2.0+0.35N)×450ps=1057.5N ps

由此可见，处理器1的cache缺失引起的额外开销最大，处理器2的执行速度最快。

22. 假定某处理器带有一个数据区容量为256B的cache，其块大小为32B。以下C语言程序段运行在该处理

器上，sizeof(int) = 4，编译器将变量i, j, c, s都分配在通用寄存器中，因此，只要考虑数组元素的访存情况。若cache采用直接映射方式，则当s=64和s=63时，缺失率分别为多少？若cache采用2-路组相联映射方式，则当s=64和s=63时，缺失率又分别为多少？ int i, j, c, s, a[128]; ……

for ( i = 0; i < 10000; i++ ) for ( j = 0; j < 128; j=j+s ) c = a[j];

参考答案：

已知块大小为32B，cache容量为256B = 8行×8字/行× 4B/字，仅考虑数组访问情况。

1) 直接映射，s=64: 访存顺序为a[0]、a[64] , a[0]、a[64], … … , 共循环10000次。这两个元素被映射到同一个cache行中，每次都会发生冲突，因此缺失率为100%。

2) 直接映射，s=63: 访存顺序为a[0]、a[63]、a[126], a[0]、a[63]、a[126], … …共循环10000次。这三个元素中后面两个元素因为映射到同一个cache行中，因此每次都会发生冲突，而a[0]不会发生冲突，故缺失率为67%。

3) 2-路组相联，s=64: 访存顺序为a[0]、a[64] , a[0]、a[64], … …, 共循环10000次。这两个元素虽然映射到同一个cache组中，但可以放在该组不同cache行中，所以不会发生冲突，缺失率为0。 4) 2-路组相联，s=63: 访存顺序为a[0]、a[63]、a[126], a[0]、a[63]、a[126], … …共循环10000次。这三个元素中后面两个元素虽映射到同一个cache组中，但可放在不同cache行中, 而a[0]不会发生冲突，故缺失率为0。

23. 假定一个虚拟存储系统的虚拟地址为40位，物理地址为36位，页大小为16KB，按字节编址。若页表中

有有效位、存储保护位、修改位、使用位，共占4位，磁盘地址不在页表中，则该存储系统中每个进程的页表大小为多少？如果按计算出来的实际大小构建页表，则会出现什么问题？ 参考答案：

因为每页大小有16KB，所以虚拟页数为240B/16KB=2(40-14)=226页。 物理页面和虚拟页面大小相等，所以物理页号的位数为36–14=22位。

页表项位数为：有效位+保护位+修改位+使用位+物理页号位数=4+22=26位。 为简化页表访问，每项大小取32位。因此，每个进程的页表大小为：226×32b=256MB。 如果按实际计算出的页表大小构建页表，则页表过大而导致页表无法一次装入内存。

24. 假定一个计算机系统中有一个TLB和一个L1 data cache。该系统按字节编址，虚拟地址16位，物理地

址12位；页大小为128B，TLB为四路组相联，共有16个页表项；L1 data cache采用直接映射方式，块大小为4B，共16行。在系统运行到某一时刻时，TLB、页表和L1 data cache中的部分内容（用十六进制表示）如下：

组号 标记 页框号 有效位 标记 页框号 有效位 标记 页框号 有效位 标记 页框号 有效位 0 1 2 3

虚页号 页框号 有效位 行索引 标记 有效位 字节3 字节2 字节1 字节0

00 01 02 03 04

08 03 14 02 – 1 1 1 1 0 0 1 2 3 4

19 15 1B 36 32 1 0 1 0 1 12 – 03 – 23 56 – 45 – 34 C9 – 12 – C2 AC – CD – 2A 03 03 02 07 – 2D – – 0 1 0 0 09 02 08 63 0D – – 0D 1 0 0 1 00 04 06 0A – – – 34 0 0 0 1 07 0A 03 72 02 – – – 1 0 0 0 (a) TLB（四路组相联）：四组、16个页表项

05 06 07 08 09 0A 0B 0C 0D 0E 0F

16 – 07 13 17 09 – 19 – 11 0D 1 0 1 1 1 1 0 1 0 1 1

5 6 7 8 9 A B C D E F

0D – 16 24 2D 2D – 12 16 33 14

1 0 1 1 0 1 0 1 1 1 0 46 – 12 23 – 43 – 76 A3 2D – 67 – 54 62 – 62 – 83 F4 4A – 23 – 65 12 – 23 – 21 23 45 – 3D – DC 3A – C3 – 35 11 55 – (b) 部分页表：（开始16项） (c) L1 data cache：直接映射，共16行，块大小为4B

请回答下列问题： （1）虚拟地址中哪几位表示虚拟页号？哪几位表示页内偏移量？虚拟页号中哪几位表示TLB标记？

哪几位表示TLB索引？

（2）物理地址中哪几位表示物理页号？哪几位表示页内偏移量？

（3）主存（物理）地址如何划分成标记字段、行索引字段和块内地址字段？

（4）CPU从地址067AH中取出的值为多少？说明CPU读取地址067AH中内容的过程。 参考答案：

（1）16位虚拟地址中低7位为页内偏移量，高9位为虚页号；虚页号中高7位为TLB标记，低2

位为TLB组索引。

（2）12位物理地址中低7位为页内偏移量，高5位为物理页号。

（3）12位物理（主存）地址中，低2位为块内地址，中间4位为cache行索引，高6位为标记。 （4）地址067AH=0000 0110 0111 1010B，所以，虚页号为0000011 00B，映射到TLB的第00组，将

0000011B=03H与TLB第0组的四个标记比较，虽然和其中一个相等，但对应的有效位为0，其余都不等，所以TLB缺失，需要访问主存中的慢表。直接查看0000011 00B =00CH处的页表项，有效位为1，取出物理页号19H=11001B，和页内偏移111 1010B拼接成物理地址：11001 111 1010B。根据中间4位1110直接找到cache第14行(即：第E行)，有效位为1，且标记为33H=110011B，正好等于物理地址高6位，故命中。根据物理地址最低两位10，取出字节2中的内容4AH=01001010B。

25. 缓冲区溢出是指分配的某个内存区域（缓冲区）的大小比存放内容所需空间小。例如，在栈(stack)中

分配了一块空间用于存放某个过程中的一个字符串，结果字符串长度超过了分配空间的大小。黑客往往会利用缓冲区溢出来植入入侵代码。请说明可以采用什么措施来防止缓冲区溢出漏洞。

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