Page Replacement Algorithms in Operating System

Understanding the process of page replacement in OS is extremely important for someone who manages various types of operating systems. An Operating System that uses demand paging requires a page replacement algorithm. The procedure of calling a page from the visual memory to the primary memory is called demand paging. But what next? How will you identify which page must be eliminated in the primary memory?

Worry not!

With my years of experience in this field, I will try my best to guide you with all my knowledge. Keep reading to understand better!

What is Virtual Memory in an Operating System?

In my opinion, if you want to learn about page replacement algorithms in OS, you must first know about virtual memory. This is a secondary memory of a computer system that gives the impression to the user that there is more memory available to store data. Virtual memory can easily hold a large-sized program even though the primary memory can not hold it.

The Operating System usually avoids storing any sort of large process in the primary memory, instead, plenty of small processes are stored in primary memory. This procedure of using primary memory and virtual memory increases the consumption by the CPU and improves multi-programming. There are two main functions of virtual memory.

The first function of virtual memory is frame allocation. Whereas, the second function is page replacement. Now let's discuss and explain the page replacement algorithm to enhance your understanding.

What is Page Replacement in OS?

A visual memory that uses demand paging requires the page replacement technique when there is a page fault. When there is a requirement to replace an existing page in the main memory with a new page from the visual memory, page replacement comes in to solve this problem. 

It decides which page should be discarded so that the new demanding page can be accommodated in the primary memory. This process is also applicable for multiprogramming OSs. 

Importance of Page Replacement Algorithms

You might be wondering why page replacement algorithms are important for your computer. So, allow me to explain their importance in detail. RAM, the primary memory of a computer does not have an extended memory like the visual memory therefore page faults often occur. In such a scenario the Operating system changes the old page with the new page with the assistance of the page replacement algorithm.

The page replacement algorithm also decides which page should be replaced with the new page and reduces the rate of page faults.

Different Types of Page Replacement Algorithms

Optimal Page Replacement Algorithm

The optimal page replacement algorithm in OS has one of the lowest number of page faults. In this algorithm, the unused pages that have not been used for the longest periods are replaced with new pages. In this manner, almost all unused pages get replaced with time in the future.

Here are some optimal page replacement algorithms in OS examples you can study to get a better comprehension:

Let’s consider the page reference string as 7,0,1,2,0,3,0 with a main memory of three slots. Now I will help you calculate the number of page faults with the help of a table:

Explanation: Here I have vividly explained the mentioned optimal page replacement algorithm example:

• Step 1: A digit i.e. 7 was entered in a blank memory frame and therefore it was a page miss.
  

• Step 2: Then 0 was inserted. As the table was not full hence it was a page miss.
  

• Step 3: Then 1 was inserted and again it was a page miss because it was not similar to the digits in the memory. 
  

• Step 4: In this step, 2 replaces 7 as the memory was full and would not be of any use in the future. Again it is a miss.
  

• Step 5: The next 0 was not included as it already existed in the memory. Therefore, it is a page-hit.
  

• Step 6: In the next step, 3 replaced 1 as it would not be required in the future. Again this was a page miss or page fault. 
  

• Step 7: In the last step a 0 was there which already existed in the algorithm. Hence, it was a page-hit. 

Advantages of Optimal Page Replacement Algorithm

• Guaranteed use of optimal memory
• Extremely efficient algorithm
• Easy comprehension with no complexity
• Implementation does not require any complicated data structure

Disadvantages of Optimal Page Replacement Algorithm

• Unreliable as it requires accurate data from the future reference pages
• Economically unreliable
• Extremely rigid so can not adapt to the new pattern requirements
• Requires a lot of time
  

First In First Out Replacement Algorithm

The next important page replacement algorithm is FIFO (First In First Out). In this algorithm, the oldest page is placed at the front end of the frame, whereas the latest page is placed at the back end or rear end. When there is any page fault the oldest page is removed from the front end and a new memory gets inserted at the back end. 

Here’s an example:

