19.1Silberschatz, Galvin and Gagne ©2005Operating System ConceptsCSMC 412CSMC 412Operating SystemsProf. Ashok K Agrawala© 2005 Ashok AgrawalaSet 99.2Silberschatz, Galvin and Gagne ©2005Operating System ConceptsVirtual MemoryVirtual Memory Background Demand Paging Process Creation Page Replacement Allocation of Frames Thrashing Demand Segmentation Operating System Examples29.3Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBackgroundBackground Virtual memory – separation of user logical memory from physical memory.z Only part of the program needs to be in memory for execution.z Logical address space can therefore be much larger than physical address space.z Allows address spaces to be shared by several processes.z Allows for more efficient process creation. Virtual memory can be implemented via:z Demand paging z Demand segmentation9.4Silberschatz, Galvin and Gagne ©2005Operating System ConceptsVirtual Memory That is Larger Than Physical MemoryVirtual Memory That is Larger Than Physical Memory⇒39.5Silberschatz, Galvin and Gagne ©2005Operating System ConceptsVirtualVirtual--address Spaceaddress Space9.6Silberschatz, Galvin and Gagne ©2005Operating System ConceptsShared Library Using Virtual MemoryShared Library Using Virtual Memory49.7Silberschatz, Galvin and Gagne ©2005Operating System ConceptsDemand PagingDemand Paging Bring a page into memory only when it is neededz Less I/O neededz Less memory needed z Faster responsez More users Page is needed ⇒ reference to itz invalid reference ⇒ abortz not-in-memory ⇒ bring to memory9.8Silberschatz, Galvin and Gagne ©2005Operating System ConceptsTransfer of a Paged Memory to Contiguous Disk SpaceTransfer of a Paged Memory to Contiguous Disk Space59.9Silberschatz, Galvin and Gagne ©2005Operating System ConceptsValidValid--Invalid BitInvalid Bit With each page table entry a valid–invalid bit is associated(1 ⇒ in-memory, 0 ⇒ not-in-memory) Initially valid–invalid but is set to 0 on all entries Example of a page table snapshot: During address translation, if valid–invalid bit in page table entry is 0 ⇒page fault1111000#Frame # valid-invalid bitpage table9.10Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPage Table When Some Pages Are Not in Main MemoryPage Table When Some Pages Are Not in Main Memory69.11Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPage FaultPage Fault If there is ever a reference to a page, first reference will trap to OS ⇒ page fault OS looks at another table to decide:z Invalid reference ⇒ abort.z Just not in memory. Get empty frame. Swap page into frame. Reset tables, validation bit = 1. Restart instruction: Least Recently Used z block movez auto increment/decrement location9.12Silberschatz, Galvin and Gagne ©2005Operating System ConceptsSteps in Handling a Page FaultSteps in Handling a Page Fault79.13Silberschatz, Galvin and Gagne ©2005Operating System ConceptsWhat happens if there is no free frame?What happens if there is no free frame? Page replacement – find some page in memory, but not really in use, swap it outz algorithmz performance – want an algorithm which will result in minimum number of page faults Same page may be brought into memory several times9.14Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPerformance of Demand PagingPerformance of Demand Paging Page Fault Rate 0 ≤ p ≤ 1.0z if p = 0 no page faults z 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+ restart overhead)89.15Silberschatz, Galvin and Gagne ©2005Operating System ConceptsSteps in Handling Page faults Steps in Handling Page faults Trap to the OS 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 dist to a free frame:z Wait in a queue for this devie until the read request is servicedz Wait for the device to seek and/ or latency timez Begin the transfer of the page to the selected free frame While waiting, allocate the CPU to some other user Receive an interrut from the disk subsystem on I/O completion Save the registers and process state for the process running Determine that the interrupt was from the disk Correct the page table and other tables to show that the desired page is in the memory now Wait for the CPU to be allocated to this process again Restore the user registers, process state, and new page table, and resume the interrupted instruction9.16Silberschatz, Galvin and Gagne ©2005Operating System ConceptsDemand Paging ExampleDemand Paging Example Memory access time = 200 ns Disk access time = 8 ms = 8,000,000 ns 50% of the time the page that is being replaced has been modified and therefore needs to be swapped out EAT = (1 – p) x 200 + p (8,000,000)= 200+7,999,800p What should p be for EAT to be <220 ns ?220 > 200 + 7999800p or p<0.000002599.17Silberschatz, Galvin and Gagne ©2005Operating System ConceptsProcess CreationProcess Creation Virtual memory allows other benefits during process creation:- Copy-on-Write- Memory-Mapped Files (later)9.18Silberschatz, Galvin and Gagne ©2005Operating System ConceptsCopyCopy--onon--WriteWrite Copy-on-Write (COW) allows both parent and child processes to initially share the same pages in memoryIf either process modifies a shared page, only then is the page copied COW allows more efficient process creation as only modified pages are copied Free pages are allocated from a pool of zeroed-out pages109.19Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBefore process 1 modifies page CBefore process 1 modifies page C9.20Silberschatz, Galvin and Gagne ©2005Operating System ConceptsAfter Process 1 Modifies page CAfter Process 1 Modifies page CCopy of C119.21Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPage ReplacementPage 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
View Full Document
Unlocking...