Skip to main content

Page Replacement Algorithms in Operating Systems

z

Page Replacement Algorithms

Page Replacement Algorithms are a core concept of Operating Systems and an essential part of Virtual Memory Management. Whenever physical memory (RAM) becomes full and a new page needs to be loaded, the operating system must decide which existing page to remove. This decision is made using page replacement algorithms.

If you haven't read about Virtual Memory yet, read it here:

1. Why Page Replacement is Needed

In demand paging systems, pages are loaded only when required. However, RAM size is limited. When memory is full and a new page must be loaded, the OS must:

  1. Select a page currently in memory.
  2. Remove it (if necessary write back to disk).
  3. Load the new page into the freed frame.

Choosing the wrong page increases page faults and decreases performance.

2. Performance Metric: Page Fault Rate

The main goal of page replacement algorithms is to minimize Page Faults.

Lower Page Fault Rate = Better Performance

3. FIFO (First-In First-Out) Algorithm

FIFO replaces the page that has been in memory for the longest time. It works like a queue.

Steps:

  • Insert pages in order of arrival.
  • When memory is full, remove the oldest page.

Example:

Reference String: 1, 2, 3, 4, 1, 2, 5 Frames = 3

Page Faults occur when new pages replace oldest ones.

Advantages

  • Simple implementation
  • Low overhead

Disadvantages

  • May remove frequently used pages
  • Suffers from Belady’s Anomaly

4. Belady’s Anomaly

Belady’s Anomaly occurs when increasing the number of frames increases the number of page faults. FIFO suffers from this problem.

5. Optimal Page Replacement Algorithm

The Optimal algorithm replaces the page that will not be used for the longest time in the future.

It provides the minimum possible page faults.

Disadvantage

Future knowledge is impossible in real systems, so it is mainly theoretical.

6. LRU (Least Recently Used) Algorithm

LRU replaces the page that has not been used for the longest time in the past.

How It Works:

  • Track usage history.
  • Replace least recently accessed page.

Advantages

  • Good performance
  • No Belady’s anomaly

Disadvantages

  • High implementation cost
  • Requires extra hardware or counters

7. LFU (Least Frequently Used)

LFU replaces the page with the lowest access frequency.

Problem

Old pages with high count may stay forever.

8. Clock (Second Chance) Algorithm

Clock algorithm is an improved version of FIFO. It gives pages a second chance using a reference bit.

Working:

  • If reference bit = 0 → Replace page
  • If reference bit = 1 → Set to 0 and skip

Efficient and widely used in modern systems.

9. Comparison Table

Algorithm Belady's Anomaly Implementation Performance
FIFO Yes Simple Moderate
Optimal No Theoretical Best
LRU No Complex Very Good
LFU No Moderate Good
Clock No Efficient Very Good

10. Numerical Example (Exam Important)

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3 Frames = 3

Students are often asked to compute page faults using FIFO, LRU, and Optimal.

Practice calculating faults manually for exams.

11. Which Algorithm is Best?

  • Optimal → Theoretical best
  • LRU → Practical best
  • Clock → Efficient real-world solution

12. Real-World Implementation

Modern operating systems use variations of:

  • LRU approximation
  • Clock algorithm
  • Working Set Model

Conclusion

Page Replacement Algorithms are crucial for efficient memory management. Understanding FIFO, LRU, Optimal, LFU, and Clock helps in exams, interviews, and system-level programming.

Frequently Asked Questions (FAQs)

What is page replacement?

Page replacement is the process of selecting a page to remove from memory when RAM is full.

Which algorithm is best?

Optimal is theoretically best, but LRU is widely used in practice.

What is Belady’s anomaly?

It is a phenomenon where increasing frames increases page faults (seen in FIFO).

Labels:

Comments

Post a Comment

Popular posts from this blog

A Comparative Study of Deep Learning Architectures for Chest X-Ray Image Classification

Comparative Analysis of Deep Learning Models for Chest X-Ray Image Classification Author: Akrash Noor, Saba Latif & Hifzun Nisa | Published: December 21, 2025 | Category: AI · Medical Imaging · Deep Learning Introduction Medical imaging has become an important aspect in the contemporary healthcare and especially the diagnosis of thoracic diseases utilizing the images of chest X-ray. In recent years, artificial intelligence has advanced significantly, and convolutional neural networks that are based on deep learning have demonstrated impressive results in the domain of automated disease detection and classification. This paper compares and contrasts several deep learning models that are trained on chest X-ray data with PyTorch and TensorFlow in their accuracy, generalization, and computational efficiency. Deep Learning Models Used Custom Convolutional Neural Networks (CNN) ResNet (Residual Networks) DenseNet VGG-styl...
2 comments
Read more

Process vs Threads

Process vs Threads in Operating Systems Process vs Threads in Operating Systems Operating System Course Article Introduction An operating system is responsible for managing system resources and ensuring that multiple programs run efficiently at the same time. Modern systems perform multitasking by executing several activities concurrently. To achieve this, operating systems rely on two fundamental execution units: processes and threads . Although both represent executing tasks, processes and threads differ in memory usage, execution speed, communication methods, and reliability. Understanding these differences is essential for learning CPU scheduling, concurrency, and parallelism. What is a Process? A process is a program that is cur...
Post a Comment
Read more

AI-Driven Protein Designer for Cancer Therapy

Deep Learning Based Protein Design for Targeted Cancer Treatment Author: Akrash Noor & Saba  | Published: September 10, 2025 | Category: AI, Bioinformatics, Cancer Therapy This article presents a mathematical and computational overview of an AI-driven protein design framework for cancer therapy . It explains how artificial intelligence can assist in designing novel proteins that selectively target cancer-related biomarkers. 1. Protein Sequence Representation A protein can be represented as a sequence of amino acids: P = (a₁, a₂, a₃, …, aₙ), aᵢ ∈ A n is the length of the protein A represents the 20 standard amino acids Each amino acid is converted into a numerical vector using encoding techniques such as one-hot encoding or learned embeddings: aᵢ → xᵢ ∈ ℝᵈ 2. AI-Based De Novo Protein Generation Protein design is treated as a sequence generation problem: P* = arg max P p(P...
Post a Comment
Read more