Section 8: Virtual Memory Question 1 What are the two characteristics of simple paging that lead to, and the fundamental idea defines virtual memory? Hint: Three parts in slides. Answer The two characteristics of simple paging are: 1. Because of the indirection between logical and physical addresses, a process’s pages can be located anywhere in memory and can be moved (relocated). 2. The frames occupied by a process’s pages do not need to be contiguous i.e. they can be spread throughout physical memory. And the fundamental idea in virtual memory is: 3. Not all of a process’s pages need to be maintained in physical memory for the process to execute. Only those pages in the process’s working set need to be resident. Question 2 1. Describe Page Fault. 2. Describe Page Fault Rate (PFR). 3. Describe Thrashing. Answer 1. A page fault is the interrupt generated by the memory management unit when the process references a page that is not resident in memory i.e. not in the resident set. 2. The page fault rate is a metric that describes the number of page faults that occur over some time period e.g. PFs per minute. 3. Thrashing occurs when a process’s page fault rate (PFR) rises to a point that the process cannot make progress i.e. each time the process is scheduled for execution (is made runnable) its execution takes it to a missing page and the page fault blocks the process’s execution. Question 3 1. Describe a process’s Resident Set. 2. What is the result of setting a process’s resident set size too small? 3. What is the result of setting a process’s resident set size too large?Answer The resident set is the set of process pages that are resident i.e. are contained in a memory frame. A resident set that is too small will cause an increase in the number of page faults and so will cause the process to begin thrashing. A resident set that is too large wastes memory (frames) by maintaining process pages in memory frames that are no longer being referenced by the process. This has the effect of reducing the overall number of processes that can be maintained in memory. Question 4 1. Briefly describe a process’s Working Set. 2. Briefly describe the relationship between a process’s working set and its resident set. 3. Generally, how is a process’s page fault frequency used to adjust a process’s resident set size? Answer 1. The Working Set is the set of pages that the process currently needs to execute. Any page in the working set that is not resident must be swapped in. 2. The resident set must include at least the working set. If the resident set is smaller than the process’s working set, the process will begin to thrash. 3. If the resident set is smaller than the working set, the PF Frequency will rise providing an indication that the process’s resident set’s size must be increased. When the resident set contains the working set, the PF Frequency will drop. The OS can monitor the PF Frequency using it as an indicator of how to adjust the process’s resident set size up or down. Question 5 1. What three pieces of information is maintained in a page table entry (as described in the slides)? 2. How many page table entries are needed with a 32 bit address and a page size of 8192? 3. What is the technique described in the book, and in class, that reduces the number of page table entries needed to be maintained in memory? Answer 1. Mainly each entry maintains the upper N bits of the physical address of the memory frame containing the page. The PT Entry also maintains a ‘Present bit’ that indicates whether the page is resident (1) or must be retrieved from disk (0).The PT entry also maintains a ‘modified bit’ that indicates whether the page has been written to (modified) since it was made resident. 2. A 32 bit address range with a page size of 213 bits permits (32-13) 219 (524288) pages. 3. Multi-Level Page Table. That is, dividing the page table into multiple levels greatly reduces the number of PTE that must be maintained in memory (Figure 5.8). Question 6 What are two disadvantages of multi-level page tables? Answer 1) Each level in a multi-level page table increases the number of physical memory accesses by one e.g. a two-level page table will require three physical memory accesses. 2) The M-L page table introduces additional complexity in the design of the memory management unit hardware. Question 7 Describe the purpose of the Translation Lookaside Buffer. Answer The TLB is a fast memory cache for page table entries. When the TLB hits, it avoids the additional memory reference needed to retrieve one or more page table entries from memory depending on whether a 1, 2, 3, etc. level page table is being employed. Without a TLB, every virtual memory reference would require two or more memory accesses (i.e. 1, 2, or more page table entries) plus the reference to the target frame. Question 8 1. Describe the Operating System’s Fetch Policy. 2. Describe Demand Paging and Prepaging? 3. Which fetch policy is most common? Answer The fetch policy determines when a page is made resident i.e. swapped from disk into memory. Demand paging occurs when the OS installs a page into a frame when the process executes instructions or data on the page i.e. paging as needed.Prepaging occurs when the OS installs pages from a process image into frames before the process access the memory. It is a technique designed to avoid page faults during the process’s execution. Demand paging is the most often used fetch policy. Question 9 1. Describe the goal of a Page Replacement Policy. 2. In theory, how does the Least Recently Used page replacement policy select a page to be replaced when a new page must be made resident? 3. Describe how the ‘use bit’ marks pages in the Clock Algorithm. How is the use bit used to select a page for replacement? Answer To reduce the page fault rate by selecting pages for replacement that will not be referenced for the longest amount of time. The LRU policy selects the page that has not been referenced in the longest amount of time. According to the principle of locality, the LRU page is least likely to be referenced in the near future. The frame table maintains a use bit (UB) for every memory frame. The UB is an indicator of whether the frame has been referenced in the recent past. The Clock page replacement algorithm scan the frame table until a UB = 0 is located which is then selected for