The page table lookup may also fail if the page is not resident in physical memory.
When physical memory is not full this is a simple operation; the page is written back into physical memory, the page table and TLB are updated, and the instruction is restarted.