Hello! Welcome back to our journey through Operating Systems.
In our last lesson, we tackled the crucial and calculation-heavy topic of Effective Memory Access Time (EMAT). We saw that a page fault is the most expensive event in the memory access cycle, requiring the OS to intervene and fetch a page from the slow secondary disk. This naturally raises a critical question: what happens if a page fault occurs when all of main memory's frames are already full?
This lesson answers that very question. We will dive into the heart of demand paging: page replacement algorithms. When the OS needs to bring in a new page and there's no free space, it must select a "victim" page to swap out. The algorithm that makes this choice has a massive impact on system performance.
Today, you will learn to trace the behavior of the three fundamental page replacement algorithms that are perennial favorites in the GATE exam:
- First-In, First-Out (FIFO)
- Least Recently Used (LRU)
- Optimal (OPT)
Our goal is to master the mechanics of tracing these algorithms for a given memory reference string and frame count, enabling you to accurately calculate the number of page faults and hits.
The Page Replacement Scenario
Before we dive into the algorithms, let's establish the common framework for these problems. You will typically be given two things:
- Reference String: A sequence of numbers representing the pages requested by the CPU over time. For example:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, ... - Number of Frames: The number of page-sized slots allocated to the process in main memory.
For each page in the reference string, we check if it is already present in one of the frames.
- If it is, we have a page hit. Nothing changes.
- If it is not, we have a page fault.
- If there is an empty frame, we simply load the page into it.
- If all frames are full, we must use a page replacement algorithm to select a victim page to swap out, making room for the new page.
The objective is always to minimize the number of page faults.
1. First-In, First-Out (FIFO) Algorithm
FIFO is the simplest page replacement algorithm. As the name suggests, it replaces the page that has been in memory for the longest time. It maintains a queue of the pages in memory; the page at the head of the queue (the oldest) is the victim.
Let's see this in action. The following video provides an excellent step-by-step trace of the FIFO algorithm.
L-5.22: Page Replacement Introduction | FIFO Page Replacement algorithm | Operating System
This Gate Smashers video will walk you through a complete example of the FIFO algorithm, from the initial setup to calculating the final miss ratio.
Watch the video carefully, focusing on the following stages: Introduction (Why we need replacement): The video starts by recapping the concept of virtual memory and why page replacement is necessary, which directly follows from our last lesson. Problem Setup (The example): Pay attention to the given reference string and the number of frames (3 in this case). This is the standard format for GATE questions. FIFO Tracing (The trace): This is the core of the video. Follow along as the presenter fills the frames. Crucially, observe how the victim is chosen once the frames are full. In FIFO, you don't need to track usage, only the order of arrival. Notice the pointer that cycles through frames 1, 2, and 3 to select the victim. Final Calculation (The result): After the trace is complete, see how the total number of hits and faults are tallied to calculate the hit and miss ratios. After watching, you should be comfortable with the simple, mechanical nature of FIFO replacement.
Belady's Anomaly
FIFO is simple, but it has a surprising and counter-intuitive flaw known as Belady's Anomaly. This is a situation where increasing the number of allocated frames can, paradoxically, increase the number of page faults. This is a classic GATE topic.
Consider the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
- With 3 frames: You would experience 9 page faults.
- With 4 frames: You would experience 10 page faults!
This happens because the "older" page that FIFO evicts might be one that is needed again soon, while a more optimal algorithm would have kept it. Both LRU and Optimal algorithms do not suffer from Belady's Anomaly; for them, more frames will always result in an equal or fewer number of page faults.
2. Least Recently Used (LRU) Algorithm
The LRU algorithm is a significant improvement over FIFO. It operates on the principle of locality of reference, a common program behavior where recently accessed memory locations are likely to be accessed again soon. Therefore, LRU replaces the page that has not been used for the longest period. It looks backward in time.
To trace LRU, you must keep track of the recency of use for each page in memory. A common way to visualize this for manual tracing is to think of a stack. Every time a page is referenced, it moves to the top of the stack. The page at the bottom of the stack is the least recently used and becomes the victim for replacement.
Let's see an example. The video below covers all three algorithms, but we'll focus on the LRU part.
FIFO,LRU AND OPTIMAL PAGE REPLACEMENT ALGORITHMS | OPERATING SYSTEMS
This video from Last moment tuitions demonstrates the LRU algorithm. We'll use the same reference string from the previous video for comparison later, but for now, focus on the technique shown here.
Please watch the segment on the LRU algorithm, which starts around the 6-minute mark (this is an estimate). Focus on how the "victim" is selected. At each step where a replacement is needed, look backward in the reference string from the current position. The page in memory whose last use was furthest in the past is the one to be replaced. For example, if your frames hold pages {A, B, C} and you need to replace one for page D, you would look back in the reference string to see which of A, B, or C was referenced least recently.
Let's trace a small example together.
Reference String: 7, 0, 1, 2, 0, 3, 0, 4
Frames: 3
| Ref | Frame 1 | Frame 2 | Frame 3 | Fault/Hit | Comment |
|---|---|---|---|---|---|
| 7 | 7 | Fault | |||
| 0 | 7 | 0 | Fault | ||
| 1 | 7 | 0 | 1 | Fault | Frames are full. |
| 2 | 2 | 0 | 1 | Fault | Replace 7 (least recently used of 7,0,1) |
| 0 | 2 | 0 | 1 | Hit | 0 is already in memory. |
| 3 | 2 | 0 | 3 | Fault | Replace 1 (least recently used of 2,0,1) |
| 0 | 2 | 0 | 3 | Hit | 0 is already in memory. |
| 4 | 4 | 0 | 3 | Fault | Replace 2 (least recently used of 2,0,3) |
Notice how for each fault, we look at the pages currently in memory (e.g., {7, 0, 1} before referencing 2) and find the one whose last appearance in the string is furthest to the left.
3. Optimal (OPT) Algorithm
The Optimal algorithm, also known as MIN, provides the best possible performance. It has the lowest page fault rate of any algorithm and does not suffer from Belady's Anomaly.
Its logic is simple but impossible to implement in practice: replace the page that will not be used for the longest period in the future. This algorithm is "clairvoyant"—it knows the entire sequence of future requests.
While not practical, OPT is used as a benchmark. It allows us to measure how close a practical algorithm like LRU comes to the theoretical best.
FIFO,LRU AND OPTIMAL PAGE REPLACEMENT ALGORITHMS | OPERATING SYSTEMS
Now, let's examine the Optimal algorithm using the same video.
Watch the segment on the Optimal algorithm, which should start around the 11-minute mark (this is an estimate). The key is the "look-ahead" logic. When a page fault occurs and frames are full, look forward in the reference string. The page currently in a frame that is referenced furthest in the future (or never referenced again) is the one you replace.
Let's trace the same example with OPT.
Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 (shortened for brevity)
Frames: 3
| Ref | Frame 1 | Frame 2 | Frame 3 | Fault/Hit | Comment |
|---|---|---|---|---|---|
| 7 | 7 | Fault | |||
| 0 | 7 | 0 | Fault | ||
| 1 | 7 | 0 | 1 | Fault | Frames are full. |
| 2 | 2 | 0 | 1 | Fault | Replace 7. (Future uses: 0, 1, 2. 7 is furthest away) |
| 0 | 2 | 0 | 1 | Hit | |
| 3 | 3 | 0 | 1 | Fault | Replace 2. (Future uses: 0, 1. 2 is furthest away) |
| 0 | 3 | 0 | 1 | Hit | |
| 4 | 4 | 0 | 1 | Fault | Replace 3. (Future uses: 0, 1. 3 is furthest away) |
When replacing for page 2, the pages in memory were {7, 0, 1}. Looking ahead, 0 is used next, then 3 (not in memory), then 0 again, then 4, then 2. The future uses are 0, 1, 2. Page 7 is not used again, so it is the optimal page to replace. Correction in my trace: looking at the reference string, page 2 is used, page 0 is used, page 1 is not used. Let me re-do the trace to be more careful, this is a common mistake.
Let's re-trace 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. Frames: 3.
Memory: {7,0,1}. Next ref: 2.
- Future use of 7: Not seen.
- Future use of 0: Immediate.
- Future use of 1: Not seen.
Replace 7 or 1. Let's say 7. Memory becomes {2,0,1}. Fault.
Next ref: 0. Hit. Memory {2,0,1}.
Next ref: 3. Memory {2,0,1}. - Future use of 2: Yes.
- Future use of 0: Yes.
- Future use of 1: No.
Replace 1. Memory becomes {2,0,3}. Fault.
And so on. The key is the forward-looking strategy.
Summary and Comparison
This is a high-yield topic for GATE, and questions often ask you to compare the number of page faults for the same string across different algorithms.
| Algorithm | Replacement Logic | Performance | Implementable? | Belady's Anomaly |
|---|---|---|---|---|
| FIFO | Oldest in memory (time of arrival) | Can be poor | Yes (Simple queue) | Yes |
| LRU | Least recently used (time of last use) | Good, near-optimal | Yes (Complex hardware) | No |
| Optimal | Farthest future use | The best possible | No (Requires clairvoyance) | No |
Key Takeaways
- Page replacement algorithms decide which page to evict from memory when a page fault occurs and all frames are full.
- FIFO is simple but can make poor decisions. You trace it by tracking the arrival order, like a queue.
- LRU is a practical and effective algorithm that approximates optimal behavior by replacing the page unused for the longest time (looking backward).
- Optimal is the theoretical benchmark that replaces the page unused for the longest time in the future (looking forward). It gives the minimum possible page faults.
- For GATE, you must be able to meticulously trace a given reference string for all three algorithms and count the page faults accurately. Practice is key.
In our final lesson for the Operating Systems module, we will shift our focus from memory to persistent storage. We will explore how File Systems are structured and how the OS manages disk access through I/O Scheduling algorithms.