Lecture 20

The crux

How can we speed up address translation, and generally avoid the 

extra memory reference that paging seems to require? 

What hardware support is required? What OS involvement is needed?

Solution: Translation-lookaside buffer aka TLB

TLB is part of MMU

Better name for TLB: Address traslation cache

What is TLB?

• Cache: Smaller, faster memory
• TLB contains popular PTEs to speed up translation
• Location: on-chip
• Upon each virtual memory reference, HW first checks TLB to see if the desired translation is held therein
• How many entries to store in TLB: 32, 64, 128, 256?
• TLB searches entries in parallel, i.e., TLB is associative

TLB algorithm in words

Check TLB for PTE

• Extract VPN from the virtual address
• Check if the TLB holds the translation for this VPN

TLB Hit

• Extract PFN, form PA
• Access PA

TLB Miss

• Access PT to get the PTE
• Add it to TLB
• Retry instruction

TLB algorithm: pseudocode

Check TLB for PTE

// extract VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// check if the TLB holds the translation for this VPN
(Success, TlbEntry) = TLB_Lookup(VPN)

TLB Hit

if (Success == True)   
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)

TLB Miss

  else    
    // HW accesses PT to find the translation
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if (PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else if (CanAccess(PTE.ProtectBits) == False)
        RaiseException(PROTECTION_FAULT)
    else
        // If mem ref is valid and accessible, add it to TLB
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()

Example: Accessing an array

• \(10\) \(4\)-byte integers in memory, starting at virtual address \(100\)
• \(8\)-bit virtual AS, with 16-byte pages \(\Rightarrow\) \(4\)-bit VPN, a \(4\)-bit offset

int sum = 0;
for (i = 0; i < 10; i++) {
sum += a[i]; 
}

Misses: ? Hits: ?

TLB hit rate: ?

Locality

• TLB improves performance due to spatial locality
  • The elements of the array are packed tightly into pages, and thus only the first access to an element on a page yields a TLB miss.

• Temporal Locality
  • the idea is that an instruction or data item that has been recently accessed will likely be re-accessed soon in the future
  • e.g. loop variables

Who Handles The TLB Miss?

• HW or OS?

Hardware

• HW handles the TLB miss on CISC (complex-instruction set computers)
  • HW has to know exactly where the page tables are located in memory.
  • HW walks the PT, finds the PTE and extracts the desired translation
  • e.g. Intel x86

OS

• RISC (reduced-instruction set computers) have software-managed TLB
• On a mem ref, HW extracts VPN from VA and checks TLB
• If hit, VPN\(\rightarrow\)PFN, fetch PA
• else raise TLBmiss exception
  • Trap to OS
    • Check PT for PTE
    • If valid, etc: extract PFN
    • Update TLB (privileged? special instruction?)
  • Return from trap

Who handles TLB miss: H/W or OS?

Why bother?

• H/W is simpler
• S/W is more flexible
• Aside: RISC vs CISC, read the book note

Lecture 21

TLB contents

• How many entries to store in TLB: 32, 64, 128, 256?
• TLB searches entries in parallel, i.e., TLB is associative

TLB entry

• Other
  • valid: Does this entry have valid info?
  • protection: Bits for prot check

TLB issue: Context switches

• Proc P1 is running, VPN 10 mapped to PFN 100
• OS switches to proc P2. VPN 10 of P2 mapped to PFN 170
• If entries for both processes were in the TLB,

Solutions

Flush

• Flush TLB on context switch
• H/W managed TLB: flush on PTBR change
• S/W managed TLB: need a privileged instruction
• Disadvantage: Lots of TLB misses when a proc starts running

ASID

• Address space identifier in TLB

• VPN	PFN	valid	prot	ASID
  10	100	1	rwx	1
  -	-	-	-	-
  10	170	1	rwx	2
  -	-	-	-	-

• How does H/W know ASID of current proc?