Operating System Concepts - Chapter 9 Virtual Memory PDF

Chapter 9: Virtual Memory Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 9: Virtual Memory Subtopics: 9.1 Background 9.2 Demand...

Chapter 9: Virtual Memory Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 9: Virtual Memory Subtopics: 9.1 Background 9.2 Demand Paging 9.4 Page Replacement Operating System Concepts – 9th Edition 9.2 Silberschatz, Galvin and Gagne ©2013  Objectives At the end of this topic, students should be able: ▪ To describe the benefits of a virtual memory system. ▪ To explain the concepts of demand paging, page-replacement algorithms, and allocation of page frames. ▪ To discuss the principle of the working-set model. Operating System Concepts – 9th Edition 9.3 Silberschatz, Galvin and Gagne ©2013  9.1 Background ▪ Code needs to be in memory to execute, but entire program rarely used. ▪ Entire program code not needed at same time. ▪ Consider ability to execute partially-loaded program: ✔ Program no longer constrained by limits of physical memory. ✔ Each program takes less memory while running; hence more programs run at the same time. ▪ Increased CPU utilization and throughput with no increase in response time or turnaround time. ✔ Less I/O needed to load or swap programs into memory; hence, each user program runs faster. Operating System Concepts – 9th Edition 9.4 Silberschatz, Galvin and Gagne ©2013  9.1 Background Concepts Virtual memory – separation of user logical memory from physical memory: Only part of the program needs to be in memory for execution. Logical address space can therefore be much larger than physical address space Allows address spaces to be shared by several processes. Allows for more efficient process creation. More programs running concurrently. Less I/O needed to load or swap processes. Operating System Concepts – 9th Edition 9.5 Silberschatz, Galvin and Gagne ©2013  9.1 Background Virtual address space of a process refers to the logical (or virtual) view how it stored in memory. Backing Store Figure 9.1 Virtual Memory That is Larger Than Physical Memory. th Operating System Concepts – 9 Edition 9.6 Silberschatz, Galvin and Gagne ©2013  9.1 Background Virtual memory can be implemented via TWO approaches: Virtual Memory Demand Demand Paging Segmentation (Not cover in this course) Operating System Concepts – 9th Edition 9.7 Silberschatz, Galvin and Gagne ©2013  Virtual Memory: Demand Paging Operating System Concepts – 9th Edition 9.8 Silberschatz, Galvin and Gagne ©2013  9.2 Demand Paging Overview ▪ Allowed for wide availability of virtual memory concept: – Provides appearance of almost infinite or nonfinite physical memory. – Jobs run with less main memory than required in paged memory allocation scheme. ▪ Disadvantages: Solution: Swapping – Increased overhead caused by How and when pages tables and page interrupts. passed in memory? – Requires high-speed direct access Depends on predefined storage device. policies. Operating System Concepts – 9th Edition 9.9 Silberschatz, Galvin and Gagne ©2013  9.2 Demand Paging A strategy to implement virtual memory ▪ Bring a page into memory only when it is needed: Lazy swapper – Less I/O needed never swaps a page – Less memory needed into memory unless page will be needed – Faster response Swapper that deals – More users with pages is a pager ▪ Page is needed reference to it – invalid reference abort – not-in-memory bring to memory Operating System Concepts – 9th Edition 9.10 Silberschatz, Galvin and Gagne ©2013  9.2 Demand Paging Figure 9.4 Transfer of a paged memory to contiguous disk space. Operating System Concepts – 9th Edition 9.11 Silberschatz, Galvin and Gagne ©2013  9.2 Demand Paging 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. ▪ Instead of swapping in a whole process, the pager brings in only those “guessed” pages into memory. ▪ Need new MMU functionality to implement demand paging. ✔ Need to distinguish between the pages that are in memory and the pages that are on the disk. ✔ Use a variation of the valid-invalid scheme used for protection (see next slide). Operating System Concepts – 9th Edition 9.12 Silberschatz, Galvin and Gagne ©2013  9.2 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. Operating System Concepts – 9th Edition 9.13 Silberschatz, Galvin and Gagne ©2013  9.2 Demand Paging Valid-Invalid Bit With each page table entry a valid–invalid bit is associated: (v in-memory i not-in-memory) Initially valid–invalid bit is set to i on all entries. Operating System Concepts – 9th Edition 9.14 Silberschatz, Galvin and Gagne ©2013  9.2 Demand Paging Invalid the page either: ❑ not valid (not in the logical address space of the process), or ❑ valid but is currently on the disk. Access to a page Backing Store marked invalid causes a page fault. Figure 9.5 Page Table When Some Pages are Operating System Concepts – 9th Edition 9.15 Not in Main Silberschatz, Memory Galvin and Gagne ©2013  9.2 Demand Paging Page Fault ▪ If there is a reference to a page, first reference to that page will trap to operating system page fault ▪ Actions when a page fault occurs: 1. Operating system looks at another table to decide: ▪ Invalid reference abort 2. Valid but not in memory Go to step (3). 3. Find free frame in memory; 4. Swap page into frame via scheduled disk operation; 5. Reset tables to indicate page now in memory; Set validation bit = v; 6. Restart the instruction. Operating System Concepts – 9th Edition 9.16 Silberschatz, Galvin and Gagne ©2013  9.2 Demand Paging Backing Store Trap result of the OS’s failure to bring the desired page into memory. If no free frame, use a page replacement algorithm to select a victim frame. Operating System Concepts – 9th Edition Figure 9.6 Steps in Handling 9.17 a Page Fault. Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Overview ▪ Page replacement occurs when: ▪ A page fault occurs and we need to bring the desired page into memory. ▪ There are NO free frames. ▪ Page replacement – find page in memory, but not really in use, page it out: ▪ Algorithm – decide which victim frame to free. ▪ Performance – need an algorithm which will result in minimum number of page faults. Same page may be brought into memory several times. Operating System Concepts – 9th Edition 9.18 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Example All frames are used, no free fames, user 2 needs B. (Page: 402) Backing Store Operating System Concepts – 9th Edition 9.19 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Basic page replacement 1. Find the location of the desired page on disk; 2. Find a free frame: - If there is a free frame, use it; - If there is no free frame, use a page replacement algorithm to -Select a victim frame; -Write victim frame to disk if dirty 3. Bring the desired page into the (newly) free frame; update the page and frame tables 4. Restart the process that caused the page fault; Operating System Concepts – 9th Edition 9.20 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Figure 9.10 Page replacement. Operating System Concepts – 9th Edition 9.21 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Problems: Overhead Solution: If no free frames TWO Use modify bit (or dirty bit) to page transfers (one out one reduce overhead of page in): transfers: ✔ Doubles the page-fault ✔ only modified pages are service time. written to back to disk. ✔ Increases access time. ▪ Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory. Operating System Concepts – 9th Edition 9.22 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Page-Replacement Algorithms ▪ Frame-allocation algorithm: determines ✔ How many frames to give each process? ✔ Which frames to replace? ▪ Page-replacement algorithm: ✔ need an algorithm which will result in minimum number of page faults. Operating System Concepts – 9th Edition 9.23 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Page-Replacement Algorithms ▪ Evaluate algorithm by running it on a particular string of memory references (reference string) and compute the number of page faults on that string. ❑ String is just page numbers, not full addresses. ❑ Repeated access to the same page does not cause a page fault. ❑ Results depend on number of frames available. Operating System Concepts – 9th Edition 9.24 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement If the number of frames increases, then the number of page faults decreases. Figure 9.11 Graph of Page Faults Versus the Number of Frames. Operating System Concepts – 9th Edition 9.25 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Reference String ▪ If CPU accesses the following addresses: 0100 0432 0101 0612 0102 0102 0000 Page 0 0103 0104 0101 0611 0105 0105 0100 Page 1 0103 0103 0104 0101 0610 0107 Page 2 0200 0103 0104 0101 0609 0101 0300 Page 3 0400 If page size = 100 byte, reference string will be: Page 4 0500 Page 5 0600 1 4 1 6 1 1 1 1 6 1 1 Page 6 0700 Operating System Concepts – 9th Edition 9.26 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Example ▪ Reference String: 1 4 1 6 1 6 1 6 1 6 1 ▪ Number of frames = 3 ▪ What is the total number of page fault? Solution 1 4 1 6 1 6 1 6 1 6 1 Frame #0 1 1 1 Frame #1 4 4 Frame #2 6 ▪ Number of page fault = 3 Operating System Concepts – 9th Edition 9.27 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Exercise Given a reference string: 1 4 1 6 1 6 1 6 1 6 1 If the number of frame is 1 and 2 respectively, define how many number of page faults will be generated for each of them. Show your works. 1 4 1 6 1 6 1 6 1 6 1 Frame #0 1 4 1 6 1 6 1 6 1 6 1 – Number of page fault = 11 Operating System Concepts – 9th Edition 9.28 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement ▪ Policy to select page removal: – Crucial to system efficiency. ▪ Page replacement polices: ❑ First-In First-Out (FIFO) policy Best page to remove is one in memory longest. ❑ Optimal Page Replacement (OPT) policy Best page to remove is one not be accessed longest. ❑ Least Recently Used (LRU) policy Best page to remove is least recently accessed. Operating System Concepts – 9th Edition 9.29 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement ▪ Another Page Replacement Policies: ❑ Random Page Replacement - Replace page at random. ❑ LRU Approximation Algorithms ❑ Additional Reference Bits Algorithm ❑ Second Chance Algorithm ❑ Enhanced Second Chance Algorithm ❑ Counting-Based Replacement ❑ Least Frequently Used (LFU) - replaces page with smallest count ❑ Most Frequently Used (MFU) -based on the argument that the page with the smallest count was probably just brought in and has yet to be used Operating System Concepts – 9th Edition 9.30 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement (a) First-In First-Out (FIFO) ▪ Removes the page that in memory with the longest of time; ▪ Efficiency – Ratio of page interrupts to page requests. – Not so good ▪ FIFO anomaly – More memory does not lead to better performance. Operating System Concepts – 9th Edition 9.31 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Example ▪ FIFO. (Page: 406) ▪ Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1 ▪ 3 frames = 3 (3 pages can be in memory at a time per process) ▪ What is the total number of page fault? 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 Frame #0 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7 Frame #1 0 0 0 3 3 3 2 2 2 1 1 1 0 0 Frame #2 1 1 1 0 0 0 3 3 3 2 2 2 1 ▪ Number of page fault = 15 th Operating System Concepts – 9 Edition 9.32 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Exercise ▪ FIFO. ▪ Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1 ▪ Number of frames = 4 ▪ What is the total number of page fault? Operating System Concepts – 9th Edition 9.33 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Number of Frames vs Page Faults ▪ One would expect that the more frames are allocated to a process the fewer page faults. Exercise Consider the reference string: 1 2 3 4 1 2 5 1 2 3 4 a) How many page faults if we have 3 frames? b) How many page faults if we have 4 frames? Operating System Concepts – 9th Edition 9.34 Silberschatz, Galvin and Gagne ©2013  Reference String: 1 2 3 4 1 2 5 1 2 3 4 3 frames (3 pages can be in memory at a time per process) How many page faults? Solution: Number of Page faults = 9 Frame # 1 2 3 4 1 2 5 1 2 3 4 1 1 1 1 4 4 4 5 5 5 2 2 2 2 1 1 1 3 3 3 3 3 3 2 2 2 4 Operating System Concepts – 9th Edition 9.35 Silberschatz, Galvin and Gagne ©2013  Reference String: 1 2 3 4 1 2 5 1 2 3 4 4 frames (4 pages can be in memory at a time per process) How many page numbers? Solution: Number of Page faults = 9 Frame # 1 2 3 4 1 2 5 1 2 3 4 1 1 1 1 1 5 5 5 5 4 2 2 2 2 2 1 1 1 1 3 3 3 3 3 2 2 2 4 4 4 4 4 3 3 Operating System Concepts – 9th Edition 9.36 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Belady’s Anomaly ▪ If we use FIFO for page replacement, we can encounter the anomaly that more frames may lead to more page faults. ▪ FIFO Illustrating Belady’s Anomaly Figure 9.13 Page-fault curve for FIFO replacement on a reference string. Operating System Concepts – 9th Edition 9.37 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement (b) Optimal Page Replacement (OPR) ▪ Replace page that will not be accessed for longest period of time. ▪ Q: How do you know which page will not be accessed for longest period of time? ▪ Can’t read the future ▪ Used mainly for measuring how well a given algorithm performs. Operating System Concepts – 9th Edition 9.38 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Example ▪ OPR (Page: 407) ▪ Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1 ▪ 3 frames = 3 (3 pages can be in memory at a time per process) ▪ What is the total number of page fault? 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 Frame #0 7 7 7 2 2 2 2 2 7 Frame #1 0 0 0 0 4 0 0 0 Frame #2 1 1 3 3 3 1 1 ▪ Number of page Operating System Concepts – 9th Edition 9.39 fault = 9 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Exercise ▪ OPR ▪ Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1 ▪ Number of frame = 4 ▪ What is the total number of page fault? Operating System Concepts – 9th Edition 9.40 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement (c) Least Recently Used (LRU) ▪ Use past knowledge rather than future. ▪ Replace page that has not been used for the longest period of time. ▪ Associate time of last use with each page. Operating System Concepts – 9th Edition 9.41 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Example ▪ LRU. (Page: 407) ▪ Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1 ▪ 3 frames = 3 (3 pages can be in memory at a time per process) ▪ What is the total number of page fault? 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 Frame #0 7 7 7 2 2 4 4 4 0 1 1 1 Frame #1 0 0 0 0 0 0 3 3 3 0 0 Frame #2 1 1 3 3 2 2 2 2 2 7 ▪ Number of page Operating System Concepts – 9th Edition 9.42 fault = 12 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Exercise ▪ LRU. ▪ Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1 ▪ Number of frame = 4 ▪ What is the total number of page fault? Operating System Concepts – 9th Edition 9.43 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement LRU Implementation ▪ Problem: To determine an order for the frames defined by the time of last use. ▪ How to implement LRU algorithm? ▪ Two implementations: 1. Counter 4 Every page table entry has a counter associated with it; 4 Every time page is referenced through this entry, the content of the clock if copied into the counter 4 We replace the page with the smallest time value – search through table needed Operating System Concepts – 9th Edition 9.44 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement 2. Stack 4 keep a stack of page numbers in a double link form: (Header pointer & Tail pointer) 4 When a page is referenced: – move page to the top – Therefore, most recently used page is on top while least recently used is always at the bottom. 4 No search for replacement LRU needs special hardware and is still slow LRU and OPT are cases of stack algorithms that don’t suffer from Belady’s Anomaly Operating System Concepts – 9th Edition 9.45 Silberschatz, Galvin and Gagne ©2013  9.4 Page Replacement Example (Page: 409) Figure 9.16 Use of a stack to record the most recent page references. Operating System Concepts – 9th Edition 9.46 Silberschatz, Galvin and Gagne ©2013  9.11 Summary ▪ It is able to execute a process with the logical address space larger than the available physical address space. ▪ Virtual memory allows : ✔ to run extremely large processes. ✔ to raise the degree of multiprogramming. ✔ to increase CPU utilization. ▪ Virtual memory: ▪ Programs execute if not stored entirely in memory. ▪ Job’s size no longer restricted to main memory size. Operating System Concepts – 9th Edition 9.47 Silberschatz, Galvin and Gagne ©2013  9.11 Summary ▪ Demand paging can be used to reduce the number of frames allocated to a process ▪ If total memory requirements exceed the capacity of physical memory, replace the pages from memory to free frames for new pages. ✔ Various page-replacement algorithms are used. ✔ FIFO: easy to program but suffers from Belady’s anomaly. ✔ OPT: requires future knowledge. ✔ LRU: approximates the OPT, but difficult to implement. Operating System Concepts – 9th Edition 9.48 Silberschatz, Galvin and Gagne ©2013  Exercise Consider the following page reference string: 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 How many page faults would occur for the following replacement algorithms, assuming 1, 3 and 5 frames? Remember that all frames are initially empty. a) FIFO replacement. b) LRU replacement. c) OPT replacement. Operating System Concepts – 9th Edition 9.49 Silberschatz, Galvin and Gagne ©2013  Exercises From Silberchatz, Operating System Concepts Chapter 9 Exercises (page: 441 - 446) ❑ 9.5 ❑ 9.12 ❑ 9.6 ❑ 9.17 ❑ 9.8 ❑ 9.19 ❑ 9.9 ❑ 9.20 ❑ 9.11 ❑ 9.21 Operating System Concepts – 9th Edition 9.50 Silberschatz, Galvin and Gagne ©2013