方式5：4路高位交叉4路低位交叉
方式6：4路并行访问4路低位交叉
4. 一个程序由5个虚页组成，采用LRU替换算法，在程序执行过程中依次访
问的页地址流如下：
P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3
⑴ 可能的最高页命中率是多少?
⑵ 至少要分配给该程序多少个主存页面才能获得最高的命中率?
⑶ 如果在程序执行过程中每访问一个页面，平均要对该页面内的存储单元访问
1024次，求访问存储单元的命中率。 答： ⑴
在分配的主存页面数目足够大的情况下，除了第一次调入不命中，以后的访问均命中，可以达到最高的页面命中率，即：实际命中的次数为7次，所以可能达到的最高页面命中率为：
H?712?0.5833
⑵
由于在页面数大于等于5的情况下，肯定可以达到最高命中率，所以我们来看页面数小于5时能否达到该命中率：
若分配的主存页面数等于4时，调度过程如下： 访问流 P4 LRU 4 P5 4 P3 P2 P5 P1 P3 P2 P3 P5 P1 P3 统计 4 4* 4* 1 1 1 1 1* 1 1 命中 算法 5 5 3 5 3 2 5 3 2 5 5 5* 5* 5 3 3 2 3 2 5 3 5 3 7次 3* 3 2 2* 2 2* 2* 调入 调入 调入 调入 命中 调入 命中 命中 命中 命中 命中 命中 此时也可以达到最高命中率；
若分配的主存页面等于3时，调度过程如下：
访问流 P4 P5 P3 P2 P5 P1 P3 P2 P3 P5 P1 P3 统计 4 LRU 算法 4 5 4* 5 3 2 2 2* 3 3* 5 5* 2 1 1 1 3 3 3* 3 1 5 1 5 命中 3次 5* 5 3 3* 2 2* 1* 5 调入 调入 调入 调入 命中 调入 调入 调入 命中 调入 调入 命中 此时不能达到最高命中率。 所以至少应该分配4个主存页面。 ⑶
我们假设程序每次只访问一个存储单元，这样，对每一个特定页面的访问过程可以描述如下：因为第一次总是不命中的，而平均起来，随后的1023次总是命中的，然后再次被调出主存，并再次重复先前的过程。所以访问存储单元的命中率为：
H?10231024?0.999
5. 假设在一个采用组相联映象方式的Cache中，主存由B0～B7共8块组成，
Cache有2组，每组2块，每块的大小为16个字节，采用LRU块替换算法。在一个程序执行过程中依次访问这个Cache的块地址流如下：
B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3
⑴ 写出主存地址的格式，并标出各字段的长度。 ⑵ 写出Cache地址的格式，并标出各字段的长度。 ⑶ 画出主存与Cache之间各个块的映象对应关系。
⑷ 如果Cache的各个块号为C0、C1、C2和C3，列出程序执行过程中Cache
的块地址流情况。
⑸ 如果采用FIFO替换算法，计算Cache的块命中率。 ⑹ 如果采用LRU替换算法，计算Cache的块命中率。
⑺ 如果改用全相联映象方式，再做⑸和⑹，可以得到什么结论？
⑻ 如果在程序执行过程中，每从主存装入一块到Cache，则平均要对这个块访
问16次。请计算在这种情况下的Cache命中率。 答：
⑴ 主存地址的格式为：
高 低 1bit区号 1bit组号 1bit组内块号 4bit块内地址 ⑵ Cache地址的格式为：
高 低
1bit组号 ⑶
主存 0 1
Cache 0
第0组
1 2
第1组
3
2 3 4 5 6 7
第1组
第1区
第1组 第0组 第0组
第0区
1bit组内块号 4bit块内地址 主存的组到Cache的组之间是直接映象，对应组的块之间是全相联映象。即：主存块0、1、4、5只能装入Cache块0、1的任何块位置上，主存块2、3、6、7只能装入Cache块2、3的任何块位置上。 ⑷
由于主存按Cache大小分区，因此去掉主存块地址中的区号就可以得出满足组相联映象关系的一种Cache块地址，所以该主存块地址流相应的一种Cache的块地址流为：
主 存 Cache B6 110 10 C2 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 011 11 C3 010 100 001 100 110 011 10 C2 00 C0 01 C1 00 C0 10 C2 11 C3 000 100 101 111 00 C0 00 C0 01 C1 11 C3 ⑸ 采用FIFO替换算法，Cache的块命中率为：3/12=0.25。 访问流 B6 C0 C1 C2 C3 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 统计 B4 B4* B4* B4* B4* B0 B0* B5 B5 B5 B1 B1 B1 B1 B1* B4 B4* B4* B4* 命中 B6 B6* B6* B6* B6* B6* B3 B3 B3 B3 B3* B3* B2 B2 B2 B2 B2 B2* B2* B2* B2* B7 B7 3次 动作 调入 调入 调入 调入 命中 命中 调入 调入 调入 调入 调入 命中 ⑹ 采用LRU替换算法，Cache的块命中率为：4/12≈0.33。 访问流 B6 C0 C1 C2 C3 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 统计 B4 B4* B4 B4 B4 B4* B4 B4* B4* B4* B1 B1* B1* B1* B0 B0* B5 B5 B5 命中 B6 B6* B6* B6* B6* B6 B6* B6* B6* B6* B7 B7* B2 B2 B2 B2 B2* B3 B3 B3 B3 B3* B3 4次 动作 调入 调入 调入 调入 命中 命中 调入 调入 命中 调入 调入 命中 ⑺ 采用全相联映象、FIFO替换算法，Cache的块命中率为：4/12≈0.33。 访问流 B6 C0 C1 C2 C3 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 统计 B6 B6* B6* B6* B6* B6* B3 B3 B3 B3 B3* B3* B2 B2 B2 B2 B2 B2* B0 B0 B0 B0 B0 B4 B4 B4 B4 B4 B4* B4* B5 B5 B5 B1 B1 B1 B1 B1 B1 B1* B7 B7 命中 4次 动作 调入 调入 调入 调入 命中 命中 调入 调入 命中 调入 调入 命中 采用全相联映象、LRU替换算法，Cache的块命中率为：3/12=0.25。 访问流 B6 C0 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 统计 B6 B6* B6* B6* B6* B6 B6 B6 B6* B5 B5 B5 命中 C1 C2 C3 B2 B2 B2 B2 B2* B3 B3 B3 B3* B7 B7 3次 B4 B4 B4 B4 B4 B4* B4 B4 B4 B4* B1 B1 B1 B1* B0 B0 B0 B0* B3 动作 调入 调入 调入 调入 命中 命中 调入 调入 命中 调入 调入 调入 结论：Cache的命中率与地址流分布情况、替换算法、相联度等因素有关。 ⑻
Cache命中率为：H=15/16=93.75%