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 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.
Paging concept was developed to overcome issues in memory partitioning and to provide flexible options to optimally utilize memory while serving multiple users environments.
In this article let us understand about memory pages, virtual memory, demand paging and the way pages in main memory are getting refreshed from virtual memory residing in 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 the all pages of a process for execution is made available in any of the frames and priority is given to fit them in a contiguously available frames for better performance. Pages of the process which goes into hibernation are removed from the main memory and pages of new process waiting in queue will be loaded.
OS maintains the page table by mapping logical address of all the processes with the physical address of the memory where they are stored. This Page table enables OS to get the physical address of any page of any process and access its contents stored in the memory and executes 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 size of the main memory, is created in secondary storage and made available to the users as the main memory to them virtually.
4.6 (3,144 ratings)
View Course
All the processes including the big sized process will be initially moved to the virtual memory instead of 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 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 page is 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 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 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 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 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 a replaced page is immediately sought by CPU it will result 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 less 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 in the bottom in the queue, will be removed to pave way for new one.
This method has a lacuna with a possibility of more page faults. There is a high degree of possibility that page which came first may be required in the immediate future and removing that will result in duplication of efforts.
2. Optimal Page Replacement
Page which will not be referred in the future by CPU will be removed to give way for 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 frequently will continue to be used in the future also and vice versa. It is an effective algorithm over all, since it was proved that it has 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 –
