§21.4–21.7What If Memory Is Full? … Summary

Servicing a fault assumed a free frame was waiting. Suppose none is.

21.4 What If Memory Is Full?

Then the OS must first page out one or more residents to make room — and choosing the victim is the page-replacement policy page-replacement policy The decision of WHICH page to kick out when memory is full. Choosing badly runs programs at disk speed — 10,000–100,000× slower — which is why it gets its own chapter. defined in ch. 21 — open in glossary , a decision with terrifying stakes: evict the wrong page and a program runs at disk-like speeds instead of memory-like speeds — 10,000 to 100,000× slower. That number is why the policy gets the entire next chapter; for now it’s enough that one exists, built on this chapter’s mechanisms.

21.5 Page Fault Control Flow

Everything the hardware can encounter on a reference, in one place — so when someone asks “what happens when a program fetches data from memory?”, you have the full answer. The hardware side (Figure 21.2):

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 if (PTE.Present == True)
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()
        else if (PTE.Present == False)
            RaiseException(PAGE_FAULT)

And the OS side — the handler itself, seven lines that carry the whole illusion (Figure 21.3):

PFN = FindFreePhysicalPage()
if (PFN == -1)              // no free page found
    PFN = EvictPage()       // run replacement algorithm
DiskRead(PTE.DiskAddr, PFN) // sleep (waiting for I/O)
PTE.present = True          // update page table with present
PTE.PFN     = PFN           // bit and translation (PFN)
RetryInstruction()          // retry instruction

21.6 When Replacements Really Occur

Waiting until memory is entirely full before evicting is a little unrealistic. Real systems keep a cushion, governed by high and low watermarks watermarks The high/low free-memory thresholds (HW/LW) governing proactive eviction: below LW the swap daemon wakes and frees pages until HW are available, so the fault path rarely has to evict synchronously. defined in ch. 21 — open in glossary and patrolled by a background thread — the swap daemon swap daemon The background thread (a.k.a. page daemon; 'daemon' via Multics from Maxwell's demon) that evicts pages when free memory dips below the low watermark, until the high watermark is restored — enabling clustered swap writes along the way. defined in ch. 21 — open in glossary :

21.7 Summary

More memory than physically exists: a present bit in the PTE, a page-fault handler that fetches from swap, and a policy (pending) for making room. The amazing part is that it all happens transparently — the process just accesses its private, contiguous virtual memory, never learning that its pages scatter across arbitrary frames or vanish to disk entirely. In the common case, a memory access is fast; in the worst case, one instruction takes multiple disk operations and many milliseconds — the hierarchy’s whole span, hidden inside a single load.