Online (Page Replacements)

Description

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: Offline

Parameters

$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
Not recently used	1940	$O(nk)$?	$O(k)$	Exact	Deterministic
First-in, first-out	1940	$O(nk)$?	$O(k)$	Exact	Deterministic
Second-chance	1940	$O(nk)$?	$O(k)$	Exact	Deterministic
Clock	1940	$O(nk)$?	$O(k)$	Exact	Deterministic
Least recently used	1940	$O(nk)$?	$O(k)$	Exact	Deterministic
Random	1940	$O(n)$	$O(k)$?	Exact	Randomized
Not frequently used (NFU)	1940	$O(nk)$?	$O(k)$	Exact	Deterministic
Aging	1940	$O(nk)$?	$O(k)$	Exact	Deterministic
Longest distance first (LDF) page replacement algorithm	2017	$O(nk)$?	$O(k)$	Exact	Deterministic	Time

Time Complexity Graph