Page Replacement Algorithms in OS

While working with an operating system, one of the most important things it does is manage memory efficiently. Since the main memory is limited, the operating system needs to decide which pages it should keep in memory and which ones it should replace. This is where the page replacement algorithms in OS come into play. In this blog, you will learn about what page replacement algorithms are, why they are important, and the types of page replacement algorithms in OS, like FIFO, LRU, MRU, and Optimal Replacement Algorithm in OS.

Table of Contents:

• What is Page Replacement in Operating Systems
• Types of Page Replacement Algorithms in OS
  1. First In First Out (FIFO) Page Replacement Algorithm
  2. Least Recently Used (LRU) Page Replacement Algorithm
  3. Most Recently Used (MRU) Page Replacement Algorithm
  4. Optimal Page Replacement Algorithm in OS
  5. Last In First Out (LIFO) Page Replacement Algorithm
  6. Random Page Replacement Algorithms
• Comparison of Page Replacement Algorithms in OS
• Best Practices for Page Replacement in OS
• Conclusion

What is Page Replacement in Operating Systems

In simple words, page replacement in the operating system happens when the memory of your computer (RAM) is full, and a new page needs to be loaded. The Operating System needs to decide which existing page it should remove and make space for the new page. This process is an important part of the page replacement mechanism in the OS, which is used in systems that work with virtual memory and demand paging. In demand paging, only a few pages of a program are loaded into the memory at a time instead of the whole program. This helps multiple programs run smoothly together without consuming too much memory.

Therefore, when a program requests a page that is not currently present in the memory, the operating system brings back that page from the disk and uses a page replacement algorithm in OS, which helps to choose which old pages need to be replaced. This helps the system run efficiently, even though memory is limited.

Types of Page Replacement Algorithms in OS

In this section, we will be discussing the different types of page replacement algorithms in OS

1. First In First Out (FIFO) Page Replacement Algorithm

The FIFO page replacement algorithm in OS is one of the simplest and easiest to understand among all the page replacement algorithms in OS. In this method, the operating system keeps a queue of all the pages that are currently present in the memory. The page that entered the memory first is placed at the front of the queue, and the page that is added most recently is placed at the end. 

Whenever a page fault occurs, which means that the required page is not in the memory, the operating system replaces the page that has been longest in the memory at the front of the queue, whereas the new page that was just requested is placed at the last of the queue. Hence, the FIFO page replacement algorithm in OS works on the principle of “first-come, first-served”. The oldest page is removed first to make space for the new one. For example, suppose a page reference string is 3, 1, 2, 1, 6, 5, 1, 3 with 3 page frames. Here, you have to find the number of page faults:

Step 1: Page 3 Arrives

At first, the memory is empty. Therefore, page 3 is loaded into the first frame. It’s a miss because the page was not present in the memory before.

Step 2: Page 1 Arrives

After 3 is added to the first frame, there is still some space left in the memory. Therefore, page 1 is added next. Another miss occurs because the page is new.

Step 3: Page 2 Arrives

The last empty frame of the memory is filled with page 2. This is also a miss because it is being loaded for the first time.

Step 4: Page 1 Arrives Again

Since page 1 is already present in the memory, it’s a hit. Here, no replacement occurs, and the memory stays the same.

Step 5: Page 6 Arrives:

Now, the memory is full. According to FIFO, the oldest page (3) is now replaced with 6. This leads to a miss.

Step 6: Page 5 Arrives

The oldest page in the memory is 1, and it gets replaced by 5. This causes a miss again.

Step 7: Page 1 Arrives

Now, the oldest page in the memory is 2, which then gets replaced by 1. This causes another miss.

Step 8: Page 3 Arrives

Now the oldest page that is left is 6, therefore it gets replaced by 3. This is also a miss.

In summary:

• Total Page Faults (Misses): 7
• Total Page Hits: 1
• Replacement Order: 3 -> 1 -> 2 -> 6 -> 5 -> 1 -> 3

Hence, we can conclude that the FIFO page replacement algorithm in OS always removes the oldest page first. It is very simple to use, but it does not always make an efficient choice.

Advantages of FIFO

1. Easy to Understand and Implement: The FIFO page replacement algorithm in OS is very simple and easy to use. You just need to keep track of the order in which the pages enter the memory. Here, no complex calculations are required.

2. Requires Less Overhead: Since FIFO only requires a basic queue structure, it does not require any extra memory or processing to record the history of page usage. This helps to make the algorithm lightweight and efficient for small systems.

3. Predictable Behavior: FIFO is easy to predict because pages are replaced in the same order they entered memory.

Disadvantages of FIFO

1. Poor Performance with certain workloads: The FIFO page replacement algorithm in the OS can remove pages that are still used frequently. This slows down the system.

