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.