Welcome back. In our previous lesson, we delved into the mechanics of virtual-to-physical address translation, exploring how paging and multi-level page tables make virtual memory possible. We concluded by noting that when a program accesses a page that isn't in physical memory, the hardware triggers a page fault. This brings us to a crucial question: if all physical memory frames are occupied, how does the operating system decide which page to evict to make room for the new one?
This lesson addresses that exact problem. You will learn about page replacement algorithms, which are the strategies the OS uses to select a "victim" page for eviction. The efficiency of this choice directly impacts system performance, as a poor choice can lead to frequent page faults, a phenomenon known as thrashing. Our goal is to compare the most common algorithms—First-In, First-Out (FIFO) and Least Recently Used (LRU)—by applying them to a sequence of memory accesses, called a reference string, and calculating the resulting number of page faults.
The Page Replacement Problem
When a page fault occurs, the OS must bring the required page from the disk into a physical page frame. If there are no free frames, the OS must choose a page currently in memory, write it back to disk if it has been modified (if its "dirty" bit is set), and then load the new page into the now-free frame.
The central challenge is selecting the best victim page. The ideal algorithm would evict a page that won't be needed for the longest time, minimizing future page faults. We evaluate different algorithms by running them on a given reference string and counting how many page faults they generate. The fewer the faults, the better the algorithm.
[PDF] Operating System: Page Replacement Algorithms
This document introduces the fundamental concepts of page replacement. It defines the problem and the evaluation criteria.
Please read the first page, from the beginning down to the end of the section on reference strings. This will solidify the concepts of a page fault, the principle of page replacement, and the use of a reference string to evaluate performance.
First-In, First-Out (FIFO)
The simplest page replacement policy is First-In, First-Out (FIFO). As the name implies, the OS tracks the order in which pages are loaded into memory and evicts the one that has been there the longest. This is analogous to a basic queue data structure.
While simple to implement, its logic is not always effective. A page might be old but still in active use, yet FIFO would evict it regardless.
Let's see this in action. The best way to understand these algorithms is to trace them manually.
The following video provides an excellent, step-by-step walkthrough of how to calculate page faults for FIFO using a common reference string. It shows both a detailed method tracking the state of memory and a quicker "shortcut" method.
EASY-HOW-TO Page Replacement Algorithm (FIFO, Optimal, and LRU) Tutorial (Manual)
This video from Blancaflor Arada clearly demonstrates the manual calculation for FIFO.
Watch the segment on the FIFO algorithm, from the start of the FIFO section to its conclusion. Follow along as the presenter traces the reference string and determines which pages are replaced, ultimately counting the total page faults.
Belady's Anomaly
A surprising and counterintuitive property of FIFO is Belady's Anomaly, where increasing the number of available page frames can, in some cases, increase the number of page faults. This is the opposite of what one would expect.
[PDF] Operating System: Page Replacement Algorithms
This section of the document you read earlier provides a concrete example of this strange behavior.
Find the heading "FIFO (First In First Out) Page Replacement" and read the short section below the first example titled Belady's Anomaly. Notice how going from 3 frames to 4 frames with the given reference string increases the page faults from 9 to 10.
This anomaly, combined with its disregard for a page's recent usage patterns, makes FIFO a less-than-ideal choice in most modern systems.
Least Recently Used (LRU)
A much more effective algorithm is Least Recently Used (LRU). This policy is based on the principle of locality, which observes that programs tend to reuse data and instructions they have recently accessed. LRU leverages this by replacing the page that has not been used for the longest amount of time. The assumption is that a page that hasn't been used in a while is less likely to be needed in the near future.
Let's trace the same reference string from the video, but this time using the LRU policy.
Now, let's return to the video tutorial to see the manual calculation for LRU. The presenter will again use the same reference string, which allows for a direct comparison with FIFO.
EASY-HOW-TO Page Replacement Algorithm (FIFO, Optimal, and LRU) Tutorial (Manual)
This segment of the video demonstrates the LRU calculation.
Watch the explanation of the LRU algorithm, from the start of the LRU section to its conclusion. Pay close attention to how, at each step, you must look backwards in the reference string to determine which page in memory has been unused for the longest time.
LRU generally performs very well and is a good approximation of the theoretical best-case algorithm. It does not suffer from Belady's Anomaly. However, a pure implementation can be complex, as it requires the system to keep track of when every page was last accessed, which can involve significant overhead. Hardware support, such as an "accessed" bit in the page table entry and timestamping mechanisms, is often used to create efficient approximations of LRU.
The Optimal Algorithm (OPT/MIN)
To properly evaluate algorithms like FIFO and LRU, we need a baseline for what is theoretically possible. This baseline is provided by the Optimal Page Replacement Algorithm (OPT), also known as MIN.
The OPT algorithm has a simple, but impossible, policy: replace the page that will not be used for the longest period of time in the future.
This requires clairvoyance—the OS would need to know the entire future sequence of memory references. While this makes it impossible to implement in a real system, it's extremely valuable as a benchmark. It tells us the absolute minimum number of page faults that can be achieved for a given reference string. The performance of any practical algorithm can be measured by how close it gets to the optimal result.
Let's complete our exercise by watching the walkthrough for the OPT algorithm.
EASY-HOW-TO Page Replacement Algorithm (FIFO, Optimal, and LRU) Tutorial (Manual)
This final segment of the video demonstrates the OPT calculation.
Watch the section on the Optimal algorithm, from the start of the Optimal section to its conclusion. Notice how the decision at each step involves looking forward in the reference string to see which page will be referenced furthest in the future.
Comparison and Conclusion
Let's summarize the results from the video's example (3 frames, specific reference string):
- FIFO: 15 page faults
- LRU: 12 page faults
- Optimal: 9 page faults
As expected, Optimal gives the best result. LRU performs significantly better than FIFO and is a reasonable approximation of Optimal. This is a common outcome and illustrates why LRU and its variants are far more prevalent in real-world systems than FIFO.
Here is a summary of the key characteristics:
| Algorithm | Eviction Policy | Key Characteristics |
|---|---|---|
| FIFO | Oldest page in memory. | Simple to implement (a queue). Can perform poorly; suffers from Belady's Anomaly. |
| LRU | Longest time since last use. | Generally good performance; approximates OPT. Doesn't suffer from Belady's Anomaly. More complex to implement efficiently. |
| Optimal | Longest time until next use. | Guarantees the fewest possible page faults. Impossible to implement in practice; used as a benchmark. |
In this lesson, you've learned how to analyze and compare fundamental page replacement algorithms. By tracing a reference string and counting page faults, you can quantitatively assess their performance. This practical skill is essential for understanding one of the core trade-offs in operating system memory management: the balance between algorithmic complexity and performance.
Our focus so far has been on how the OS manages a single process's access to resources like memory. However, modern systems run many processes and threads concurrently. This introduces a new set of challenges related to coordination and shared access. In our next lesson, we will shift our focus to concurrency control and investigate what happens when multiple threads try to access the same data simultaneously. This will lead us to the concept of a race condition and the primary tool used to prevent it: the mutex.