GATE 2015 Question: Solving FIFO and LRU Page Replacement Problems

Learn how to solve a GATE 2015 question on page replacement algorithms. This tutorial demonstrates calculating page faults using First-In-First-Out (FIFO) and Least Recently Used (LRU) algorithms for a given page reference string, enhancing your understanding of memory management techniques.

GATE 2015 Question: FIFO and LRU Page Replacement

Problem Description

This problem examines page replacement policies in a virtual memory system. Given a sequence of page references (3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3) and five page frames, we need to determine the number of page faults using First-In-First-Out (FIFO) and Least Recently Used (LRU) algorithms.

FIFO Page Replacement

FIFO (First-In-First-Out) replaces the page that has been in memory the longest. Let's trace the page replacements:

Number of page faults: 9

LRU Page Replacement

LRU (Least Recently Used) replaces the page that hasn't been accessed for the longest time. Let's trace the page replacements:

Number of page faults: 9

Solution

Both FIFO and LRU result in the same number of page faults (9) for this specific sequence. Therefore, the correct answer is A.