Offline (Page Replacements)

From Algorithm Wiki
Jump to navigation Jump to search


When page fault occurs during the program execution, operating systems use page replacement algorithms to select a victim page from primary memory and makes room for the required page.

Related Problems

Related: Online


$n$: number of page requests

$k$: number of pages able to fit in cache

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
The theoretically optimal page replacement algorithm 1940 $O(n^{2})$ $O(k)$ Exact Deterministic

Time Complexity Graph

Page Replacements - Offline - Time.png