§19.1–19.2TLB Basic Algorithm … Example: Accessing An Array

Paging’s extra memory reference — before every fetch, load, and store — is prohibitively slow. Time to make the common case fast.

Help comes from the OS’s old friend, the hardware: a translation-lookaside buffer (TLB) tlb Translation-lookaside buffer: a small, fast, fully-associative cache of VPN→PFN translations inside the MMU, checked before the page table on every reference — the hardware that 'in a real sense makes virtual memory possible'. defined in ch. 19 — open in glossary — part of the MMU, and simply a hardware cache of popular virtual-to-physical translations (a better name would be address-translation cache). On every reference the hardware checks the TLB first; only when the translation is absent does anyone touch the page table. TLBs, in a real sense, make virtual memory possible.

19.1 TLB Basic Algorithm

The hardware’s control flow (linear page table, hardware-managed TLB — Figure 19.1):

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)    // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else                    // TLB Miss
    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
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()

A hit tlb hit The desired translation is already in the TLB: the physical address forms in a few cycles with no page-table access — the common case everything is designed around. defined in ch. 19 — open in glossary forms the physical address in a few cycles — the TLB sits right next to the core. A miss tlb miss The translation is absent: the page table must be consulted (extra memory reference or worse), the TLB updated, and the instruction retried — the retry then hits. defined in ch. 19 — open in glossary pays the old price (the page-table access, an extra memory reference or more), installs the translation, and retries the instruction — which now hits. The premise, as with all caches: misses are rare, hits are the common case.

19.2 Example: Accessing An Array

Ten 4-byte integers at virtual address 100, in an 8-bit address space with 16-byte pages (4-bit VPN, 4-bit offset):

Now run for (i = 0; i < 10; i++) sum += a[i]; against a cold TLB — counting only the array accesses:

miss, hit, hit, miss, hit, hit, hit, miss, hit, hit — a 70% hit rate on the very first pass, thanks to spatial locality spatial locality After touching address x, nearby addresses are likely next (array streaming, sequential code). defined in ch. 10 — open in glossary : array elements pack tightly onto pages, so only the first touch of each page misses. Doubling the page size would halve the misses; with realistic 4KB pages, dense array code misses roughly once per thousand accesses. And if the program loops over the array again soon after? Ten hits out of ten — temporal locality temporal locality Data accessed now is likely accessed again soon (loop variables, instructions). defined in ch. 10 — open in glossary , the quick re-reference of recently-used items.