1Previous Lectures Memory Management Approaches Allocate contiguous memory for the whole process Use paging (map fixed size logical pages to physical frames) Use segmentation (user’s view of address space in mapping) Use a hybrid approach that has paged segments Do we need to have all the physical address space allocated? No! 90% of the time we use perhaps 10% of address space Degree of multiprogramming can be improved We don’t need the process to fit in memory before it can started This is where virtual memory comes into picture…. Can we extend what we learned to achieve this? Yes Demand based paging, demand based segmentation… What else do we need then? A couple of things such as replacement techniques etc.Chapter 10: Virtual Memory Background Demand Paging Process Creation Page Replacement Allocation of Frames Thrashing Operating System Examples2Background Virtual memory – separation of user logical memory from physical memory (even size does not need to match). 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 segmentationVirtual Memory That is Larger Than Physical Memory3Demand 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 memoryTransfer of a Paged Memory to Contiguous Disk Space4Valid-Invalid Bit With each page table entry a valid–invalid bit is associated(1 in-memory, 0 not-in-memory) Initially valid–invalid bit 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 fault.1111000Frame # valid-invalid bitpage tablePage Table When Some Pages Are Not in Main Memory5Page Fault If there is ever a reference to a page, first reference will trap to OS page fault (BDW can we get a page fault in a non-demand based paging environment?) OS looks at another table to decide if what happened is an: Invalid reference abort. Or page just not in memory. What happens during a fault? Get empty frame. Swap page into frame. Reset tables, validation bit = 1. Restart instruction: Least Recently Used But what happens during a block move instruction –(e.g., in PDP11 was such an instruction)? Page fault in the middle of transfer…things get complicated as some memory locations are already changed.Steps in Handling a Page Fault6What 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 times.Performance 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)PageFaultService time7Demand Paging Example Memory access time = 100 nsec = 0.1usec Page fault service time = 25 msec = 25,000usec EAT (usec) = (1 – p) x 0.1 + p (25,000) Assuming we have p=0.1 (10% of the case page fault) EAT(usec) = 0.9 x 0.1 + 0.1* 25,000 ~2500usec=2.5msecProcess Creation Virtual memory allows other benefits during process creation:- Copy-on-Write- Memory-Mapped Files8Copy-on-Write Copy-on-Write (COW) allows both parent and child processes to initially share the same pages in memory.If 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 pages.Memory-Mapped Files Memory-mapped file I/O allows file I/O to be treated as routine memory access by mapping a disk block to a page in memory. A file is initially read using demand paging. A page-sized portion of the file is read from the file system into a physical page. Subsequent reads/writes to/from the file are treated as ordinarymemory accesses. Simplifies file access by treating file I/O through memory rather than read() write() system calls. Also allows several processes to map the same file allowing the pages in memory to be shared.9Memory Mapped FilesPage 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.10Need For Page ReplacementBasic Page Replacement1. 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.3. Read the desired page into the (newly) free frame. Update the page and frame tables.4. Restart the process.11Page ReplacementPage 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, 5.12Graph of Page Faults Versus The Number of FramesFirst-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’s Anomaly more frames less page faults?1231234125349 page faults1231235124510 page faults44 313FIFO Page ReplacementFIFO Illustrating Belady’s Anomaly14Optimal Algorithm Replace page that will not be used for longest period of time. 4 frames example1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 How do you know this? Used for measuring how well your algorithm performs.12346 page faults45Optimal Page Replacement15Least Recently Used (LRU) Algorithm Reference string:
View Full Document