Basic Concepts

• When a process is to be swapped in, the pager guesses which pages will be used before the process is swapped out again.
• It avoids reading into memory pages that will not be used anyway, decreasing the swap time and the amount of physical memory needed.
• Some form of hardware support is needed to distinguish between the pages that are in memory and the pages that are on the disk.
• The valid -invalid bit scheme can be used for this purpose.
  • This time however, when this bit is set to ``valid'', the associated page is both legal and in memory.
  • If the bit is set to ``invalid'', the page either is not valid (that is, not in the logical address space of the process) or is valid but is currently on the disk.
  • The page-table entry for a page that is brought into memory is set as usual,
  • but the page-table entry for a page that is not currently in memory is either simply marked invalid or contains the address of the page on disk (see Fig. 5).

  Figure 5: Page table when some pages are not in main memory.

  
• While the process executes and accesses pages that are memory resident, execution proceeds normally.
• But what happens if the process tries to access a page that was not brought into memory? Access to a page marked invalid causes a page-fault trap.
• The paging hardware, in translating the address through the page table, will notice that the invalid bit is set, causing a trap to the OS. The procedure for handling this page fault is straightforward (see Fig. 6).

  Figure 6: Steps in handling a page fault.

  
  1. We check an internal table (in PCB) for this process to determine whether the reference was a valid or an invalid memory access.
  2. If the reference was invalid, we terminate the process. If it was valid, but we have not yet brought in that page, we now page it in.
  3. We find a free frame.
  4. We schedule a disk operation to read the desired page into the newly allocated frame.
  5. When the disk read is complete, we modify the internal table kept with the process and the page table.
  6. We restart the instruction that was interrupted by the trap.
• In the extreme case, we can start executing a process with no pages in memory.
  • When the OS sets the instruction pointer to the first instruction of the process, which is on a non-memory-resident page, the process immediately faults for the page.
  • After this page is brought into memory, the process continues to execute, faulting as necessary until every page that it needs is in memory.
• At that point, it can execute with no more faults. This scheme is pure demand paging: Never bring a page into memory until it is required.
• Theoretically, some programs could access several new pages of memory with each instruction execution (one page for the instruction and many for data), possibly causing multiple page faults per instruction.
• This situation would result in unacceptable system performance (but fortunately this behavior is exceedingly unlikely).
• Programs tend to have locality of reference which results in reasonable performance from demand paging.
• Because we save the state (registers, condition code, instruction counter) of the interrupted process when the page fault occurs, we must be able to restart the process in exactly the same place and state.
  • If the page fault occurs on the instruction fetch, we can restart by fetching the instruction again.
  • If a page fault occurs while we are fetching an operand, we must fetch and decode the instruction again and then fetch the operand.