Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 67 ยท Virtual Memory and Storage

TLBs and Page Replacement Algorithms

See how the TLB hides page-table cost and how FIFO, LRU, Clock and Optimal page replacement compare, including Belady's anomaly, with Python simulations.

Address translation by walking page tables, as you saw in Virtual Memory and Paging, would make every load and store several times slower. Two mechanisms rescue performance. The TLB (translation lookaside buffer) caches recent translations so most accesses skip the table walk. Page replacement decides which page to throw out of RAM when a new page must come in and no frame is free, so that page faults, which are enormously more expensive than any cache miss, stay rare.

This lesson simulates both. First you will measure TLB hit rates and the average cost of translation, then you will count page faults for FIFO, LRU, Optimal and Clock replacement, and see the surprising case where adding memory makes FIFO worse.

The translation lookaside buffer

The TLB is a small cache (commonly 16 to 64 entries at the first level, plus a larger second-level TLB with a thousand or more entries) that maps virtual page numbers to frame numbers. It sits next to the L1 cache and is searched in parallel or just before it, usually fully or highly associative, and it works exactly like the caches in Cache Mapping: a hit costs about one cycle, a miss triggers a page-table walk (done by dedicated hardware on x86 and ARM, by software on some older RISC chips), and the result is stored in the TLB, evicting an older entry.

flowchart TD
  A["CPU issues virtual address"] --> T{"VPN in TLB?"}
  T -- "hit" --> P["Frame number from TLB<br/>about 1 cycle"]
  T -- "miss" --> W["Walk the page table<br/>one or more memory reads"]
  W --> V{"Page present?"}
  V -- "yes" --> F["Fill TLB entry"] --> P
  V -- "no" --> PF["Page fault: OS loads the page"] --> F
  P --> M["Physical address goes to the cache"]

The TLB short-circuits the walk; only a TLB miss pays for the table, and only a missing page pays for the OS.

Two housekeeping facts matter to programmers. First, TLB entries belong to one address space. On a context switch the OS either flushes the TLB or tags entries with an address-space identifier (ASID or PCID) so entries of different processes can coexist. Second, when the OS changes a mapping it must invalidate the matching TLB entry, otherwise the CPU keeps using a stale translation. On multicore machines this causes TLB shootdowns, interrupts sent to every core that might cache the entry.

Effective translation time

If a TLB hit costs t and a miss adds one extra memory reference of cost m for a single-level table, then the average cost of translation is

t + (1 - hit rate) x m

(A four-level walk costs up to four such references, so TLB misses hurt more on 64-bit systems.) The simulation below builds two access patterns of 131,072 accesses and replays them through an LRU TLB of 16 and of 64 entries.

Python TLB hit rate for two access patterns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sequential pattern is nearly perfect with any TLB: a 4 KB page holds 1,024 integers, so one miss serves 1,024 accesses (99.9 percent hits, about 1.1 cycles of translation). The page-hopping pattern touches 64 different pages in a cycle, one access each. A 16-entry LRU TLB gets zero hits (the same cyclic-thrashing effect as with caches) and every access pays about 101 cycles. With 64 entries the working set of 64 pages fits and the hit rate returns to 99.95 percent.

The number to remember is the TLB reach: entries x page size. Sixty-four entries of 4 KB reach only 256 KB. Programs with a bigger hot set (databases, large matrices) lose time to TLB misses, and that is why systems offer huge pages (2 MB or 1 GB): a single entry then covers 512 times as much memory.

Page replacement

When a page fault occurs and all frames are in use, the OS must choose a victim page. This is the same problem as cache replacement, but the stakes are higher: a disk read costs milliseconds, so even one avoided fault is worth thousands of simple instructions. We evaluate algorithms by feeding them a reference string (the sequence of page numbers touched) and counting faults.

