Page Replacement Algorithms Explained (FIFO, LRU, Optimal)

The operating system (OS) is responsible for memory management. Managing memory efficiently is one of the most critical responsibilities of the OS. Physical memory is not enough as programs grow larger and more complex. Modern systems solve this problem using virtual memory, a memory that is used to execute processes even when only a part of the process is loaded into RAM.

Read: Process vs. Thread: Key Differences Explained with Examples.

However, virtual memory comes with a new challenge; it has to decide which memory pages to replace when memory is full. This problem is remedied using special algorithms known as Page Replacement Algorithms.

This article explores the three foundational page replacement algorithms: FIFO, LRU, and Optimal Page Replacement. We will examine how they work, their advantages and disadvantages, and their practical significance in modern systems.

What is Page Replacement?

Page replacement in the OS is a virtual memory management technique that swaps out or replaces existing pages from physical memory (RAM) to secondary storage when memory is full and a new page is requested. It determines which page to replace, reduces page faults, and ensures efficient memory usage.

• Memory is divided into fixed-size units called pages.
• Physical memory is divided into frames.
• Pages are loaded into frames as needed.
• When a page is requested but not present in memory, it results in a page fault.
• If all frames are occupied by pages, the system must replace an existing page and make room for a new page.

It is crucial to choose a page to be removed from the frame. A wrong page chosen for removal may lead to frequent page faults and degraded system performance. A correct page removed, however, improves the system efficiency.

• Minimizes the number of page faults
• Is computationally efficient
• It is easy to implement in real systems

Key Concepts: Page Replacement

• Page Fault: Occurs when a program accesses a page mapped in the virtual address space but not present in physical memory.
• Victim Page: The page selected to be swapped out to the disk.
• Dirty Bit: A mechanism to determine if a page has been modified; dirty pages must be written back to the disk, increasing page fault penalty.

Need for Page Replacement

• Memory Management: Enables systems to execute processes that are larger than physical memory. By swapping pages between RAM and secondary storage (disk/SSD), the system creates the illusion of having more memory than is physically installed.
• Handling Page Faults: A “page fault” occurs when a process needs a page not currently in RAM. If there are no empty frames, the OS must perform page replacement to continue execution. Without a page replacement mechanism, the process would crash or be unable to proceed.
• System Performance: Page replacement reduces expensive I/O operations from swapping pages from disk and directly impacts system performance.
• Optimal Allocation: When memory is full, it ensures only the most relevant pages stay in RAM, and allocation is optimum.
• Multitasking: Page replacement ensures multiple applications reside in memory simultaneously. Even if the total demand exceeds physical capacity, the OS manages which parts of which programs remain active.

Types of Page Replacement Algorithms

1. First-In-First-Out (FIFO): This is the simplest page replacement algorithm, and it replaces the oldest page that was brought into memory first. It is easy to implement but may suffer from Belady’s anomaly.
2. Least Recently Used (LRU): LRU replaces the page that has not been accessed for the longest time. In other words, it replaces the page that has been least recently used.
3. Optimal (MIN): This algorithm replaces the page that will not be used for the longest period in the future. This algorithm requires future knowledge, and though it has the lowest possible page fault rate, it is impossible to implement perfectly because it requires future knowledge.

We will discuss these three page replacement algorithms in detail in subsequent sections.

FIFO (First-In-First-Out) Page Replacement Algorithm

FIFO is the simplest page replacement algorithm. It operates on the principle:

The page in memory that has been there the longest is replaced first.

• The oldest page is removed first.
• New pages are added at the end.

This method focuses on the order of the pages and does not consider how often or how recently a page has been used.

In simple terms, when a new page is to be placed from secondary memory to main memory, the FIFO algorithm selects the front of the queue, which is the oldest page present, and removes it.

Example of FIFO Algorithm

Consider the following data:

• Number of frames = 3
• Page reference string:

5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0

Let’s simulate the FIFO algorithm. The step-by-step process is shown below:

Total page faults = 11

Advantages

• It is extremely simple to understand and implement.
• The FIFO algorithm requires minimal bookkeeping.
• It has low computational overhead.
• It is especially beneficial for small systems.

Disadvantages

• The FIFO algorithm ignores how frequently or recently a page is used.
• It may unnecessarily remove frequently used pages.
• FIFO can suffer from Belady’s Anomaly.
• It uses an additional queue data structure.

Belady’s Anomaly

Belady’s Anomaly is a counterintuitive phenomenon in the OS where increasing the number of frames allocated to a process results in more page faults. FIFO is one of the few algorithms that exhibits Belady’s anomaly, making it unreliable in certain scenarios.

Under normal circumstances, you would expect that providing more physical memory (frames) would lead to more pages staying in RAM, thereby reducing the frequency of page faults.

However, certain page-replacement algorithms, such as FIFO, cause the system to evict a page that will be needed sooner than others, even when more space is available.

Example of the Belady’s Anomaly

