Page Replacement Algorithms in Operating System
In this tutorial, we will be covering the concept of Page replacement and its algorithms in the Operating system.
As studied in Demand Paging, only certain pages of a process are loaded initially into the memory. This allows us to get more processes into memory at the same time. but what happens when a process requests for more pages and no free memory is available to bring them in. Following steps can be taken to deal with this problem :
-
Put the process in the wait queue, until any other process finishes its execution thereby freeing frames.
-
Or, remove some other process completely from the memory to free frames.
-
Or, find some pages that are not being used right now, move them to the disk to get free frames. This technique is called Page replacement and is most commonly used.
In this case, if a process requests a new page and supposes there are no free frames, then the Operating system needs to decide which page to replace. The operating system must use any page replacement algorithm in order to select the victim frame. The Operating system must then write the victim frame to the disk then read the desired page into the frame and then update the page tables. And all these require double the disk access time.
-
Page replacement prevents the over-allocation of the memory by modifying the page-fault service routine.
-
To reduce the overhead of page replacement a modify bit (dirty bit) is used in order to indicate whether each page is modified.
-
This technique provides complete separation between logical memory and physical memory.
Page Replacement in OS
In Virtual Memory Management, Page Replacement Algorithms play an important role. The main objective of all the Page replacement policies is to decrease the maximum number of page faults.
Page Fault – It is basically a memory error, and it occurs when the current programs attempt to access the memory page for mapping into virtual address space, but it is unable to load into the physical memory then this is referred to as Page fault.
Basic Page Replacement Algorithm in OS
Page Replacement technique uses the following approach. If there is no free frame, then we will find the one that is not currently being used and then free it. A-frame can be freed by writing its content to swap space and then change the page table in order to indicate that the page is no longer in the memory.
-
First of all, find the location of the desired page on the disk.
-
Find a free Frame:
a) If there is a free frame, then use it.
b) If there is no free frame then make use of the page-replacement algorithm in order to select the victim frame.
c) Then after that write the victim frame to the disk and then make the changes in the page table and frame table accordingly.
-
After that read the desired page into the newly freed frame and then change the page and frame tables.
-
Restart the process.
Figure: Page Replacement
Page Replacement Algorithms in OS
This algorithm helps to decide which pages must be swapped out from the main memory in order to create a room for the incoming page. This Algorithm wants the lowest page-fault rate.
Various Page Replacement algorithms used in the Operating system are as follows;
Let us discuss all algorithms one by one in the upcoming sections:
1. FIFO Page Replacement Algorithm
It is a very simple way of Page replacement and is referred to as First in First Out. This algorithm mainly replaces the oldest page that has been present in the main memory for the longest time.
- This algorithm is implemented by keeping the track of all the pages in the queue.
-
As new pages are requested and are swapped in, they are added to the tail of a queue and the page which is at the head becomes the victim.
-
This is not an effective way of page replacement but it can be used for small systems.
Advantages
Disadvantages
-
This algorithm does not make the use of the frequency of last used time rather it just replaces the Oldest Page.
-
There is an increase in page faults as page frames increases.
-
The performance of this algorithm is the worst.
2. LIFO Page Replacement Algorithm
This Page Replacement algorithm stands for "Last In First Out".This algorithm works in a similar way to the LIFO principle.
-
In this, the newest page is replaced which is arrived at last in the primary memory
-
This algorithm makes use of the stack for monitoring all the pages.
3. LRU Page Replacement Algorithm in OS
This algorithm stands for "Least recent used" and this algorithm helps the Operating system to search those pages that are used over a short duration of time frame.
-
The page that has not been used for the longest time in the main memory will be selected for replacement.
-
This algorithm is easy to implement.
-
This algorithm makes use of the counter along with the even-page.
Advantages of LRU
-
It is an efficient technique.
-
With this algorithm, it becomes easy to identify the faulty pages that are not needed for a long time.
-
It helps in Full analysis.
Disadvantages of LRU
- It is expensive and has more complexity.
- There is a need for an additional data structure.
4. Optimal Page Replacement Algorithm
This algorithm mainly replaces the page that will not be used for the longest time in the future. The practical implementation of this algorithm is not possible.
-
Practical implementation is not possible because we cannot predict in advance those pages that will not be used for the longest time in the future.
-
This algorithm leads to less number of page faults and thus is the best-known algorithm
Also, this algorithm can be used to measure the performance of other algorithms.
Advantages of OPR
-
This algorithm is easy to use.
-
This algorithm provides excellent efficiency and is less complex.
-
For the best result, the implementation of data structures is very easy
Disadvantages of OPR
5. Random Page Replacement Algorithm
As indicated from the name this algorithm replaces the page randomly. This Algorithm can work like any other page replacement algorithm that is LIFO, FIFO, Optimal, and LRU.
