Question

Consider a 2-way set associative cache memory with 4 sets and total 8 cache blocks (0-7) and a main memory with 128 blocks (0-127). What memory blocks will be present in the cache after the following sequence of memory block references if LRU policy is used for cache block replacement. Assuming that initially the cache did not have any memory block from the current job?
0 5 3 9 7 0 16 55

• A. 0 3 5 7 9 16 55
• B. 3 5 7 9 16 55
• C. 0 5 7 9 16 55
• D. 0 3 5 7 16 55

Answer 1

The correct option is C 0 5 7 9 16 55

$Numberofbitsrequiresfor128main$
$memoryblock$

$=lo{g}_2(!28)$
$=7$ bits

$Mainmemoryformat:$


Since main memory and cache memory offset will be same.

$Numberofbitsforset=lo{g}_2\left(4\right)=2$

So, cache memory format will be:



So, each set can maps 32 blocks and at one time can hold only 2 different block


So, for block 55, block 3 will be replaced since 3 is come before block 7.

So, memory block 0, 5, 7, 9, 16 and 55 will be present in cache.