A classic example of Belady’s Anomaly occurs with the page reference string:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Example 1: With 3 Frames

Let us see how the FIFO algorithm works with 3 frames for the page reference string above. The steps are shown in the following table:

Using FIFO, this string results in 9 page faults.

Now, let us increase the number of frames to 4 and see how the FIFO algorithm behaves.

Example 2: With 4 frames

The following table shows the step-by-step working of the FIFO algorithm for the given page reference string with 4 frames:

Using FIFO with 4 frames, the same string results in 10 page faults.

This is the Belady’s anomaly, in which page faults increase as the number of frames increases.

As FIFO does not account for the frequency or recency of page usage, only the time a page is entered into memory is considered. So, by increasing the number of frames, the “queue” of pages is shifted so that a page required in the very near future is evicted earlier than it would have been with fewer frames. This results in Belady’s anomaly.

LRU (Least Recently Used) Page Replacement

LRU is an improvement upon FIFO. It incorporates the concept of temporal locality, which suggests that recently used pages are more likely to be used again soon. The basic idea behind LRU is:

Replace the page that has not been used for the longest time.

Unlike FIFO, which focuses on the arrival time of the page, LRU tracks its usage history.

In this algorithm, the page that has not been used for the longest period of time is selected for replacement

Example of LRU Algorithm

• Frames = 3
• Reference string:

5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0

The following table shows the simulation results of LRU:

In the above example, total page faults = 12

Although this example yields more page faults than FIFO, LRU generally performs better for most real-world workloads.

Implementation Techniques for LRU

1. Counters: In this, each page entry has a time-of-use field and a CPU counter that increments on every memory reference. The page with the lowest counter value is replaced.
2. Stack (Linked List): A stack data structure is used to keep track of page references. The most recently used page is moved to the top, and the least recently used page stays at the bottom.

LRU caching is typically implemented using a Doubly Linked List paired with a HashMap to achieve time complexity for both get and put operations. The list maintains the chronological order of usage (head for the most recent, tail for the least recent), while the map provides rapid access to list nodes.

Advantages

• It performs better than FIFO in most cases
• LRU uses actual usage patterns to make decisions
• This algorithm does not suffer from Belady’s Anomaly
• It is open for full analysis
• It is easy to choose a faulted page that hasn’t been used for a long time

Disadvantages

• LRU is more complex than FIFO
• It requires additional hardware or software support
• LRU has higher overhead due to tracking usage
• It requires an additional data structure to be implemented

Read: Data Structures and Algorithm Complexity: Complete Guide.

Optimal Page Replacement Algorithm

The Optimal algorithm is currently theoretical and represents the best possible strategy:

Replace the page that will not be used for the longest time in the future.

This approach guarantees the minimum number of page faults.

According to this algorithm, a page that will not be used for the longest period of time is to be replaced. This algorithm used the future knowledge of the reference string.

Example of Optimal Algorithm

Using three frames and the same reference string:

5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0

The following shows the result of the optimal algorithm:

Total page faults = 9

Advantages

• An optimal algorithm produces the lowest possible number of page faults
• It serves as a benchmark for evaluating other algorithms
• The complexity of this algorithm is less, and it is easier to implement
• The assistance needed is low, i.e., data structures used are easy and light

Disadvantages

• The optimal page-replacement algorithm is perfect but not possible in practice, because the operating system cannot know future requests
• It is not implementable in real systems
• Error handling is tough in this algorithm

Conclusion

Page replacement algorithms are a cornerstone of operating system design, especially in modern systems that rely on virtual memory. These algorithms determine how efficiently memory is utilized and how smoothly programs run.

The FIFO page replacement algorithm is simple and easy to implement, but it lacks intelligence, leading to poor performance. LRU is a more informed approach that considers usage history and is widely used in the form of its approximations. The optimal page replacement algorithm serves as a more informed approach but is theoretical and helps evaluate other algorithms.

While no single algorithm is perfect, understanding these three lays a strong foundation for grasping more advanced memory management techniques. Modern systems continue to evolve, but the key principles behind FIFO, LRU, and Optimal remain fundamental to designing efficient computing systems.

Frequently Asked Questions (FAQs)

1. What is a page fault?
   When a process tries to access a page that is not present in physical memory (RAM), a page fault occurs. The system is then required to fetch that page from disk, considerably slowing down the execution.
2. Why are page replacement algorithms important?
   Page replacement algorithms directly impact system performance. Efficient ones reduce page faults, improve memory utilization, and ensure faster execution of programs.
3. Which page replacement algorithm is best?
   LRU and its approximations are commonly used in real systems for their performance. Although the Optimal algorithm is theoretically considered the best, it cannot be implemented.
4. Is LRU used in real operating systems?
   Real operating systems mostly use approximations of LRU, such as Clock algorithms or the Second Chance algorithm. Pure LRU is rarely used due to its complexity.

Shilpa Prabhudesai