Page Replacement Algorithms

Suppose a process faults on a valid page, but physical memory has no free frames. To load the needed page, the operating system must reclaim a frame currently used by another page.

That creates a policy decision:

Which resident page should lose its frame?

The selected page is the victim page. If its contents can be discarded or safely preserved, the kernel reuses its frame for the incoming page.

Choosing poorly can evict a page that the workload needs again immediately, causing another fault. Choosing well can remove a page that will not be used for a long time.

Page replacement algorithms define how the operating system makes this victim choice.

No algorithm can create more physical memory. The purpose of replacement is to use the available frames in a way that minimizes expensive future faults and write-back work while preserving fairness and acceptable overhead.

This chapter compares FIFO, Optimal, LRU, Clock, and enhanced Clock replacement, explains reference and dirty bits, Belady's anomaly, local and global policies, and why production kernels approximate recency.