Paging with Translation Lookaside Buffer (TLB) Scheme

Paging is a virtual memory technique in which a logical address is split into a page number and a page offset. The page number identifies which virtual page is being referenced, while the offset identifies the exact location within that page. In a simple paging system, the processor must consult the page table to translate the virtual page number into a physical frame number before accessing memory, which can add substantial overhead.2

A Translation Lookaside Buffer (TLB) is introduced to reduce this overhead. The TLB is a small, fast associative cache inside or near the MMU, storing recently used page-table entries. If the required translation is found in the TLB, address translation completes quickly without consulting the page table in main memory; this is called a TLB hit. If the translation is absent, a TLB miss occurs, and the hardware or operating system must walk the page table, install the translation into the TLB, and then proceed.3

Without a TLB, a one-level page table usually requires two memory references for each access: one to fetch the page-table entry and another to fetch the actual data. With a high TLB hit ratio, most references need only one main-memory access after a very small TLB lookup cost, making paging practical in modern systems.3

Footnotes

1. Translation lookaside buffer - Wikipedia - Overview of TLB purpose, hits, misses, and its role in reducing paging overhead. ↩ ↩² ↩³

2. Translation Lookaside Buffer (TLB) in Paging - GeeksforGeeks - Stepwise explanation of TLB hit/miss flow and standard EMAT formula. ↩

3. Faster Translations (TLBs) - OSTEP PDF - Detailed academic treatment of TLBs, address translation, misses, and context-switch issues. ↩ ↩²

4. Translation Lookaside Buffer | TLB | Paging | Gate Vidyalay - Concise explanation of paging with TLB, hit/miss behavior, and update process. ↩

5. Translation Lookaside Buffer (TLB) | COMS W4118 Operating Systems I - Effective access time discussion and why high hit ratio makes paging efficient. ↩

Basic address translation in paging with TLB

A virtual address is conventionally divided into two fields:

$$\text{Virtual Address} = (\text{Page Number}, \text{Offset})$$

If page size is $2^d$ bytes, then the lower $d$ bits form the offset and the remaining higher-order bits form the page number.2 The TLB stores mappings of the form:

$$\text{Virtual Page Number} \rightarrow \text{Physical Frame Number}$$

Once the frame number is found, the physical address is formed as:

$$\text{Physical Address} = (\text{Frame Number}, \text{Offset})$$

The offset does not change during translation because both pages and frames are the same size.2

A typical TLB entry contains the virtual page number tag, corresponding physical frame number, and control bits such as valid, protection, dirty, or access permissions. Many systems also include an ASID or process identifier so that entries from different processes can coexist safely.2

Footnotes

1. Translation Lookaside Buffer (TLB) in Paging - GeeksforGeeks - Stepwise explanation of TLB hit/miss flow and standard EMAT formula. ↩ ↩²

2. Translation Lookaside Buffer | TLB | Paging | Gate Vidyalay - Concise explanation of paging with TLB, hit/miss behavior, and update process. ↩ ↩² ↩³

3. Lecture 18 Virtual Memory 2 - MIT PDF - Hardware-oriented notes on TLB design, ASIDs, hardware page walks, and page faults. ↩

TLB hit and TLB miss behavior

The TLB scheme is best understood by separating the two common cases:

On a TLB hit, the system avoids a page-table memory reference entirely. On a TLB miss, the system pays an additional penalty to fetch the page-table entry and update the TLB. If the page is not resident in physical memory, the event escalates to a page fault, which is much more expensive than a mere TLB miss because it may require disk I/O.3

This distinction is crucial: a TLB miss does not necessarily mean a page fault. A TLB miss only means the translation is not cached in the TLB; the page may still be present in memory and correctly described by the page table.2

Footnotes

1. Translation lookaside buffer - Wikipedia - Overview of TLB purpose, hits, misses, and its role in reducing paging overhead. ↩

2. Faster Translations (TLBs) - OSTEP PDF - Detailed academic treatment of TLBs, address translation, misses, and context-switch issues. ↩ ↩²

3. Lecture 18 Virtual Memory 2 - MIT PDF - Hardware-oriented notes on TLB design, ASIDs, hardware page walks, and page faults. ↩ ↩²

Effective Memory Access Time (EMAT)

The central performance reason for using a TLB is reduction of effective memory access time. Let:

• $h$ = TLB hit ratio
• $c$ = TLB lookup time
• $m$ = main memory access time

