Page Replacement in OS: Algorithms, Types & Examples
Memory fills up, a new page needs to come in, every frame is already taken, and the OS has to pick something to throw out. That decision is the entire page replacement algorithm problem in one sentence. Get it right and the system barely notices. Get it wrong and you're deep into thrashing, swapping pages in and out faster than anything useful actually runs. Once you understand how paging maps pages to frames , the replacement question is really the only interesting part left. This page runs every major replacement policy, FIFO, Optimal, LRU, Clock, LIFO, MRU and Random, against one shared 20-reference string, so you can watch them fight over the exact same input and see which one actually holds up. There's a comparison table right below for the two-minute version, and five solved GATE-style numericals near the bottom if you'd rather test yourself first.
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.
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.
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 moreTypes 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.
The 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.
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+ morePage 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
Turn Learning into Career Growth
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
Last 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.
Conclusion
-
The objective of page replacement algorithms is to minimize the page faults for managing memory in computer systems and improving system performance
-
FIFO page replacement algorithm replaces the oldest page in the memory
-
Optimal page replacement algorithm replaces the page which will be referred farthest in the future
-
LRU page replacement algorithm replaces the page that has not been used for the longest duration of time
-
LIFO page replacement algorithm replaces the newest page in memory
-
Random page replacement algorithm replaces any page at random
-
Optimal Page Replacement algorithm is considered to be the most effective algorithm but is mainly used as a benchmark because it requires future knowledge and cannot be implemented in practical scenarios due to various limitations
