Page Replacement Algorithms: LRU, FIFO & Optimal |…

What Page Replacement Algorithms Are

Page replacement is a fundamental concept in operating systems where memory management is concerned. It involves deciding which pages to replace when the system runs out of space for new pages. The goal is to minimize page faults, which occur when a requested page is not currently in physical memory.

The simulation allows you to experiment with three common algorithms: Least Recently Used (LRU), First-In-First-Out (FIFO), and Optimal. Each algorithm has its own strategy for choosing which pages to replace.

How LRU, FIFO & Optimal Work

The LRU algorithm replaces the page that was least recently used first. This approach tends to be effective because it assumes that a page not accessed in some time is less likely to be needed soon.

FIFO, on the other hand, replaces the oldest page in memory. While simple, this method can lead to Bélády's anomaly, where increasing the number of frames actually increases the number of page faults.

live demo · related simulation● LIVE

Why It Matters

Efficient page replacement is crucial for system performance and resource utilization. Poor algorithms can lead to high page fault rates, which degrade overall system responsiveness and throughput.

The simulation helps in understanding the trade-offs between different strategies and provides insights into why certain policies might be more suitable under specific conditions.

Real-World Applications

Page replacement algorithms are not just theoretical constructs. They are used in various systems, from web browsers to operating system kernels, where managing memory efficiently is critical.

For instance, LRU is widely used in caching mechanisms because it tends to keep the most recently accessed data in memory, reducing the likelihood of future page faults.

Frequently asked questions

What is Bélády's anomaly?

Bélády's anomaly occurs when increasing the number of frames actually increases the number of page faults. This happens with FIFO but not with LRU or optimal algorithms.

Why does FIFO perform worse as frame size increases in some cases?

FIFO tends to replace the oldest pages, which can lead to a situation where frequently accessed pages are evicted and then need to be reloaded, increasing page faults.

How is LRU different from FIFO in practice?

LRU considers the recency of access when deciding which page to replace, whereas FIFO simply replaces the oldest page. This makes LRU generally more efficient for managing memory.

What does an optimal algorithm do?

An optimal algorithm always chooses the page that will not be needed until the farthest future time, theoretically minimizing page faults but being impractical to implement in real systems.

Try it live

Everything above runs in your browser — open Page Replacement — LRU, FIFO & Optimal and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Page Replacement — LRU, FIFO & Optimal simulation