2. Belady’s Anomaly: Sometimes, increasing the memory size may cause more page faults than with a smaller memory size when using FIFO. This behavior is known as Belady’s Anomaly

3. Ignores Page Usage: FIFO does not check how recently a page is used. This may remove the important pages.

2. Least Recently Used (LRU) Page Replacement Algorithm

The LRU page replacement algorithm in an OS is one of the page replacement algorithms that helps to keep track of the number of pages that are used over time. It works on the idea that programs use the same memory locations repeatedly in a short period. This is called the principle of locality of reference. This means that pages used frequently in the past are likely to be used again in the future.

In this algorithm, whenever a page fault occurs, the page that has not been used for the longest period of time is removed and replaced with a new page that is required by the program. In this way, the LRU page replacement algorithm in the OS tries to make memory usage more efficient.

Example: Now let us have a look at the performance of LRU on the same reference string 3, 1, 2, 1, 6, 5, 1, 3 with 3-page frames.

Step 1: Start with an Empty Memory

At first, the memory does not contain any pages; therefore, the first few pages are added directly. Here, page 3 is loaded at first.

Step 2: Add New Pages Until Memory is Full

In the next step, pages 1 and 2 are added. Now the memory contains [3, 1, 2]

Step 3: Check for Repeated Changes

When you request page 1 again, it is already present in the memory. Therefore, you do not need any replacement for it.

Step 4: Replace the Least Recently Used Page

When you request page 6 inside the memory, the memory is already full. The page that has not been used for the longest time is removed and replaced with 6.

Step 5: Continue Peplacing Based on LRU

In the next step, page 5 is replaced by the page that is least recently used (2). This happens because the memory becomes full again.

Step 6: Reuse of Existing Pages

When you request page 1 again, it is already present in the memory. Therefore, no replacement of page 1 is required.

Step 7: Final Replacement

When page 3 is requested, the page that is least recently used (6) is replaced with 3.

This shows how the LRU page replacement algorithm always removes the page that has not been used for the longest time by keeping the frequently used pages in the memory.

Advantages of LRU

1. Better Performance: The LRU page replacement algorithm usually performs better than FIFO. This is because it replaces the page that is likely to be used soon.

2. Reduces Page Faults: LRU keeps the pages that are used in memory frequently. This helps to reduce the faults when compared to FIFO.

3. Adapts to Program Behavior: Unlike the FIFO page replacement algorithm in OS, LRU considers only the actual usage of pages. Therefore, it adapts to the memory access patterns of the program.

Disadvantages of LRU

1. Difficult to Implement: The LRU page replacement algorithm in the OS requires extra hardware or software to track the order of page usage. This makes it harder to implement when compared to other algorithms.

2. More Memory and Time Needed: In order to keep track of which pages are used recently, LRU requires additional memory and processing time, which can eventually slow down the system.

3. Not Perfect for All Workloads: The LRU page replacement algorithm in the OS works well when the pages are used repeatedly, but it may not perform well when programs access memory randomly.

3. Most Recently Used (MRU) Page Replacement Algorithm

The MRU page replacement algorithm in the OS is one of the most important page replacement algorithms. Instead of removing the page that is least recently used, it removes the page that was most recently used. The main concept behind MRU page replacement is that it removes the most recently used page, assuming it is less likely to be used soon. This method can be effective in situations like sequential data access, where the pages that are used recently are not needed again. However, in most cases, MRU is less efficient than LRU as it might remove the pages that will be required shortly after.

Example: Given below is an example of MRU using the reference string 3, 1, 2, 1, 6, 5, 1, 3.

Step 1: Start with an Empty Memory

At the first step, the memory is empty. Pages 3, 1, and 2 are added one by one until the memory becomes full.

Step 2: Handle Repeated Page Access

When you request page 1 again, it is already present in the memory. Therefore, there is no need to replace any page. Now, page 1 has become the most recently used page.

Step 3: Replace the Most Recently Used Page

When you request page 6 and find out that the memory is full, the most recently used page (1) is removed and replaced with 6.

Step 4: Continue Replacing Based on MRU

At the next step, when page 5 is requested, the currently most used page in the memory is 6. Therefore, it is removed and gets replaced with 5, as per the MRU rule.

Step 5: Reuse Existing Pages

When you request page 1 again, it is not present in the memory. Therefore, the most recently used page in the memory is 5, which is then replaced by 1.

Step 6: Final Replacement

At last, when you request page 3, it is already present in the memory. Therefore, no replacement occurs this time.

Advantages of MRU

1. Good for Sequential Access: Good for workloads where recently used pages are less likely to be reused soon.

2. Simple to Implement: When compared to more complex algorithms like LRU, MRU is easier to implement because it only needs to track the page that is most recently used.

