Analysis of Various Page Replacement Algorithms in Operating System

Bhagyashree A. Tingare, Vaishali L. Kolhe

Abstract: Page replacement algorithms were a warm topic of research and debate in the 1960s and 1970s. In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault occurs and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages i lower than some threshold. The page replacing problem is a typical online problem from the competitive analysis perspective in the sense that the optimal deterministic algorithm is known. This paper is analysis on various page replacement algorithms like Optimal replacement, Random replacement, Not Recently Used (NRU), First-In, First-Out (FIFO), Least Recently Used (LRU), Second Change and CLOCK, Not Frequently Used (NFU), and some approaches like Aging, Two Queue (2Q), SEQ, Adaptive Replacement Cache (ARC), CLOCK with Adaptive Replacement (CAR), CAR with Temporal filtering (CART), Token-ordered LRU, CLOCK-Pro.

Keywords: Optimal replacement, Random replacement, NRU, Aging, ARC, CART, Tokenordered LRU