Paging & TLB in OS — Interactive Address Translation Guide

Section 01

The Story That Explains Paging

📖 Real World Analogy

The Airport Storage Lockers

A busy international airport has 10 000 storage lockers, all identical size — say 30 cm × 30 cm × 60 cm. A traveller arriving with a large suitcase can't fit it in one locker. But she can disassemble her belongings and stow them across several lockers. Locker 47 holds her jacket, locker 291 her books, locker 8034 her toiletries.

She keeps a small card in her pocket: "jacket → 47, books → 291, toiletries → 8034". When she wants her books, she looks at the card, walks to locker 291, opens it. The lockers themselves don't need to be next to each other. In fact they're deliberately scattered so the airport can keep every locker in use, no gaps.

That's paging. The traveller's belongings = a process's memory. The lockers = fixed-size frames in physical RAM. The card = the page table. And the beauty: because every locker is the same size, there's never any wasted gap between them. External fragmentation is impossible.

💡

The Core Idea

Divide physical memory into fixed-size frames and logical memory into fixed-size pages of the same size. A process's pages need not be contiguous in physical memory — they can be scattered anywhere. A page table per process records where each page lives.

Section 02

Basic Method — Pages and Frames

Two definitions that every paging discussion depends on:

👤

Page

unit of logical memory

A fixed-size chunk of the process's logical address space. Page 0 is the first bytes; page 1 the next, and so on. Common size: 4 KB (4096 bytes).

💾

Frame

unit of physical memory

A fixed-size chunk of physical RAM, the same size as a page. Frame 0 is the first 4 KB of RAM, frame 1 the next, and so on. Frames are the "lockers" from Section 01.

📋

Page Table

page → frame map

A per-process array where PageTable[i] = the frame number where page i currently lives. The OS maintains it; the MMU reads it on every access.

Logical Pages → Physical Frames (via Page Table)

Section 03

Address Translation Formula

Every logical address emitted by the CPU is split into two parts by the MMU:

📋 Logical Address Split

Page number. High-order bits. Used as index into the page table.

Offset within page. Low-order bits. Byte position within the page (0 to page_size − 1).

🔑

Why Power-of-Two Page Sizes?

If page size = 2ⁿ bytes, then the low n bits of a logical address are automatically the offset, and the rest are the page number. No division or modulo needed — just bit slicing, which is instant in hardware. Typical page size 4 KB = 2¹², so offset = low 12 bits.

Two-Step Translation

# Given logical address L and page_size = 2^n
p = L / page_size          # or equivalently: L >> n  (high bits)
d = L % page_size          # or equivalently: L & (page_size − 1)  (low n bits)

f = PageTable[p]           # look up frame number

physical_address = f × page_size + d
                # or equivalently: (f << n) | d  (bit concatenation)

Section 04

🎮 Interactive — Basic Address Translation

Small system for clarity: Page size = 4 bytes (offset = 2 bits). Logical address space = 32 bytes (page number = 3 bits, so 5-bit address total). Physical memory = 32 bytes (8 frames).

Page table:

Page	→	Frame
0	→	1
1	→	4
2	→	3
3	→	7
4	→	0
5	→	2
6	→	6
7	→	5

Address translation with bit slicing — logical → physical

Step 0 of 6

START Page size = 4 bytes (2 offset bits). Logical addresses are 5-bit (0–31). Click Next to translate the first address: 13 (binary 01101).

Section 05

Fragmentation in Paging

✅ External Fragmentation? NO.

All frames are the same size — every free frame can hold any page

Frames don't need to be adjacent to each other

No holes possible → external fragmentation eliminated ✓

This is the killer advantage of paging over contiguous allocation

⚠️ Internal Fragmentation? YES.

Last page of a process is often partially used

Example: process needs 15 KB → uses 4 pages (16 KB) → 1 KB wasted at the end

Average internal fragmentation ≈ page_size / 2 per process

Small pages → less waste but bigger page tables. Trade-off drives page size choice.

