Page Replacement Algorithms in OS: FIFO, LRU, Optimal & Solved Examples

OPERATING SYSTEM - CHAPTER 25

Page Replacement Algorithms in OS: FIFO, LRU, Optimal and Solved Examples

Demand Paging allows the operating system to load a page only when it is needed. But what happens when a page fault occurs and every physical frame is already occupied?

The operating system must choose one page already present in RAM, remove or replace it, and use that frame for the incoming page.

The rule used to choose that page is called a Page Replacement Algorithm.

Quick Answer:

A Page Replacement Algorithm decides which page should be removed from physical memory when a page fault occurs and no free frame is available.

FIFO removes the page that entered memory first.
LRU removes the page that has not been used for the longest time in the past.
Optimal removes the page whose next use is farthest in the future.

The main objective is to reduce the number of page faults while keeping the replacement decision practical.

Jump to a Topic

Why Replacement Is Needed Important Terms Working FIFO Belady's Anomaly Optimal LRU Comparison Simulator Exam Revision FAQ

Why Do Page Replacement Algorithms Feel Difficult?

Students usually understand the definition of FIFO, LRU and Optimal. The real confusion starts when a long reference string is given and frames must be updated one page at a time.

1

Hit and Fault Get Mixed Up If the requested page already exists in a frame, nothing should be replaced.

2

Replacement Rule Changes FIFO looks at arrival order, LRU looks at past usage, while Optimal looks at future usage.

3

Same Reference String, Different Result The same pages and same number of frames can produce different page-fault counts with different algorithms.

Easy Memory Trick:

FIFO = Who came first?

LRU = Who was used least recently?

Optimal = Who will be needed farthest in the future?

Why Do We Need Page Replacement?

In demand paging, a page fault occurs when the required page is not currently present in physical memory.

If a free frame exists, the solution is simple. The operating system can load the required page into that free frame.

But physical memory may already be full.

RAM Before Page Fault

Frame 0 = Page 2

Frame 1 = Page 7

Frame 2 = Page 4

→

New Page Needed

Required Page = Page 5

No Free Frame

One Existing Page Must Leave

When no free frame is available, the operating system selects one existing page as a victim page.

How Page Replacement Works

PAGE REPLACEMENT PIPELINE

1 Page Requested CPU references a virtual page.

2 Page Fault Required page is not resident in RAM.

3 Check Frames OS checks whether a free frame is available.

4 Choose Victim If memory is full, replacement algorithm selects a page.

5 Load New Page Required page enters the selected frame and mappings are updated.

Important Terms Before Solving Page Replacement Problems

Reference String Sequence of page numbers referenced by the process.

Page Frame Fixed-size physical-memory slot that can store one page.

Page Fault Required page is not currently resident in the available frames.

Page Hit Required page is already present in a frame.

Victim Page Existing page selected for replacement.

Dirty Page A page modified after being loaded into memory.

What Is a Page Hit?

Suppose RAM contains:

Frame 1 = Page 2 Frame 2 = Page 4 Frame 3 = Page 7

If the CPU now requests Page 4, Page 4 is already resident.

This is a Page Hit. No page replacement is required.

Hit Ratio:

Hit Ratio = Number of Page Hits / Total Page References

What Is a Page Fault in Replacement Problems?

Again assume the frames contain:

Page 2 Page 4 Page 7

If Page 5 is requested, it is not currently resident.

A Page Fault occurs. If all frames are occupied, the selected page replacement algorithm must decide which current page should leave.

Page Fault Ratio:

Page Fault Ratio = Number of Page Faults / Total Page References

Do We Replace a Page When a Free Frame Exists?

No.

This is an important exam rule.

Suppose there are three frames but currently only two frames are occupied.

Frame 1 = Page 2 Frame 2 = Page 5 Frame 3 = Empty

If Page 7 arrives, it is simply loaded into the empty frame.

Replacement begins only when:

Required page is absent
AND
No usable free frame is available.

Three Main Page Replacement Algorithms

FIFO

First In First Out

Remove the page that has stayed in memory for the longest time.

Think of a normal queue.

LRU

Least Recently Used

Remove the page that was used least recently in the past.

Think of recent usage history.

OPTIMAL

Optimal Replacement

Remove the page whose next use is farthest in the future.

Think of perfect future knowledge.

FIFO Page Replacement Algorithm

