When the frames assigned to a single process are occupied altogether and the CPU wants to load another page into main memory then according to the Page replacement Algorithm, Operating System finds out the victim frame(frame in which page is replaced) and the new incoming page is replaced in victim frame.
Range:
- In this article, we will discuss important page replacement algorithms and their conceptualization.
- Along with this, we will also discuss how it will work with respective examples to get more insights about algorithms.
Types of Page Replacement Algorithms:
1. First In First Out Algorithm :
This is the most basic and easy-to-implement page replacement algorithm in os which is known as “First In First Out”. As per the name of the algorithm we can say that Queue is the underlying data structure for this implementation. In this algorithm when the CPU asks for any page which results in page fault then it will consider the victim frame based on the FIFO principle.
For eg. Let's say [7, 0, 1, 2, 0, 3] is a reference string from the CPU and 3 frames are allocated for this process. In this case, the Operating System serves page faults for the first 3 pages as they are getting loaded for the first time in the main memory. Now for the 4th page with page number 2 all the frames are occupied so the operating system will select the 1st page with page number 7 as the victim page as this came first in memory so it will get replaced first in the main memory. This is how the FIFO page replacement algorithm in os works.
2. Optimal Page Replacement Algorithm :
If we consider the best scenario the pages which are going to be replaced are either never to be demanded in the future or it has a maximum number of page requests to be served before its demand in the future this algorithm is known as “Optimal Page Replacement Algorithm.” This algorithm will assure the lowest possible page fault rate for a fixed number
of frames. This algorithm is difficult to implement as compared to other page replacement algorithms in os due to it being a feature of tracking future knowledge of reference strings.
For eg. Suppose [7,0,1,2,0,3,2,7,4,1,6,5] is a reference string from the CPU and let's assume we have 3 frames for this process. By default, by serving page faults the first 3 pages are filled in empty frames. Now for the 4th reference with page number 2 the algorithm looks for previous pages for its next references. In this case page numbers, 0,7, and 1 will get page requests in the future at reference 5th,8th and 10th reference respectively. So we can see page number 1 will get served after the max number of page requests so replace that with page number 2. That's how the Optimal page replacement algorithm in os works.
3. LRU page replacement :
There is a key distinction between FIFO and Optimal page replacement algorithms in os where FIFO keeps track of the time when a page is brought into the main memory and the Optimal page replacement algorithm keeps track of future references. In the “Least Recently Used Page Replacement algorithm” we can use past references as a short future estimation. In this case, the os will replace the page which has not been used in the past over the longest period of time.
For eg. Let's assume [4,1,2,1,2,4,5,0,4] is a reference string from the CPU and we have 3 frames for the process. By default, the first 3 pages are loaded into an empty frame by serving page faults. Then from the 4th to 6th reference, we have pages loaded into main memory so it can be said as page hits. Now for the 7th reference with page number 5, it will take a look in the past and 1 is the least recently used page in the past so the operating system selects the frame with page 1 as the victim frame and applies a replacement algorithm over it. That's how the LRU replacement algorithm works.
Summary:
- Page replacement algorithms are simple techniques used by the operating system to minimize the page fault rate and maximize the CPU utilization by keeping necessary pages in the main memory.
- First In First Out page replacement algorithm is simple and easy to implement and uses queue as the underlying data structure.
- The optimal Page replacement algorithm looks for pages to replace which will be referenced after the maximum number of page requests.
- LRU page replacement algorithm is as its name suggests replaces the page which has not been used in the past for the longest duration of time.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Author Bio:
Author Bio:
Akash Pawar is a software engineer and has a passion to write technical blogs with expertise in Data Structures and Algorithms, Operating systems and has exposure to large-scale System Designs.
