页面替换算法-Cache和组相连映像

列：在一个采用LRU算法和组相联映象的Cache系统中，主存由0—15共16块组成：Cache分为2组，每组2块，每块大小为16个存储字。在某个程序执行时，访存的主存块地址流为：6、2、4、1、4、6、3、0、4、5、7、3。 1）写出主存块地址和Cache块地址的格式，并指出各字段的长度。 2）画出主存和Cache空间块的映像对应关系示意图。 3）画出Cache内各块实际替换过程图，并标出命中时刻、计算命中率。

解1：

主存块格式

区号	组号	组内块号	块内地址
2	1	1	4

Cache块格式

组号	组内块号	块内地址
1	1	4

1. 主存比Cache多一个区号，主存区号=主存块数量/Cache数量，$16/4=4$；4个字节的长度需要$log_2{4}=2$位二进制；

解2：

解3：

根据题2示意图知:

Cache0组对应主存块为：（0、1）、（4、5）、（8、9）、（12、13）

Cache1组对应主存块为：（2、3）、（6、7）、（10、11）、（14、15）

页/地址流		6	2	4	1	4	6	3	0	4	5	7	3
	0组0块			4	4	4			4*	4	4*
Cache地址	0组1块				1	1*			0	0*	5
	1组0块	6	6				6	6*				7	7*
	1组1块		2				2*	3				3*	3
命中						H	H			H			H

补全表格后:

页/地址流		6	2	4	1	4	6	3	0	4	5	7	3
	0组0块			4	4	4	4	4	4*	4	4*	4*	4*
Cache地址	0组1块				1	1*	1*	1*	0	0*	5	5	5
	1组0块	6	6*	6*	6*	6*	6	6*	6*	6*	6*	7	7*
	1组1块		2	2	2	2	2*	3	3	3	3	3*	3
命中						H	H			H			H

命中率 $H=\frac{4}{12}=\frac{1}{3}$

延伸阅读