Section 06

The Translation Lookaside Buffer (TLB)

Under plain paging, every memory reference requires TWO memory accesses: one to read the page table entry, another to fetch the actual data. That halves effective speed. The fix is a small, ultra-fast associative cache in the MMU called the Translation Lookaside Buffer (TLB).

⚡ TLB Characteristics

Size

Small: 64 to 1024 entries typically. Each entry: (page_number, frame_number).

Type

Fully associative — all entries compared in parallel in a single cycle.

TLB hit

Page found in TLB → get frame instantly, no page-table lookup needed.

TLB miss

Page not in TLB → access page table in memory → cache the result in TLB.

Replacement

When full, evict oldest / LRU entry to make room for the new one.

Context switch

OS must flush TLB (or use ASIDs) since each process has its own page table.

🎮 Interactive — TLB Hit / Miss Sequence

A 3-entry TLB uses LRU replacement. Watch it fill up, evict entries, and cache page-to-frame mappings across an access sequence.

TLB in action — hits, misses, and LRU eviction

Step 0 of 8

START Empty TLB with 3 entries. Access sequence: pages 3, 3, 5, 3, 5, 7, 2, 3. Assume the underlying page table maps every page to some frame. Click Next to fire the first access.

Section 07

Effective Access Time (EAT)

With a TLB, most accesses are fast (hits) and a few are slow (misses). The Effective Access Time is the expected access time weighted by hit and miss probabilities.

📈

Galvin's EAT Formula

Let α = TLB hit ratio, T_TLB = TLB access time, T_mem = memory access time.

EAT = α × (T_TLB + T_mem) + (1 − α) × (T_TLB + 2 × T_mem)

On hit: TLB lookup + one memory access for the actual data.
On miss: TLB lookup + memory access for the page table + memory access for the data.

Section 08

Numerical Problem 1 — Effective Access Time

Given

📋 Parameters

Memory access time (T_mem) = 100 ns

TLB access time (T_TLB) = 20 ns

TLB hit ratio (α) = varies per part

📋 Formula Reminder

Hit cost: T_TLB + T_mem = 20 + 100 = 120 ns

Miss cost: T_TLB + 2 × T_mem = 20 + 200 = 220 ns

EAT = α × 120 + (1 − α) × 220

Part (a) — Hit Ratio = 80%

EAT = 0.80 × 120 + 0.20 × 220
    = 96 + 44
    = 140 ns

Part (b) — Hit Ratio = 98%

EAT = 0.98 × 120 + 0.02 × 220
    = 117.6 + 4.4
    = 122 ns

Part (c) — Slowdown vs Unpaged Memory

Unpaged memory access = 100 ns. With paging, we pay a slowdown factor.

# Slowdown = EAT / T_mem
slowdown_at_80% = 140 / 100 = 1.40x  # 40% overhead
slowdown_at_98% = 122 / 100 = 1.22x  # 22% overhead

# Without TLB (worst case): every access needs 2 memory reads
no_tlb_time = 2 × 100 = 200 ns → 100% slowdown

🏆

Key Insight

Going from 80% to 98% hit ratio cut the paging overhead from 40% to 22% — a huge improvement. Modern TLBs achieve 99%+ hit ratios through prefetching and larger sizes, keeping the paging overhead in the low single-digit percent. Without a TLB, paging would double the access time.

Section 09

Numerical Problem 2 — Interactive Address Translations

Setup: Page size = 1024 bytes (1 KB). Process has 8 pages (max logical address = 8191). Physical memory has enough frames. Page table:

Page	→	Frame
0	→	8
1	→	3
2	→	1
3	→	5
4	→	6
5	→	7
6	→	2
7	→	4

Multiple address translations — click Next to try each in sequence

Logical Address

—

p = ?, d = ?

Lookup Result

frame f = ?
check: —

Physical Address

        Awaiting first address…
      

Step 0 of 5

START Five logical addresses to translate. Some are valid, one goes outside the process's page range. Click Next to translate the first: 3200.

