Page replacements

Problem Description

In an operating system that uses paging for memory management, a page replacement algorithm is needed to decide which page needs to be replaced when new page comes in.

Page Fault – A page fault happens when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory.

Since actual physical memory is much smaller than virtual memory, page faults happen. In case of page fault, Operating System might have to replace one of the existing pages with the newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to reduce the number of page faults.

Bounds Chart

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic	[ The theoretically optimal page replacement algorithm (1940)] [ Not recently used (1940)] [ First-in, first-out (1940)] [ Second-chance (1940)] [ Clock (1940)] [ Least recently used (1940)] [ Not frequently used (NFU) (1940)] [ Aging (1940)] [ Longest distance first (LDF) page replacement algorithm (2017)]
nlogn
Linear	[ Random (1940)]
logn