Master Page Replacement Algorithms: FIFO, LRU, LFU | 🚀 Exam Prep

💡 A subjective question for exam preparation is at the end of this post. Try to calculate the number of page faults for each algorithm yourself.

❗️ Page replacement algorithms are used in virtual memory systems. This technology makes the limited physical memory (RAM) appear much larger than it actually is to a process.

🧠 Understanding Pages and Page Faults

For a computer to execute a program, its code and data must be loaded into physical memory (RAM). However, RAM is limited, and running multiple programs simultaneously can lead to a shortage of space. This is where the operating system uses a technique called virtual memory.

1. What is a Page?

A page is a fixed-size block of memory used to manage memory in a virtual memory system. It's a way of dividing a program's code and data, stored on a secondary storage device like a hard disk, into equal-sized chunks. RAM is also divided into frames of the same size as pages.

• Key Idea: A process is divided into pages, and these pages must be loaded into RAM frames to be executed.

2. What is a Page Fault?

A page fault occurs when a process tries to access a page that is not currently in RAM (physical memory).

When a page fault happens, the following steps occur:

1. The CPU transfers control to the operating system (OS).
2. The OS finds the required page on the secondary storage device.
3. If there is a free frame in RAM, the page is loaded into it.
4. What if there are no free frames? An existing page in RAM is moved out to the secondary storage (swap-out), and the new page is brought into the now-free frame (swap-in).

The rule that decides "which page to swap out" is the page replacement algorithm.

---

🔄 Major Page Replacement Algorithms

The goal of a page replacement algorithm is to minimize the number of page faults, thereby improving system performance. FIFO, LRU, and LFU are the most well-known algorithms.

1. FIFO (First-In, First-Out)

This is the simplest algorithm. It evicts the page that has been in RAM the longest, just like a queue where the first person to arrive is the first to leave.

• Advantage: Very simple to implement.
• Disadvantage: It can be inefficient by replacing a frequently used page simply because it was loaded first. This is known as Belady's Anomaly, where increasing the number of frames can paradoxically increase the number of page faults.

2. LRU (Least Recently Used)

This algorithm replaces the page that has not been used for the longest period of time. It is based on the idea of temporal locality, which suggests that pages used recently are likely to be used again in the near future.

• Advantage: Generally results in a lower page fault rate than FIFO and performs well.

• Disadvantage: Requires tracking the last access time for each page, which adds overhead and complexity to the OS.

3. LFU (Least Frequently Used)

This algorithm replaces the page with the lowest reference count. It operates on the assumption that pages used frequently in the past will be used frequently in the future.

• Advantage: It can account for long-term access patterns that LRU might miss.

• Disadvantages:

  • The overhead of calculating reference counts is significant.
  • A page that was heavily used initially but is no longer needed might remain in memory.
  • If multiple pages have the same reference count, an additional rule (e.g., FIFO) is needed to decide which one to replace.

---

📝 Exam Prep Problem

Solution Breakdown

1. FIFO (First-In, First-Out)

• Total Page Faults: 9

2. LRU (Least Recently Used)

• Total Page Faults: 7

3. LFU (Least Frequently Used)

• Total Page Faults: 7
• Reference Count Changes
  • 2: 1 -> 2 -> 3 -> 4 -> 5
  • 3: 1 -> 2 -> 3
  • 1: 1
  • 5: 1 -> 2 -> 3
  • 4: 1

➡️ Recommended Next Reads

• Ultimate Guide to Acing the Information Processing Engineer Practical Exam 📝
• Key Database Concepts for the Information Processing Engineer Exam