TLB - Translation Lookaside Buffer & Effective Access Time

▶

Steps

setup

Initialize Simulation

Initialize the simulation with a list of memory accesses to translate. The TLB is empty, and no accesses have started yet.

💡 Starting with an empty TLB and all accesses queued shows the baseline before any translation occurs.

Line:

tlb = {}
memory_accesses = [0x1A3, 0x1A4, 0x2B7]
current_time = 0

💡 The simulation begins with no cached translations, so the first accesses will miss the TLB.

traverse

Start First Memory Access Translation

The first memory access (0x1A3) is selected from the ready queue and starts running to check the TLB.

💡 Processing accesses one by one simulates how the CPU handles address translation sequentially.

Line:

current_access = memory_accesses.pop(0)
active_pid = 1

💡 The first access begins translation, allowing us to observe TLB lookup and possible miss.

compare

Check TLB for First Access (Miss)

Check if the page number for address 0x1A3 is in the TLB. It is not found, resulting in a TLB miss.

💡 A miss means the translation must be fetched from the page table, which is slower.

Line:

if page_number not in tlb:
    tlb_miss = True

💡 TLB misses cause additional delay due to page table lookup.

traverse

Perform Page Table Lookup for First Access

The process waits for the page table lookup to complete, simulating the longer access time.

💡 Page table lookup is slower and blocks the process until translation is found.

Line:

page_table_access_time = 100
wait(page_table_access_time)

💡 Waiting models the delay caused by accessing main memory page tables.

insert

Complete Page Table Lookup and Update TLB

Page table lookup completes; the translation is added to the TLB cache for faster future access.

💡 Updating the TLB after a miss caches the translation to speed up subsequent accesses.

Line:

tlb[page_number] = frame_number
process.state = 'ready'

💡 Caching translations reduces future lookup times.

compare

Resume First Access Translation (TLB Hit Now)

The first access resumes and checks the TLB again, this time finding the translation (TLB hit).

💡 A hit means the translation is found quickly, avoiding page table lookup delay.

Line:

if page_number in tlb:
    tlb_hit = True

💡 TLB hits drastically reduce access time.

traverse

Complete First Access Translation

The first access completes translation and finishes execution, freeing the CPU for the next access.

💡 Completing the access allows the simulation to proceed to the next memory request.

Line:

process.state = 'terminated'

💡 Each access completes after translation, simulating sequential CPU processing.

traverse

Start Second Memory Access Translation

The second memory access (0x1A4) starts running and checks the TLB for translation.

💡 Processing the next access continues the simulation of multiple translations.

Line:

active_pid = 2
process.state = 'running'

💡 Sequential processing models real CPU behavior.

compare

Check TLB for Second Access (Hit)

The TLB contains the translation for page number 0x1A, so the second access results in a TLB hit.

💡 A hit means the translation is found quickly, avoiding page table lookup delay.

Line:

if page_number in tlb:
    tlb_hit = True

💡 Repeated accesses to the same page benefit from cached translations.

traverse

Complete Second Access Translation

The second access completes translation and terminates, freeing the CPU for the next access.

💡 Completing the access allows the simulation to proceed to the next memory request.

Line:

process.state = 'terminated'

💡 Each access completes after translation, simulating sequential CPU processing.

traverse

Start Third Memory Access Translation

The third memory access (0x2B7) starts running and checks the TLB for translation.

💡 Processing the next access continues the simulation of multiple translations.

Line:

active_pid = 3
process.state = 'running'

💡 Sequential processing models real CPU behavior.

compare

Check TLB for Third Access (Miss)

The TLB does not contain the translation for page number 0x2B, resulting in a TLB miss.

💡 A miss means the translation must be fetched from the page table, which is slower.

Line:

if page_number not in tlb:
    tlb_miss = True

💡 TLB misses cause additional delay due to page table lookup.

traverse

Perform Page Table Lookup for Third Access

The process waits for the page table lookup to complete, simulating the longer access time.

💡 Page table lookup is slower and blocks the process until translation is found.

Line:

wait(page_table_access_time)

💡 Waiting models the delay caused by accessing main memory page tables.

insert

