GATE - 2004 | OS | Consider a fully associative cache with 8 cache blocks (numbered 0-7)

GATE - 2004 | OS | Consider a fully associative cache with 8 cache blocks (numbered 0-7)
Posted on 22-02-2022

GATE - 2004 [Operating System]

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

  

Solution:

Option (B) is Correct.

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


CPU array (first element being least recently used)
[4, 3, 19, 6, 25, 8, 16, 35]

So, 45 replaces 4.


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

Thank You

Download App for Free PDF Download

GovtVacancy.Net Android App: Download

government vacancy govt job sarkari naukri android application google play store https://play.google.com/store/apps/details?id=xyz.appmaker.juptmh