FIFO stands for First In First Out.

The page that entered physical memory first is selected for replacement first.

FIFO Rule:

Oldest loaded page leaves first.

Think of RAM as a Queue

Oldest

P2

P5

P7

Newest

If a new page must enter and memory is full, P2 will be removed first because it entered the queue first.

FIFO Algorithm Step by Step

1. Start with empty frames.
2. Read the next page from the reference string.
3. If the page is already present, count a Page Hit.
4. If the page is absent, count a Page Fault.
5. If a free frame exists, place the page there.
6. If all frames are full, remove the page that entered memory earliest.
7. Add the new page to the newest position of the FIFO queue.
8. Continue until the entire reference string is processed.

Reference String Used in Our Solved Examples

We will use the same reference string for FIFO, LRU and Optimal so that the difference becomes very clear.

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 Number of Frames: 3

Using the same reference string is important because it lets us compare the algorithms fairly.

FIFO Solved Example with 3 Frames

Reference	Frame 1	Frame 2	Frame 3	Result
7	7	-	-	Fault
0	7	0	-	Fault
1	7	0	1	Fault
2	2	0	1	Fault
0	2	0	1	Hit
3	2	3	1	Fault
0	2	3	0	Fault
4	4	3	0	Fault
2	4	2	0	Fault
3	4	2	3	Fault
0	0	2	3	Fault
3	0	2	3	Hit
2	0	2	3	Hit

Total References = 13 FIFO Page Faults = 10 Page Hits = 3 Page Fault Ratio = 10 / 13 Hit Ratio = 3 / 13

FIFO Final Answer:
Total Page Faults = 10

Advantages and Disadvantages of FIFO

Advantages

• Very simple to understand.
• Easy to implement using a queue.
• Replacement decision has low conceptual complexity.
• Does not require tracking detailed usage history.

Disadvantages

• Oldest page may still be heavily used.
• Ignores recent usage.
• Can generate more page faults than smarter policies.
• Can suffer from Belady's Anomaly.

What Is Belady's Anomaly?

Normally, students expect that increasing the number of frames should reduce page faults.

Surprisingly, with FIFO there are reference strings where increasing the number of frames can actually increase the number of page faults.

Definition:
Belady's Anomaly is the phenomenon in which increasing the number of page frames causes more page faults for certain page replacement algorithms such as FIFO.

Classic Reference String

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

FIFO with 3 Frames 9 Page Faults

FIFO with 4 Frames 10 Page Faults

Frames increased from 3 to 4, but page faults increased from 9 to 10. This is Belady's Anomaly.

Do LRU and Optimal Suffer from Belady's Anomaly?

LRU and Optimal have an important theoretical property known as the stack property.

Informally, pages held with fewer frames form a subset of pages that can be held with more frames under these algorithms.

LRU and Optimal do not exhibit Belady's Anomaly in the way FIFO can.

Optimal Page Replacement Algorithm

Optimal replacement is also called OPT or sometimes MIN.

It replaces the page whose next use occurs farthest in the future.

Optimal Rule:

Look into future references.

Remove the resident page that will be needed latest in the future.

If a page will never be used again, that page is an excellent victim.

How Optimal Chooses a Victim Page

Suppose frames contain:

Page 2 Page 0 Page 3

And the future reference string is:

Future References

4

2

3

0

3

2

Among pages 2, 0 and 3:

• Page 2 will be required relatively soon.
• Page 3 will also be required.
• Page 0 is needed later than some alternatives.

Optimal examines these future positions and selects the page whose next use is farthest away.

Optimal Algorithm Step by Step

1. Read the next page reference.
2. If the page is already present, count a Hit.
3. If absent, count a Page Fault.
4. If a free frame exists, use it.
5. If memory is full, inspect future references of all resident pages.
6. Find the resident page whose next use is farthest in the future.
7. If a resident page is never referenced again, it can be selected.
8. Replace the victim and continue.

Optimal Solved Example with 3 Frames

Reference	Frame 1	Frame 2	Frame 3	Result
7	7	-	-	Fault
0	7	0	-	Fault
1	7	0	1	Fault
2	2	0	1	Fault
0	2	0	1	Hit
3	2	0	3	Fault
0	2	0	3	Hit
4	2	4	3	Fault
2	2	4	3	Hit
3	2	4	3	Hit
0	2	0	3	Fault
3	2	0	3	Hit
2	2	0	3	Hit