Suppose the string variable to be 2,3,5,2,8,9,4,5 in five-page frames. Here are the tables below:

Explanation: Here is the complete explanation of the example of the FIFO algorithm:

• Step 1: In the first step 2 was added and it was a page miss.
  

• Step 2: In the next two steps 3 and 5 were added. Again these were a miss since the frame was not filled.
  

• Step 3: In the next step was a page-hit as the digit 2 already existed in the frame.
  

• Step 4: In the next two steps, 8 and 9 were added. These steps were considered page misses because in the first instance, the frame was not completed and in the second instance the digit did not exist in the frame.
  

• Step 5: In the last step was a page-hit as 5 already existed in the page frame.

Advantages of  First Out Replacement Algorithm

• Extremely comprehensive
• Reduces the rate of unnecessary overhead
• Non-tedious implementation

Disadvantages of  First Out Replacement Algorithm

• The performance rate is not up to the mark
• May face Belady’s anomaly
  

Least Recently Used (LRU) Page Replacement Algorithm

The Least Recently Used (LRU) page replacement algorithm is the last page replacement in OS. According to this algorithm, a page that has been frequently used will be used in the future as well. Therefore, this algorithm replaces the new page in demand with an old page that has not been used for the longest period.

Let's say that the string variable is 7,0,1,2,0,3,0,4,2 in a 4-frame page.

Explanation: Here is the explanation of the above table:

• Step 1: 7 was inserted and it was a page miss as the page frame was empty.
  

• Step 2: 0,1, and 2 were inserted and those were a page miss as they did not exist in the main memory. 
  

• Step 3: In the next step 0 was interested and it was a page-hit as 0 already existed in the memory. 
  

• Step 4: In the next step 3 was added and it replaced 7 as there is no space on the in page. 
  

• Step 5: Again 0 was inserted and it was a page-hit as 0 already existed in the memory. 
  

• Step 6: In the next step 4 was added and it replaced 1 as it was the least used number.
  

• Step 7: Lastly, 2 was inserted and it was a page-hit as 2 already existed in the page memory.

Advantages of Least Recently Used (LRU) Page Replacement Algorithm

• A full analysis is possible in this algorithm
• This is the most efficient page replacement algorithm in OS

Disadvantages of Least Recently Used (LRU) Page Replacement Algorithm

• Extremely complicated than other replacement algorithms
• Implementation of this algorithm requires extra structure
• Help from hardware is always needed
  

Conclusion

As I have stated, different types of page replacement algorithms come with their advantages and disadvantages. The choice is up to you and your requirements.

If you are willing to commence a career in this field I would recommend you to pursue some online courses like the ones upGrad offers. These well-executed courses will not only enhance your knowledge but also expand your skills.

Frequently Asked Questions

1. What are page replacement algorithms in OS?

Page replacement in OS is a procedure where a page from the secondary memory is replaced with a page from the primary memory when any page fault occurs.

2. What is the best algorithm for page replacement?

The best algorithm for page replacement is the Optimal page replacement algorithm. This is because it has the minimum amount of page faults.

3. What is the FIFO algorithm in OS?

The first come first out (FIFO) algorithm in OS replaces the oldest page at the front end with the latest page in demand.

4. Which page replacement algorithm is used in Mac OS?

The page replacement algorithm used by Mac OS is the First come first out (FIFO) algorithm. 

5. What is page replacement and its types?

Page replacement in OS is a procedure where a page from the secondary memory is replaced with a page from the primary memory. There are three types of page replacement: Optimal Page Replacement, First in first out (FIFO) Page Replacement, and Least Recently Used (LRU) Page Replacement.

6. Why is the page replacement algorithm used?

The page replacement algorithm in OS is mainly used to decrease the frequency of page faults.

7. What is the least page replacement algorithm?

Least Recently Used (LRU) page replacement is the least used page replacement algorithm in OS.

8. What are the basic steps of page replacement?

Swapping is the basic step that is used in a page replacement algorithm.