11,790 views

Consider a fully associative cache with $8$ cache blocks (numbered $0-7$) and the following sequence of memory block requests:

$4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7$
If LRU replacement policy is used, which cache block will have memory block $7$?

1. $4$
2. $5$
3. $6$
4. $7$

Is your definition of compulsory miss correct?
edited

Source: "Computer Organization and Design book by D. A. Patterson and J. L. Hennessy 5th Edn" @Tuhin Dutta thanks for the new technique, its effective for LRU, saves space and revising is also easy.

When $45$ comes, the cache contents are:
$4$ $3$ $25$ $8$ $19$ $6$ $16$ $35$

LRU array (first element being least recently used)

$[4$ $3$ $19$ $6$ $25$ $8$ $16$ $35]$.

So, $45$ replaces $4$.

4$5$ $3$ $25$ $8$ $19$ $6$ $16$ $35$ $[3$ $19$ $6$ $25$ $8$ $16$ $35$ $45]$

Similarly, $22$ replaces $3$ to give:

$45$ $22$ $25$ $8$ $19$ $6$ $16$ $35$ $[19$ $6$ $25$ $8$ $16$ $35$ $45$ $22]$

$8$ hits in cache.

$45$ $22$ $25$ $8$ $19$ $6$ $16$ $35$ $[19$ $6$ $25$ $16$ $35$ $45$ $22$ $8$]

$3$ replaces $19$

$45$ $22$ $25$ $8$ $3$ $6$ $16$ $35$ $[6$ $25$ $16$ $35$ $45$ $22$ $8$ $3]$

$16$ and $25$ hits in cache.

$45$ $22$ $25$ $8$ $3$ $6$ $16$ $35$ $[6$ $35$ $45$ $22$ $8$ $3$ $16$ $25]$

Finally, $7$ replaces $6$, which is in block $5$.

by

@srestha m blocks and m-way set associativity. So, the number of sets = 1. So, we always divide by the number of sets.
Is it right that "mod method works only in direct and set associative manner " ??
edited

@Asim Siddiqui 4 ...yes

simply remember whenever fully associativity mapping apply direct algorithm.......like what we do in OS .

Frame size = no. of cache blocks

Although many people have given correct answer but mentioning another approach to reduce error probability.

In the following image X axis is representing cache block and Y axis is representing Time. by

### 1 comment

Perfect Method. Thank You!

Ans: B by