Total References = 13 Optimal Page Faults = 7 Page Hits = 6

Optimal Final Answer:
Total Page Faults = 7

Why Is Optimal Not Normally Implemented Exactly?

Optimal requires the operating system to know the exact future memory references of a process.

In a real running system, the operating system generally does not know the complete future reference sequence in advance.

Therefore, exact Optimal replacement is mainly useful as a theoretical benchmark.

It tells us the lowest page-fault count achievable for a given reference string and number of frames under the ideal future-knowledge model.

Advantages and Limitations of Optimal Replacement

Advantages

• Produces the minimum possible page faults for the given reference string.
• Excellent benchmark for comparing other algorithms.
• Easy to understand in solved examination problems.
• Does not suffer from Belady's Anomaly.

Limitations

• Requires knowledge of future references.
• Exact implementation is not generally practical online.
• Mainly used for analysis and comparison.

LRU Page Replacement Algorithm

LRU stands for Least Recently Used.

Instead of checking when a page entered memory, LRU checks when the page was last used.

LRU Rule:

Replace the resident page that has not been referenced for the longest time in the past.

Understanding "Least Recently Used"

Suppose frames contain:

Page 2 Page 0 Page 3

Their recent usage order is:

Recent Usage Timeline

P2
Oldest Use

P3

P0
Most Recent

If another page must enter, LRU selects P2 because P2 was used least recently.

LRU Algorithm Step by Step

1. Read the next reference.
2. Check whether the page is already resident.
3. If present, record its latest use.
4. If absent, count a Page Fault.
5. Use a free frame if available.
6. If all frames are full, inspect the past use of resident pages.
7. Replace the page whose last use occurred farthest in the past.
8. Update usage information and continue.

LRU Solved Example with 3 Frames

Reference	Frame 1	Frame 2	Frame 3	Result
7	7	-	-	Fault
0	7	0	-	Fault
1	7	0	1	Fault
2	2	0	1	Fault
0	2	0	1	Hit
3	2	0	3	Fault
0	2	0	3	Hit
4	4	0	3	Fault
2	4	0	2	Fault
3	4	3	2	Fault
0	0	3	2	Fault
3	0	3	2	Hit
2	0	3	2	Hit

Total References = 13 LRU Page Faults = 9 Page Hits = 4

LRU Final Answer:
Total Page Faults = 9

How Can LRU Be Implemented?

LRU needs information about recent page usage. There are several conceptual ways to maintain this information.

METHOD 1 Counter or Timestamp

Store the time of the most recent reference for each page.

METHOD 2 Stack / Ordered List

Move a referenced page toward the most-recent position.

PRACTICAL IDEA Approximation

Real systems may use hardware reference bits and LRU-like approximations.

Why Can Exact LRU Be Expensive?

Exact LRU needs the system to know the precise recency order of memory references.

Updating detailed recency information for every memory access can create implementation overhead.

Because of this, real systems often use hardware-supported reference information or algorithms that approximate LRU behavior rather than maintaining a perfect software history of every access.

Advantages and Disadvantages of LRU

Advantages

• Uses actual recent reference behavior.
• Often performs better than simple FIFO.
• Works well with locality of reference.
• Does not exhibit Belady's Anomaly.

Disadvantages

• Exact recency tracking adds overhead.
• Requires additional implementation support.
• More complex than FIFO.
• Practical systems often approximate it.

FIFO vs LRU vs Optimal: Same Example Comparison

For the reference string:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 Frames = 3

FIFO 10 Page Faults

LRU 9 Page Faults

Optimal 7 Page Faults

These numbers apply to this specific reference string and three-frame configuration. A different reference string can produce different results.

Difference Between FIFO, LRU and Optimal

Basis	FIFO	LRU	Optimal
Full Form	First In First Out	Least Recently Used	Optimal Page Replacement
Decision Basis	Arrival time	Past usage	Future usage
Victim Page	Oldest loaded page	Least recently referenced page	Page needed farthest in future
Main Data Needed	Queue order	Recency information	Future reference string
Implementation	Simple	More complex	Not exactly practical online
Belady's Anomaly	Can occur	Does not occur	Does not occur
Page Fault Quality	May be relatively high	Often good	Minimum possible for given reference string
Real-Time Future Knowledge	Not required	Not required	Required
Main Use	Simple replacement concept	Practical replacement principle	Benchmark and theoretical comparison

