Translation Lookaside Buffer (TLB) in Operating Systems - Step-by-Step Execution

Concept Flow - Translation Lookaside Buffer (TLB)

CPU issues virtual address

↓

Check TLB for virtual address

↓

Use physical [Access page table

↓

Page table lookup

↓

Update TLB with new entry

↓

Use physical address

↓

Access memory

The CPU sends a virtual address which the TLB checks first. If the address is found (hit), it uses the physical address directly. If not (miss), it looks up the page table, updates the TLB, then accesses memory.

Execution Sample

Operating Systems

CPU requests virtual address VA
Check TLB for VA
If hit: use physical address PA
Else: lookup page table
Update TLB with PA
Access memory at PA

This sequence shows how a virtual address is translated to a physical address using the TLB and page table.

Analysis Table

Step	Action	TLB Check Result	Page Table Lookup	TLB Update	Physical Address Used
1	CPU requests VA=0x1A3	Check TLB for 0x1A3	No entry found	Add entry VA=0x1A3 -> PA=0x3F7	Use PA=0x3F7
2	CPU requests VA=0x1A3 again	TLB hit for 0x1A3	No lookup needed	No update	Use PA=0x3F7
3	CPU requests VA=0x2B4	Check TLB for 0x2B4	No entry found	Add entry VA=0x2B4 -> PA=0x4C2	Use PA=0x4C2
4	CPU requests VA=0x1A3	TLB hit for 0x1A3	No lookup needed	No update	Use PA=0x3F7
5	CPU requests VA=0x3D9	Check TLB for 0x3D9	No entry found	Add entry VA=0x3D9 -> PA=0x5E1	Use PA=0x5E1
6	CPU requests VA=0x2B4	TLB hit for 0x2B4	No lookup needed	No update	Use PA=0x4C2
7	CPU requests VA=0x7FF	Check TLB for 0x7FF	No entry found	Add entry VA=0x7FF -> PA=0x9AB	Use PA=0x9AB
8	CPU requests VA=0x1A3	TLB hit for 0x1A3	No lookup needed	No update	Use PA=0x3F7
9	CPU requests VA=0xFFFF	Check TLB for 0xFFFF	No entry found	Add entry VA=0xFFFF -> PA=0x1234	Use PA=0x1234
10	CPU requests VA=0x1A3	TLB hit for 0x1A3	No lookup needed	No update	Use PA=0x3F7
Exit	No more requests	-	-	-	-

💡 Execution stops as there are no more virtual address requests.

State Tracker

Variable	Start	After 1	After 3	After 5	After 7	After 9	Final
TLB Entries	Empty	{0x1A3->0x3F7}	{0x1A3->0x3F7, 0x2B4->0x4C2}	{0x1A3->0x3F7, 0x2B4->0x4C2, 0x3D9->0x5E1}	{0x1A3->0x3F7, 0x2B4->0x4C2, 0x3D9->0x5E1, 0x7FF->0x9AB}	{0x1A3->0x3F7, 0x2B4->0x4C2, 0x3D9->0x5E1, 0x7FF->0x9AB, 0xFFFF->0x1234}	{0x1A3->0x3F7, 0x2B4->0x4C2, 0x3D9->0x5E1, 0x7FF->0x9AB, 0xFFFF->0x1234}
Last PA Used	None	0x3F7	0x4C2	0x5E1	0x9AB	0x1234	0x3F7

Key Insights - 3 Insights

Why does the CPU sometimes need to check the page table even though the TLB exists?

When the TLB does not have the virtual address entry (a miss), the CPU must look up the page table to find the physical address, as shown in steps 1, 3, 5, 7, and 9 in the execution_table.

Does the TLB update every time the CPU requests a virtual address?

No, the TLB only updates when there is a miss. On hits, it uses the existing entry without updating, as seen in steps 2, 4, 6, 8, and 10.

What happens if the TLB is full and a new entry needs to be added?

Though not shown in this trace, typically the TLB replaces an old entry using a replacement policy (like LRU) to add the new entry.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What happens when the CPU requests VA=0x2B4?

A TLB hit and physical address used directly

B No TLB check, direct page table access

C TLB miss, page table lookup, TLB updated, then physical address used

D CPU waits for memory access without translation

💡 Hint

Refer to row 3 in execution_table showing TLB miss and update.

According to variable_tracker, what is the state of TLB entries after step 5?

A Entries for VA=0x1A3, VA=0x2B4, and VA=0x3D9

B Entries for VA=0x1A3 and VA=0x2B4 only

C Only one entry for VA=0x1A3

D TLB is empty

💡 Hint

Check the TLB Entries row after After 5 column in variable_tracker.

At which step does the CPU first use the physical address 0x3F7 from the TLB without a page table lookup?

A Step 1

B Step 2

C Step 4

D Step 10

💡 Hint

Look for TLB hit with no page table lookup in execution_table.

Concept Snapshot

Translation Lookaside Buffer (TLB):
- A small fast cache in the CPU for virtual-to-physical address mappings.
- On a virtual address request, CPU checks TLB first.
- If TLB hit: use physical address immediately.
- If TLB miss: consult page table, update TLB, then use physical address.
- Speeds up memory access by avoiding slow page table lookups.

Full Transcript

The Translation Lookaside Buffer (TLB) is a small, fast cache inside the CPU that stores recent virtual address to physical address translations. When the CPU requests a virtual address, it first checks the TLB. If the address is found (a hit), the CPU uses the physical address from the TLB directly, speeding up memory access. If the address is not found (a miss), the CPU looks up the page table in memory to find the physical address, updates the TLB with this new mapping, and then accesses memory. This process repeats for each virtual address request, with the TLB helping to reduce the number of slow page table lookups. The execution table shows step-by-step how the CPU handles virtual addresses, when it hits or misses the TLB, and how the TLB updates over time.

Practice

1. What is the primary purpose of the Translation Lookaside Buffer (TLB) in an operating system?

easy

A. To store user data temporarily

B. To speed up virtual to physical address translation

C. To manage file system permissions

D. To handle network packet routing

Solution

1. Step 1: Understand the role of TLB

   The TLB is a cache used specifically for address translation in memory management.

2. Step 2: Identify its main function

   It speeds up the process of converting virtual addresses to physical addresses by caching recent translations.

3. Final Answer:

   To speed up virtual to physical address translation -> Option B

4. Quick Check:

   TLB = Speed up address translation [OK]

Hint: TLB caches address translations to speed memory access [OK]

Common Mistakes:

• Confusing TLB with general data cache
• Thinking TLB manages files or network
• Assuming TLB stores user data

2. Which of the following best describes the correct function of a TLB entry?

easy

A. Mapping a virtual page number to a physical frame number

B. Storing the contents of a physical memory page

C. Holding the process ID of the current running process

D. Tracking the number of page faults

Solution

1. Step 1: Identify what a TLB entry stores

   A TLB entry holds the mapping between virtual page numbers and physical frame numbers.

2. Step 2: Exclude unrelated functions

   It does not store page contents, process IDs, or page fault counts.

3. Final Answer:

   Mapping a virtual page number to a physical frame number -> Option A

4. Quick Check:

   TLB entry = virtual to physical mapping [OK]

Hint: TLB entries map virtual pages to physical frames [OK]

Common Mistakes:

• Confusing TLB entry with memory content storage
• Mixing TLB with process management data
• Assuming TLB tracks page faults

3. Consider a system where the TLB has 4 entries and uses a Least Recently Used (LRU) replacement policy. The TLB currently holds mappings for virtual pages 1, 2, 3, and 4. If the CPU accesses virtual pages in this order: 2, 5, 1, 6, which virtual page mapping will be removed from the TLB after these accesses?

medium

A. Virtual page 4

B. Virtual page 2

C. Virtual page 3

D. Virtual page 1

Solution

1. Step 1: Track TLB entries and accesses

   Initial TLB: pages 1, 2, 3, 4. Access order: 2 (hit), 5 (miss), 1 (hit), 6 (miss).

2. Step 2: Apply LRU replacement on misses

   Access 2: hit, update usage. Access 5: miss, replace least recently used page (which is 3). Access 1: hit, update usage. Access 6: miss, replace least recently used page (which is 4).

3. Final Answer:

   Virtual page 3 -> Option C

4. Quick Check:

   LRU removes least recently used page = 3 [OK]

Hint: LRU removes least recently used page on TLB miss [OK]

Common Mistakes:

• Forgetting to update usage on hits
• Replacing wrong page on miss
• Confusing LRU with FIFO replacement

4. A programmer notices frequent TLB misses causing slow memory access. Which of the following changes would most likely reduce TLB misses?

medium

A. Increasing the size of the TLB cache

B. Reducing the size of physical memory

C. Disabling virtual memory

D. Increasing the CPU clock speed

Solution

1. Step 1: Understand cause of TLB misses

   TLB misses happen when the needed virtual-to-physical mapping is not in the TLB cache.

2. Step 2: Identify effective solution

   Increasing TLB size allows more mappings to be cached, reducing misses. Other options do not directly reduce TLB misses.

3. Final Answer:

   Increasing the size of the TLB cache -> Option A

4. Quick Check:

   Bigger TLB = fewer misses [OK]

Hint: Bigger TLB cache reduces misses [OK]

Common Mistakes:

• Thinking CPU speed affects TLB misses directly
• Assuming disabling virtual memory helps
• Reducing physical memory size worsens performance

5. In a system with a two-level page table and a TLB, which of the following best explains how the TLB improves memory access time during address translation?

hard

A. By storing the entire page table in fast memory

B. By increasing the size of physical memory

C. By eliminating the need for virtual memory

D. By caching the final physical frame number, avoiding both page table levels on hits

Solution

1. Step 1: Understand two-level page table translation

   Two-level page tables require two memory accesses to find the physical frame number.

2. Step 2: Role of TLB in this process

   The TLB caches the final physical frame number for virtual pages, so on a hit, the system skips both page table lookups, speeding access.

3. Final Answer:

   By caching the final physical frame number, avoiding both page table levels on hits -> Option D

4. Quick Check:

   TLB caches final frame number, skips page tables [OK]

Hint: TLB caches final frame number, skipping page tables [OK]

Common Mistakes:

• Thinking TLB stores entire page tables
• Assuming TLB removes virtual memory need
• Confusing TLB with physical memory size