大门|大门IT 2005 |问题61

考虑具有4组和总共8个高速缓存块（0～7）和128块（0～127）的主存储器的2路集合关联高速缓存存储器。如果使用LRU策略替换缓存块，则在以下一系列内存块引用之后，缓存中会出现哪些内存块。假设缓存最初没有来自当前作业的任何内存块？ 0 5 3 9 7 0 16 55

（A） 0 3 5 7 16 55 （B） 0 3 5 7 9 16 55 （C） 0 5 7 9 16 55 （D） 3 5 7 9 16 55 答复: （C） 说明：

2-way set associative cache memory, .i.e K = 2.

No of sets is given as 4, i.e. S = 4 ( numbered 0 - 3 )

No of blocks in cache memory is given as 8, i.e. N =8 ( numbered from 0 -7)

Each set in cache memory contains 2 blocks.

The number of blocks in the main memory is 128, i.e  M = 128.  ( numbered from 0 -127)

A referred block numbered X of the main memory is placed in the 
set numbered ( X mod S ) of the the cache memory. In that set, the 
block can be placed at any location, but if the set has already become
 full, then the current referred block of the main memory should replace
 a block in that set according to some replacement policy. Here 
the replacement policy is LRU ( i.e. Least Recently Used block should 
be replaced with currently referred block).

X ( Referred block no ) and 
the corresponding Set values are as follows:

X-->set no ( X mod 4 )

0--->0   ( block 0 is placed in set 0, set 0 has 2 empty block locations,
              block 0 is placed in any one of them  )

5--->1   ( block 5 is placed in set 1, set 1 has 2 empty block locations,
              block 5 is placed in any one of them  )

3--->3  ( block 3 is placed in set 3, set 3 has 2 empty block locations,
             block 3 is placed in any one of them  )

9--->1  ( block 9 is placed in set 1, set 1 has currently 1 empty block location,
             block 9 is placed in that, now set 1 is full, and block 5 is the 
             least recently used block  )

7--->3  ( block 7 is placed in set 3, set 3 has 1 empty block location, 
             block 7 is placed in that, set 3 is full now, 
             and block 3 is the least recently used block)

0--->block 0 is referred again, and it is present in the cache memory in set 0,
            so no need to put again this block into the cache memory.

16--->0  ( block 16 is placed in set 0, set 0 has 1 empty block location, 
              block 0 is placed in that, set 0 is full now, and block 0 is the LRU one)

55--->3 ( block 55 should be placed in set 3, but set 3 is full with block 3 and 7, 
             hence need to replace one block with block 55, as block 3 is the least 
             recently used block in the set 3, it is replaced with block 55.

因此，高速缓存中的主内存块是： 0, 5, 7, 9, 16, 55 .

( 笔记 ：块3不在高速缓存中，已被块55替换）

阅读以下文章，了解与上述问题有关的更多信息： 高速缓存 缓存组织|简介 这个问题的小测验