Unformatted text preview:

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

UMass Amherst ECE 397A - ECE 397A Lecture Notes

Download ECE 397A Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ECE 397A Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ECE 397A Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?