3. Faster Decision Making: Since MRU directly replaces the page that is most frequently used, it can make replacement decisions without keeping records for page usage.

Disadvantages of MRU

1. Poor for Workloads with Repeated Page Use: When recently used pages are needed again soon, MRU removes them too early, leading to more page faults.

2. Not Ideal for Real-World Applications: Unlike LRU, the MRU page replacement algorithm in OS often removes pages that are still useful. This makes it less efficient for general programs.

3. High page faults in certain scenarios: Using MRU can lead to more faults in pages if the access pattern of your memory goes on revisiting the pages that are used recently. This slows down your system.

4. Optimal Page Replacement Algorithm in OS

The Optimal page replacement algorithm in OS is basically a strategy that removes the page that will not be used for the longest amount of time in the future. This helps to minimize faults in pages. It is a highly efficient algorithm and can be used as a benchmark to compare with other algorithms like FIFO, LRU, or MRU. Although it is theoretically perfect, the Optimal page replacement algorithm is hard to implement in real-time systems. This is because it requires knowledge of future page references. 

Example: Now, let us take the same page reference string 3, 1, 2, 1, 6, 5, 1, 3. This example will help you understand why the Optimal page replacement algorithm in an OS works the best.

Step 1: Page 3 Comes First

Since the memory is empty at first, page 3 is loaded into the memory. This is a miss.

Step 2: Page 1 Comes Next

Since page 1 is not present in the memory, therefore, it is loaded onto the second frame. This is also a miss.

Step 3: Page 2 Comes Next

Now, both the frames are full. The Optimal page replacement algorithm in OS is used to check which page will be used farthest in the future. Looking ahead (1, 6, 5, 1, 3), page 3 is used farthest in the future compared to page 1. Therefore, page 3 is replaced by page 2. This is a miss as well.

Step 4: Page 1 Comes Again

As page 1 is already present in the memory, it is a hit. No replacement occurs here.

Step 5: Page 6 Comes Next

Now, the memory is fullLooking ahead to upcoming page requests, page 2 is required in the future than page 1. Therefore, page 2 is replaced. This is a miss.

Step 6: Page 5 Comes Next

Memory is full again. Based on the upcoming page requests (1, 3), page 6 will not be needed again, while page 1 will be used soon. Therefore, page 6 is replaced by page 5. This is a miss as well.

Step 7: Page 1 Comes Again

As page 1 is already in the memory, it is a hit.

Step 8: Page 3 Comes at Last

Page 3 comes at last: Memory is full. Looking ahead, neither page 1 nor page 5 will be used again. Therefore, page 5 is replaced by page 3.

Advantages of Optimal Page Replacement

1. Fewer Page Faults: This helps to replace the page that will not be used for the longest period of time, reducing the page faults.

2. Better Performance: Optimal page replacement helps to minimize access delays. This allows programs to run faster.

3. Benchmark Standard: It also works as a reference for the best page replacement performance.

Disadvantages of Optimal Page Replacement

1. Not Practical: It requires future knowledge of page references, which is usually not possible.

2. Complex to Implement: Tracking the use of future pages makes it hard to apply in real systems.

3. High Overhead: Calculating the optimal page for replacement can use a lot of extra time and resources.

5. Last In First Out (LIFO) Page Replacement Algorithm

The LIFO page replacement algorithm in OS works similarly to a stack. The page that is most recently added to the memory is the one that is to be removed when a new page requires space. It is very easy to implement because you can keep track of the last page that is loaded in your memory. But it can be inefficient because the page that is most recently may still be needed shortly. This results in more page faults.

Example: Now, let us see how the LIFO performs for the same reference string 3, 1, 2, 6, 5, 1, 3.

Step 1: Page 3

At the start, the memory is empty. The page is loaded in the first frame. The page fault occurs because the page was not present in the memory. Now the memory will look like: [3]

Step 2: Page 1

Page 1 is not present in the memory. Hence, it is added to the next frame. Another page fault occurs. Now, the memory looks like: [3,1]

Step 3: Page 2

Page 2 is also not present in the memory. Therefore, it fills the last empty frame. Again, a page fault occurs. Now the memory looks like: [3,1,2]

Step 4: Page 1: Page 1 is already present in the memory. Therefore, no replacement is required. The memory remains [3,1,2] and no page fault occurs.

Step 5: Page 6

Now, the memory seems full. According to LIFO, the page that is added most recently (2) is replaced. A page fault occurs here, and the memory becomes [3, 1, 6].

Step 6: Page 5

Now, the memory is full again. The last page that is loaded is 6 and is replaced by page 5. Now, the memory looks like [3, 1, 5]

Step 7: Page 1

Page 1 is already present in memory. Therefore, no replacement is required. The memory remains unchanged [3,1,5], and no page fault occurs.

