struct pt_color { int c; int m; int y; int k; } struct pt_color square[8][8]; int i, j; for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { square[i][j].c = 0; square[i][j].m = 0; square[i][j].y = 1; square[i][j].k = 0; } } struct pt_color { int c; int m; int y; int k; } struct pt_color quare[8][8]; int i, j; for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { square [j] [i].c = 0; square [j] [i].m = 0; square [j] [i].y = 1; square [j] [i].k = 0; } } struct pt_color { int c; int m; int y; int k; } struct pt_color square[8][8]; int i, j; for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) square[i][j].y = 1; for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) { square[i][j].c = 0; square[i][j].m = 0; square[i][j].k = 0; }
程序段A 程序段B 程序段C
假设cache的数据区大小为512B，采用直接映射，块大小为32B，存储器按字节编址，sizeof(int)=4。编译时变量i和j分配在寄存器中，数组square按行优先方式存放在000008C0H开始的连续区域中，主存地址为32位。要求： （1） 对三个程序段A、B、C中数组访问的时间局部性和空间局部性进行分析比较。 （2） 画出主存中的数组元素和cache中行的对应关系图。 （3） 计算三个程序段A、B、C中的写操作次数、写不命中次数和写缺失率。 参考答案：
（1） 对于时间局部性来说：
程序段A、B和C中，都是每个数组元素只被访问一次，所以都没有时间局部性； 对于空间局部性来说：
程序段A访问顺序和存放顺序一致，所以，空间局部性好； 程序段B访问顺序和存放顺序不一致，所以，空间局部性不好；
程序段C虽然访问顺序和存放顺序一致，但同一个主存块有两次访问，所以空间局部性不好； （2）cache的行数为512B/32B=16；数组首地址为0000 0C80H，因为0000 0C80H正好是主存第
1100100B（100）块的起始地址。所以数组从主存第100块开始存放，一个数组元素占4×4B=16B，所以每2个数组元素占用一个主存块。8×8的数组共占用32个主存块，正好是cache数据区大小的2倍。
主存中的数组元素与cache行的映射关系图如下：
Cache行号 0# 1# 2# 3# 4# 5#
Square[3][4]/ [3][5] 15#
Square[3][6]/ [3][7] Square[4][0]/ [4][1] Square[0][0]/ [0][1] Square[0][2]/ [0][3] Square[0][4]/ [0][5] Square[0][6]/ [0][7] Square[1][0]/ [1][1] 主存块号 100# 101# 102# 103#
114# 115# 116#
Square[7][0]/ [7][1] Square[7][2]/ [7][3] Square[7][4]/ [7][5] Square[7][6]/ [7][7] 128# 129# 130# 131#
（3）对于程序段A：
每两个数组元素（共涉及8次写操作）装入到一个cache行中，总是第一次访问时未命中，后面7次都命中，所以，总的写操作次数为64 × 4 = 256次，写不命中次数为256×1/8 = 32次，因而写缺失率为12.5%。 对于程序段B：
每两个数组元素（共涉及8次写操作）装入到一个cache行中，但总是只有一个数组元素（涉及4次写操作）在被淘汰之前被访问，并且总是第一次不命中，后面3次命中。即写不命中次数为256×1/4 = 64次，因而写缺失率为25%。 对于程序段C：
第一个循环共64次访问，每次装入两个数组元素，第一次不命中，第二次命中；第二个循环，共访问64×3次，每两个数组元素（共涉及6次写操作）装入到一个cache行中，并且总是第一次不命中，后面5次命中。所以总的写不命中次数为32+(3×64)×1/6 = 64次，因而总缺失率为25%。
17. 假设某计算机的主存地址空间大小为64MB，采用字节编址方式。其cache数据区容量为4KB，采用4
路组相联映射方式、LRU替换和回写（write back）策略，块大小为64B。请问：
（1）主存地址字段如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。 （2）该cache的总容量有多少位？ （3）若cache初始为空，CPU依次从0号地址单元顺序访问到4344号单元，重复按此序列共访问16次。
若cache命中时间为1个时钟周期，缺失损失为10个时钟周期，则CPU访存的平均时间为多少时钟周期？ 参考答案：
（1）cache的划分为：4KB = 212B = 24组×22行/组×26字节/行，所以，cache组号（组索引）占4位。
主存地址划分为三个字段：高16位为标志字段、中间4位为组号、最低6位为块内地址。 即主存空间划分为：64MB = 226B = 216组群×24块/组群×26字节/块
（2）cache共有64行，每行中有16位标志、1位有效位、1位修改(dirty)位、2位LRU位，以及数
据64B。故总容量为64×(16+1+1+2+64×8)=34048位。 （3）因为每块为64B，CPU访问的单元范围为0～4344，共4345个单元，4345/64=67.89，所以CPU
访问的是主存前68块（第0～67块），也即CPU的访问过程是对前68块连续访问16次，总访存次数为16×4345 = 69520。
16次
0 0#
cache共有16组，每组4行，采用LRU算法的替换情况如下图所示： 1 63
64 1#
65 128
2#
4288 67#
4344 4352 68#
根据图中所示可知，第一次循环的每一块只有第一次未命中，其余都命中；以后15次循环中，有20块的第一字未命中，其余都命中。所以命中率p为(69520–68–15×20)/69520 = 99.47%
平均访存时间为：Hit Time + (1–p) × Miss Penalty
=1+10×(1–p) = 1+0.0053×10 = 1.053个时钟周期
18. 假定某处理器可通过软件对高速缓存设置不同的写策略，那么，在下列两种情况下，应分别设置成什
么写策略？为什么？
（1）处理器主要运行包含大量存储器写操作的数据访问密集型应用。
（2）处理器运行程序的性质与（1）相同，但安全性要求高，不允许有任何数据不一致的情况发生。 参考答案：
（1）采用write back策略较好，可减少访存次数。
（2）采用write through策略较好，能保证数据的一致性。
19. 已知cache1采用直接映射方式，共16行，块大小为1个字，缺失损失为8个时钟周期；cache2也采用直
接映射方式，共4行，块大小为4个字，缺失损失为11个时钟周期。假定开始时cache为空，采用字编址方式。要求找出一个访问地址序列，使得cache2具有更低的缺失率，但总的缺失损失反而比cache1大。
参考答案：
假设cache1和cache2的缺失次数分别为x和y，根据题意，x和y必须满足以下条件： 11×y > 8×x 且 x > y，显然，满足该条件的x和y有许多，例如，x=4，y=3、x=5，y=4等等。 对于以下的访问地址序列：0，1，4，8，cache1缺失4次，而cache2缺失3次；
对于以下的访问地址序列：0，2，4，8，12，cache1缺失5次，而cache2缺失4次；
对于以下的访问地址序列：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
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个页表项