DOC PREVIEW
UMass Amherst ECE 397A - ECE 397A Lecture Notes

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

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.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

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?