CSMC 412Operating SystemsProf. Ashok K Agrawala© 2006 Ashok AgrawalaSet 9October 2006 1CMSC 412 Set 9Virtual Memory• Background• Demand Paging• Process Creation• Page Replacement• Allocation of Frames • Thrashing• Demand Segmentation• Operating System ExamplesOctober 2006 2CMSC 412 Set 9Background• 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.• Virtual memory can be implemented via:– Demand paging – Demand segmentationOctober 2006 3CMSC 412 Set 9Virtual Memory That is Larger Than Physical MemoryOctober 2006 4CMSC 412 Set 9Virtual-address SpaceOctober 2006 5CMSC 412 Set 9Shared Library Using Virtual MemoryOctober 2006 6CMSC 412 Set 9Demand Paging• Bring a page into memory only when it is needed– Less I/O needed– Less memory needed – Faster response– More users• Page is needed reference to it– invalid reference abort– not-in-memory bring to memoryOctober 2006 7CMSC 412 Set 9Transfer of a Paged Memory to Contiguous Disk SpaceOctober 2006 8CMSC 412 Set 9Valid-Invalid 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 fault1111000Frame # valid-invalid bitpage tableOctober 2006 9CMSC 412 Set 9Page Table When Some Pages Are Not in Main MemoryOctober 2006 10CMSC 412 Set 9Page 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:– Invalid reference abort.– Just not in memory.• Get empty frame.• Swap page into frame.• Reset tables, validation bit = 1.• Restart instruction: Least Recently Used – block move– auto increment/decrement locationOctober 2006 11CMSC 412 Set 9Steps in Handling a Page FaultOctober 2006 12CMSC 412 Set 9What happens if there is no free frame?• Page replacement – find some page in memory, but not really in use, swap it out– algorithm– performance – want an algorithm which will result in minimum number of page faults• Same page may be brought into memory several timesOctober 2006 13CMSC 412 Set 9Performance of Demand Paging• Page Fault Rate 0 p 1.0– 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+ restart overhead)October 2006 14CMSC 412 Set 9Steps 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:– Wait in a queue for this devie until the read request is serviced– Wait for the device to seek and/ or latency time– 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 instructionOctober 2006 15CMSC 412 Set 9Demand 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.0000025October 2006 16CMSC 412 Set 9Process Creation• Virtual memory allows other benefits during process creation:- Copy-on-Write- Memory-Mapped Files (later)October 2006 17CMSC 412 Set 9Copy-on-Write• 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 pagesOctober 2006 18CMSC 412 Set 9Before process 1 modifies page COctober 2006 19CMSC 412 Set 9After Process 1 Modifies page CCopy of COctober 2006 20CMSC 412 Set 9Page 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 memoryOctober 2006 21CMSC 412 Set 9Need For Page ReplacementOctober 2006 22CMSC 412 Set 9Basic Page Replacement1. Find the location of the desired page on disk2. 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 frame3. Read the desired page into the (newly) free frame. Update the page and frame tables.4. Restart the processOctober 2006 23CMSC 412 Set 9Page ReplacementOctober 2006 24CMSC 412 Set 9Page Replacement Algorithms• Want lowest page-fault rate• Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string• In all our examples, the reference string is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5October 2006 25CMSC 412 Set 9Graph of Page Faults Versus The Number of FramesOctober 2006 26CMSC 412 Set 9First-In-First-Out (FIFO) Algorithm• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• 3 frames (3 pages can be in memory at a time per process)• 4 frames• FIFO Replacement – Belady’sAnomaly– more frames more page faults1231234125349 page faults1231235124510 page faults44 3October 2006 27CMSC 412 Set 9FIFO Page ReplacementOctober 2006 28CMSC 412 Set 9FIFO Illustrating Belady’s Anom
View Full Document
Unlocking...