Page Replacement Algorithms in Operating System

Page replacement is an important part of virtual memory management in an operating system. When a process requests a page that is not currently available in physical memory, a page fault occurs. If all available page frames are already occupied, the operating system must decide which existing page should be removed so that the required page can be loaded.

The method used to select the page that will be removed is called a page replacement algorithm. Different algorithms make this decision using different information such as the order in which pages entered memory, their recent usage, or their expected future usage.

What is a Page Fault?

A page fault occurs when a process references a page that is not currently present in its allocated physical memory frames. The operating system must then locate the required page in secondary storage, bring it into RAM, and update the necessary memory-management information.

If an empty frame is available, the required page can be loaded directly. If no free frame exists, a page replacement algorithm is required to select a victim page for removal.

What is a Page Hit?

A page hit occurs when the requested page is already present in one of the available page frames. Since the page is already in physical memory, the operating system does not need to fetch it from secondary storage.

Why is Page Replacement Required?

Physical memory is limited, while a process may reference more pages than can fit into the currently available frames. Therefore, when all frames are occupied and a new page is required, the operating system needs a systematic method for deciding which page should leave memory.

• Physical RAM has limited capacity.
• A process may require more pages than the available frames.
• Only a subset of a program may need to remain in RAM at a particular time.
• An appropriate replacement decision can reduce unnecessary page faults.
• Lower page-fault frequency can improve overall memory-management performance.

Important Terms Used in Page Replacement

Term	Meaning
Page	A fixed-size unit of a process's virtual address space.
Frame	A fixed-size block of physical memory that can hold a page.
Reference String	The sequence in which pages are requested by a process.
Page Hit	The requested page is already present in memory.
Page Fault	The requested page is absent from physical memory.
Victim Page	The page selected for removal when a replacement is required.

Types of Page Replacement Algorithms

Several page replacement algorithms have been proposed to make replacement decisions. The most commonly studied algorithms in operating-system courses are:

1. FIFO – First In First Out
2. LRU – Least Recently Used
3. Optimal Page Replacement
4. MRU – Most Recently Used

---

1. FIFO Page Replacement Algorithm

FIFO stands for First In First Out. It replaces the page that has been present in memory for the longest time. The algorithm follows the same basic principle as a queue: the page that entered first is considered for removal first.

FIFO Solved Example

Consider the following page reference string with three available frames.

• Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 1, 2, 0
• Number of Frames: 3
• Algorithm: FIFO

The first three different pages can occupy the three available frames. When page 2 is requested, all frames are occupied, so FIFO removes page 7 because it was the first page loaded into memory.

The same procedure continues for every subsequent page reference. Whenever the requested page is already present, the event is counted as a hit. Otherwise, a page fault occurs and FIFO replaces the oldest resident page.

FIFO Result

• Total Page References: 15
• Total Page Faults: 12
• Total Page Hits: 3
• Number of Frames: 3

Advantages of FIFO

• Simple to understand and implement.
• Requires relatively little information about page usage.
• Queue-based implementation makes the replacement order easy to maintain.
• Useful for understanding the basic concept of page replacement.

Disadvantages of FIFO

• It does not consider how frequently a page is being used.
• A frequently referenced page may be removed simply because it is old.
• Its replacement decisions may result in unnecessary page faults.
• FIFO can exhibit Belady's Anomaly for certain reference strings.

---

2. LRU Page Replacement Algorithm

LRU stands for Least Recently Used. Instead of looking at the arrival order of pages, LRU considers their recent access history. When replacement becomes necessary, it removes the page that has not been used for the longest period of time.

LRU Solved Example

• Page Reference String: 7, 0, 1, 2, 0, 2, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• Number of Frames: 4
• Algorithm: LRU

During execution, every page reference is checked against the four available frames. If the requested page is already present, the reference is a hit. Otherwise, a page fault occurs.

Once all four frames are occupied, LRU examines the previous access history. The page that has remained unused for the longest time is selected as the victim.

LRU Result

• Total Page References: 20
• Total Page Faults: 8
• Total Page Hits: 12
• Number of Frames: 4

Advantages of LRU

• Uses actual recent-reference information.
• Often performs better than simple FIFO for suitable workloads.
• It is based on the principle of locality of reference.
• It is an important practical and theoretical page-replacement technique.

Disadvantages of LRU

• Tracking recent usage can require additional hardware or software support.
• Exact implementation can be more complicated than FIFO.
• Maintaining access history can introduce overhead.

---

3. Optimal Page Replacement Algorithm

The Optimal Page Replacement Algorithm, also known as OPT or MIN, replaces the page whose next use occurs farthest in the future.

If a page will never be referenced again, it becomes an ideal candidate for replacement. Because the algorithm assumes knowledge of future references, it provides a theoretical lower bound on the number of page faults for a particular reference string and number of frames.

Optimal Algorithm Example

• Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 1, 2, 0
• Number of Frames: 4
• Algorithm: Optimal

When all four frames are occupied and a new page is required, the algorithm looks ahead in the reference string. It determines which currently resident page will be required farthest in the future and replaces that page.

Optimal Result

• Total Page References: 15
• Total Page Faults: 7
• Total Page Hits: 8

Advantages of Optimal Replacement

• Produces the minimum possible page faults for a known reference string.
• Useful as a benchmark for evaluating practical algorithms.
• Provides an ideal reference point for theoretical analysis.

Disadvantages of Optimal Replacement

• Requires knowledge of future page references.
• Exact future behavior is not normally available during execution.
• Therefore, it is mainly useful for theoretical study and comparison.

---

4. MRU Page Replacement Algorithm

MRU stands for Most Recently Used. It follows a strategy opposite to LRU in one important respect. When replacement is required, MRU selects the page that was accessed most recently.

