Question

A system with four physical memory frames (initially empty) and the reference string is 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6. What will be the final content of memory if the LRU page replacement policy is used?

(a) 3, 7, 6, 2
(b) 6, 2, 3, 7
(c) 6, 7, 3, 2
(d) 2, 3, 6, 7

Answer 1

The final memory content using the LRU policy with the reference string (1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6) is 6, 2, 3, 7, matching option (c).

When applying the Least Recently Used (LRU) page replacement policy to the given reference string (1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6) with four physical memory frames, we will process the pages as follows, with the least recently used pages being replaced as necessary:

• 1 -> Memory: [1, , , ]
• 2 -> Memory: [1, 2, , ]
• 3 -> Memory: [1, 2, 3, ]
• 4 -> Memory: [1, 2, 3, 4]
• 2 is already in memory (hit).
• 1 is already in memory (hit).
• 5 replaces 4 -> Memory: [1, 2, 3, 5]
• 6 replaces 1 -> Memory: [6, 2, 3, 5]
• 2 is already in memory (hit).
• 1 replaces 5 -> Memory: [6, 2, 3, 1]
• 2 is already in memory (hit).
• 3 is already in memory (hit).
• 7 replaces 1 -> Memory: [6, 2, 3, 7]
• 6 is already in memory (hit).

The final content of memory, therefore, is 6, 2, 3, 7, which matches option (c).

So, the LRU page replacement policy always replaces the page that has not been used for the longest period of time, which leads to the final answer as stated.