TLBs, effective access time and multilevel page tables

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Page-table size = ? from Lesson 5.2.1
2. Physical address from frame f and offset d? from Lesson 5.2.1
3. What does a context switch save and load? from Lesson 1.1.2

1 · The Hook

A librarian who checks the index card for every single book fetch is slow; one who remembers the last few cards is fast. The TLB is that memory: a tiny, very fast cache of recent page→frame translations. GATE's favourite memory numerical, "effective memory access time", is built on it. And when page tables grow to many megabytes, we page the page table itself: multilevel paging.

3 · Core Concept

Predict First — the answer

200 ns: 100 ns to read the page-table entry, then 100 ns for the data itself.

In plain words

The TLB is a small hardware table of recent (page → frame) pairs, searched all at once. If the page is there (a hit), translation is almost free. If not (a miss), read the page table in memory and remember the pair in the TLB. Multilevel paging splits the page number into parts, each indexing a smaller table, so tables for unused regions need not exist.

1. Effective access time with a TLB

Let t = TLB lookup time, m = memory access time, h = hit ratio.

• Hit: t + m. Miss: t + m (page table) + m (data) = t + 2m.
• EAT = h(t + m) + (1 − h)(t + 2m).

Example: m = 100 ns, t = 20 ns, h = 0.8 → 0.8 × 120 + 0.2 × 220 = 140 ns. With h = 0.98: 122 ns. If the question says TLB time is negligible, put t = 0.

2. TLB facts

• Typically 32–1024 entries, searched in parallel (associative memory).
• On a context switch the TLB must be flushed, unless entries carry an address-space identifier (ASID).
• Higher hit ratio → EAT close to a single memory access.

3. Multilevel (hierarchical) paging

Problem: a 4 MB page table per process, mostly unused. Solution: split the page number. Two-level example (32-bit addresses, 4 KB pages, 4-byte entries):

• One page holds 4096 / 4 = 1024 entries → 10 bits index each level.
• Address = p1 (10) | p2 (10) | offset (12). p1 indexes the outer table; that entry gives the inner table; p2 indexes it.
• Only inner tables for used regions are created.

General rule: entries per page = page size / PTE size; bits per level = log₂ of that; levels = ⌈(logical bits − offset bits) / bits per level⌉. Example: 48-bit addresses, 4 KB pages, 8-byte entries → 512 entries per page → 9 bits per level → 36 / 9 = 4 levels.

4. EAT with k levels

A TLB miss needs k page-table reads plus the data: t + (k + 1)m. Example: 4 levels, m = 100, t = 10, h = 0.95 → 0.95 × 110 + 0.05 × 510 = 130 ns.

5. Other page-table designs

• Inverted page table: one entry per frame (not per page), holding (process id, page). One table for the whole system; small, but finding a page means searching, so it is combined with a hash table.
• Hashed page table: hash the page number into a bucket of (page, frame) pairs; good for 64-bit addresses.

4 · Visual

Two-level paging, 32-bit address, 4 KB pages

+---------+---------+------------+
| p1 (10) | p2 (10) | offset(12) |
+---------+---------+------------+
     |          |
     v          v
 outer table -> inner table -> frame f  ->  physical = f x 4096 + offset
 (1024 entries)  (1024 entries)

TLB hit : t + m        TLB miss: t + 2m (one level)   t + (k+1)m (k levels)

5 · Worked Examples

Example 1 Easy

m = 100 ns, TLB time negligible, hit ratio 0.9. EAT?

Solution

0.9 × 100 + 0.1 × 200 = 110 ns.

Example 2 Medium

32-bit addresses, 4 KB pages, 4-byte entries, two-level paging with each table one page. How large is the outer page table?

Solution

1024 entries × 4 B = 4 KB (exactly one page).

Example 3 GATE

46-bit virtual addresses, 8 KB pages, 4-byte entries, every page table must fit in one page. How many levels?

Solution

8 KB / 4 B = 2048 entries → 11 bits per level. 46 − 13 = 33 bits → 33 / 11 = 3 levels.

6 · GATE Traps

• A TLB miss costs t + 2m (one level), not just 2m, when t is given.
• Levels: divide the page-number bits (not all address bits) by bits per level, and round up.
• Inverted page table size depends on physical memory (one entry per frame).
• Flushing the TLB on a context switch is avoided with ASIDs.

7 · Memory Hook

"Hit: t + m. Miss: t + (levels + 1)m. Levels = ⌈page bits / log₂(page size / PTE)⌉."

8 · Connect the Dots

Paging cuts programs into equal pieces that mean nothing to the programmer. The next lesson looks at segmentation, which divides a program into meaningful parts (code, data, stack), and at combining the two.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — EAT

Memory access 100 ns, TLB lookup 20 ns, hit ratio 0.8 (single-level paging). Effective access time in ns?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — EAT

Memory access 50 ns, TLB lookup 10 ns, hit ratio 0.9 (single-level paging). Effective access time in ns?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Levels

48-bit virtual addresses, 4 KB pages, 8-byte page-table entries; each table fits in one page. Number of levels?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Multilevel EAT

4-level paging, memory access 100 ns, TLB 10 ns, hit ratio 0.95. EAT in ns?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Inverted page table

An inverted page table has one entry per:

1. (A) process
2. (B) TLB entry
3. (C) physical frame
4. (D) page of each process

10 · Rule Card

• EAT = h(t + m) + (1 − h)(t + 2m); with k levels the miss costs t + (k + 1)m.
• TLB: small associative cache; flush on switch unless ASIDs.
• Multilevel: entries per page = page size / PTE; bits per level = log₂ of it; levels = ⌈(m − d) / bits per level⌉.
• Inverted table: one entry per frame, searched via hashing.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

translation lookaside bufferTLB hit and misshit ratioeffective access timeASIDmultilevel pagingouter and inner page tablesnumber of levelsinverted page tablehashed page table