Updated April 1, 2023
Introduction to Page Replacement Algorithms
Random Access Memory (RAM), or Main memory in the computer, was a precious resource during the pre-digital era and the memory management function played an important role in effectively managing the multi-user environment with the available memory.
In the earlier versions of computers, multiple processes were loaded into fixed partitions of memory, and it was allowed to run. It had internal and external fragmentation issues. Dynamic partition resolved internal fragmentation and external fragmentation issues persisted, and it was overcome by adopting Compaction. This process had alleviated the issues but got into performance glitches.
The paging concept was developed to overcome memory partitioning issues and provide flexible options to utilize memory while serving multiple users environments optimally.
In this article, let us understand memory pages, virtual memory, demand paging, and how pages in main memory are getting refreshed from virtual memory residing in the hard disk.
What is a Memory Page?
Processes are divided into pages of manageable size, say 1MB or 2MB, and the main memory of the computer is divided into frames of the same size, and any page of any process will fit into any frames. OS ensures all pages of a process for execution are made available in any frames, and priority is given to fit them in a contiguously available frame for better performance. Pages of the process which goes into hibernation are removed from the main memory, and pages of the new process waiting in the queue will be loaded.
OS maintains the page table by mapping the logical address of all the processes with the memory’s physical address. This Page table enables OS to get the physical address of any page of any process, access its contents stored in the memory, and execute it. Pages facilitate utilization of the main memory optimally as well as the execution of multiple processes efficiently.
What is Virtual Memory?
There is always a need to augment main memory in order to execute processes of sizes bigger than memory and handle more processes simultaneously. A huge sized memory, multiple times the main memory size, is created in secondary storage and made available to the users as the main memory to them virtually.
All the processes, including the big sized process, will be initially moved to the virtual memory instead of the main memory as in the earlier version of Memory management. OS will load only the needed pages into the main memory, and this method improves the ability of OS to manage more processes and performance of the CPU.
- Demand Paging: OS loads only the needed portion of the processes (few pages) in the main memory at any given time. It is difficult to decide which pages should be made available in memory and when it is required?. Demand paging functionality of OS handles this situation by loading all the pages of all the processes in the virtual memory first and supplies any pages of any processes to the memory whenever it is demanded.
- Page Fault: CPU executes instructions of a process, page after page, as found in the main memory and in its flow; if any of the pages are not available in the main memory, it raises an alert to OS to fetch the required page from virtual memory in secondary storage. This alert is known as a page fault.
Page Replacement Algorithm
Whenever CPU raises a page fault, OS does not immediately bring the required page from the virtual space. If there is a free frame (main memory page) available, OS will fill it with a new page brought from Virtual memory; otherwise, it has to clear a frame (after backing it up into virtual memory) to accommodate the new page. Any page cannot be removed randomly, and there should be some logic or algorithm in replacing the pages in the memory.
Importance of Page Replacement Algorithm
Page replacement algorithm handles two major aspects viz.,
- No of frames to be allotted for each process
- Logic to decide upon which frame should be replaced
If the initial frame is the allocation is insufficient, it may result in thrashing. There will be more page faults as most of the pages reside in virtual memory, and excess frame allocation will result in internal fragmentation. Hence no of the frames allocated should be accurate for optimal performance.
Similarly, if the right algorithm is not chosen, it will result in too many page fault that will impact the performance. If the CPU immediately seeks a replaced page, it will result in unwanted swap out, swap in and OS will be doing unwanted work and degrade the performance. It’s important to choose the right algorithm that will result in a fewer page fault.
Types of Page Replacement Algorithms
There are different algorithms available, and each one has its own methods to decide on the pages to be replaced.
1. First in First Out (FIFO)
This method is the simplest of all the logics in which the system maintains the order of page loading from virtual to main memory in a queue. Whenever page fault occurs, the page that came first, residing at the bottom in the queue, will be removed to pave the way for a new one.
This method has a lacuna with a possibility of more page faults. There is a high degree of possibility that the page that came first may be required in the immediate future, and removing that will duplicate efforts.
2. Optimal Page Replacement
The page that will not be referred to in the future by CPU will be removed to give a new one. This method is not practically possible to adopt, and it may be used as a benchmark for evaluating the veracity of other methods.
3. Least Recently Used
Pages referred infrequently or not referred in the recent past will be replaced with new ones. It is effective in that it looks for the past activities and decide the page to be removed. This is based on a probability theory that a page referred to frequently will continue to be used in the future also and vice versa. It is an effective algorithm overall since it was proved that it has the least page faults.
Recommended Articles
This is a guide to Page Replacement Algorithms. Here we also discuss the Introduction and importance of page replacement algorithm along with different types. You may also have a look at the following articles to learn more –
