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.Where are we in the course?■5 more lectures✦ 2 about virtual memory✦ 1 lecture introduction to file systems✦ 1 lecture about distributed systems✦ One is related to Final exam reviewWe covered: operating services, hardware support, processes, threads, Java threads, synchronization, deadlocks, memory management, virtual memory (some).2Chapter 10: Virtual Memory■Background■Demand Paging■Process Creation■Page Replacement■Allocation of Frames ■Thrashing■Operating System ExamplesBackground■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 segmentation3Virtual Memory That is Larger Than Physical MemoryDemand 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 memory4Transfer of a Paged Memory to Contiguous Disk SpaceValid-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 table5Page Table When Some Pages Are Not in Main MemoryPage 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 –PDP11? Page fault in the middle of transfer… things get complicated as some memory locations are already changed.6Steps in Handling a Page FaultWhat 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.7Performance 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 timeDemand 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.5msec8Process Creation■Virtual memory allows other benefits during process creation:- Copy-on-Write- Memory-Mapped FilesCopy-on-Write■Copy-on-Write (COW) allows both parent and child processes to initially sharethe 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 poolof zeroed-out pages.9Memory-Mapped Files■Memory-mapped file I/O allows file I/O to be treated as routine memory access by mappinga 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.Memory Mapped Files10Page Replacement■Prevent over-allocation of memory by modifying page-fault service routine to include page replacement.■Use modify(dirty) bitto 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.Need For Page Replacement11Basic 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 victimframe.3.Read the desired page into the (newly) free frame. Update the page and frame tables.4.Restart the process.Page Replacement12Page 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.Graph of Page Faults Versus The Number of Frames13First-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 faults1231234125349 page faults1231235124510 page faults44 3FIFO Page Replacement14FIFO Illustrating Belady’s AnomalyOptimal Algorithm■Replace page that will not be used for longest period of time.■4 frames example1, 2, 3, 4, 1, 2,
View Full Document