15
4 0 1 2 3 4 5 6 7 4 0 1 2 3 4 5 6 7
8 0 1 2 3 4 5 6 7 8 9 5 0 1 2 3 4 5 6 7 8 9
11
h 4
h
6
h 9
h 17 8 9 （2）
地址序列 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3
20 17 19 56 9 0 1 2 3 4 5 6 7 8 9 43 5
16 16 16 16 16 16 16 16 16 8 17 17 17 17 17 17 17 17 17 9 18 18 18 18 18 18 18 18 18 10 10 19 19 19 19 19 19 19 19 19 11 11 4 5 6 7 8 9 4 5 6 7 8 9 56 56 56 56 56 56 56 56 16 57 57 57 57 57 57 57 57 17 58 58 58 58 58 58 58 58 18 59 59 59 59 59 59 59 59 19 8 9 8 9 8 9 4 5 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 10 10 10 10 10 10 10 10 6 11 11 11 11 11 11 11 11 8 0 1 2 3 4 5 6 7 8 9 h 5 0 1 2 3 4 5 6 7 8 9 7 20 20 20 20 20 20 20 40 40 40 40 40 21 21 21 21 21 21 21 41 41 41 41 41 22 22 22 22 22 22 22 42 42 42 42 42 23 23 23 23 23 23 23 43 43 43 43 43
h
h
h 11
4
h
h 6
9
17
（3）根据使用频率计算得到的结果是：
地址序列 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3
20 17 19 56 9 0 1 2 3 4 5 6 7 8 9 43 5
16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 4 5 6 7 8 9 4 5 6 7 8 9 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 56 56 56 56 40 40 40 40 40 57 57 57 57 41 41 41 41 41 10 10 10 10 10 58 58 58 58 42 42 42 42 42 11 11 11 11 11 59 59 59 59 43 43 43 43 43
h
20 20 20 20 8 21 21 21 21 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9 22 22 22 22 10 10 10 10 10 10 10 10 23 23 23 23 11 11 11 11 11 11 11 11
r
h
r
r
h
h
r
h
h
h
h
根据近期最久未使用法得到的结果是：
地址序列 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3
4 0 1 2 3 4 5 6 7
8 0 1 2 3 4 5 6 7 8 9 5 0 1 2 3 4 5 6 7 8 9 20 17 19 56 9 0 1 2 3 4 5 6 7 8 9 11 4 43 5 6 9 17
16 16 16 16 16 16 40 40 40 40 40 17 17 17 17 17 17 41 41 41 41 41 18 18 18 18 18 18 42 42 42 42 42 19 19 19 19 19 19 43 43 43 43 43 4 5 6 7 8 9 4 5 6 7 8 9 4 5 6 7 8 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 56 56 56 56 56 56 56 56 16 57 57 57 57 57 57 57 57 17 10 10 10 10 10 58 58 58 58 58 58 58 58 18 11 11 11 11 11 59 59 59 59 59 59 59 59 19
h
20 20 20 20 20 20 4 21 21 21 21 21 21 5 22 22 22 22 22 22 6 23 23 23 23 23 23 7
r
h
r
r
h
h
4 5 6 7 r
4 5 6 7 h
4 5 6 7 h
4 5 6 7 h
4 5 6 7 r
33. 对于下述访存地址序列（字地址）：
1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17
假定cache的容量都是16字，初始时cache为空。在下列情况下，标出每次访存的cache命
中情况以及最后cache的内容： (1) cache是4路组相联映象，每块一字，采用FIFO替换策略。
(2) cache是2路组相联映象，每块4字，采用LRU替换策略。 答：（1）
地址序列 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 4 1 4 8 1 4 8 5 1 4 5 8 20 17 19 56 9 1 4 5 1 1 1 1 11 1 4 1 43 5 1 1 6 1 9 1 17 1 17 17 17 17 17 17 17 17 17 17 17 4 5 19 19 19 19 19 19 19 19 19 19 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 20 20 20 20 20 20 20 20 20 20 20 20 8 8 8 8 8 8 8 6 6 6 43 43 43 43 43 56 56 56 56 56 56 56 56 56 9 9 9 9 9 9 9 9 11 11 11 11 11 11 11 15
h
h
h
h
（2）
地址序列 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3
4 0 1 2 3 4 5 6 7
8 0 1 2 3 4 5 6 7 8 9 5 0 1 2 3 4 5 6 7 8 9 20 17 19 56 9
11
4
43 5 4 5 6 7 4 5 6 7 6 4 5 6 7 9 4 5 6 7 17 4 5 6 7 20 20 20 20 20 20 4 21 21 21 21 21 21 5 22 22 22 22 22 22 6 23 23 23 23 23 23 7 4 5 6 7 8 9 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 8 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11
h
h
56 56 56 56 40 40 40 40 40 57 57 57 57 41 41 41 41 41 58 58 58 58 42 42 42 42 42 59 59 59 59 43 43 43 43 43
h
h
h
h
h
h
34. 设2路组相联映象的cache容量为214块，每块是一个32位的字，主存容量是cache的
256倍，其中有如下数据（地址和数据均用十六进制表示）：
地址 000000 000008 010000 010004 00FFFC FFFFF8 FFFFFC 数据 13579246 87654321 77777777 11235813 12345678 11223344 24682468 将主存中这些数据装入cache后，cache中各块的数据内容以及相应的标记是什么？
答：主存地址中有8位区号、13位组号、1位块号，块内地址2位。地址位数共24位，表
中数据装入cache后，cache的标记是区号和块号，有9位。操作过程中，各cache块装入的数据如下： 地址 000000 000008 010000 010004
组号 000 001 000 000
主存块号
0 0 0 1
Cache块号 块内地址
0 0 1 0
0 0 0 0
标记 00 00 02 03
数据 13579246 87654321 77777777 11235813
00FFFC FFFFF8 FFFFFC
1FFF 1FFF 1FFF
1 0 1
0 1 0
0 0 0
01 1FE 1FF
12345678 11223344 24682468
其中，地址为010004的块将覆盖地址为000000的块，最后一个装入的块将覆盖地址为
00FFFC的块。操作完成后，cache中有关块的内容如下表所示：
组号 000 000 001 1FFF 1FFF
Cache块号 块内地址
0 1 0 0 1
0 0 0 0 0
标记 03 02 00 1FF 1FE
数据 11235813 77777777 87654321 24682468 11223344
43. 一个两级存储器系统有八个磁盘上的虚拟页需要映射到主存中的四个页框架中。某程序生成以下访存页号序列：
1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3
画出每个页号访问请求之后存放在主存中的位置，采用LRU替换策略，计算主存的命中率，假定初始时主存为空。
答：主存中页面分配的情况如下表所示
地址流: 1 0 2 2 1 7 6 7 0 1 2 0 3 0 4 5 1 5 2 4 5 6 7 6 7 2 4 2 7 3
页面:
1 1* 1 1* 1 1 1 1 1* 1 1 1 1* 1* 4 4 4 4 4* 4 4 4 4* 4* 4* 2 2 2 2 2 - 0 0 0 0* 0* 6 6 6 6* 2 2 2 2 2* 5 5 5 5 5 5 5 5 5 5 5* 4 4 4 4* - - - 2 2 2 2 2* 2* 0 0 0 0 0 0 0 0 0* 0* 2 2 2 2* 7 7 7 7 7 7 7 7 - - - - 7 7 7 7 7 7* 7* 3 3 3 3* 1 1 1 1* 1* 6 6 6 6 6 6* 6* 6* 3 n n y n y y n n y y n n y y n
命中: n n n y y n n y n y n y n y n 从表中可见，命中13次，命中率=13/30=43.3%
第6章
9. 设计算机A有60条指令，指令操作码为6位固定长度编码，从000000到111011。其后继产品B需要增加32条指令，并与A保持兼容，
(1) 试为计算机B设计指令操作码。 (2) 计算操作码平均长度。
答:：（1）6位操作码中保留了111100到111111四个码字，如果不再保留码字可增加3位扩展码，这样增加的32条指令的操作码为111100,000到111111,111中的一个。 （2）如果每条指令的使用概率相等，则平均指令长度为：
(6×60 + 9×32)/(60+32) = 7.04
注意：B计算机与A计算机保持兼容意味着B计算机原封不动地采纳A计算机的指令，可增加新的指令，但A计算机中已有的指令不能做任何改动。
10. 某计算机的指令系统字长定长为16位，采用扩展操作码，操作数地址需要4位。该指令系统已有三地址指令M条，二地址指令N条，没有零地址指令，问系统最多还有多少条一地址指令？
答：三种指令的操作码长度分别为4位、8位和12位。设系统最多有L条一地址指令，则有