4003-440-02 Operating Systems I Module 8. Memory Management -- Lecture Notes Prof. Alan Kaminsky -- Winter Quarter 2012 Rochester Institute of Technology -- Department of Computer Science Address Mapping Goal: Support multiple concurrently running processes (multiprocessing) Logical addresses Addresses generated and used by a program Physical addresses Addresses presented to the main memory hardware Address mapping Conversion of a logical address in the program to a physical address in the main memory Address mapping technique: No mapping Physical address = Logical address Implications for multiprocessing Address mapping technique: Relocation Base register, limit register If logical address >= limit register, error; else physical address = base address + logical address Implications for multiprocessing Swapping Copy a non-running process's memory contents from main memory to secondary memory Frees up space in the main memory to load in and run another process Problem: Fragmentation Address mapping technique: Paging Logical address split into (page number, page offset) Main memory divided into page frames Page table Index page table by page number to get page frame number; physical address = (page frame number, page offset) Illustrate with 16-bit addresses, 4096-byte pages Solves the fragmentation problem Problem: Typically too many page table entries to hold the page table in CPU hardware Solution: Store the page table in main memory; page table register Problem: Reading or writing data requires two memory accesses Solution: Cache the page table entries; translation lookaside buffer (TLB) Problem: For larger addresses (64-bit or even 32-bit) the page table takes up too much memory Address mapping technique: Multi-level paging Logical address split into (first level page number, second level page number, page offset) Hierarchical page table Can have more than two levels of page tables Problem: We lost the protection (limit register) Address mapping technique: Segmentation Divide a process's address space into segments based on what's stored -- code segments, data segments, stack segments, etc. Logical address split into (segment number, segment offset) Segment table Base address (physical address) Limit (size) Protection -- executable/nonexecutable, read-write/read-only, user/kernel, etc. Index segment table by segment number to get base address; physical address = base address + segment offset Hierarchical page table Can have more than two levels of page tables Problem: We're back to needing contiguous memory allocation (fragmentation) Address mapping technique: Segmentation plus paging The Intel Pentium address mapping scheme: Logical address uses segmentation, translates to a linear address 213 local segments plus 213 global segments Linear address uses paging, translates to a physical address Two-level paging 10-bit first level page number 10-bit second level page number 12-bit page offset Implementation of inter-process shared memory segments Virtual Memory Demand paging: Don't load in all of a process's pages, only load in the pages the process actually references Working set: The set of pages the process is actually referencing at any given time Page fault: Generated by the hardware when the process references a logical address that is not loaded Page fault processing -- three cases: If the process has not yet loaded the full number of page frames allotted by the operating system: Read new page from disk into an unused page frame Else select a page for page replacement. If the selected page is clean (has not been written into since it was loaded): Read new page from disk into the selected page frame Else the selected page is dirty (has been written into since it was loaded): Write old page from the selected page frame to disk Read new page from disk into the selected page frame Metrics for measuring virtual memory performance Hit ratio = 1 - miss ratio Miss ratio = number of page faults / number of memory accesses Dirty miss ratio = number of page faults where a dirty page is replaced / number of memory accesses Effect of number of available page frames on metrics Page replacement algorithms Optimal (OPT) -- theoretical baseline First In First Out (FIFO) -- practical, easy to program, but tends not to be close to optimal Least Recently Used (LRU) -- practical, gives results close to optimal, but time-consuming Various other algorithms try to approximate LRU while taking less time Second Chance -- practical, results similar to LRU, easier to program and faster OPT page replacement algorithm example Replace the page that will not be needed again for the longest time in the future A process is using 4 page frames The process accesses the following sequence of pages: 6, 2, 6, 3, 4, 4, 0, 3, 7, 5, 2, 0, 0, 0, 1, 7 The OPT algorithm makes the following decisions: Pages Page Page Page Loaded Accessed Fault? Replaced . . . . 6 Yes . 6 . . . 2 Yes . 6 2 . . 6 . . 6 2 . . 3 Yes . 6 2 3 . 4 Yes . 6 2 3 4 4 . . 6 2 3 4 0 Yes 6 (or 4) 0 2 3 4 3 . . 0 2 3 4 7 Yes 3 (or 4) 0 2 7 4 5 Yes 4 0 2 7 5 2 . . 0 2 7 5 0 . . 0 2 7 5 0 . . 0 2 7 5 0 . . 0 2 7 5 1 Yes 0 (or 2 or 5) 1 2 7 5 7 . . 1 2 7 5 Number of page faults (misses) = 8 Number of page accesses = 16 Miss ratio = 8/16 = 0.5 Hit ratio = 1 − 0.5 = 0.5 FIFO page replacement algorithm example Replace the page that was loaded the longest ago in the past A process is using 4 page frames The process accesses the following sequence of pages: 6, 2, 6, 3, 4, 4, 0, 3, 7, 5, 2, 0, 0, 0, 1, 7 The FIFO algorithm makes the following decisions: Pages Page Page Page Loaded Accessed Fault? Replaced . . . . 6 Yes . 6 . . . 2 Yes . 6 2 . . 6 . . 6 2 . . 3 Yes . 6 2 3 . 4 Yes . 6 2 3 4 4 . . 6 2 3 4 0 Yes 6 2 3 4 0 3 . . 2 3 4 0 7 Yes 2 3 4 0 7 5 Yes 3 4 0 7 5 2 Yes 4 0 7 5 2 0 . . 0 7 5 2 0 . . 0 7 5 2 0 . . 0 7 5 2 1 Yes 0 7 5 2 1 7 . . 7 5 2 1 Number of page faults (misses) = 9 Number of page accesses = 16 Miss ratio = 9/16 = 0.56 Hit ratio = 1 − 0.56 = 0.44 LRU page replacement algorithm example Replace the page that was accessed the longest ago in the past A process is using 4 page frames The process accesses the following sequence of pages: 6, 2, 6, 3, 4, 4, 0, 3, 7, 5, 2, 0, 0, 0, 1, 7 The LRU algorithm makes the following decisions: Pages Page Page Page Loaded Accessed Fault? Replaced . . . . 6 Yes . 6 . . . 2 Yes . 6 2 . . 6 . . 2 6 . . 3 Yes . 2 6 3 . 4 Yes . 2 6 3 4 4 . . 2 6 3 4 0 Yes 2 6 3 4 0 3 . . 6 4 0 3 7 Yes 6 4 0 3 7 5 Yes 4 0 3 7 5 2 Yes 0 3 7 5 2 0 Yes 3 7 5 2 0 0 . . 7 5 2 0 0 . . 7 5 2 0 1 Yes 7 5 2 0 1 7 Yes 5 2 0 1 7 Number of page faults (misses) = 11 Number of page accesses = 16 Miss ratio = 11/16 = 0.69 Hit ratio = 1 − 0.69 = 0.31 Second Chance page replacement algorithm example Keep track of whether each page has been accessed Replace the page that was loaded the longest ago in the past (FIFO) . . . But if that page has been accessed, give it a second chance: move the page to the end of the queue, clear its accessed bit, and try the next page Repeat until we find a page with the accessed bit clear A process is using 4 page frames The process accesses the following sequence of pages: 6, 2, 6, 3, 4, 4, 0, 3, 7, 5, 2, 0, 0, 0, 1, 7 The Second Chance algorithm makes the following decisions: Pages Page Page Page Loaded Accessed Fault? Replaced . . . . 6 Yes . 6* . . . 2 Yes . 6* 2* . . 6 . . 6* 2* . . 3 Yes . 6* 2* 3* . 4 Yes . 6* 2* 3* 4* 4 . . 6* 2* 3* 4* 0 Yes 6 2 3 4 0* 3 . . 2 3* 4 0* 7 Yes 2 3* 4 0* 7* 5 Yes 4 0* 7* 3 5* 2 Yes 3 5* 0 7 2* 0 . . 5* 0* 7 2* 0 . . 5* 0* 7 2* 0 . . 5* 0* 7 2* 1 Yes 7 2* 5 0 1* 7 Yes 5 0 1* 2 5 *Accessed Number of page faults (misses) = 10 Number of page accesses = 16 Miss ratio = 10/16 = 0.63 Hit ratio = 1 − 0.63 = 0.37 Simulations -- see "Memory Trace Analysis" Operating Systems I • 4003-440-02 • Winter Quarter 2012 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 30-Jan-2013. Please send comments to ark­@­cs.rit.edu.