Operating systems

Paging: Faster translations

Prashanth L.A.

2023-09-12

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?

TLB algorithm in words

Check TLB for PTE

TLB Hit

TLB Miss

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