Aging — Page Replacement

Overview

What this concept solves

Aging is software's best cheap imitation of LRU. The problem with exact LRU is the cost of maintaining a precise recency order on every access. Aging instead keeps a small counter per page — typically 8 bits — and updates it only at periodic clock ticks. The counter encodes recency over the last several intervals, and the page with the smallest counter is the least-recently-used-ish victim.

The trick is how the counter is built. At each tick, you shift the counter right by one bit and slide the page's reference bit into the newly-vacated leftmost (most significant) position. So the high bits record recent intervals and the low bits record older ones. A page used in the most recent interval has a 1 in the top bit, making its counter large; a page idle for many intervals shifts its 1s down and out, making its counter small.

Because more-significant bits dominate the numeric value, recent use outweighs old use automatically — exactly LRU's instinct — but you only ever do a cheap shift-and-OR per page per tick, never a per-access list update.

Mechanics

How it works

The rule, step by step

On a reference: set the page's R bit to 1 (just a flag for this interval). A hit needs nothing more.
On a clock tick: for every page, counter = (counter >> 1) | (R << (n-1)) — shift right, drop R into the top bit — then clear R to 0. This is the 'aging' step.
On a fault with a free frame: load the page with a counter of 0 and R = 1.
On a fault with no free frame: evict the page with the numerically smallest counter — the one least recently (and least often) used across the recent intervals.

Why it approximates LRU — and where it differs

Comparing counters mostly answers 'who was referenced most recently?' because the top bit (most recent interval) dominates. But Aging has finite memory: with 8 bits it only remembers 8 intervals. Two pages both idle for 8+ intervals both reach counter 0 — Aging can't tell which was used more recently beyond its window, where true LRU always can. Within its window, though, it tracks recency remarkably well for the cost.

Aging is the polished descendant of NFU (Not Frequently Used), which simply added the R bit to a counter each interval. NFU's flaw: a page heavily used long ago keeps a huge count forever (it never forgets). The right-shift fixes exactly that — old activity decays away one bit at a time, so the counter measures recent behavior, not all-time totals.

Interactive prototype

Run it. Break it. Tune it.

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

simulation › Aging

About this simulation

Each page carries an 8-bit counter, shown as a strip of bits (leftmost = most recent interval). A reference sets the page's R bit. On every clock tick, every counter shifts right by one and the R bit drops into the leftmost position, then R clears. On a fault, the page with the smallest counter is evicted. Watch the bits march rightward and the counters separate hot pages from cold ones.

Hands-on

Try these on your own

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

try 01

Watch the bits shift on every tick

Load the Classic textbook preset and step forward to a tick (highlighted rows; banner reads 'counters shifted right, R inserted at the top'). Watch each page's bit strip slide one cell to the right, with the most-recent interval's bit appearing at the left. Pages referenced this interval get a fresh 1 up top; idle pages lose their leftmost 1s downward.

try 02

See a hot page keep the highest counter

Run Hot page wins. The repeatedly-referenced page sets its R bit nearly every interval, so the shift keeps injecting 1s into its top bit and its counter stays large — it's never the smallest, so it's never evicted. The decision card lists every counter (binary + value) on each eviction so you can confirm the smallest one loses.

try 03

Find the horizon limit

Run Two working sets (two groups of pages used in alternating phases). When a group goes idle for more than 8 intervals, every counter in it shifts down to 0 — and Aging can no longer tell those pages apart, unlike true LRU. This is the finite-memory limit of the n-bit counter, made visible.

In practice

When to use it — and what you give up

When Aging is a good fit

Software-managed page replacement — when you want LRU-quality decisions but can only afford periodic, bounded work, not per-access bookkeeping.
When you have a periodic timer anyway — Aging piggybacks on a clock interrupt the OS already runs.
When a few bits of recency history are enough — most working sets are stable over a handful of intervals, which is exactly Aging's window.
Tune the counter width and tick period together — more bits and finer ticks track recency more precisely, at proportional cost.

Aging vs Clock vs LRU

Clock keeps one bit and is dirt cheap but very coarse. Exact LRU keeps perfect order but is expensive on every access. Aging sits between them: an n-bit counter updated per tick gives several bits of recency history — much finer than Clock, much cheaper than true LRU. It's the natural choice when Clock's single bit isn't discriminating enough.

Pros

Close to LRU's quality for a fraction of the cost — recent use dominates automatically.
Cheap, bounded work — one shift-and-OR per page per tick; nothing on the access hot path beyond setting a bit.
Decays old activity — fixes NFU's 'never forgets' problem so the counter reflects recent behavior.
Tunable resolution — pick the counter width and tick rate to trade precision for cost.

Cons

Finite memory horizon — an n-bit counter can't distinguish pages idle longer than n intervals; both hit 0.
Tick granularity blurs order — references within the same interval are indistinguishable; their order is lost.
Per-tick scan — updating every page's counter each tick is O(frames) work, periodically.
Still not exact — when precise LRU truly matters and is affordable, Aging is an approximation, not a replacement.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

aging.ts

// Aging: per-page n-bit shift-register counter approximating LRU.
const BITS = 8;
interface Slot { page: number; r: 0 | 1; counter: number; }

class Aging {
  private slots: (Slot | null)[];
  faults = 0; hits = 0;

  constructor(frames: number) { this.slots = Array(frames).fill(null); }

  // called periodically: shift right, drop R into the top bit, clear R
  tick() {
    for (const s of this.slots) if (s) {
      s.counter = (s.counter >>> 1) | (s.r << (BITS - 1));
      s.r = 0;
    }
  }

  access(page: number): "hit" | "fault" {
    const slot = this.slots.find((s) => s?.page === page);
    if (slot) { slot.r = 1; this.hits++; return "hit"; }   // mark referenced
    this.faults++;
    const free = this.slots.indexOf(null);
    if (free >= 0) { this.slots[free] = { page, r: 1, counter: 0 }; return "fault"; }

    // evict the smallest counter: least recently used over the recent window
    let victim = 0;
    this.slots.forEach((s, i) => {
      if (s!.counter < this.slots[victim]!.counter) victim = i;
    });
    this.slots[victim] = { page, r: 1, counter: 0 };
    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 each clock tick, how does Aging update a page's counter?

question 02 / 03

What problem in NFU does Aging's right-shift fix?

question 03 / 03

What is the fundamental limitation of using a fixed n-bit counter?

0/3 answered