Complete Page Table Lookup and Update TLB for Third Access

Page table lookup completes; the translation is added to the TLB cache for faster future access.

💡 Updating the TLB after a miss caches the translation to speed up subsequent accesses.

Line:

tlb[page_number] = frame_number
process.state = 'ready'

💡 Caching translations reduces future lookup times.

compare

Resume Third Access Translation (TLB Hit Now)

The third access resumes and checks the TLB again, this time finding the translation (TLB hit).

💡 A hit means the translation is found quickly, avoiding page table lookup delay.

Line:

if page_number in tlb:
    tlb_hit = True

💡 TLB hits drastically reduce access time.

traverse

Complete Third Access Translation

The third access completes translation and terminates, ending the simulation of all memory accesses.

💡 Completing the last access concludes the simulation.

Line:

process.state = 'terminated'

💡 All accesses have been processed sequentially with TLB hits and misses.

reconstruct

Calculate Effective Access Time

Calculate the effective access time using the formula: EAT = (hit ratio * TLB access time) + (miss ratio * (TLB access time + page table access time + memory access time)).

💡 This calculation summarizes the overall performance impact of TLB hits and misses.

Line:

EAT = hit_ratio * tlb_time + miss_ratio * (tlb_time + page_table_time + memory_time)

💡 Effective access time quantifies the average memory access delay considering TLB behavior.

tlb = {}
memory_accesses = [0x1A3, 0x1A4, 0x2B7]
tlb_time = 1  # TLB access time
page_table_time = 100  # Page table access time
memory_time = 1  # Memory access time

current_time = 0

# STEP 1: Initialize simulation
for i, address in enumerate(memory_accesses):
    pid = i + 1
    # STEP 2: Start translation
    page_number = address >> 4  # example page number extraction
    if page_number not in tlb:
        # STEP 3: TLB miss
        # STEP 4: Wait for page table lookup
        current_time += page_table_time
        # STEP 5: Update TLB
        tlb[page_number] = 'frame'
    # STEP 6: TLB hit
    current_time += tlb_time + memory_time
    # STEP 7: Complete translation

# STEP 17: Calculate Effective Access Time
hit_ratio = 2/3
miss_ratio = 1/3
EAT = hit_ratio * tlb_time + miss_ratio * (tlb_time + page_table_time + memory_time)

📊

TLB - Translation Lookaside Buffer & Effective Access Time - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the TLB cache speeds up address translation and how misses affect performance, which is difficult to grasp from code alone.

Transition none → ready pid:1 - initialization

1

ready

2

ready

3

ready

Ready Queue

123

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:1 - start translation

1

running

2

ready

3

ready

Ready Queue

23

Waiting Queue

empty

🖥CPU1t=1

idle

Transition running → waiting pid:1 - TLB miss, page table lookup needed

1

waiting

2

ready

3

ready

Ready Queue

23

Waiting Queue

1 (page_table_lookup)

🖥CPU1t=2

1

Transition waiting → waiting pid:1 - page table lookup in progress

1

waiting

burst: 100

2

ready

3

ready

Ready Queue

23

Waiting Queue

1 (page_table_lookup)

🖥CPUidlet=3

idle

Transition waiting → ready pid:1 - page table lookup complete, TLB updated

1

ready

2

ready

3

ready

Ready Queue

123

Waiting Queue

empty

🖥CPUidlet=103

idle

Transition ready → running pid:1 - TLB hit, fast translation

1

running

2

ready

3

ready

Ready Queue

23

Waiting Queue

empty

🖥CPU1t=104

1

Transition running → terminated pid:1 - translation complete

1

terminated

2

ready

3

ready

Ready Queue

23

Waiting Queue

empty

🖥CPUidlet=105

1

Transition ready → running pid:2 - start translation

1

terminated

2

running

3

ready

Ready Queue

3

Waiting Queue

empty

🖥CPU2t=106

2

Transition running → running pid:2 - TLB hit

1

terminated

2

running

3

ready

Ready Queue

3

Waiting Queue

empty

🖥CPU2t=107

2

Transition running → terminated pid:2 - translation complete

1

terminated

2

terminated

