1. Introduction
In a paging system, every memory reference requires address translation before the actual data can be accessed.
Without any optimization, each memory access involves:
Accessing the page table to obtain the frame number
Accessing the desired memory location
This effectively doubles memory access time.
To reduce this overhead, modern operating systems use a specialized hardware cache called the Translation Lookaside Buffer (TLB).
2. What is a TLB?
A Translation Lookaside Buffer (TLB) is a small, high-speed associative memory that stores recently used page table entries.
Its purpose is to speed up the translation of logical addresses into physical addresses.
Key Idea
Page Number
↓
TLB Lookup
↓
Frame Number
Instead of accessing the page table in memory every time, the processor first checks the TLB.
3. Why is TLB Needed?
Without a TLB:
CPU
↓
Page Table Access
↓
Memory Access
Two memory accesses are required.
With a TLB:
CPU
↓
TLB
↓
Memory Access
Only one memory access is needed if the page table entry is found in the TLB.
4. Structure of a TLB
A TLB stores recent mappings:
| Page Number | Frame Number |
|---|---|
| 0 | 5 |
| 1 | 2 |
| 2 | 8 |
| 3 | 1 |
Each entry may also contain:
Valid bit
Protection bits
Dirty bit
Reference bit
5. Working of TLB
When the CPU generates a logical address:
(Page Number, Offset)
the following steps occur:
Search the TLB using the page number
If found, obtain frame number immediately
If not found, access page table
Update TLB
Access memory
6. TLB Hit
A TLB Hit occurs when the requested page number is present in the TLB.
Process
CPU
↓
TLB
↓ (Found)
Frame Number
↓
Memory Access
Example
Logical Address:
Page = 2
Offset = 100
TLB contains:
Page 2 → Frame 8
Physical Address:
(Frame 8, Offset 100)
No page table lookup is required.
7. TLB Miss
A TLB Miss occurs when the page number is not present in the TLB.
Process
CPU
↓
TLB
↓ (Not Found)
Page Table
↓
Frame Number
↓
Update TLB
↓
Memory Access
Example
Logical Address:
Page = 5
Offset = 50
Page 5 is not in TLB.
The system:
Accesses page table
Finds frame number
Updates TLB
Accesses memory
8. TLB Hit vs TLB Miss
| Case | Operations Required |
|---|---|
| TLB Hit | Memory Access Only |
| TLB Miss | Page Table Access + Memory Access |
| Case | Memory Accesses |
|---|---|
| TLB Hit | 1 |
| TLB Miss | 2 |
Key Insight
The effectiveness of a TLB depends on how frequently hits occur.
9. Address Translation Using TLB
Logical Address:
Page Number + Offset
Translation Process:
Page Number
↓
TLB
↓
Frame Number
↓
Physical Address
(Frame Number + Offset)
The offset remains unchanged during translation.
10. TLB Hit Ratio
The Hit Ratio (h) represents the probability that a requested page mapping is found in the TLB.
Hit Ratio = Number of TLB Hits
------------------
Total References
Example:
80 hits out of 100 accesses
Then:
Hit Ratio = 0.8
or
80%
11. Effective Access Time (EAT)
The performance benefit of a TLB is measured using Effective Access Time (EAT).
Formula
EAT = (Hit Ratio × Memory Access Time)
+ (Miss Ratio × 2 × Memory Access Time)
where:
Miss Ratio = 1 − Hit Ratio
12. Numerical Example
Given
Memory Access Time = 100 ns
Hit Ratio = 0.8
Step 1
Calculate miss ratio:
Miss Ratio = 1 − 0.8
= 0.2
Step 2
Apply formula:
EAT = (0.8 × 100)
+ (0.2 × 200)
= 80 + 40
= 120 ns
Final Answer
Effective Access Time = 120 ns
13. Comparison Without TLB
Without TLB:
Page Table Access = 100 ns
Memory Access = 100 ns
Total = 200 ns
With TLB:
EAT = 120 ns
Improvement:
200 − 120 = 80 ns
This shows why TLBs are critical in modern systems.
14. Why TLB Works So Well
TLBs rely on the principle of Locality of Reference.
Programs tend to:
Reuse the same pages repeatedly
Access nearby memory locations
As a result:
High TLB Hit Rate
↓
Fast Translation
↓
Better Performance
15. Types of Locality
Temporal Locality
Recently used pages are likely to be used again.
Example:
for(i=0;i<100;i++)
sum += A[i];
The same code pages are accessed repeatedly.
Spatial Locality
Nearby addresses are likely to be accessed soon.
Example:
A[1], A[2], A[3], A[4]
These often lie within the same page.
16. TLB Characteristics
Very Fast
Implemented using associative memory.
Small
Usually contains a few dozen to a few thousand entries.
Hardware-Based
Located inside or very close to the CPU.
Expensive
Uses high-speed memory technology.
17. Associative Memory
Unlike ordinary memory:
Index → Data
Associative memory works as:
Search Key → Matching Entry
Example:
Search: Page 2
TLB immediately returns:
Frame 8
This enables extremely fast lookup.
18. TLB and Paging
Normal Paging:
CPU
↓
Page Table
↓
Memory
Paging with TLB:
CPU
↓
TLB
↓
Memory
The page table still exists.
The TLB merely caches frequently used entries.
19. TLB vs Cache
| Feature | TLB | Cache |
|---|---|---|
| Stores | Page Table Entries | Actual Data |
| Purpose | Address Translation | Faster Data Access |
| Size | Very Small | Larger |
| Location | MMU/CPU | CPU |
| Accessed Before | Memory Access | Data Access |
Key Difference
TLB caches addresses
Cache stores data
20. Advantages of TLB
Faster Address Translation
Reduces lookup overhead.
Improved Performance
Lowers effective memory access time.
Essential for Virtual Memory
Makes paging practical.
Exploits Locality
Achieves high hit rates.
21. Disadvantages of TLB
Hardware Cost
Requires specialized memory.
Limited Size
Cannot store all page mappings.
Miss Penalty
A miss requires page table access.
Additional Complexity
Needs replacement policies and management.
22. Real-World Analogy
Imagine a large phone directory.
Without a TLB:
Search directory every time
With a TLB:
Keep frequently used contacts
in a favorites list
Finding contacts becomes much faster.
Most Important Point
The TLB is a high-speed cache for page table entries that significantly improves paging performance by reducing the number of memory accesses required for address translation.