Page Fault | Operating System - Computer Science Engineering (CSE) PDF Download

Page Fault Handling in Operating System

A page fault occurs when a program attempts to access data or code that is in its address space, but is not currently located in the system RAM. So when page fault occurs then following sequence of events happens :

• The computer hardware traps to the kernel and program counter (PC) is saved on the stack. Current instruction state information is saved in CPU registers.
• An assembly program is started to save the general registers and other volatile information to keep the OS from destroying it.
• Operating system finds that a page fault has occurred and tries to find out which virtual page is needed. Some times hardware register contains this required information. If not, the operating system must retrieve PC, fetch instruction and find out what it was doing when the fault occurred.
• Once virtual address caused page fault is known, system checks to see if address is valid and checks if there is no protection access problem.
• If the virtual address is valid, the system checks to see if a page frame is free. If no frames are free, the page replacement algorithm is run to remove a page.
• If frame selected is dirty, page is scheduled for transfer to disk, context switch takes place, fault process is suspended and another process is made to run until disk transfer is completed.
• As soon as page frame is clean, operating system looks up disk address where needed page is, schedules disk operation to bring it in.
• When disk interrupt indicates page has arrived, page tables are updated to reflect its position, and frame marked as being in normal state.
• Faulting instruction is backed up to state it had when it began and PC is reset. Faulting is scheduled, operating system returns to routine that called it.
• Assembly Routine reloads register and other state information, returns to user space to continue execution.

Page Replacement Algorithms in Operating Systems

In an operating system that uses paging for memory management, a page replacement algorithm is needed to decide which page needs to be replaced when new page comes in.

Page Fault: A page fault happens when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory.
Since actual physical memory is much smaller than virtual memory, page faults happen. In case of page fault, Operating System might have to replace one of the existing pages with the newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to reduce the number of page faults.

Page Replacement Algorithms:

• First In First Out (FIFO)
  This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
  Example-1Consider page reference string 1, 3, 0, 3, 5, 6 with 3 page frames. Find number of page faults.Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3 Page Faults.
  when 3 comes, it is already in  memory so —> 0 Page Faults.
  Then 5 comes, it is not available in  memory so it replaces the oldest page slot i.e 1. —>1 Page Fault.
  6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3 —>1 Page Fault.
  Finally when 3 come it is not avilable so it replaces 0 1 page fault
• Belady’s anomaly: Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.  For example, if we consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.
• Optimal Page replacement 
  In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.
  Example-2: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, with 4 page frame. Find number of page fault.
  Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
  0 is already there so —> 0 Page fault.
  when 3 came it will take the place of 7 because it is not used for the longest duration of time in the future.—>1 Page fault.
  0 is already there so —> 0 Page fault..
  4 will takes place of 1 —> 1 Page Fault.
  Now for the further page reference string —> 0 Page fault because they are already available in the memory.
  Optimal page replacement is perfect, but not possible in practice as the operating system cannot know future requests. The use of Optimal Page replacement is to set up a benchmark so that other replacement algorithms can be analyzed against it.
• Least Recently Used:
  In this algorithm page will be replaced which is least recently used.
  Example-3 Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 4 page frames. Find number of page faults.
  
  Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
  0 is already their so —> 0 Page fault.
  when 3 came it will take the place of 7 because it is least recently used —>1 Page fault 
  0 is already in memory so —> 0 Page fault.
  4 will takes place of 1 —> 1 Page Fault
  Now for the further page reference string —> 0 Page fault because they are already available in the memory.