For a one-level paging system, a common EMAT model is:

$$\text{EMAT} = h(c + m) + (1-h)(c + 2m)$$

Explanation:

• On a hit, cost is $c + m$
• On a miss, cost is $c + 2m$ because one memory access is needed for the page-table entry and another for the actual data3

This expression can be simplified:

$$\text{EMAT} = c + 2m - hm$$

assuming the same $c$ is paid in both cases.

Example

Suppose:

• $c = 10 \text{ ns}$
• $m = 100 \text{ ns}$
• $h = 0.90$

Then:

$$\text{EMAT} = 0.9(10 + 100) + 0.1(10 + 200)$$ $$= 0.9(110) + 0.1(210) = 99 + 21 = 120 \text{ ns}$$

Without a TLB, access would require approximately $200 \text{ ns}$ in a simple one-level model. Thus, even a modestly sized TLB with high locality substantially improves performance.3

Footnotes

1. Translation Lookaside Buffer (TLB) in Paging - GeeksforGeeks - Stepwise explanation of TLB hit/miss flow and standard EMAT formula. ↩ ↩²

2. Translation Lookaside Buffer (TLB) | COMS W4118 Operating Systems I - Effective access time discussion and why high hit ratio makes paging efficient. ↩ ↩²

3. Virtual Memory and Page Tables - University of Pennsylvania PDF - Lecture notes explaining TLB locality, small associative structures, and MMU refill behavior. ↩ ↩² ↩³

Suitable conceptual diagram of paging with TLB

The following diagram captures the hardware path more explicitly:

This diagram emphasizes four core observations:

1. The TLB sits on the critical path of address translation.2
2. A hit avoids page-table access entirely.2
3. A miss causes a page-table walk and then usually a TLB refill.2
4. Only if the page-table entry is invalid or nonresident does the system trigger a page fault.2

In practice, modern processors may use multi-level TLB hierarchies, multi-level page tables, and hardware page walkers. Nevertheless, the conceptual model above remains the standard explanation for paging with TLBs.3

Footnotes

1. Faster Translations (TLBs) - OSTEP PDF - Detailed academic treatment of TLBs, address translation, misses, and context-switch issues. ↩ ↩² ↩³ ↩⁴

2. Translation Lookaside Buffer | TLB | Paging | Gate Vidyalay - Concise explanation of paging with TLB, hit/miss behavior, and update process. ↩ ↩²

3. Translation Lookaside Buffer (TLB) in Paging - GeeksforGeeks - Stepwise explanation of TLB hit/miss flow and standard EMAT formula. ↩

4. Translation Lookaside Buffer (TLB) | COMS W4118 Operating Systems I - Effective access time discussion and why high hit ratio makes paging efficient. ↩

5. Lecture 18 Virtual Memory 2 - MIT PDF - Hardware-oriented notes on TLB design, ASIDs, hardware page walks, and page faults. ↩ ↩² ↩³

Advantages and limitations of the TLB scheme

Advantages

• It reduces average address-translation overhead by caching frequently used page-table entries.2
• It makes paging feasible for large address spaces where repeated page-table access would otherwise be too slow.2
• It exploits locality, so a relatively small hardware structure can provide large performance gains.2

Limitations

• TLB misses still incur additional latency because page-table walking is slower than a TLB hit.2
• Context switches may require flushing or tagging entries, introducing design complexity.2
• The TLB does not eliminate page faults; it only accelerates translation for pages that are already mapped and resident.2

Thus, the TLB should be understood as a high-speed translation cache that optimizes paging, not as a replacement for the page table itself.2

Footnotes

1. Translation lookaside buffer - Wikipedia - Overview of TLB purpose, hits, misses, and its role in reducing paging overhead. ↩ ↩²

2. Faster Translations (TLBs) - OSTEP PDF - Detailed academic treatment of TLBs, address translation, misses, and context-switch issues. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

3. Lecture 18 Virtual Memory 2 - MIT PDF - Hardware-oriented notes on TLB design, ASIDs, hardware page walks, and page faults. ↩ ↩² ↩³

4. Virtual Memory and Page Tables - University of Pennsylvania PDF - Lecture notes explaining TLB locality, small associative structures, and MMU refill behavior. ↩

5. Translation Lookaside Buffer | TLB | Paging | Gate Vidyalay - Concise explanation of paging with TLB, hit/miss behavior, and update process. ↩