Second Chance — Page Replacement

Overview

What this concept solves

Second Chance is the smallest possible fix to FIFO's biggest flaw. FIFO evicts the oldest page even if it's being used constantly. Second Chance adds one reference bit per page and asks a single extra question before evicting: has this page been used recently? If yes, it gets a reprieve.

The bit is set to 1 whenever the page is referenced. When FIFO would evict the front-of-queue page, Second Chance checks that bit. If it's 0, evict as normal. If it's 1, the page has earned a second chance: clear the bit to 0 and send the page to the back of the queue, as if it had just arrived. Then look at the new front.

This tiny change makes a big difference: a page that keeps getting used keeps getting its bit set, so it keeps rotating to the back and survives. A page nobody touches has bit 0 and gets evicted on its turn. You've turned pure age into 'age, unless recently used' — a cheap nod toward LRU.

Mechanics

How it works

The rule, step by step

Page already in the queue? Hit. Set its reference bit to 1. It keeps its position — the order doesn't change.
Not in memory, free frame available? Append it to the back of the queue with R = 1.
Not in memory, queue full? Look at the front page. If its R = 1: clear it to 0, move the page to the back, and look at the new front. Repeat. The first page you find with R = 0 is evicted; the new page joins the back with R = 1.

What happens when every bit is set?

If every resident page has R = 1, the scan clears them all to 0 as it rotates the whole queue exactly once — and then evicts the original front page, which is now back at the front with R = 0. So in the worst case Second Chance degrades gracefully to plain FIFO (it evicts the oldest), never looping forever. The prototype's Bits stay set preset drives this case.

The hidden cost is the rotation. Every second chance physically moves a page from the front to the back of the queue — real pointer surgery on a linked list. On a hot workload that's a lot of list shuffling. That inefficiency is precisely what Clock removes: same algorithm, but the pages stay put and a moving 'hand' does the scanning instead.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Second Chance

About this simulation

FIFO with one extra bit per page. The queue runs front (oldest) → back (newest), and each frame shows its reference bit (R). A hit sets R = 1. On a fault, inspect the front: if R = 1, clear it and rotate the page to the back (a second chance); repeat until you reach a page with R = 0 — that one is evicted. Watch the Chances given counter climb as hot pages keep dodging eviction.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Give a page its second chance

Load the Classic textbook preset and step to the first fault that hits a full queue. Read the decision card's scan log: it shows each front page with R = 1 getting its bit cleared and rotating to the back, until a page with R = 0 is found and evicted. The 'Chances given' stat ticks up each time.

try 02

Protect a hot page

Run the Hot page spared preset. The repeatedly-referenced page keeps having its R bit set, so every time the scan reaches it, it's spared and rotated to the back. It survives the whole run — exactly the page FIFO would have wrongly evicted.

try 03

Force the FIFO worst case, then compare to Clock

Run Bits stay set: when every page's bit is 1, the scan clears them all in one rotation and falls back to evicting the oldest — Second Chance behaving as plain FIFO. Then open the Clock prototype with the same string and frame count and confirm the fault totals are identical. Same algorithm, different machinery.

In practice

When to use it — and what you give up

When to reach for it

As the obvious upgrade from FIFO — one bit and one check buy most of the benefit of tracking usage, with almost no added complexity.
When hardware gives you a reference bit for free — most MMUs already set an 'accessed' bit on each page table entry, so the metadata costs nothing extra.
As a stepping stone to Clock — understand Second Chance and Clock is just the efficient implementation of the identical idea.
Prefer Clock for real systems — if you're going to ship this logic, ship it as Clock to avoid the queue-rotation overhead.

Second Chance and Clock are the same algorithm

They make identical eviction decisions on the same input — the only difference is the data structure. Second Chance moves pages around a queue; Clock leaves them in a ring and moves a pointer. If that clicks, you understand both at once. Open both prototypes on the same reference string and compare the fault counts: they match.

Pros

Fixes FIFO's worst mistake for one bit per page and one extra check.
Uses hardware you already have — the MMU's accessed bit.
Can't starve a hot page — repeated use keeps re-setting the bit.
Degrades gracefully — worst case is just FIFO, never an infinite loop.

Cons

Queue rotation is costly — each second chance moves a node to the back of the list.
Only one bit of history — it knows 'used since last checked or not', nothing finer; coarser than true LRU.
Clock strictly dominates it — identical decisions, cheaper implementation, so pure Second Chance is rarely the right ship.
Bit can lag reality — between scans the single bit can't distinguish a page used once from one used a thousand times.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

second-chance.ts

// Second Chance: FIFO queue + one reference bit per page.
interface Slot { page: number; ref: 0 | 1; }

class SecondChance {
  private frames: number;
  private queue: Slot[] = [];   // front = index 0 (oldest)
  faults = 0; hits = 0;

  constructor(frames: number) { this.frames = frames; }

  access(page: number): "hit" | "fault" {
    const slot = this.queue.find((s) => s.page === page);
    if (slot) { slot.ref = 1; this.hits++; return "hit"; } // mark used
    this.faults++;
    if (this.queue.length < this.frames) {
      this.queue.push({ page, ref: 1 });                   // free frame
      return "fault";
    }
    // scan from the front, sparing pages whose ref bit is set
    while (this.queue[0].ref === 1) {
      const spared = this.queue.shift()!;
      spared.ref = 0;                 // clear the bit...
      this.queue.push(spared);        // ...and rotate to the back
    }
    this.queue.shift();               // first page with ref 0 is evicted
    this.queue.push({ page, ref: 1 });
    return "fault";
  }
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

On a fault with a full queue, what does Second Chance do with a front page whose reference bit is 1?

question 02 / 03

If every resident page has its reference bit set to 1, how does Second Chance behave?

question 03 / 03

What is the key inefficiency of Second Chance that Clock eliminates?

0/3 answered