Step 8: Page 3

Page 3 is already present in the memory. Here, no page fault occurs, and the memory stays the same.

Advantages of LIFO

1. Simple to Implement: LIFO works similarly to a stack, so it becomes easy to track the last page.

2. Fast Decisions: It also helps to identify which page you need to replace.

3. Minimal Overload: LIFO doesn’t need any complex calculations.

Disadvantages of LIFO

1. High Page Faults: LIFO may remove a page that is required soon in the future.

2. Unpredictable Performance: LIFO does not consider the patterns of actual usage of pages.

3. Not Efficient: It performs worse than FIFO or Optimal Algorithms in many cases.

6. Random Page Replacement Algorithm

The Random page replacement algorithm in OS is used to replace any page in the memory randomly when a new page is loaded. It does not follow a specific rule like FIFO or LRU. Instead, it picks up a page randomly for replacement. This randomness works well, but it can also lead to unwanted page faults.

Example: Now let us see how the Random Page Replacement Algorithm performs for the same reference string 3, 1, 2, 1, 6, 5, 1, 3.

Step 1: Page 3

In the first step, the memory is empty. Therefore, page 3 is loaded into the first frame. Therefore, a page fault occurs. The memory looks like: [3].

Step 2: Page 1

Page 1 is not present in the memory. Therefore, it is added to the next empty frame. Another page fault occurs here. The memory looks like: [3, 1].

Step 3: Page 2

Page 2 is also not present in the memory. Hence, it fills the last empty space in the frame. A page fault occurs here as well. The memory now looks like [3, 1, 2]

Step 4: Page 1

Page 1 is already present in the memory.  Therefore, no replacement is required. Memory remains the same: [3, 1, 2]

Step 5: Page 6

Since the memory is full, therefore, one page is chosen randomly so that it can be replaced (for example, page 1). It is replaced by page 6, and hence a page fault occurs. Now, the memory becomes: [3,6,2]

Step 6: Page 5

Here, memory is full again. Therefore, another page is randomly chosen for replacement (page 3). It is replaced by page 5. As a result, a page fault occurs. Now, the memory becomes: [5, 6, 2]

Step 7: Page 1

Since page 1 is now not present in the memory, it is replaced by something else randomly (for example, page 6). As a result, a page fault occurs. Now the memory becomes [5, 3, 1].

Step 8: Page 3

Page 3 is not present in the memory. Therefore, since the chosen page for replacement was already occupied, a different random page (for example, page 6) is selected. Page 3 then replaces this newly chosen page, and hence a page fault occurs. Now, the memory becomes: [5, 3, 1]

Advantages of Random Page Replacement Algorithms

1. Easy to Implement: For random page replacement algorithms, you don’t have to track usage or order of pages.

2. Low Overhead: It does not require extra data structures or calculations.

3. Performs Well: It sometimes provides you with results that are closer to more complex algorithms.

Disadvantages of Random Page Replacement Algorithms

1. Unpredictable Results: It might randomly replace a page that is required soon.

2. Higher Page Faults: Random Page replacement algorithms can also lead to poor performance.

3. Rarely Used: Random page replacement is rarely used in practice because it is unpredictable.

Comparison of Page Replacement Algorithms in OS

Given below is a comparison table for all the Page Replacement algorithms we have studied above.

Become a Job-Ready Software Engineer

Master coding, system design, and real-world projects with expert mentors. Get certified and land your dream tech job

Explore Program

Best Practices for Page Replacement in OS

1. Choose the Right Algorithm: You should always pick an algorithm that suits your workload. For example, you can use LRU for programs that consist of repeated access patterns, and you can also use Random or FIFO for simpler systems.
   
2. Keep Track of Usage: Algorithms like LRU perform better when the system accurately tracks the pages that are used recently. This helps to reduce unnecessary page faults.
   
3. Avoid Replacing Frequently Used Pages: You should not remove pages that are still actively being used. This is because it increases page faults and slows down the system.
   
4. Use Efficient Tracking Techniques: For algorithms like LRU, you should always maintain simple data structures (like counters or stacks). This helps you to track the usage without slowing the system.

Conclusion

Page replacement algorithms in the OS play an important role in managing memory efficiently and ensuring that you can execute your programs smoothly. Different algorithms like FIFO, LRU, MRU, Optimal, LIFO, and Random each have their own way of deciding which page to replace when memory gets full. Choosing the right one depends on how your program accesses data and how much memory is available. By understanding and applying these algorithms properly, you can reduce page faults and improve overall system performance.

Take your skills to the next level by enrolling in the Software Engineering Course today and gain hands-on experience. Also, prepare for job interviews with the Software Engineering Interview Questions prepared by industry experts.

Also explore our other operating system related blogs:

Page Replacement Algorithms in OS – FAQs