Page Replacement Algorithms in Operating System
Page Replacement Algorithm tells which page is to be replaced.This article covers different page replacement algorithms.If you want to learn it with examples then read this article.
In data processing, page replacement is a technique that helps to reduce the time required to access and update data. This can be achieved by replacing pages in a database as they become outdated or no longer needed. Page replacement algorithms vary in how they choose which pages to replace, but all seek to achieve the same goal: more rapid access to updated information. There are two main types of page replacement algorithms: first in, first out (FIFO), and least recently used (LRU). The operating system is responsible for doing page replacement algorithms.
Must Check: History of Operating Systems
Table of contents
- What is a page replacement algorithm?
- Why is a page replacement algorithm needed?
- Belady’s Anamoly in page replacement algorithm
- Types of Page Replacement Algorithm
Best-suited Operating Systems courses for you
Learn Operating Systems with these high-rated online courses
What is a page replacement algorithm?
A page replacement algorithm is a systems management tool that helps optimize and manage the web server. It helps eliminate the need to restart the web server after large updates or changes to the web pages. A page replacement algorithm usually erases old pages and creates new ones with new information.
Also explore: What is Operating Systems (OS) – Types, Functions, and Examples
Also explore: Operating system interview questions
Why is a page replacement algorithm needed?
Actual RAM is much smaller than virtual memory. So it is not possible to keep all the data in RAM, So it is needed to load the pages when required(demand paging). If the page is found in RAM, then good otherwise, page faults will occur. Therefore, when a page fault occurs, the operating system must replace the existing page in RAM with the newly requested page. In this scenario, the page replacement algorithm helps the operating system determine which page to replace.
Belady’s Anamoly in page replacement algorithm
The percentage of page faults depends directly on the number of frames allocated to each process. Increasing the number of frames will significantly reduce the number of page faults. However, the opposite action can occur as the number of frames increases and the page faults increase. This exception is known as Balady’s anomaly. Optimal and LRU are the two mainly used page replacement algorithms, but Balady’s anomaly does not occur with these algorithms in the reference string because they belong to a class of stack-based page replacement algorithms.
Types of Page Replacement Algorithm
1. First in, first out (FIFO)
A first in, first out (FIFO) Page Replacement Algorithm assigns pages sequentially according to the order in which they were accessed most recently. The algorithm looks for the latest accessed page and then assigns the next page in the sequence to that location.
If a page is not found, the algorithm will search for the page with the oldest access time and assign it to the location. Pages are never reassigned to a location if they have already been assigned to that location by another algorithm.
Consider the page reference string as 7,1,0,2,0,3,0,4,2,1,0 with 4-page frames. Let’s try to find the total number of page faults:
- Initially, all slots are empty, so 4-page faults will occur on adding 7,1,0,2 in the starting.
Page faults = 4(Hit)
- When page 0 comes, it is in the memory, so no page fault occurs.
Page faults = 5
- When page 3 comes, it is not present, and you get a page fault. There are no empty slots, so delete page 7 (the pages will be replaced according to their insertion time in the queue.)First, page 7 was replaced as it was inserted first in the queue.
Page faults = 5(Hit)
- When page 0 comes, it is in the memory, so no page fault occurs.
Page faults = 6
- When page 4 comes, it is not present, and you get a page fault. There are no empty slots, so delete page 1 (the pages will be replaced according to their insertion time in the queue.)First, page 7 was replaced before as it was inserted first in the queue. But this time, page 1 will be replaced as it was inserted after page 7.
Page faults = 6(Hit)
- When page 0 comes, it is present; hence, no page fault occurs.
Page faults = 7
- When page 1 comes, It doesn’t exist, and you get a page fault. There are no empty slots, so delete Page 0 is removed as it was inserted after page 1.
Page faults = 8
- When page 0 comes, it is again not found in memory, a page fault occurs, and page 2 is removed as it was inserted after page 0 in the queue.
Total page faults = 8
2. Least recently used (LRU)
The least recently used (LRU) Page Replacement Algorithm assigns pages sequentially according to the order in which they were accessed least recently. The algorithm works by first looking for the least recently used page and then assigning the next page in the sequence to that location.Consider the page reference string as 7,1,0,2,0,3,0,4,2,1,0 with 4-page frames. Let’s try to find the total number of page faults:
- Initially, since all the slots are empty, pages 7,1,0,2 cause a page fault and take the empty slots. So 4-page faults will be there.
Page faults = 4(Hit)
- When page 0 comes, it is in the memory, so no page fault occurs.
Page faults = 5
- When page 3 comes, it is not in the memory, so a page fault occurs and the least recently used page 7 is removed.
Page faults = 5(Hit)
When page 0 comes, it is in memory so that no page fault will be there.
Page faults = 6
- When page 4 comes, it is not in the memory; hence, page 0 is removed according to the LRU.
Page faults = 6(Hit)
- When page 2 comes, it is in memory so that no page fault will be there.
Page faults = 7
- When page 1 comes, it is not in the memory; hence, page 3 is removed according to the LRU.
Page faults = 7(Hit)
- When page 0 comes, it is in memory, so no page fault will be there.
Total page faults = 7
3. LIFO Page Replacement Algorithm
This page replacement algorithm stands for “last in, first out.” This algorithm works in the same way as the LIFO principle. This replaces the latest page that last arrived in primary storage. This algorithm uses the stack to monitor every page.
Consider the page reference string as 7,1,0,2,0,3,0,4,2,1,0 with 4-page frames. Let’s try to find the number of page faults:
- Initially, since all the slots are empty, pages 7,1,0,2 cause a page fault and take the empty slots. So 4-page faults will be there.
Page faults = 4(Hit)
- When page 0 comes, it is in the memory, so no page fault occurs.
Page faults = 5
- When page 3 comes, it is not in the memory, so a page fault occurs, and the last inserted page, i.e., page 2, is removed.
Page faults = 5(Hit)
When page 0 comes, it is in memory so that no page fault will be there.
Page faults = 6
- When page 4 comes, it is not in the memory; hence, page 3 is replaced by page 4 as it was the last inserted page.
Page faults = 7
- When page 2 comes, it is not in memory, so the last inserted page, i.e., page 2, will be removed and replaced by page 2.
Page faults = 7(Hit)
- When page 1 comes, it is there in memory. So there is no page fault.
Page faults = 7(Hit)
- When page 0 comes, it is in memory, so no page fault will be there.
Total page faults=7
4. Optimal Page Replacement Algorithm
The best page replacement algorithm is the best page replacement algorithm because it has the fewest page faults. This algorithm replaces the pages that would not be used for the longest time in the future. It will replace the most referenced in-memory page in the future.
Consider the page reference string as 7,1,0,2,0,3,0,4,2,1,0 with 4-page frames. Let’s try to find the number of page faults:
- Initially, since all the slots are empty, pages 7,1,0,2 cause a page fault and take the empty slots. So 4-page faults will be there.
Page faults = 4(Hit)
- When page 0 comes, it is in the memory, so no page fault occurs.
Page faults = 5
- When page 3 comes, it is not in the memory, so a page fault occurs, and the least recently used page 7 is removed as it will not be used for the longest time in the future.
Page faults = 5(Hit)
When page 0 comes, it is in memory, so no page fault will be there.
Page faults = 6
- When page 4 comes, it is not in the memory; hence, page 3 is removed as it will not be used for the longest time in the future.
Page faults = 6(Hit)
- When page 2 comes, it is in memory, so no page fault will be there.
Page faults = 6(Hit)
- When page 1 comes, it is in memory so no page fault will be there.
Page faults = 6(Hit)
- When page 0 comes, it is in memory so no page fault will be there.
Total Page faults=6
Optimal page replacement algorithm have the lowest number of page faults.
Conclusion
The page replacement algorithm is an important task in the operating system to free up disk space and manage files. By default, the operating system performs a page replacement algorithm at four pages per minute. If the system requires more pages to be replaced, then the operating system increases the rate of page replacement. If you liked the article, then please share and like it.
Keep Learning!!!
Keep sharing!!!
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
