A process faults on a valid page, but physical memory has no free frame. To make the requested page resident, the operating system must reclaim a frame currently holding some other 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.

Textbook replacement problems use a deliberately small model:

The sequence of page numbers is called a reference string.

For example:

The numbers represent virtual pages, not byte addresses. Repeated references to addresses within the same page appear as the same page number.

Assume three frames begin empty:

The first references to pages 7, 0, and 1 each fault and fill a free frame:

The next reference is page 2. All frames are occupied, so the replacement algorithm must choose among pages 7, 0, and 1.

Different algorithms make different choices because they use different information about the past or assumed future.

The simplest evaluation metric is the number of page faults for a given reference string and frame count:

Fewer faults are generally better, but production replacement has additional costs.

A dirty victim contains changes that do not exist in its backing store. The kernel must preserve those contents before reusing the frame. A clean page whose contents can be reconstructed may be discarded without a write.

The kernel also spends CPU time finding victims and maintaining policy metadata. An algorithm that requires an expensive update on every memory access can cost more than its improved decisions save.

A practical policy therefore balances:

Textbook traces usually count faults and assume every replacement has equal cost. That simplified model is the right starting point, but it is not the complete kernel problem.

First-In, First-Out, or FIFO, evicts the page that has been resident for the longest time.

The operating system maintains a queue:

FIFO evicts from the front, so page 7 goes first purely because it arrived first.

On a fault:

A hit does not change the FIFO order. The algorithm tracks arrival time, not recent use.

Use three frames and the reference string:

The full trace is:

FIFO produces:

Its strength is simplicity. Queue updates occur only when pages enter or leave, so no work is required on every hit.

Its weakness is that age in memory does not predict future usefulness. A heavily used page can be the oldest resident page. FIFO evicts it even if it was accessed one instruction ago.

The Optimal algorithm, also called OPT or MIN, chooses the resident page whose next reference occurs farthest in the future.

If a resident page never appears again, it is the best victim because evicting it cannot cause another fault in the reference string.

On a fault with resident pages 7, 0, and 1, examine the remaining references:

Page 0 is needed immediately. Pages 7 and 1 are never needed again. OPT can evict either 7 or 1.

The rule is:

For the complete example with three frames, OPT produces:

No other algorithm can produce fewer faults for the same fixed reference string and frame count. If another algorithm did, OPT's chosen victim would not have been optimal.

The problem is that a real operating system does not know the exact future reference string. It cannot know which page a process will access ten milliseconds from now.

OPT is therefore not an implementable online policy for general workloads. It is a benchmark:

It also teaches the central replacement principle: the ideal victim is the page whose absence will hurt latest, or never at all.

Least Recently Used, or LRU, replaces the page whose most recent access occurred farthest in the past.

LRU relies on temporal locality:

A page used recently is more likely to be used again soon than a page that has not been used for a long time.

Maintain pages from least to most recently used:

The order looks the same as the FIFO queue, but it is maintained by access rather than by arrival. Touching page 7 would move it to the other end.

Every reference moves its page to the most-recent end. On a fault, evict the page at the least-recent end.

For the example:

Continuing through the full reference string gives:

LRU outperforms FIFO for this sequence because hits refresh a page's recency. FIFO ignores those hits.

Exact LRU is expensive to implement at operating-system scale. Two classical representations illustrate the cost.

Timestamp implementation

Record a counter or timestamp on every page reference. To choose a victim, find the smallest timestamp.

Recency-list implementation

Maintain all resident pages in exact recency order. Every reference moves one page to the most-recent end.

Applications execute enormous numbers of memory references. Trapping into the kernel or updating a global software structure on every one would be impractical.

Real systems therefore approximate LRU using hardware-provided access information and periodic or fault-driven kernel work.

Hardware can help the operating system approximate page usage.

A page-table entry commonly exposes two useful status concepts:

Conceptually:

The kernel can clear reference bits and later inspect which pages hardware marked again. That provides a sampled view:

This does not reveal the exact order of every access. It distinguishes recent from not recently observed at a coarser granularity.

The dirty bit affects replacement cost. A clean page can often be discarded and reconstructed from its file or other known backing. A dirty page must be written to a safe backing location before its frame can be reused, unless the contents are no longer needed.

An ideal victim is therefore not determined by recency alone. Among similarly cold pages, a clean page can be much cheaper to reclaim than a dirty one.

The Clock algorithm, also called Second Chance, arranges candidate frames in a circle. A clock hand points to the next candidate.

Each frame has a reference bit:

When a page is accessed, its reference bit becomes 1.

On replacement, the algorithm examines the frame under the hand:

A page with R = 1 receives a second chance. If it is referenced again before the hand returns, hardware sets the bit back to 1, and it receives another chance.

Assume empty frames are filled starting at frame 0 and the hand advances after every insertion. For the same three-frame reference string, this Clock variant produces:

That happens to match exact LRU for this sequence, but Clock and LRU are not equivalent. Clock sees a one-bit recency sample rather than the precise access order.

Clock has attractive implementation properties:

The scan can examine many frames when most reference bits are set. Clearing those bits turns the scan into a new observation period, so a later pass can distinguish pages not referenced again.

A replacement policy can combine recency with write-back cost.

Using reference bit R and dirty bit D, pages fall into four classes:

An enhanced Clock scan prefers unreferenced clean pages. It can clear reference bits as it scans and arrange dirty-page write-back so some candidates become clean before memory is urgently needed.

The ordering is a policy preference, not an absolute rule. A very hot clean page may be worse to evict than a long-idle dirty page. Production kernels combine multiple signals and often perform write-back in the background.

The important addition is:

Counting only future page faults treats clean and dirty victims as equally expensive when they are not.

It seems intuitive that giving a process more frames should never increase its page faults. FIFO can violate that expectation.

This behavior is Belady's anomaly.

Use the reference string:

With three frames, FIFO outcomes are:

The frame states after each reference are:

With four frames:

The frame states are:

Adding a fourth frame changes FIFO's arrival order and later victims. The larger resident set does not always contain everything that the three-frame execution would contain at the same point, so it can follow a worse path.

Belady's anomaly does not mean more memory is generally harmful. It means FIFO lacks a structural property that guarantees monotonic improvement for every reference string.

A replacement algorithm has the stack property if, at every point in a reference string:

The name comes from imagining pages in an ordered stack of preference. Increasing capacity includes one more page without changing which higher-ranked pages remain included.

LRU has the stack property. The N most recently used pages are always a subset of the N + 1 most recently used pages.

OPT also has the stack property under its future-use ordering.

Consequently:

LRU and OPT cannot exhibit Belady's anomaly.

FIFO is not a stack algorithm. Its resident pages depend on the arrival and eviction history for that particular capacity, which is why the three-frame and four-frame sets can diverge.

Clock approximates recency but does not inherit every formal guarantee of exact LRU.

For the original reference string with three frames:

The verified results are:

This single sequence does not prove that Clock always matches LRU or that FIFO is always worse. Algorithm performance depends on the reference string.

The general lessons are:

No replacement policy dominates every other practical policy for every workload once tracking cost, dirty pages, fairness, and latency are included.

Victim selection also needs a scope.

With local replacement, a faulting process selects a victim only from frames assigned to that process.

This provides isolation. Process B's memory behavior cannot directly take all of A's frames through one replacement decision. The drawback is that A can fault heavily while B retains frames it is barely using.

With global replacement, the kernel selects from a system-wide or broader pool:

Global replacement can use physical memory more flexibly. Cold pages from an idle process can give way to active pages from a busy process.

The risk is interference. One process that rapidly grows its resident demand can cause faults in unrelated services by displacing their pages.

Practical systems combine global resource management with boundaries such as process policies, memory-control groups, priorities, or protected minimums. The choice is not merely one FIFO or LRU queue for the whole machine.

Replacement chooses among reclaimable frames, not every frame in the machine.

Some memory may be:

The kernel must also understand the page's backing.

A textbook algorithm that selects page number 7 assumes page 7 can be evicted immediately. A real kernel may skip a theoretically cold page because reclaiming it is unsafe or currently too expensive.

The simple model waits until a page fault needs a frame and then chooses a victim synchronously.

Real systems often maintain a supply of free or readily reusable frames in advance. Background reclaim can scan candidates, discard clean pages, and begin writing dirty pages before memory becomes completely exhausted.

This moves some work away from the faulting thread and gives write-back time to complete before a frame is urgently required.

If memory demand rises faster than background reclaim can respond, the faulting or allocating thread may need to participate directly in reclaim and wait longer.

Page replacement is therefore both:

The textbook algorithms isolate the victim-choice logic so it can be reasoned about clearly.

Exact LRU would require a precise global order for vast numbers of page references occurring concurrently on many CPUs.

Updating that order on every instruction fetch, load, and store would create unacceptable synchronization and cache-coherence traffic. Hardware reference bits provide cheaper observations, but they expose coarse evidence rather than a perfect timeline.

Production policies therefore use techniques such as:

Exact structures and policies vary by operating system and evolve over time. They are best understood as approximations to questions such as:

The classical algorithms provide the vocabulary and correctness baseline. Kernel policies adapt those ideas to hardware constraints and real workloads.

When evaluating a replacement trace, keep the method disciplined:

For FIFO, maintain arrival order separately from visual frame positions. Replacing frame 0 does not imply frame 0 is always the oldest.

For LRU, update recency on hits as well as faults. Forgetting hit updates accidentally turns the algorithm into something closer to FIFO.

For Optimal, inspect only future references after the current position. Past use is irrelevant to its choice.

For Clock, state the initial hand position and whether the hand advances after insertion. Small convention differences can change a trace, so the algorithm variant must be explicit.

In a production analysis, add questions that the simple trace omits:

Page replacement is required when a page needs to become resident and no suitable free frame is available. The operating system selects a victim, preserves dirty contents when necessary, removes the old translation, and reuses the frame.

FIFO replaces the oldest arrival and is simple but can exhibit Belady's anomaly. Optimal replaces the page needed farthest in the future and establishes the theoretical minimum fault count, but requires impossible future knowledge. LRU uses recent history as a locality predictor but is expensive to track exactly. Clock approximates LRU with reference bits and a circular second-chance scan.

Real replacement also considers dirty-page write-back, reclaim eligibility, local versus global scope, fairness, and scanning overhead. Classical algorithms isolate the core decision, while production kernels approximate recency and reclaim pages continuously under real hardware and workload constraints.