What Happens to the Victim Page?

Choosing a victim page is only one part of replacement.

The operating system must also determine whether the victim page has been modified.

C

Clean Page If the page has not been modified, its frame may be reused without writing modified contents back.

D

Dirty Page If page contents have changed, backing data may need updating before the frame is reused.

I/O

Extra Cost Writing a dirty page can increase page-fault service time.

Local vs Global Page Replacement

Replacement can also be discussed based on which frames are eligible to be selected.

Local Replacement

A process chooses a victim only from the frames currently allocated to that process.

One process cannot directly take an arbitrary frame belonging to another process under the local policy.

Global Replacement

The system may choose a victim from a wider set of frames, potentially including frames currently used by other processes, according to the system's allocation policy.

How Does the Number of Frames Affect Page Faults?

In general, having more useful physical frames gives a process more room to keep its actively referenced pages resident.

This can reduce page faults.

However, FIFO teaches us an important exception: increasing frames does not guarantee fewer faults for every algorithm and every reference string.

Never write: "More frames always means fewer page faults."

FIFO may show Belady's Anomaly.

Page Replacement and System Performance

Every page fault can require expensive operating-system work and potentially storage I/O.

Therefore, a page replacement algorithm should attempt to keep pages that are likely to be needed and remove pages that are less useful.

Better replacement decision → fewer unnecessary page faults → lower paging overhead → better effective performance

Best Method to Solve Page Replacement Numericals

1. Write the reference string clearly from left to right.
2. Draw exactly the number of frames given in the question.
3. Start with all frames empty.
4. Process one reference at a time.
5. First check whether the page is already present.
6. Mark a Hit if present.
7. Mark a Fault if absent.
8. Use a free frame before performing replacement.
9. When memory is full, apply only the rule of the selected algorithm.
10. Do not change frame contents on a normal hit.
11. Count faults only after completing the complete reference string.
12. Recheck every replacement if the final answer looks suspicious.

Common Mistakes Students Make

Mistake 1: Replacing a Page on a Hit

If the requested page is already present, there is no page fault and no normal replacement is required.

Mistake 2: Using FIFO Order as LRU Order

FIFO asks when the page entered memory. LRU asks when the page was last referenced. These are not the same thing.

Mistake 3: Looking Backward in Optimal

Optimal looks forward into future references, not backward into past references.

Mistake 4: Looking Forward in LRU

LRU only needs past usage information.

Mistake 5: Ignoring Empty Frames

Do not select a victim page if an unused frame is still available.

Mistake 6: Counting First Loads as Hits

Loading a page into an empty frame because it was absent still produces a page fault.

Mistake 7: Updating FIFO Order on Every Hit

In standard FIFO, a hit does not make the page "new". FIFO order is based on when pages entered memory.

Mistake 8: Not Updating LRU Recency on Hits

In LRU, every reference matters. A hit makes that page recently used.

Interactive Page Replacement Simulator

Enter a reference string, number of frames and algorithm.

You can write the reference string with commas or spaces.

FIFO, LRU and Optimal Simulator

Reference String

Number of Frames

Algorithm FIFO LRU Optimal

Are FIFO, LRU and Optimal the Only Page Replacement Algorithms?

No.

They are the three most important algorithms for understanding the basic concept, but several other policies also exist.

Second Chance Improves FIFO by giving recently referenced pages another chance.

Clock Algorithm Practical circular-pointer implementation related to Second Chance.

LFU Least Frequently Used considers how often pages are referenced.

MFU Most Frequently Used uses a different frequency-based assumption.

NRU Not Recently Used can use reference and modification information to group candidate pages.

These algorithms build on the same foundation: when a page fault occurs and a frame is required, the operating system needs a policy for selecting a victim.

One-Minute Revision

Page Replacement Select a victim when a required page must enter full memory.

Reference String Ordered sequence of page references.

Page Fault Requested page is not currently resident.

Page Hit Requested page is already resident.

FIFO Replace the oldest loaded page.

LRU Replace the least recently referenced page.

Optimal Replace the page needed farthest in the future.

Belady's Anomaly More frames can sometimes cause more FIFO faults.

Dirty Page Modified victim may require additional write-back work.

Page Replacement Algorithms Exam Preparation

2-Mark Definition