Section 10

Protection and Sharing with Paging

Protection Bits per Page Table Entry

✅

Valid / Invalid Bit

is this page in memory?

Every page table entry has a valid bit. If not set, the page is not in RAM (may be on disk, or the address is beyond the process's memory). Accessing it triggers a page fault — handled by the OS.

🔒

R / W / X Bits

per-page permissions

Each entry can independently mark a page read-only, writable, or executable. Same idea as segmentation, applied at page granularity. This is how modern OSes implement NX-bit (non-executable stack/heap).

👥

Page Sharing

two processes, one frame

If two processes' page tables both point their page 4 to physical frame 7 (say, libc code), they share one physical copy. Marked read-only for safety. Same idea as shared library code but at page granularity.

🔑

Copy-on-Write (COW)

When a process forks, both parent and child start with identical pages — no point in copying them yet. The OS marks all shared pages read-only. If either process tries to write, a fault occurs and the OS copies just that page. This makes fork() nearly instantaneous even for huge processes.

Section 11

Real-World Applications

💾

Every Modern OS

Linux, Windows, macOS, iOS, Android — all use paging with 4 KB pages (some also support 2 MB "huge pages"). Contiguous allocation is essentially extinct for user processes.

4 KB / 2 MB pages

⚡

Intel / AMD x86-64 MMU

Four-level page tables (PML4 → PDPT → PD → PT). Each level indexes 512 entries. TLB typically 64 L1 entries + 1024 L2 entries per core. Aggressive prefetching.

4-level tables · L1/L2 TLB

🖥️

Copy-on-Write in fork()

Linux's fork() uses COW paging so that a parent with 4 GB memory can spawn a child instantly. Pages are only duplicated on first write, which for many forks (like exec() immediately after) never happens.

COW · Linux fork

📂

Memory-Mapped Files

mmap() maps a file into a process's virtual address space. Uses paging: file blocks are loaded into frames on demand via page faults. Very fast — zero-copy file access.

mmap · Zero-copy IO

📡

Shared Libraries

libc.so (glibc) is loaded once and shared via paging across all processes on the system. Hundreds of MB saved. Same trick as segmentation-based sharing, applied per-page.

Shared frames

🔒

KASLR & Sandboxing

Kernel Address Space Layout Randomization uses per-boot page-table shuffling to prevent attackers from predicting kernel addresses. Container isolation also builds on paging.

KASLR · KPTI · Docker

Section 12

Golden Rules — Paging & TLB

🔑 Galvin's Non-Negotiable Rules

A logical address under paging is the pair <p, d> — page number and offset. If page size = 2ⁿ, the offset is the low n bits and the page number is the rest. No arithmetic — just bit slicing.

The MMU translates <p, d> to (PageTable[p] × page_size) + d. On hardware, this is a bit shift + OR — effectively free.

Paging eliminates external fragmentation because all frames are the same size. This is its single biggest advantage over contiguous allocation.

Paging introduces internal fragmentation only in the last page of each process. Average waste ≈ page_size / 2 — a much smaller cost than external fragmentation.

Without a TLB, every memory reference requires TWO memory accesses: one for the page table entry, one for the data. This would halve system performance.

The TLB is a small, fully associative cache in the MMU that stores recent page-to-frame translations. A hit means one memory access; a miss means two.

Effective Access Time formula: EAT = α × (T_TLB + T_mem) + (1 − α) × (T_TLB + 2 × T_mem). Higher hit ratio α → EAT closer to raw memory time.

Modern TLBs achieve 99%+ hit ratios in typical workloads, keeping the paging overhead in the low single digits. The TLB is essentially the reason paging is practical.

On a context switch, the OS must either flush the TLB or use per-process address space identifiers (ASIDs). Failing this causes wrong translations.

Page-table entries carry protection bits (R, W, X, valid). Same protection ideas as segmentation, applied per-page. This is how NX-bit, COW-fork, and shared libraries all work.