# TLB and Effective Access Time — Page Table Size, Multi-Level Paging and Page-Fault Numericals

Source: https://skills101.in/learn/operating-systems/os-tlb-effective-access-time — Skills101 free tutorial (Operating Systems). Updated 2026-11-21.

Paging (lesson 6) has a hidden cost: before the CPU can read a byte, it must find out **which frame** holds the page — and the page table itself lives in RAM. This lesson measures that cost, shows how the **TLB** hides it, and solves the effective-access-time (EAT) questions that appear in nearly every OS exam.

## 1. The problem: two memory reads for one

With a single-level page table in RAM, every memory access becomes:

1. Read the **page table entry** (one memory access) to get the frame number.
2. Read the **data** (a second memory access).

If one memory access takes 100 ns, every load or store now takes **200 ns** — paging has made memory twice as slow.

## 2. The TLB

The **TLB** (Translation Lookaside Buffer) is a small, very fast cache **inside the CPU** that remembers recent page → frame translations. It usually holds from a few dozen to a few thousand entries and is searched in parallel, so a lookup takes about one CPU cycle.

![TLB address translation: the CPU looks up page p in the TLB; on a hit it gets the frame at once and reads the data; on a miss it reads the page table in RAM first. Hit costs TLB time plus one memory access; miss costs TLB time plus two memory accesses](https://skills101.in/learn-img/operating-systems/tlb-lookup.svg)

- **TLB hit:** TLB time + 1 memory access.
- **TLB miss:** TLB time + 1 access for the page table + 1 for the data. The translation is then put into the TLB.

Programs have **locality** — they keep using the same few pages — so hit ratios are usually very high.

## 3. Effective access time with a TLB

With hit ratio h, TLB lookup time t and memory access time m:

**EAT = h × (t + m) + (1 − h) × (t + 2m)**

**Worked example.** t = 20 ns, m = 100 ns, h = 80%.

- Hit: 20 + 100 = 120 ns.
- Miss: 20 + 100 + 100 = 220 ns.
- EAT = 0.8 × 120 + 0.2 × 220 = 96 + 44 = **140 ns**.

Compared with 200 ns without a TLB, that is a big saving, and a better hit ratio helps more:

```python
def eat(hit, tlb, mem, levels=1):
    on_hit = tlb + mem                      # translation found in the TLB
    on_miss = tlb + levels * mem + mem      # walk the page table(s), then the data
    return hit * on_hit + (1 - hit) * on_miss

for h in (0.80, 0.90, 0.98):
    print(f"hit {h:.0%}: one level {eat(h, 20, 100):6.1f} ns   two levels {eat(h, 20, 100, 2):6.1f} ns")
print("no TLB, one level:", 2 * 100, "ns")
```

```text
hit 80%: one level  140.0 ns   two levels  160.0 ns
hit 90%: one level  130.0 ns   two levels  140.0 ns
hit 98%: one level  122.0 ns   two levels  124.0 ns
no TLB, one level: 200 ns
```

**Two exam variations to watch for:**

- Some questions say the TLB is searched **in parallel** with memory, or ignore the TLB time. Then a hit costs just m and a miss 2m. Read the question.
- **Reverse question:** "What hit ratio gives an EAT of 130 ns?" Solve 120h + 220(1 − h) = 130 → 220 − 100h = 130 → **h = 0.9**.

## 4. How big is a page table?

**Number of entries = 2^(logical address bits) / page size. Size = entries × entry size.**

32-bit addresses, 4 KB (2¹²) pages, 4-byte entries:

- Entries = 2³² / 2¹² = 2²⁰ = **1,048,576**.
- Size = 2²⁰ × 4 B = **4 MB** — for **every** process, even one that uses only a few pages.

On a 64-bit machine using 48-bit virtual addresses with 8-byte entries, a single flat table would need 2³⁶ × 8 B = **512 GB**. Impossible. That is why page tables are split into levels.

## 5. Two-level (multi-level) paging

Split the page number into two parts. The **outer** page table points to **inner** page tables, and inner tables are created **only for the parts of memory the process actually uses**.

![Two-level paging for a 32-bit address with 4 KB pages: 10 bits index the outer table, 10 bits index an inner table, and 12 bits are the offset; each table has 1024 entries of 4 bytes, exactly one 4 KB page, instead of a 4 MB single-level table](https://skills101.in/learn-img/operating-systems/two-level-paging.svg)

Why 10 + 10 + 12? The offset needs 12 bits for 4 KB pages. A page-sized table holds 4096 / 4 = 1024 = 2¹⁰ entries, so each level uses 10 bits. 10 + 10 + 12 = 32.

**Space saved.** A small program using 3 regions of memory needs 1 outer table + 3 inner tables = 4 × 4 KB = **16 KB** instead of 4 MB.

**Time cost.** A TLB miss now needs **two** page-table reads before the data. With the same numbers (t = 20, m = 100):

- 80% hits: 0.8 × 120 + 0.2 × (20 + 200 + 100) = 96 + 64 = **160 ns**.
- 98% hits: **124 ns** — almost the same as one level.

So multi-level tables save huge amounts of memory, and the TLB hides most of the extra time. 64-bit x86 processors use **four** levels (and newer ones optionally five).

## 6. Effective access time with page faults

If the page is not in RAM at all, a **page fault** must load it from disk — millions of times slower than RAM. With page-fault rate p, memory access time m and page-fault service time s:

**EAT = (1 − p) × m + p × s**

**Example.** m = 200 ns, s = 8 ms = 8,000,000 ns.

| Fault rate p | EAT |
|---|---|
| 1 in 1,000 | 0.999 × 200 + 0.001 × 8,000,000 = **8199.8 ns** (about 41× slower) |
| 1 in 100,000 | ≈ **280 ns** (40% slower) |

**How rare must faults be to stay within 10% of 200 ns?** Need 200 + p × (8,000,000 − 200) < 220 → p < 20 / 7,999,800 ≈ 2.5 × 10⁻⁶ — fewer than **one fault in about 400,000 accesses**. This is why thrashing (lesson 7) is so damaging: even a small rise in the fault rate ruins performance.

## 7. Inverted page tables

Instead of one table **per process** with one entry per **page**, an **inverted page table** has one entry per **physical frame** for the whole system, each saying "this frame holds page p of process id". Its size depends on RAM size, not on the address space. The downside: to translate an address you must **search** for (process, page), so it is combined with hashing — and with a TLB, of course.

| Page table type | Size depends on | Lookup |
|---|---|---|
| Single-level | virtual address space (per process) | one index — fast |
| Multi-level | the memory a process actually uses | one read per level |
| Inverted | physical memory (one table in total) | search / hash |

## Common mistakes

- Charging only one memory access on a TLB miss — a miss needs the page-table read **and** the data read.
- Forgetting the extra level on a miss with two-level paging.
- Mixing ns and ms in the page-fault formula — convert everything to ns first.
- Computing page-table entries from the **physical** address size instead of the **logical** one.
- Thinking multi-level paging makes every access slower — with a good TLB hit ratio the difference is small.

## Quick recap

- No TLB: every access costs 2 memory reads with one-level paging.
- EAT = h(t + m) + (1 − h)(t + (levels + 1)m).
- Page table entries = 2^(address bits) / page size; 32-bit, 4 KB, 4 B entries → 4 MB.
- Multi-level tables store only the parts in use; each level adds one read on a TLB miss.
- With page faults: EAT = (1 − p)m + p·s, so p must be tiny.


Practice quiz and free certificate: https://skills101.in/learn/operating-systems/os-tlb-effective-access-time