Page Replacement Algorithm Basics

Introduction

Page replacement is used in virtual memory systems when a process needs a page that is not currently present in RAM. If RAM still has a free frame, the operating system can load the required page directly.

The real page replacement problem begins when all frames are already occupied. In that case, the operating system must choose one existing page as the victim, remove it from RAM, and bring the required page into that freed frame.

Why Page Replacement Is Needed

A process uses virtual addresses while running. Each virtual address belongs to a virtual page, and the page table maps that virtual page to a physical frame in RAM. If the page table entry shows that the page is present, the memory access can continue normally.

If the page is not present in RAM, a page fault occurs. The required page may still exist on disk or secondary storage, but it is not immediately available in physical memory. The operating system must then bring that page into RAM before the instruction can complete.

Replacement is needed only when a page fault occurs and there is no free frame available.

The Page Replacement Problem

After a page fault, the operating system faces one of two cases:

• Free frame available: The required page is loaded into the free frame, the page table is updated, and the instruction can restart.

• No free frame available: The operating system must select a victim page, remove it from RAM, load the required page, update the page table, and restart the instruction.

This selection of the victim page is the main job of a page replacement algorithm. RAM behaves like a fast cache for virtual memory pages, so replacing the wrong page can make future memory accesses slower.

A good replacement removes a page that will not be needed soon. A bad replacement removes a page that is used again immediately, causing another page fault and extra disk I/O.

Page Hit, Page Fault, and Victim Page

Every page reference has one of two basic outcomes:

• Page Hit: The requested page is already present in RAM, so it can be accessed directly.

• Page Fault: The requested page is not present in RAM, so the OS must handle the fault and bring the page into memory.

• Victim Page: The page selected for removal when RAM has no free frame.

• Dirty Page: A page that has been modified after being loaded into RAM and may need to be written back to storage.

If the victim page is dirty, the operating system must write it back to storage before replacing it. If it is clean, it can usually be removed without a writeback because its storage copy is already up to date.

Basic Page Replacement Flow

The page replacement flow is mostly the same across different algorithms. The difference lies in how the victim page is selected.

The basic flow is:

• Reference occurs: A process tries to access a virtual page.

• Page table is checked: The operating system or MMU checks whether the page is present in RAM.

• If it is a hit: The page is used directly, and algorithm-related metadata may be updated.

• If it is a fault: The operating system checks for a free frame.

• If a free frame exists: The required page is loaded into that frame.

• If no free frame exists: A replacement algorithm chooses a victim page.

• If the victim is dirty: It is written back to storage first.

• Page table is updated: The old page is marked not present, and the new page is mapped to the frame.

• Instruction restarts: The memory reference is tried again with the required page now in RAM.

This flow shows why page replacement is part of demand paging and virtual memory management. The operating system loads pages only when needed, but must also decide what to remove when memory becomes full.

Reference String and Frame Table

A reference string is the sequence of page numbers accessed by a process. For example: 7, 0, 1, 2, 0, 3

This means page 7 is accessed first, then page 0, then page 1, and so on. Page replacement numericals usually use a reference string and a fixed number of frames.

A frame table records the state of RAM after each page reference. It commonly shows the referenced page, whether it caused a hit or fault, the victim page if replacement happened, and the final frame contents after that access.

For 3 frames and reference string 7, 0, 1, 2, 0, 3, a simple demonstration may look like this:

Here, the first three faults happen because the frames are initially empty. Later, replacement is needed because all three frames are full. In real numericals, the victim is not chosen randomly; it follows the given algorithm such as FIFO, LRU, Optimal, or another policy.

What Makes a Replacement Algorithm Good

The main goal of a page replacement algorithm is to reduce page faults. Fewer page faults usually mean fewer expensive disk accesses and better effective memory access time.

A good algorithm tries to keep useful pages in RAM and remove pages that are less likely to be used soon. Since a real operating system cannot know the future perfectly, practical algorithms estimate usefulness from past access patterns, reference bits, timestamps, or queue order.

Common replacement policies differ mainly in victim selection:

• FIFO: Removes the page that entered memory first.

• LRU: Removes the page that has not been used for the longest time.

• Optimal: Removes the page that will not be used for the longest time in the future, but it is mainly theoretical because future references are not known in real systems.

• Clock: Uses reference bits to approximate recent usage with lower overhead than exact LRU.

These algorithms share the same page fault handling flow. Their difference is the rule used to choose the victim page.

Evaluation Metrics

Page replacement performance is usually measured using page hits and page faults.

• Page fault rate = Number of page faults / Total number of references

• Hit rate = Number of page hits / Total number of references

A lower page fault rate generally means better performance, but fault count is not the only cost. If an algorithm frequently evicts dirty pages, the system may need more writebacks to storage, which increases I/O overhead.

So, while page fault rate and hit rate are the basic measures, practical performance also depends on dirty-page writebacks, replacement overhead, and how well the algorithm matches the program’s locality of reference.

Summary

Page replacement is the operating system’s decision about which page should leave RAM when a page fault occurs and no free frame is available. It is an important part of virtual memory because RAM is limited, while a process may refer to many virtual pages over time.

A page replacement algorithm should reduce unnecessary page faults and avoid costly dirty-page writebacks where possible. Frame tables, reference strings, hit rate, and page fault rate help analyze how well a replacement policy behaves for a given sequence of memory references.