3

ready

Ready Queue

3

Waiting Queue

empty

🖥CPUidlet=108

2

Transition ready → running pid:3 - start translation

1

terminated

2

terminated

3

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU3t=109

3

Transition running → waiting pid:3 - TLB miss, page table lookup needed

1

terminated

2

terminated

3

waiting

Ready Queue

empty

Waiting Queue

3 (page_table_lookup)

🖥CPU3t=110

3

Transition waiting → waiting pid:3 - page table lookup in progress

1

terminated

burst: 100

2

terminated

3

waiting

burst: 100

Ready Queue

empty

Waiting Queue

3 (page_table_lookup)

🖥CPUidlet=111

idle

Transition waiting → ready pid:3 - page table lookup complete, TLB updated

1

terminated

2

terminated

3

ready

Ready Queue

3

Waiting Queue

empty

🖥CPUidlet=211

idle

Transition ready → running pid:3 - TLB hit, fast translation

1

terminated

2

terminated

3

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU3t=212

3

Transition running → terminated pid:3 - translation complete

1

terminated

2

terminated

3

terminated

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=213

3

Transition terminated → terminated - calculated effective access time

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=213

idle

Key Takeaways

✓ TLB hits significantly reduce memory access time by avoiding slow page table lookups.

This speedup is hard to see from code alone because it depends on runtime cache state and hit/miss patterns.

✓ TLB misses cause the process to wait for page table lookup, which adds substantial delay.

Visualizing the waiting state clarifies why misses are costly.

✓ The effective access time formula combines hit ratio and miss penalty to quantify average performance.

Seeing the formula applied after the simulation connects theory to practice.

Practice

1. Trace the sequence of events when a user program invokes a system call to read a file. Which step happens immediately after the CPU switches to kernel mode?

easy

A. The kernel verifies the system call number and arguments

B. The hardware raises an interrupt to the device

C. The user program resumes execution in user mode

D. The kernel copies data directly to the user buffer without validation

Solution

1. Step 1: User program issues system call

   The user program executes a special instruction causing a trap to kernel mode.

2. Step 2: CPU switches to kernel mode

   Control transfers to the OS kernel with elevated privileges.

3. Step 3: Kernel validates system call

   The kernel inspects the system call number and arguments to ensure they are valid and safe.

4. Step 4: Why other options are incorrect

   The kernel copies data directly to the user buffer without validation is unsafe; kernel must validate before copying data. The user program resumes execution in user mode happens after system call completion, not immediately after mode switch. The hardware raises an interrupt to the device is unrelated here; hardware interrupts occur asynchronously, not immediately after mode switch.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   System call trap -> kernel mode -> validate call -> execute service [OK]

Hint: Kernel validates system call immediately after mode switch

Common Mistakes:

• Assuming kernel copies data before validation
• Confusing interrupt handling with system call flow
• Thinking user mode resumes immediately after trap

2. Which of the following statements about the LRU page replacement algorithm's complexity and implementation is TRUE?

medium

A. LRU requires hardware support or additional data structures to track usage efficiently

B. LRU can be implemented with O(1) time complexity per page reference using a stack

C. LRU always performs better than FIFO regardless of workload

D. LRU does not require any extra space beyond the page frames

Solution

1. Step 1: Analyze LRU Implementation Complexity

   LRU needs to track the order of page usage, which is costly without hardware or data structures.

2. Step 2: Evaluate Each Option

   LRU requires hardware support or additional data structures to track usage efficiently is true; LRU requires hardware support or additional data structures to track usage efficiently.
   LRU can be implemented with O(1) time complexity per page reference using a stack is false; a stack alone cannot provide O(1) updates on every reference.
   LRU always performs better than FIFO regardless of workload is false; LRU can perform worse than FIFO in some workloads (e.g., scan patterns).
   LRU does not require any extra space beyond the page frames is false; LRU requires extra space for tracking usage metadata.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Efficient LRU needs support beyond just frames.

Hint: LRU needs extra tracking structures or hardware support [OK]

Common Mistakes:

• Assuming LRU is always better than FIFO
• Believing LRU can be done with no extra space
• Thinking a simple stack suffices for O(1) LRU

