Demand Paging
- Demand paging is a technique used to implement the concept of virtual memory.
- It combines the concept of paging and swapping.
- The various processes are initially stored in secondary storage device such as disk. All the pages of a process are stored contiguously in the swap space on secondary storage.
- Whenever a process is to be executed, it is brought into main memory.
- In demand paging, only those pages of the process are brought into the memory that are required. All other pages reside on secondary storage and are brought into the memory when needed.
- This task of bringing in and out the various pages of a process is done by a pager.
- This concept is called demand paging because the page is not loaded the memory until it is not required.
- When a process is to be swapped in, the pager guesses which pages will be used before the process is swapped out again. As a result, only required pages are brought into the memory.
- Thus, demand paging avoid bringing those pages that will not be used at a particular moment. As a result of this, swap time is decreased and the amount of physical memory needed is also decreased.
- For the purpose of address translation, demand paging uses page table. The page table stores the information about-which page of program is stored in which frame of the physical memory.
- In order to distinguish between those pages that are in memory and those pages that are on disk, demand paging scheme uses valid/invalid bit in page table for each entry.
- When this bit is set to valid, it indicates that the corresponding page is legal and is in main memory.
- If this bit is invalid for a particular page then it indicates that either it is on disk or it is not within the logical address space of process i.e. it does not belong to the process in whose context it is being accessed.
- If the accessed page is not present in the main memory then it is known as page fault.
- When a page fault occurs, memory management unit (MMU) swaps in the requested page from the secondary memory into the main memory.
- In case there is no free space in the main memory, MMU finds free space in the secondary memory.
- MMU then swaps out an unused page from the main memory and stores the unused page in the free space in the secondary memory for creating space in the main memory. The requested page is then loaded into the main memory.
- Finally the page table is updated for this entry.
Pure demand paging
- Pure demand paging is the form of demand paging in which not even a single page is loaded into the memory, initially.
- Thus, the very first instruction causes a page fault in this case as it is not residing in main memory.
- This kind of demand paging may significantly decrease the performance of a computer system by generally increasing the effective access time of memory.
- If ma is the memory access time and p is the probability of occurrence of a page fault. Then the effective access time is :
Effective access time = (1-p) * ma + p * page fault time.
For example, suppose the average page fault service time is 20 milliseconds and memory access time is 200 nanoseconds. Suppose, we wish to have less than 10% degradation in the memory access when a page fault occurs, what must the page fault rate be less than ?
This means that we want effective access time should be less than:
(10/100 * 200 + 200) * 10^-9 seconds
i.e. 220 x 10^-9 seconds.
Effective access time is obtained as :
(1-p) x 200 x 10^-9 + p x 20 x 10^-3
= 2x 10^-7 – 2 x 10^-7 p +2 x 10^-2 p
Now, 2x 10^-7 + 1.99 x 10^-2 p should be less than 220 x 10^-9
=> Thus, 2×10^-7 +1.99 x 10^-2 p < 220 x 10^-9
=> 1.99 x 10^-2 p < 2.2 x 10^-7 – 2 x 10^-7
=> 1.99 x 10^-2 p < .2 x 10^-7
=> p < .2 x 10^-7 /1.99 x 10^-2
=> p < .2 x 10^-5/1.99
=>p < .10050 x 10^-5
=>p < .00001 approx.
This means that probability of occurring of a page fault should be less than .00001 so as to achieve a degradation of less than 10%. This implies that page fault rate should be kept as low as possible so that effective memory access time should not increase.