Computer Operating System - Lecture 10: Virtual Memory - Nguyen Thanh Son

Nội dung text: Computer Operating System - Lecture 10: Virtual Memory - Nguyen Thanh Son

1. Chapter’s Content  Background  Demand Paging  Process Creation  Page Replacement  Allocation of Frames  Thrashing  Operating System Examples BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 2
2. Virtual Memory That is Larger Than Physical Memory BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 4
3. Transfer of a Paged Memory to Contiguous Disk Space BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 6
4. Page Table When Some Pages Are Not in Main Memory BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 8
5. Steps in Handling a Page Fault BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 10
6. 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) BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 12
7. Process Creation  Virtual memory allows other benefits during process creation: - Copy-on-Write - Memory-Mapped Files BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 14
8. 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 ordinary memory 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. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 16
9. Page 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 BK TP.HCM provided on a smaller physical memory. 07-Feb-17 Faculty of Computer Science & Engineering 18
10. Basic Page Replacement 1) 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. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 20
11. Page 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. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 22
12. First-In-First-Out (FIFO) Algorithm  Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 1 4 5  3 frames (3 pages can be in 9 page faults 2 2 1 3 memory at a time per process) 2 4 3 3  4 frames 1 1 5 4 10 page faults FIFO Replacement – Belady’s 2 2 1 5 Anomaly 3 3 2  more frames less page 4 4 3 faults BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 24
13. Optimal Algorithm  Replace page that will not be used for longest period of time.  4 frames example: 4 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 2 6 page faults 3 4 5  How do you know this?  Used for measuring how well your algorithm performs. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 26
14. Least Recently Used (LRU) Algorithm  Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 5 2 3 5 4  Counter implementation 4 3  Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter.  When a page needs to be changed, look at the counters to determine which are to change. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 28
15. LRU Algorithm (Cont.)  Stack implementation – keep a stack of page numbers in a double link form:  Page referenced:  move it to the top  requires 6 pointers to be changed  No search for replacement BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 30
16. LRU Approximation Algorithms  Reference bit  With each page associate a bit, initially = 0  When page is referenced bit set to 1.  Replace the one which is 0 (if one exists). We do not know the order, however.  Second chance  Need reference bit.  Clock replacement.  If page to be replaced (in clock order) has reference bit = 1. then:  set reference bit 0.  leave page in memory.  replace next page (in clock order), subject to same rules. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 32
17. Counting Algorithms  Keep a counter of the number of references that have been made to each page.  LFU Algorithm: replaces page with smallest count.  MFU Algorithm: based on the argument that the page with the smallest count was probably just brought in and has yet to be used. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 34
18. Fixed Allocation si size of process pi  Equal allocation – S si e.g., if 100 frames m total number of frames s and 5 processes, a allocation for p i m i i S give each 20 m 64 pages. si 10  Proportional s2 127 allocation – 10 a 64 5 Allocate according 1 137 127 to the size of a 64 59 2 137 BK process. TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 36
19. Global vs. Local Allocation  Global replacement – process selects a replacement frame from the set of all frames; one process can take a frame from another.  Local replacement – each process selects from only its own set of allocated frames. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 38
20. Thrashing (Cont.)  Why does paging work? Locality model  Process migrates from one locality to another.  Localities may overlap.  Why does thrashing occur?  size of locality > total memory size BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 40
21. Working-Set Model   working-set window  a fixed number of page references Example: 10,000 instruction  WSSi (working set of Process Pi) = total number of pages referenced in the most recent (varies in time)  if too small will not encompass entire locality.  if too large will encompass several localities.  if = will encompass entire program.  D =  WSSi  total demand frames  if D > m Thrashing  Policy if D > m, then suspend one of the processes. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 42
22. Keeping Track of the Working Set  Approximate with interval timer + a reference bit  Example: = 10,000  Timer interrupts after every 5000 time units.  Keep in memory 2 bits for each page.  Whenever a timer interrupts copy and sets the values of all reference bits to 0.  If one of the bits in memory = 1 page in working set.  Why is this not completely accurate?  Improvement = 10 bits and interrupt every 1000 time units. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 44
23. Other Considerations  Prepaging  Page size selection  fragmentation  table size  I/O overhead  locality BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 46
24. Increasing the Size of the TLB  Increase the Page Size. This may lead to an increase in fragmentation as not all applications require a large page size.  Provide Multiple Page Sizes. This allows applications that require larger page sizes the opportunity to use them without an increase in fragmentation. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 48
25. Other Considerations (Cont.)  I/O Interlock – Pages must sometimes be locked into memory.  Consider I/O. Pages that are used for copying a file from a device must be locked from being selected for eviction by a page replacement algorithm. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 50
26. Operating System Examples  Windows NT  Solaris 2 BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 52
27. Solaris 2  Maintains a list of free pages to assign faulting processes.  Lotsfree – threshold parameter to begin paging.  Paging is peformed by pageout process.  Pageout scans pages using modified clock algorithm.  Scanrate is the rate at which pages are scanned. This ranged from slowscan to fastscan.  Pageout is called more frequently depending upon the amount of free memory available. BK TP.HCM 07-Feb-17 Faculty of Computer Science & Engineering 54