GATE Overflow | Operating Systems | Test 1 | Question: 25

Question

There is a 4 way set associative cache memory with 8 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in that order:
$$0,255,1,4,3,8,133,159,216,129,63,8,48,32,73,92,155 $$
Which one of the following memory block will not be in cache if LRU replacement policy is used?

• A. 159
• B. 8
• C. 129
• D. 48

Answer 1

We have 8 cache blocks and 4 blocks in a set. So, no. of sets = 2.

After each block access cache will be as follows

Set 1	Set 2
0
0	255
0	255, 1
0, 4	255, 1
0, 4	255, 1, 3
0, 4, 8	255, 1, 3
0, 4, 8	255, 1, 3, 133
0, 4, 8	1, 3, 133, 159 (255 replaced)
0, 4, 8, 216	1, 3, 133, 159
0, 4, 8, 216	3, 133, 159, 129 (1 replaced)
0, 4, 8, 216	133, 159, 129, 63 (3 replaced)
0, 4, 216, 8 (LRU info of 8 updated)	133, 159, 129, 63
4, 216, 8, 48 (0 replaced)	133, 159, 129, 63
216, 8, 48, 32 (4 replaced)	133, 159, 129, 63
216, 8, 48, 32	159, 129, 63, 73 (133 replaced)
8, 48, 32, 92 (216 replaced)	159, 129, 63, 73
8, 48, 32, 92	129, 63, 73, 155 (159 replaced)

Comments

@Arjun $sir$ @jothee $ma'am$

this question is similar to the one which came in gate2009-29.

https://gateoverflow.in/1315/gate2009-29

My doubt is when we perform $255\ mod\ 4$ it will give $3^{rd}$ set which is not present as only 2 sets are present for this question. How $255\ mod\ 4$ is going in set $2\ ?$

---

BLOCK mod 2 is being done. (BLOCK mod No_of_Sets). In 2009 question number of sets is 4.