This approach may be useful for workloads where recently accessed pages are less likely to be referenced again immediately. However, it is not generally the default choice for every workload.

MRU Example

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

The reference string contains 20 page requests. Using the MRU replacement rule, a page fault occurs whenever the requested page is not in memory. Once the frames become full, the most recently accessed resident page is selected for replacement.

MRU Result

• Total Page References: 20
• Total Page Faults: 12
• Total Page Hits: 8

Important Point About MRU

MRU should not be considered universally better or worse than LRU. Its usefulness depends on the access pattern of the application. The main distinction is simple: LRU removes the least recently accessed page, whereas MRU removes the most recently accessed page.

---

Page Fault Rate and Page Hit Rate

Page fault rate and page hit rate are useful measures for analyzing the behavior of a page replacement algorithm. They must be calculated with respect to the total number of page references.

Comparison of Page Replacement Algorithms

Algorithm	Replacement Basis	Future Knowledge Required?	Main Advantage	Main Limitation
FIFO	Oldest loaded page	No	Simple implementation	May remove frequently used pages
LRU	Least recently used page	No	Uses recent access behavior	Requires usage tracking
Optimal	Page used farthest in future	Yes	Minimum theoretical page faults	Future references are not known in practice
MRU	Most recently used page	No	Useful for selected access patterns	Can perform poorly for common locality patterns

FIFO vs LRU vs Optimal vs MRU

The main difference between these algorithms is the information used to select the victim page.

• FIFO: asks, "Which page has been in memory the longest?"
• LRU: asks, "Which page has not been used for the longest time?"
• Optimal: asks, "Which page will be needed farthest in the future?"
• MRU: asks, "Which page was used most recently?"

Why Does the Number of Page Faults Matter?

A page fault can involve accessing secondary storage, which is considerably slower than accessing RAM. Therefore, excessive page faults can increase the time required to satisfy memory references.

A good replacement strategy attempts to keep useful pages in memory and avoid unnecessary transfers. However, the best algorithm depends on the characteristics of the workload, available hardware support, implementation cost, and access pattern.

Belady's Anomaly

Belady's Anomaly is a well-known phenomenon associated with some page replacement strategies, particularly FIFO. It describes a situation where increasing the number of available page frames can unexpectedly increase the number of page faults for a particular reference string.

This result may seem counterintuitive because more frames normally appear to provide more room for pages. The phenomenon demonstrates that the behavior of a replacement algorithm depends on its replacement policy and the reference pattern.

Locality of Reference and Page Replacement

Programs often exhibit locality of reference, meaning that a process tends to access a relatively small group of pages repeatedly during a particular period.

Temporal locality means that recently used data or instructions are likely to be used again soon. Spatial locality means that addresses near a recently accessed location may also be accessed.

LRU is particularly connected with temporal locality because it attempts to retain pages that have been accessed recently.

Common Mistakes in Page Replacement Problems

1. Counting a page hit as a page fault.
   If the requested page already exists in a frame, it is a hit.
2. Using the wrong denominator for page fault rate.
   Use total page references, not the number of frames.
3. Confusing FIFO and LRU.
   FIFO considers arrival order, while LRU considers recent usage.
4. Using future information incorrectly in Optimal.
   The page whose next reference occurs farthest in the future is selected.
5. Forgetting that empty frames are used before replacement.
   Replacement is necessary only after all available frames are occupied.
6. Using frame count as total references.
   Frames and references represent two different quantities.

Exam-Oriented Short Notes

Frequently Asked Questions

Interview Questions on Page Replacement

1. What happens when all page frames are full and a page fault occurs?
   The operating system selects a victim page using the configured replacement algorithm and loads the required page into the released frame.
2. What is the difference between FIFO and LRU?
   FIFO uses page arrival order, whereas LRU uses the time since a page was last accessed.
3. Why can FIFO suffer from Belady's Anomaly?
   FIFO's queue-based replacement order does not necessarily preserve the pages that are most useful for future references.
4. Why is Optimal replacement not normally used in practice?
   Because exact future page references are unavailable during normal execution.
5. What is the difference between a page fault and a page hit?
   A fault means the page is absent from memory, while a hit means the page is already present.
6. What is a victim page?
   It is the resident page selected for removal to make room for the requested page.
7. What is page fault rate?
   It is the percentage of page references that result in page faults.
8. What is MRU?
   MRU is Most Recently Used and selects the most recently accessed page for replacement.

Practice Problems

Quick Revision: Page Replacement Algorithms

• Page Fault: Requested page is absent from physical memory.
• Page Hit: Requested page is already present in memory.
• FIFO: Removes the oldest resident page.
• LRU: Removes the least recently accessed page.
• Optimal: Removes the page whose next use is farthest in the future.
• MRU: Removes the most recently accessed page.
• Page Fault Rate: Page Faults / Total Page References × 100.
• Page Hit Rate: Page Hits / Total Page References × 100.
• Belady's Anomaly: A well-known phenomenon associated with FIFO.

Conclusion

Page replacement algorithms are an essential component of virtual memory management because physical memory cannot hold every page that a process may need during execution. Whenever a requested page is absent and no free frame is available, the operating system must select a resident page for replacement.

FIFO makes this decision using the arrival order of pages. LRU uses recent access history, while Optimal examines future references and therefore serves as an ideal theoretical benchmark. MRU uses the opposite principle of LRU by selecting the most recently accessed page.

For numerical questions, students should carefully distinguish between a page fault and a page hit, correctly maintain the contents of each frame, and use the total number of page references when calculating page fault or hit rates. Understanding these fundamentals makes problems involving FIFO, LRU, Optimal and MRU much easier to solve.