Page Replacement in OS: Algorithms, Types & Examples
A page replacement algorithm decides which page to evict from memory when a page fault occurs and every frame is already full. The operating system uses it to choose a victim page, write it back if modified, and load the requested page. Common algorithms include FIFO, Optimal, LRU, LIFO, LFU, and Random.
Key Takeaways
- Page replacement decides which page to remove from memory when a page fault occurs and all frames are occupied.
- The worked examples use the same reference string: 3, 1, 2, 1, 6, 5, 1, 3 with 3 frames.
- FIFO: 7 page faults.
- Optimal: 5 page faults.
- LRU: 6 page faults.
- LIFO: 5 page faults.
- Random: 6 page faults in the example shown; this is one possible outcome, not a fixed result.
- LFU: Replaces the page with the lowest access frequency; a verified fault count is not provided in the worked examples. Belady's anomaly: FIFO can produce more page faults when the number of frames is increased.
What is Page Replacement in Operating Systems?
Page replacement is the policy an OS uses to pick a victim page the moment a page fault happens and memory is already full. Every algorithm below is answering the same one question, differently: which resident page gets thrown out to make room for the one that just faulted?
| Term | Meaning |
|---|---|
| Page fault | The referenced page isn't resident in memory, and the OS must fetch it |
| Page hit | The referenced page is already resident, no fetch needed |
| Frame | A fixed-size slot in physical memory that holds exactly one page |
| Reference string | The sequence of page numbers a process asks for, in order |
| Victim page | The resident page chosen for eviction to make room for a new one |
| Hit ratio | hits ÷ total references, the one number people actually quote |
One cost worth flagging early: if the victim page has been modified (its dirty bit is set), it has to be written back to disk before the new page can load. A clean victim just gets overwritten. That single bit quietly shows up again in the Clock section below.
Why Need Page Replacement Algorithms?
Demand paging is deliberately over-committed. The OS loads pages only when they're actually referenced instead of the whole process upfront, which is the point of virtual memory and demand paging in the first place, but it also guarantees that running programs will ask for more than physical memory can hold. Page faults aren't a bug in this scheme, they're the price of it.
A page fault is the trap raised when a referenced page is not resident in memory, while page miss is used informally to describe the occurrence of a missing page. Compulsory misses occur when a page is accessed for the first time. In the reference string used in the examples, the first references to pages 3, 1, and 2 are compulsory misses because these pages have not been loaded into memory yet. Capacity misses occur when the available frames cannot hold all the pages a process needs. Page replacement algorithms address capacity misses by deciding which resident page should be replaced.
Here's the part that actually matters for algorithm design: once a fault happens, the fetch itself is dominated by disk I/O, which is slower than a memory access by several orders of magnitude. No algorithm can make an individual fault cheaper. The only lever anyone has is the fault count itself. Minimise faults, because you can't discount them. Get the choice wrong across an entire system and you get thrashing, the CPU spending more cycles managing memory than running anything in it.
Types of Page Replacement Algorithms (Comparison)
Before picking apart any one algorithm, here's the full comparison in one table. Every fault count below is measured on the same reference string at the same 3 frames, introduced right after this table, so nothing here is apples to oranges.
| Algorithm | Eviction rule | Faults (3 frames) | Implementable? | Belady's anomaly? | Typical exam use |
|---|---|---|---|---|---|
| FIFO | Evict the page that entered memory earliest | 15 | Yes, a simple queue | Yes | The baseline; the standard Belady's anomaly question |
| Optimal (OPT/MIN) | Evict the page whose next use is farthest away | 9 | No, needs the future | No (stack algorithm) | The theoretical floor everything else is scored against |
| LRU | Evict the page unused for the longest time | 12 | Yes, but costly | No (stack algorithm) | The practical benchmark; the most-asked numerical |
| Clock (Second-Chance) | FIFO scan, skip pages with reference bit 1 | 14 | Yes, real OSes ship this | Yes (a FIFO refinement) | "What do real operating systems use?" |
| LIFO | Evict the page loaded most recently | 12 | Yes | Yes | Rarely examined; a good counter-example |
| MRU | Evict the page used most recently | 16 | Yes | Yes | Contrast with LRU; cyclic sequential scans |
| Random | Evict a uniformly random resident page | Not fixed | Yes, very cheap | Yes | Baseline showing any policy beats none |
One row above deserves a second look. LIFO scores 12 on this string, tied with LRU, and that looks like a mistake at first glance. It isn't. LIFO scores well here only by accident, it permanently freezes the first pages loaded, so it happens to keep pages 7 and 0 resident the whole way through. On a sequential-scan string, that same freezing behaviour is catastrophic. Nobody else covering this topic seems to point that out, so consider it pointed out.
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreThe Reference String We'll Use Throughout
Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 — 20 references, 3 frames unless stated otherwise. FIFO = 15 faults, LRU = 12, Optimal = 9.
Why this exact string and not a shorter, tidier one: it's the string from Operating System Concepts (Silberschatz, Galvin & Gagne), it's the one Gate Smashers-style videos use, and it's shown up in actual GATE papers. Most people land on this page already holding this string in a notebook, checking their own trace against it. All three headline numbers here are checked against the textbook, not against another blog's answer key.
FIFO — 15 faults
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 |
| F2 | – | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| F3 | – | – | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 |
| H/F | F | F | F | F | H | F | F | F | F | F | F | H | H | F | F | H | H | F | F | F |
| Faults | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 10 | 10 | 11 | 12 | 12 | 12 | 13 | 14 | 15 |
FIFO: 15 faults, 5 hits.
![]
LRU — 12 faults
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| F2 | – | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 0 | 0 | 0 | 0 | 0 |
| F3 | – | – | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | 7 | 7 |
| H/F | F | F | F | F | H | F | H | F | F | F | F | H | H | F | H | F | H | F | H | H |
| Faults | 1 | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 9 | 9 | 9 | 10 | 10 | 11 | 11 | 12 | 12 | 12 |
LRU: 12 faults, 8 hits.
![]
Optimal — 9 faults
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | 7 | 7 |
| F2 | – | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| F3 | – | – | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| H/F | F | F | F | F | H | F | H | F | H | H | F | H | H | F | H | H | H | F | H | H |
| Faults | 1 | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 6 | 6 | 7 | 7 | 7 | 8 | 8 | 8 | 8 | 9 | 9 | 9 |
Optimal: 9 faults, 11 hits.
Same string, same three frames: Optimal 9 ≤ LRU 12 ≤ FIFO 15. Optimal is the floor no implementable algorithm can beat, and LRU is how close a real algorithm gets.
Two eviction calls worth annotating, because these are exactly where people lose marks:
● Optimal, step 4 (reference 2): resident pages are 7, 0 and 1. Their next uses land at step 18, step 5 and step 14. 7 is farthest away, so 7 is the victim, even though 7 was also the page FIFO would have picked here. That agreement is a coincidence, the two algorithms part ways almost immediately after this point.
● LRU, step 11 (reference 0): resident pages are 4, 3 and 2, last used at steps 8, 10 and 9. 4 is the least recently used and gets evicted. Page 4 also happens to never be referenced again in this string, so LRU gets this call right by luck as much as by design.
Page Replacement Algorithms in Operating Systems
First In First Out (FIFO)
The FIFO algorithm is the simplest page replacement algorithm; among page replacement algorithms FIFO maintains a queue of all the pages that are in the memory currently. The oldest page in the memory is at the front end of the queue and the most recent page is at the back or rear end of the queue.
Whenever a page fault occurs, the operating system looks at the front end of the queue, a new page is loaded, and the replacement algorithm selects the oldest page first. It also adds this newly requested page at the rear end and removes the oldest page from the front end of the queue.
Example: Consider the page reference string as 3, 1, 2, 1, 6, , 1, 3 with 3 page frames, where the frames are initially empty frames. Let’s try to find the number of page faults:
- Initially, all of the slots are empty so page faults occur at 3,1,2.
Page faults = 3
- When page 1 comes, it is in the memory so no page fault occurs.
Page faults = 3
- When page 6 comes, it is not present and a page fault occurs. Since there are no empty slots, we remove the front of the queue, i.e 3.
Page faults = 4
- When page 5 comes, it is also not present, and hence a page fault occurs. The front of the queue i.e. 1 is removed.
Page faults = 5
- When page 1 comes, it is not found in memory and again a page fault occurs. The front of the queue i.e. 2 is removed.
Page faults = 6
- When page 3 comes, it is again not found in memory, a page fault occurs, and page 6 is removed being on top of the queue
Total page faults = 7
Belady’s anomaly: Generally if we increase the number of frames in the memory, the number of page faults should decrease due to obvious reasons. Belady’s anomaly refers to the phenomena where increasing how many frames are allocated in memory can increase page faults as well, which matters because more memory does not always improve performance.
Advantages
-
Simple to understand and implement
-
Does not cause more overhead
Disadvantages
-
Poor performance
-
Can remove frequently used pages just because they are the oldest.
-
Suffers from Belady’s anomaly.
Master structured AI Engineering + GenAI hands-on, earn IIT Roorkee CEC Certification at ₹40,000
Optimal Page Replacement in OS
Optimal page replacement is the optimal algorithm as this algorithm gives the lowest page fault rate. In this algorithm, the pages are replaced with the ones that will not be used for the longest duration of time in the future. In simple terms, the pages that will be referred to farthest in the future are replaced in this algorithm, but it uses future requests from the reference string and requires future knowledge, so it is mainly treated as a theoretical benchmark.
Example:
Let’s take the same page reference string 3, 1, 2, 1, 6, 5, 1, 3 with 3-page frames as we saw in FIFO. This also helps you understand how Optimal Page replacement works the best.
- Initially, since all the slots are empty, pages 3, 1, 2 cause a page fault and take the empty slots.
Page faults = 3
- When page 1 comes, it is in the memory and no page fault occurs.
Page faults = 3
- When page 6 comes, it is not in the memory, so a page fault occurs and 2 is removed as it is not going to be used again.
Page faults = 4
- When page 5 comes, it is also not in the memory and causes a page fault. Similar to above 6 is removed as it is not going to be used again.
page faults = 5
- When page 1 and page 3 come, they are in the memory so no page fault occurs.
Total page faults = 5
Advantages
-
Excellent efficiency
-
Less complexity
-
Easy to use and understand
-
Simple data structures can be used to implement
-
Mainly used as a benchmark against other page replacement algorithms
Disadvantages
-
More time consuming
-
Difficult for error handling
-
It needs future knowledge of memory access patterns and future knowledge of the reference string, so it is impractical in real systems
Least Recently Used (LRU) Page Replacement Algorithm
The least recently used page replacement algorithm keeps the track of page usage over a period of time by monitoring page usage patterns and the order of page access. This algorithm works on the basis of the principle of locality of a reference which states that a program has a tendency to access the same set of memory locations repetitively over a short period of time and in similar page requests. So pages that have been used heavily in the past are most likely to be used heavily in the future also.
In this algorithm, when a page fault occurs, then the page that has not been used for the longest duration of time is replaced by the newly requested page.
Example: Let’s see the performance of the LRU on the same reference string of 3, 1, 2, 1, 6, 5, 1, 3 with 3-page frames:
- Initially, since all the slots are empty, pages 3, 1, 2 cause a page fault and take the empty slots.
Page faults = 3
- When page 1 comes, it is in the memory and no page fault occurs.
Page faults = 3
- When page 6 comes, it is not in the memory, so a page fault occurs and the least recently used page 3 is removed.
Page faults = 4
- When page 5 comes, it again causes a page fault, and page 1 is removed as it is now the least recently used page.
Page faults = 5
- When page 1 comes again, it is not in the memory, and hence page 2 is removed according to the LRU.
Page faults = 6
- When page 3 comes, the page fault occurs again and this time page 6 is removed as the least recently used one.
Total page faults = 7
Now in the above example, the LRU causes the same page faults as the FIFO, but this may not always be the case as it will depend upon the series, the number of frames available in memory, etc. In fact, on most occasions, LRU is better than FIFO.
Advantages
-
It is open for full analysis
-
Doesn’t suffer from Belady’s anomaly
-
Often more efficient than other algorithms
Disadvantages
-
It requires additional data structures to be implemented for tracking page access order, such as stacks or counters
-
More complex
-
High hardware assistance is required
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreLast In First Out (LIFO) Page Replacement Algorithm
This is the Last in First Out algorithm and works on LIFO principles. In this algorithm, the newest page is replaced by the requested page. This is different from the mru page replacement algorithm, which replaces the most recently used page under the assumption that less recently used pages may be needed again soon. Usually, this is done through a stack, where we maintain a stack of pages currently in the memory with the newest page being at the top. Whenever a page fault occurs, the page at the top of the stack is replaced.
Example: Let’s see how the LIFO performs for our example string of 3, 1, 2, 1, 6, 5, 1, 3 with 3-page frames:
- Initially, since all the slots are empty, page 3,1,2 causes a page fault and takes the empty slots.
Page faults = 3
- When page 1 comes, it is in the memory and no page fault occurs.
Page faults = 3
- When page 6 comes, the page fault occurs and page 2 is removed as it is on the top of the stack and is the newest page.
Page faults = 4
- When page 5 comes, it is not in the memory, which causes a page fault, and hence page 6 is removed being on top of the stack.
Page faults = 5
- When page 1 and page 3 come, they are in memory already, hence no page fault occurs.
Total page faults = 5
As you may notice, this is the same number of page faults as the Optimal page replacement algorithm. So we can say that for this series of pages, this is the best algorithm that can be implemented without the prior knowledge of future references.
Advantages
-
Simple to understand
-
Easy to implement
-
No overhead
Disadvantages
-
Does not consider Locality principle, hence may produce worst performance
-
The old pages may reside in memory forever even if they are not used
Become the Ai engineer who can design, build, and iterate real AI products, not just demos with an IIT Roorkee CEC Certification
Random Page Replacement in OS
This algorithm, as the name suggests, chooses any random page in the memory to be replaced by the requested page. This algorithm can behave like any of the algorithms based on the random page chosen to be replaced. Among other common page replacement techniques, Not Recently Used (NRU) uses referenced and modified bits, while Least Frequently Used (LFU) removes the page with the lowest frequency count.
Example: Suppose we choose to replace the middle frame every time a page fault occurs. Let’s see how our series of 3, 1, 2, 1, 6, 5, 1, 3 with 3-page frames perform with this algorithm:
- Initially, since all the slots are empty, page 3,1,2 causes a page fault and takes the empty slots
Page faults = 3
- When page 1 comes, it is in the memory and no page fault occurs.
Page faults = 3
- When page 6 comes, the page fault occurs, we replace the middle element i.e 1 is removed.
Page faults = 4
- When page 5 comes, the page fault occurs again and middle element 6 is removed
Page faults = 5
- When page 1 comes, there is again a page fault, and again the middle element 5 is removed
Page faults = 6
- When page 3 comes, it is in memory, hence no page fault occurs.
Total page faults = 6
As we can see, compared with other replacement techniques, the performance is not the best, but it’s also not the worst. The performance in the random replacement algorithm depends on the choice of the page chosen at random.
Advantages
-
Easy to understand and implement
-
No extra data structure needed to implement
-
No overhead
Disadvantages
-
Can not be analyzed, may produce different performances for the same series
-
Can suffer from Belady’s anomaly
Operating systems are the backbone of modern computing. Join our free Operating System full course and become proficient in operating systems.
Least Frequently Used (LFU) Page Replacement Algorithm
The Least Frequently Used (LFU) page replacement algorithm replaces the page that has been accessed the fewest number of times. It maintains a frequency count for each page and, when a page fault occurs with all frames occupied, replaces the page with the lowest frequency count.
If two or more pages have the same frequency, a tie-breaking rule such as FIFO or LRU can be used to decide which page to replace.
Advantages
- Uses page access frequency to make replacement decisions.
- Can retain pages that are accessed frequently.
Disadvantages
- Requires additional counters or data structures to track page frequency.
- A page that was frequently used in the past may remain in memory even after it is no longer needed.
Conclusion
Page replacement algorithms help the operating system manage limited physical memory by deciding which page to remove when a new page needs to be loaded. FIFO, LRU, Optimal, LIFO, LFU, and Random use different rules to select the page to replace, so their page-fault performance can vary depending on the reference string and number of frames.
If you want to explore the main algorithms in more detail, you can continue with our:
FIFO page replacement algorithm
LRU page replacement algorithm
Optimal page replacement algorithm
Operating systems are the backbone of modern computing. Join our free Operating System full course and become proficient in operating systems.
Turn Learning into Career Growth
FAQs
1. What is a page replacement algorithm?
A page replacement algorithm is used by an operating system to decide which page to remove from memory when a page fault occurs and all available frames are occupied. The selected page is replaced by the requested page so that the process can continue execution.
2. What are the different page replacement algorithms?
Common page replacement algorithms include FIFO, Optimal, LRU, LIFO, LFU, and Random. Each algorithm uses a different rule to select the page that should be replaced. FIFO uses arrival order, LRU uses recent access history, Optimal considers future references, while Random selects a page randomly.
3. Which page replacement algorithm gives the minimum page faults?
The Optimal page replacement algorithm gives the minimum possible number of page faults for a given reference string and number of frames. It replaces the page whose next use is farthest in the future. However, it requires knowledge of future page references, so it is mainly used as a benchmark.
4. What is Belady's anomaly in page replacement?
Belady's anomaly occurs when increasing the number of page frames causes the number of page faults to increase. It can occur with FIFO page replacement. For example, with the reference string used in this article, FIFO produces 9 faults with 3 frames and 10 faults with 4 frames.
5. What is the difference between FIFO and LRU page replacement?
FIFO replaces the page that has been in memory for the longest time, regardless of how recently it was accessed. LRU replaces the page that has not been used for the longest time. Their results can therefore differ for the same reference string, as shown by the 7 FIFO faults and 6 LRU faults in the example.
6. Does LRU suffer from Belady's anomaly?
No. LRU does not suffer from Belady's anomaly because it is a stack algorithm. With a stack algorithm, the set of pages held with n frames is always a subset of the pages held with n+1 frames. Therefore, increasing the number of frames cannot increase the number of page faults under LRU.
7. What is a page fault in an operating system?
A page fault occurs when a process references a page that is not currently present in physical memory. The operating system must bring the required page into memory before execution can continue. If all frames are occupied, a page replacement algorithm is used to select a page for removal.
8. How is the page replacement algorithm selected?
The replacement policy determines which page is selected when a page fault occurs and all frames are occupied. Different algorithms use different criteria: FIFO uses arrival order, LRU uses recent usage, Optimal uses future references, and Random selects a page without using access history. The appropriate comparison depends on the reference string and implementation requirements.