Four algorithms are worth knowing:

  • FIFO evicts the page that has been in memory longest. It is trivial to implement, but ignores usage.
  • LRU evicts the page unused for the longest time. It matches typical locality, but an exact version needs a timestamp or ordering update on every memory reference, which is far too expensive for hardware and software to do exactly.
  • Optimal (OPT, or Belady's algorithm) evicts the page whose next use is farthest in the future. It produces the fewest possible faults, but needs to know the future, so it cannot be built. It is used as a yardstick to see how close a real algorithm gets.
  • Clock (second chance) approximates LRU cheaply. Frames sit on a circular list with a reference bit, which the hardware sets whenever the page is used. A "hand" sweeps around: if the bit is 1, it clears it and moves on (a second chance); if the bit is 0, that page is the victim.
Python Counting page faults: FIFO, LRU and Optimal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 3 frames, FIFO suffers 15 faults on this 20-reference string, LRU 12 and Optimal 9. This ordering is typical: OPT is a lower bound, LRU follows closely, and FIFO trails. The first row shows that rankings are not a law: with only 2 frames, LRU (17 faults) is actually worse than FIFO (15) on this particular string, because there is so little room that recency hardly helps. Notice also that no algorithm does worse as frames are added on this string. The string touches 6 distinct pages, so no algorithm can do better than 6 faults, and with 5 frames LRU and Optimal both come within one fault of that floor (7).

Belady's anomaly

It is natural to assume that more memory never hurts. For FIFO, that assumption is false. Belady's anomaly is the effect that giving a process more frames can increase its number of page faults. The standard demonstration uses the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Algorithms such as LRU and OPT are stack algorithms: the set of pages held with N frames is always a subset of the set held with N + 1 frames, so adding frames can only keep or reduce faults. FIFO has no such property, because eviction depends on arrival order, which differs between memory sizes.

Python Belady's anomaly, with Clock for comparison

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the FIFO column: 12, 12, 9, 10, 5, 5. Going from 3 frames to 4 raises faults from 9 to 10. LRU never goes up (12, 12, 10, 8, 5, 5). The Clock algorithm shares FIFO's behaviour here because no page is referenced again before its turn comes up.

Real systems therefore do not use plain FIFO. Linux, Windows and the BSDs use variants of Clock (often with separate "active" and "inactive" lists), because it approximates LRU using only the reference bit that the MMU sets for free.

Replacement can be global (pick a victim from any process) or local (only from the faulting process). Too little memory per process causes thrashing: the system spends most of its time faulting. The usual cures are to run fewer processes at once or to give each process enough frames for its working set, the set of pages it uses during a recent window of time.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A TLB has 32 entries and 4 KB pages. What is its reach?

    Reach is entries x page size: 32 x 4 KB = 128 KB. Programs touching more memory than that in their hot set will see TLB misses.
  2. 2. The TLB hit rate is 98%, a TLB hit costs 1 cycle and each miss adds one 100-cycle memory access. What is the average translation cost?

    1 + 0.02 x 100 = 3 cycles. Even a 2% miss rate triples the cost of translation compared with a perfect TLB.
  3. 3. Why can the Optimal page replacement algorithm not be used in a real OS?

    OPT evicts the page whose next use is farthest away. A real system cannot see the future, so OPT serves only as a benchmark.
  4. 4. What is Belady's anomaly?

    For FIFO on the reference string 1 2 3 4 1 2 5 1 2 3 4 5, three frames give 9 faults but four frames give 10.
  5. 5. In the Clock algorithm, what happens when the hand reaches a page whose reference bit is 1?

    Only a page with reference bit 0 is chosen. A page with bit 1 has been used since the last sweep, so its bit is cleared and the hand advances.

Summary

  • The TLB caches virtual-to-physical translations; a hit costs about a cycle and a miss triggers a page-table walk.
  • Average translation cost is the hit time plus the miss rate times the walk cost; TLB reach (entries x page size) tells you how much memory is covered, and huge pages extend it.
  • Context switches flush the TLB or use address-space tags, and changing a mapping requires invalidating TLB entries.
  • Page replacement chooses a victim when memory is full: FIFO (oldest), LRU (least recently used), Optimal (farthest next use, an unreachable bound) and Clock (cheap LRU approximation).
  • FIFO can show Belady's anomaly, where more frames cause more faults; stack algorithms like LRU and OPT cannot.
  • Thrashing happens when processes lack enough frames for their working sets.

Continue with Disks, SSDs and RAID.