A Page Replacement Algorithm is a policy used by the operating system to select a victim page when a required page must be loaded into physical memory and no free frame is available.

FIFO Short Answer

FIFO replaces the page that entered memory first. It can be implemented using queue order.

LRU Short Answer

LRU replaces the page that has not been referenced for the longest time in the past.

Optimal Short Answer

Optimal replaces the page whose next reference is farthest in the future. It produces the minimum page faults for the given reference string but requires future knowledge.

Belady's Anomaly

Belady's Anomaly is the condition in which increasing the number of frames increases the number of page faults for certain algorithms such as FIFO.

Important Numerical Rules

FIFO = Replace Oldest Loaded Page LRU = Replace Least Recently Used Page Optimal = Replace Page Needed Farthest in Future Page Fault Ratio = Page Faults / Total References Hit Ratio = Page Hits / Total References

For a 5-Mark Question

1. Define Page Replacement.
2. Explain when replacement is required.
3. Define FIFO, LRU and Optimal.
4. Write basic advantages and disadvantages.
5. Explain Belady's Anomaly.

For a 10-Mark Question

1. Demand Paging background.
2. Need for Page Replacement.
3. Page Fault and Page Hit.
4. Reference String and Frames.
5. Victim Page.
6. FIFO Algorithm.
7. FIFO Solved Example.
8. Belady's Anomaly.
9. Optimal Algorithm.
10. Optimal Solved Example.
11. LRU Algorithm.
12. LRU Solved Example.
13. LRU Implementation.
14. Dirty Page Effect.
15. Comparison of FIFO, LRU and Optimal.

Frequently Asked Questions

What is a Page Replacement Algorithm?

A Page Replacement Algorithm selects a victim page when a required page must enter physical memory and no free frame is available.

What is FIFO Page Replacement?

FIFO replaces the page that entered memory first. It normally maintains pages in first-in-first-out order.

What is LRU Page Replacement?

LRU replaces the page that has not been referenced for the longest time in the past.

What is Optimal Page Replacement?

Optimal replacement selects the page whose next reference is farthest in the future.

Which Page Replacement Algorithm Gives Minimum Page Faults?

For a known reference string, the Optimal replacement algorithm gives the minimum possible number of page faults under its future-knowledge model.

Why Is Optimal Page Replacement Not Normally Practical?

Exact Optimal replacement requires knowledge of future page references, which a running operating system generally does not know in advance.

What Is Belady's Anomaly?

Belady's Anomaly is a situation where increasing the number of page frames causes more page faults for certain replacement algorithms such as FIFO.

Does LRU Have Belady's Anomaly?

LRU has the stack property and does not exhibit Belady's Anomaly.

What Is a Victim Page?

A victim page is the page selected by the replacement algorithm to leave physical memory so that its frame can be reused.

Does a Page Hit Cause Replacement?

No. If the requested page is already present in memory, it is a page hit and normal page replacement is not required.

Does a Page Fault Always Cause Replacement?

No. If a free frame is available, the required page can be loaded into that frame without replacing an existing resident page.

What Is the Main Difference Between FIFO and LRU?

FIFO uses page arrival order, while LRU uses recent page-reference history.

What Is the Main Difference Between LRU and Optimal?

LRU examines past references to find the least recently used page, while Optimal examines future references to find the page needed farthest in the future.

Conclusion

Page Replacement Algorithms become necessary when a page fault occurs, the required page is not resident, and no free physical frame is available.

The operating system must then select a victim page.

FIFO makes the decision using page arrival order. The oldest loaded page leaves first.

LRU uses recent history. The page that has not been used for the longest time is replaced.

Optimal uses future references. It selects the page whose next use is farthest away, producing the minimum possible page faults for the known reference string.

FIFO is simple but can suffer from Belady's Anomaly. LRU usually makes better locality-based decisions, but exact recency tracking has a cost.

Optimal provides the ideal benchmark but is not generally available as an exact online algorithm because the operating system does not know future references perfectly.

Final Memory Trick:

Page Hit = Page Already in RAM

Page Fault = Page Missing

Free Frame Available = No Victim Needed

Memory Full = Replacement Required

FIFO = Oldest Loaded Page

LRU = Least Recently Used Page

Optimal = Page Needed Farthest in Future

FIFO = Belady's Anomaly Possible

LRU and Optimal = No Belady's Anomaly