Ch 9 Virtual-Memory Management Mac 2024 (19 June).pdf

CSC204/207 : principles of operating systems (chapter 9) Dr. Mohamed Imran Mohamed Ariff Email : [email protected] Tel : +60127031179  Chapter 9: Virtual Memory Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 9: Virtu...

CSC204/207 : principles of operating systems (chapter 9) Dr. Mohamed Imran Mohamed Ariff Email : [email protected] Tel : +60127031179  Chapter 9: Virtual Memory Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 9: Virtual Memory Background Demand Paging Copy-on-Write Page Replacement Allocation of Frames Thrashing Memory-Mapped Files Allocating Kernel Memory Other Considerations Operating-System Examples Operating System Concepts – 9th Edition 9.3 Silberschatz, Galvin and Gagne ©2013  Chapter 9: Virtual Memory Operating System Concepts – 9th Edition 9.4 Silberschatz, Galvin and Gagne ©2013  Objectives 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 To examine the relationship between shared memory and memory-mapped files To explore how kernel memory is managed Operating System Concepts – 9th Edition 9.5 Silberschatz, Galvin and Gagne ©2013  Background Code needs to be in memory to execute, but entire program rarely used Error code, unusual routines, large data structures 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 -> 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 -> each user program runs faster Operating System Concepts – 9th Edition 9.6 Silberschatz, Galvin and Gagne ©2013  Background (Cont.) Virtual memory – separation of user logical memory (CPU RAM) from physical memory (RAM H/Disk) 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.7 Silberschatz, Galvin and Gagne ©2013  Background (Cont.) Virtual address space – logical view of how process is stored in memory Usually start at address 0, contiguous addresses until end of space Meanwhile, physical memory organized in page frames MMU must map logical to physical Virtual memory can be implemented via: Demand paging Demand segmentation *Paging – program broken into several pages/frames *Segmentation – program broken into several segments Operating System Concepts – 9th Edition 9.8 Silberschatz, Galvin and Gagne ©2013  Demand paging vs Demand segmentation Demand segmentation Demand paging Operating System Concepts – 9th Edition 9.9 Silberschatz, Galvin and Gagne ©2013  9.1 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 Operating System Concepts – 9th Edition 9.10 Silberschatz, Galvin and Gagne ©2013  Basic Concepts 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 Operating System Concepts – 9th Edition 9.11 Silberschatz, Galvin and Gagne ©2013  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 Operating System Concepts – 9th Edition 9.12 Silberschatz, Galvin and Gagne ©2013  Page Table When Some Pages Are Not in Main Memory Operating System Concepts – 9th Edition 9.13 Silberschatz, Galvin and Gagne ©2013  Page Fault If there is a reference to a page, first reference to that page will trap to operating system: page fault 1. Operating system looks at another table to decide: Invalid reference  abort Just not in memory 2. Find free frame 3. Swap page into frame via scheduled disk operation 4. Reset tables to indicate page now in memory Set validation bit = v 5. Restart the instruction that caused the page fault Operating System Concepts – 9th Edition 9.14 Silberschatz, Galvin and Gagne ©2013  Steps in Handling a Page Fault Operating System Concepts – 9th Edition 9.15 Silberschatz, Galvin and Gagne ©2013  9.2 Page Replacement Prevent over-allocation of memory by modifying page-fault service routine to include page replacement Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk 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.16 Silberschatz, Galvin and Gagne ©2013  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. Continue the process by restarting the instruction that caused the trap Operating System Concepts – 9th Edition 9.17 Silberschatz, Galvin and Gagne ©2013  Page Replacement Operating System Concepts – 9th Edition 9.18 Silberschatz, Galvin and Gagne ©2013  Page and Frame Replacement Algorithms Frame-allocation algorithm determines How many frames to give each process Which frames to replace Page-replacement algorithm Want lowest page-fault rate on both first access and re- access Evaluate algorithm by running it on a particular string of memory references (reference string) and computing 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 In all our examples, the reference string of referenced page numbers is 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 Operating System Concepts – 9th Edition 9.19 Silberschatz, Galvin and Gagne ©2013  First-In-First-Out (FIFO) Algorithm 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 pages can be in memory at a time per process) 15 page faults Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5 Adding more frames can cause more page faults!  Belady’s Anomaly How to track ages of pages? Just use a FIFO queue Operating System Concepts – 9th Edition 9.20 Silberschatz, Galvin and Gagne ©2013  Optimal Algorithm Replace page that will not be used for longest period of time 9 is optimal for the example How do you know this? Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5 Can’t read the future Used for measuring how well your algorithm performs Operating System Concepts – 9th Edition 9.21 Silberschatz, Galvin and Gagne ©2013  Least Recently Used (LRU) Algorithm Use past knowledge rather than future Replace page that has not been used in the most amount of time Associate time of last use with each page 12 faults – better than FIFO but worse than OPT Operating System Concepts – 9th Edition 9.22 Silberschatz, Galvin and Gagne ©2013  9.4 Thrashing If a process does not have “enough” pages, the page-fault rate is very high Page fault to get page Replace existing frame But quickly need replaced frame back This leads to:  Low CPU utilization  Operating system thinking that it needs to increase the degree of multiprogramming  Another process added to the system Thrashing  a process is busy swapping pages in and out Operating System Concepts – 9th Edition 9.23 Silberschatz, Galvin and Gagne ©2013  Thrashing (Cont.) Operating System Concepts – 9th Edition 9.24 Silberschatz, Galvin and Gagne ©2013  Question 2016 2017 Operating System Concepts – 9th Edition 9.25 Silberschatz, Galvin and Gagne ©2013  Question 2020 Operating System Concepts – 9th Edition 9.26 Silberschatz, Galvin and Gagne ©2013  End of Chapter 9 Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013