Page Fault Control Flow

Understand​ the page fault control flow in terms of both the hardware and software.

We'll cover the following

With all of this knowledge in place, we can now roughly sketch the complete control flow of memory access. In other words, when somebody asks you “what happens when a program fetches some data from memory?”, you should have a pretty good idea of all the different possibilities. See the control flow in the snippets provided in this lesson for more details; the first snippet shows what the hardware does during translation and the second, what the OS does upon a page fault.

Hardware control flow

From the hardware control flow diagram in the snippet below, notice that there are now three important cases to understand when a TLB miss occurs.

Press + to interact
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)
      // assuming hardware-managed TLB
      TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
      RetryInstruction()
    else if (PTE.Present == False)
        RaiseException(PAGE_FAULT)

First, that the page was both present and valid (Lines 18–21); in this case, the TLB miss handler can simply grab the PFN from the PTE, retry the instruction (this time resulting in a TLB hit), and thus continue as described (many times) before. In the second case (Lines 22–23), the page fault handler must be run; although this was a legitimate page for the process to access (it is valid, after all), it is not present in physical memory. Third (and finally), the access could be to an invalid page, due for example to a bug in the program (Lines 13–14). In this case, no other bits in the PTE really matter; the hardware traps this invalid access, and the OS trap handler runs, likely terminating the offending process.

Software control flow

From the software control flow in the snippet below, we can see what the OS roughly must do in order to service the page fault. First, the OS must find a physical frame for the soon-to-be-faulted-in page to reside within; if there is no such page, we’ll have to wait for the replacement algorithm to run and kick some pages out of memory, thus freeing them for use here.

Press + to interact
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

With a physical frame in hand, the handler then issues the I/O request to read in the page from swap space. Finally, when that slow operation completes, the OS updates the page table and retries the instruction. The retry will result in a TLB miss, and then, upon another retry, a TLB hit, at which point the hardware will be able to access the desired item.

Get hands-on with 1400+ tech skills courses.