GATE IT 2004 | Question: 48

Question

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$?

• A. $4$
• B. $5$
• C. $6$
• D. $7$

Comments

@Tuhin Dutta thanks for the new technique, its effective for LRU, saves space and revising is also easy.

 

---

LRU Cache Replacement Policy - Solved PYQs

---

for fully associative it can map at anywhere, where ever its free, for tracking LRU use separate queue and for associative cache block use 0 to 7 indexed blocks

Answer 1

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

So, answer is (B).

Comments

@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 " ??

---

@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

Answer 2

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. 

So answer is Option (B)

Comments

Perfect Method. Thank You!

---

good approach ,eliminates error changes.

---

i must say this is a a good method , isme time se y pta chl rha h ki sbse least kon use hua to replace krne m problem nhi ho rhi.

Answer 3

Ans: B

Answer 4

Ans

 

Answer 5

Credit to @Chhotu

I wanted to draw horizontal lines between rows, which differ more than one column for clarity during exam

Answer 6

This is my approach:

step1: make one block of 8 elements 

step2: just use LRU as below and update in block 

Note : From this method you will never  made any mistake just practice it.