Virtual Memory : Demand Paging

A demand-paging is a combination of paging and swapping. Process reside on secondary memory (which is usually disk). When a process is to be executed, it is swapped-in into main memory. The main idea of demand paging is that "do not swap-in a page into memory until that page is needed."

When a process is swapped in, the pager predicts which pages will be used before the process is swapped out again. Instead of swapping in a whole process, the pager brings only those pages that seems necessary. This scheme reduces the swap time and the amount of physical memory needed.

To implement this scheme, we need some form of H/W support to make separation between those pages already in memory and those pages that are on the disk. The valid-invalid bit scheme is used for this purpose. When this bit is set to "valid", this value indicates that the associated page is both legal and in memory. When this bit is set to "invalid", indicates that the age either is not valid (that is, not in the logical address space of the process), or is valid but is currently not available in the memory.

Execution of the process proceeds in the normal way if a page marked invalid is never accessed duing execution. But when a page marked invalid is accessed result in a page-fault trap. To correct this page-fault OS performs the following action :

  1. It checks the PCB (Process Control Block) of process to confirm that the reference was a valid of invalid memory access. 
  2. If the reference was really invalid, terminate the process. If it was valid, but not in memory, pag-in that. 
  3. To page-in first of all find a free fram eand allocate it to the desired page. 
  4. Schedule a disk operation to read the desired page into the newly allocated frame.
  5. After completing the paging, update the internal table kept with the process and the page table to indicate that the page is now in memory.
  6. Restart the instruction that was interrupted because of the trap. The process can now access the page as though it had always been in memory

The whole process can be easily understandable by the below figure.

It is important to realize that, since we save the state (registers, condition, code, instruction counter) of the interrupted process when the page fault occurs, we can restart the process in exactly the same place and state, except that the desired page is now in memory and is accessible.

The Hardware to support demand paging require :
  • Page Table : Same as in simple paging only. The difference is that this table has a valid-invalid bit.
  • Secondary memory : This is a high-speed disk (swap device) that holds those pages that are not present in main memory. The section of disk used for this purpose is known as swap space or backing store. 
In addition to this Hardware support, considerable Software is also needed.

A crucial issue in the design of this technique is how to restart a instruction after a page fault. The technical problem in restarting an instruction is that to determine that whatever actions this instructions have completed and then undo them before restarting this instruction. To solve this problem system may use temporary registers to hold the status or the value of the overwritten location etc. To undo the effects of a partially executed instruction that causes a page fault. 

Pure Demand Paging

In the extreme case, operating system could start executing a process with no pages in the memory. So page fault occurs for all pages need to execute a proecss. This scheme is called pure demand paging. When the Operation System sets the instruction pointer to the first pointer instruction of the process, which is on a non memory resident page, the process immediately faults for the process. After this page is brought into the memory, the process continues to execute, faulting as necessary until every page that it needs is in memory. At this point, it can execute with no more faults. This is Pure Demand Paging.

Performance of Demand Paging :

Demand paging can have a significant effect on the performance of a computer system. The effective time is major attribute to examine a computer system. The memory access time, for most computer systems now ranges from 10 to 200 nanoseconds. As long as there is no page faults, the effective access time is equal to the memory access time. But if P be the probability of a page fault ( 0 < p < 1 ) where we would expect P to be close to zero i.e. there will be only a few page faults. 

Page Fault rate  0 < P < 1.0

        -if P = 0 no page faults
        -if P = 1, every reference is a fault

Effective Access Time ( EAT )

        EAT = ( 1 - P ) x Memory Access + P x Page fault time

To compute EMT, we must have the information about how much time is needed to service a page fault ( Page fault overhead + Swap page out + Swap page in + Restart overhead).

Next Topic :

No comments:

Post a Comment