A Page Replacement Algorithm is a technique employed by the OS (Operating System) to manage memory by selecting which page to replace in the main memory when it becomes full. The primary goal is to minimize page faults and optimize system performance. Page fault means the page requested is not in the main memory, which results in a slower access to the secondary memory to fetch the page and load it on the main memory.
Various algorithms like FIFO (First in First out), Optimal, LRU (Least Recently Used), MRU (Most Recently Used), LFU (Least Frequently Used), MFU (Most Frequently Used), and Random are used, each with its own strategy for determining the page to evict. The choice of algorithm depends on system requirements and workload characteristics.
Of these algorithms, Optimal requires foreknowledge of the page stream and therefore is not used in practical implementations. The others use only the available data to determine which page to evict.
FIFO: The page which arrived first is replaced.
Optimal: The page with the latest next occurence is replaced.
LRU: The page with the earliest last usage is replaced.
MRU: The page with the latest last usage is replaced.
LFU: The page with the minimum number of uses is replaced. FIFO is used as tie-breaker.
MFU: The page with the maximum number of uses is replaced. FIFO is used as tie-breaker.
Random: The page to replace is selected randomly.