PUERTA | Puerta TI 2005 | Pregunta 61

Considere una memoria caché asociativa de conjuntos de 2 vías con 4 conjuntos y un total de 8 bloques de caché (0-7) y una memoria principal con 128 bloques (0-127). Qué bloques de memoria estarán presentes en la memoria caché después de la siguiente secuencia de referencias a bloques de memoria si se utiliza la política LRU para el reemplazo de bloques de memoria caché. ¿Asumiendo que inicialmente el caché no tenía ningún bloque de memoria del trabajo actual?
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

Respuesta: (C)
Explicación:

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-->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.

Por lo tanto, los principales bloques de memoria presentes en la memoria caché son: 0, 5, 7, 9, 16, 55.

( Nota : el bloque 3 no está presente en la memoria caché, fue reemplazado por el bloque 55)

Lea los siguientes artículos para obtener más información relacionada con la pregunta anterior:
Memoria
caché Organización de caché | Cuestionario de introducción de esta pregunta