Operating system 37 demand paging

A demand-paging system is similar to a paging system, discussed earlier, with a little difference that it uses - swapping.
Processes reside on secondary memory (which is usually a disk).
When we want to execute a process, we swap it into memory.
Rather than swapping the entire process into memory, however, we use a lazy swapper, which swaps a page into memory only when that page is needed.
Since we are now viewing a process as a sequence of pages, rather than one large contiguous address space, the use of the term swap will not technically correct.
A swapper manipulates entire processes, whereas a pager is concerned with the individual pages of a process.
We shall thus use the term pager, rather than swapper, in connection with demand paging.

1. Operating System 37 Demand Paging Prof Neeraj Bhargava Vaibhav Khanna Department of Computer Science School of Engineering and Systems Sciences Maharshi Dayanand Saraswati University Ajmer

2. Demand Paging Could bring entire process into memory at load time Or bring a page into memory only when it is needed Less I/O needed, no unnecessary I/O Less memory needed Faster response More users Similar to paging system with swapping (diagram on right) Page is needed  reference to it invalid reference  abort not-in-memory  bring to memory Lazy swapper – never swaps a page into memory unless page will be needed Swapper that deals with pages is a pager

3. Demand Paging With swapping, pager guesses which pages will be used before swapping out again Instead, pager brings in only those pages into memory How to determine that set of pages? Need new MMU functionality to implement demand paging If pages needed are already memory resident No difference from non demand-paging If page needed and not memory resident Need to detect and load the page into memory from storage Without changing program behavior Without programmer needing to change code

4. Basic Concepts of Demand Paging A demand-paging system is similar to a paging system, discussed earlier, with a little difference that it uses - swapping. Processes reside on secondary memory (which is usually a disk). When we want to execute a process, we swap it into memory. Rather than swapping the entire process into memory, however, we use a lazy swapper, which swaps a page into memory only when that page is needed. Since we are now viewing a process as a sequence of pages, rather than one large contiguous address space, the use of the term swap will not technically correct. A swapper manipulates entire processes, whereas a pager is concerned with the individual pages of a process. We shall thus use the term pager, rather than swapper, in connection with demand paging.

5. Basic Concepts of Demand Paging When a process is to be swapped in, the pager guesses which pages will be used before the process in swapped out again. Instead of swapping in a whole process, the pager brings only those necessary pages into memory. Thus, it avoids reading into memory pages that will not be used anyway, decreasing the swap time and the amount of physical memory needed.

6. Basic Concepts of Demand Paging With this scheme, we need some form of hardware support to distinguish between those pages that are in memory and those pages that are on the disk. The valid-invalid bit scheme described earlier can be used for this purpose. This time, however, when this bit is set to “valid”, this value indicates that the associated page is both legal and in memory. If the bit is set to “invalid,” this value indicates that 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 not in the memory.

7. Basic Concepts of Demand Paging The page-table entry for a page that is not currently in memory is simply marked invalid, or contains the address of the page on disk. Notice that marking a page invalid will have no effect if the process never attempts to access that page. Hence, if we guess right and only those pages that are actually needed are brought into the memory, the process will run exactly as though we had brought in all pages. While the process executes and accesses pages that are memory resident, execution proceeds normally.

8. Valid-Invalid Bit With each page table entry a valid–invalid bit is associated ( v  in-memory – memory resident , i  not-in-memory) Initially valid–invalid bit is set to i on all entries Example of a page table snapshot: During MMU address translation, if valid–invalid bit in page table entry is i  page fault

9. Page Table When Some Pages Are Not in Main Memory

10. Page Fault If there is a reference to a page, first reference to that page will trap to operating system: page fault Operating system looks at another table to decide: Invalid reference  abort Just not in memory Find free frame Swap page into frame via scheduled disk operation Reset tables to indicate page now in memory Set validation bit = v Restart the instruction that caused the page fault

11. Steps in Handling a Page Fault

12. Steps in Handling a Page Fault 1. We check an internal table (usually kept with the process control block) for the process under consideration, to determine whether the reference was a valid or 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 into memory, we now page in the latter. 3. We find a free frame (by taking one from the free-frame list, for example). 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 to indicate that the page is now in memory. 6. We restart the instruction that was interrupted by the illegal address trap. The process can now access the page as though it had always been in memory.

13. Handling Page Fault It is important to realize that, because 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. In this way, we are able to execute a process, even though portions of it are not (yet) in memory. When the process tries to access locations that are not in memory, the hardware traps to the operating system (page fault). The operating system reads the desired page into memory and restarts the process as though the page had always been in memory.

14. Aspects of Demand Paging Extreme case – start process with no pages in memory OS sets instruction pointer to first instruction of process, non-memory-resident -> page fault And for every other process pages on first access Pure demand paging Actually, a given instruction could access multiple pages -> multiple page faults Consider fetch and decode of instruction which adds 2 numbers from memory and stores result back to memory Pain decreased because of locality of reference Hardware support needed for demand paging Page table with valid / invalid bit Secondary memory (swap device with swap space ) Instruction restart

15. Instruction Restart Consider an instruction that could access several different locations block move auto increment/decrement location Restart the whole operation? What if source and destination overlap?

16. Performance of Demand Paging Stages in Demand Paging (worse case) Trap to the operating system Save the user registers and process state Determine that the interrupt was a page fault Check that the page reference was legal and determine the location of the page on the disk Issue a read from the disk to a free frame: Wait in a queue for this device until the read request is serviced Wait for the device seek and/or latency time Begin the transfer of the page to a free frame While waiting, allocate the CPU to some other user Receive an interrupt from the disk I/O subsystem (I/O completed) Save the registers and process state for the other user Determine that the interrupt was from the disk Correct the page table and other tables to show page is now in memory Wait for the CPU to be allocated to this process again Restore the user registers, process state, and new page table, and then resume the interrupted instruction

17. Performance of Demand Paging (Cont.) Three major activities Service the interrupt – careful coding means just several hundred instructions needed Read the page – lots of time Restart the process – again just a small amount of time Page Fault Rate 0  p  1 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 (page fault overhead + swap page out + swap page in )

18. Assignment Explain the concept and usage of Demand Paging Explain the Steps in Handling a Page Fault