3. If a process requests resources that would keep the system in a safe state but the system is currently in an unsafe state, what does the Banker's Algorithm do and why?

hard

A. It denies the request because the system must always remain in a safe state, and starting from an unsafe state invalidates the algorithm's assumptions.

B. It restarts the system to reset resource allocations and ensure safety.

C. It preempts resources from other processes to restore a safe state before granting the request.

D. It grants the request because the immediate allocation is safe, ignoring the current unsafe state.

Solution

1. Step 1: Recall Banker's Algorithm assumptions

   The algorithm assumes the system starts in a safe state to guarantee deadlock avoidance.

2. Step 2: Analyze the scenario

   If the system is already unsafe, granting requests--even if individually safe--cannot guarantee overall safety.

3. Step 3: Evaluate options

   A ignores the unsafe starting state.
   B and C describe actions outside the algorithm's scope.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Banker's Algorithm cannot recover from unsafe states; it only avoids entering them.

Hint: Banker's Algorithm requires starting safe state to function correctly [OK]

Common Mistakes:

• Assuming safe requests can fix unsafe states
• Believing the algorithm preempts resources
• Thinking system restarts are part of the algorithm

4. If the Dining Philosophers problem is extended to allow philosophers to pick up forks in any order but with a timeout mechanism to release held forks after waiting too long, what is a potential downside of this approach?

hard

A. It completely eliminates deadlock and starvation without any performance penalty

B. It may cause livelock where philosophers repeatedly pick up and release forks without eating

C. It guarantees fairness by enforcing strict turn-taking among philosophers

D. It simplifies synchronization by removing the need for semaphores or locks

Solution

1. Step 1: Understand timeout-based fork release

   Philosophers release forks if waiting too long, preventing indefinite blocking.

2. Step 2: Analyze consequences

   This can cause livelock, where philosophers continuously pick up and release forks without making progress.

3. Step 3: Evaluate other options

   It completely eliminates deadlock and starvation without any performance penalty is false because performance penalties and livelock can occur; It simplifies synchronization by removing the need for semaphores or locks is false as synchronization primitives are still needed; It guarantees fairness by enforcing strict turn-taking among philosophers is false as fairness is not guaranteed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Timeouts prevent deadlock but risk livelock due to repeated retries.

Hint: Timeouts prevent deadlock but can cause livelock [OK]

Common Mistakes:

• Assuming timeouts solve all synchronization issues
• Confusing livelock with deadlock
• Believing fairness is guaranteed by timeouts

5. If the time quantum is set equal to the longest CPU burst among all processes in Round Robin scheduling, what is the expected impact on turnaround time and fairness?

hard

A. Both turnaround time and fairness improve because processes get longer uninterrupted CPU bursts

B. Turnaround time approaches that of First-Come-First-Serve scheduling, but fairness among processes decreases

C. Fairness remains the same but turnaround time increases due to longer waiting times

D. Turnaround time decreases significantly and fairness improves due to fewer context switches

Solution

1. Step 1: Understand quantum equal to longest burst

   Setting quantum to longest burst means processes run mostly to completion without preemption.

2. Step 2: Compare to FCFS

   This behavior mimics FCFS, where processes run in arrival order without interruption.

3. Step 3: Analyze fairness and turnaround

   Fairness decreases because shorter processes wait longer, losing RR's time-sharing benefit. Turnaround time approaches FCFS values.

4. Step 4: Evaluate incorrect options

   Turnaround time decreases significantly and fairness improves due to fewer context switches is wrong because fewer context switches do not improve fairness. Fairness remains the same but turnaround time increases due to longer waiting times is wrong as fairness changes. Both turnaround time and fairness improve because processes get longer uninterrupted CPU bursts is wrong because fairness does not improve.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Quantum = longest burst -> RR ≈ FCFS -> fairness ↓, turnaround ~ FCFS.

Hint: Quantum = longest burst -> RR behaves like FCFS

Common Mistakes:

• Assuming fairness always improves with larger quantum
• Believing fewer context switches always reduce turnaround
• Ignoring that RR degenerates to FCFS with large quantum