……

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

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

19 15 1B 36 1 0 1 0 12 – 03 – 56 – 45 – C9 – 12 – AC – CD – 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个页表项

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

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

4 5 6 7 8 9 A B C D E F

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

1 1 0 1 1 0 1 0 1 1 1 0 23 46 – 12 23 – 43 – 76 A3 2D – 34 67 – 54 62 – 62 – 83 F4 4A – C2 23 – 65 12 – 23 – 21 23 45 – 2A 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)

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

第 5 章习题答案

3． 假定某计算机中有一条转移指令，采用相对寻址方式，共占两个字节，第一字节是操作码，第二字节

是相对位移量（用补码表示），CPU每次从内存只能取一个字节。假设执行到某转移指令时PC的内容为200，执行该转移指令后要求转移到100开始的一段程序执行，则该转移指令第二字节的内容应该是多少？ 参考答案：

因为执行到该转移指令时PC为200，所以说明该转移指令存放在200单元开始的两个字节中。因为CPU每次从内存只能取一个字节，所以每次取一个字节后PC应该加1。

该转移指令的执行过程为：取200单元中的指令操作码并译码→PC+1→取201单元的相对位移量→PC+1→计算转移目标地址。假设该转移指令第二字节为Offset，则100=200+2+Offset，即Offset=100–202=–102=10011010B

（注：没有说定长指令字，所以不一定是每条指令占2个字节。）

4． 假设地址为1200H的内存单元中的内容为12FCH，地址为12FCH的内存单元的内容为38B8H，而

38B8H单元的内容为88F9H。说明以下各情况下操作数的有效地址和操作数各是多少？ （1）操作数采用变址寻址，变址寄存器的内容为12，指令中给出的形式地址为1200H。 （2）操作数采用一次间接寻址，指令中给出的地址码为1200H。

（3）操作数采用寄存器间接寻址，指令中给出的寄存器编号为8，8号寄存器的内容为1200H。 参考答案：

（1） 有效地址EA=000CH+1200H=120CH，操作数未知。 （2） 有效地址EA=(1200H)=12FCH，操作数为38B8H。 （3） 有效地址EA=1200H，操作数为12FCH。

5． 通过查资料了解Intel 80x86微处理器和MIPS处理器中各自提供了哪些加法指令，说明每条加法指令

的汇编形式、指令格式和功能，并比较加、减运算指令在这两种指令系统中不同的设计方式，包括不同的溢出处理方式。 参考答案（详细信息略）： MIPS:

Intel 80x86:

6． 某计算机指令系统采用定长指令字格式，指令字长16位，每个操作数的地址码长6位。指令分二地

址、单地址和零地址三类。若二地址指令有k2条，无地址指令有k0条，则单地址指令最多有多少条？ 参考答案：

设单地址指令有k1条，则 ((16 –k2) ×26 –k1) ×26 = k0，所以 k1= (16 –k2) ×26 –k0/26

7． 某计算机字长16位，每次存储器访问宽度16位，CPU中有8个16位通用寄存器。现为该机设计指

令系统，要求指令长度为字长的整数倍，至多支持64种不同操作，每个操作数都支持4种寻址方式：立即（I）、寄存器直接（R）、寄存器间接（S）和变址（X），存储器地址位数和立即数均为16位，任何一个通用寄存器都可作变址寄存器，支持以下7种二地址指令格式（R、I、S、X代表上述四种寻址方式）：RR型、RI型、RS型、RX型、XI型、SI型、SS型。请设计该指令系统的7种指令格式，给出每种格式的指令长度、各字段所占位数和含义，并说明每种格式指令需要几次存储器访问？ 参考答案：

指令格式可以有很多种，只要满足以下的要求即可。

操作码字段：6位；寄存器编号：3位；直接地址和立即数：16位；变址寄存器编号：3位；总位数是8的倍数。 指令格式例1：

RR型 RI型 RS型 RX型

0000 0010 OP (6位) OP (6位) OP (6位) OP (6位) R t (3位) Rs (3位) Rt (3位) 000 Imm16 (16位) 0100 0110 R t (3位) Rs (3位) Rt (3位) Rx (3位) Offset16 (16位) XI型 SI型 SS型

1000 OP (6位) OP (6位) OP (6位) Rx (3位) 000 Offset16 (16位) Imm16 (16位) Imm16 (16位) 1010 1100 R t (3位) 000 Rt (3位) Rs (3位)

指令格式例2：

RR型 OP (6位) RI型 RS型

01 R t (3位) Rt (3位) 01 00 Rs (3位) Imm16 (16位) 000 OP (6位) 01 OP (6位) 01 R t (3位) 01 R t (3位) 10 11 Rs (3位) Rx (3位) Offset16 (16位) RX型 OP (6位) XI型 SI型

OP (6位) 11 Rx (3位) Offset16 (16位) 00 10 00 Imm16 (16位) 000 000 OP (6位) 10 10 R t (3位) Rt (3位) Imm16 (16位) Rs (3位) SS型 OP (6位)

寻址方式字段(2位)----00：立即；01：寄直；10：寄间；11-变址

8． 有些计算机提供了专门的指令，能从32位寄存器中抽取其中任意一个位串置于一个寄存器的低位有

效位上，并高位补0，如下图所示。MIPS指令系统中没有这样的指令，请写出最短的一个MIPS指令序列来实现这个功能，要求i=5, j=22, 操作前后的寄存器分别为$s0和$s2。