›

Bài giảng Operarting System Concepts - Chapter 10: Virtual Memory

ppt 55 trang huongle 3040
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Operarting System Concepts - Chapter 10: Virtual Memory", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_operarting_system_concepts_chapter_10_virtual_memo.ppt

Nội dung text: Bài giảng Operarting System Concepts - Chapter 10: Virtual Memory

  1. Chapter 10: Virtual Memory n Background n Demand Paging n Process Creation n Page Replacement n Allocation of Frames n Thrashing n Operating System Examples Operating System Concepts 10.1 Silberschatz, Galvin and Gagne 2002
  2. Background n Virtual memory – separation of user logical memory from physical memory. F Only part of the program needs to be in memory for execution. F Logical address space can therefore be much larger than physical address space. F Allows address spaces to be shared by several processes. F Allows for more efficient process creation. n Virtual memory can be implemented via: F Demand paging F Demand segmentation Operating System Concepts 10.2 Silberschatz, Galvin and Gagne 2002
  3. Virtual Memory That is Larger Than Physical Memory Operating System Concepts 10.3 Silberschatz, Galvin and Gagne 2002
  4. Demand Paging n Bring a page into memory only when it is needed. F Less I/O needed F Less memory needed F Faster response F More users n Page is needed reference to it F invalid reference abort F not-in-memory bring to memory Operating System Concepts 10.4 Silberschatz, Galvin and Gagne 2002
  5. Transfer of a Paged Memory to Contiguous Disk Space Operating System Concepts 10.5 Silberschatz, Galvin and Gagne 2002
  6. Valid-Invalid Bit n With each page table entry a valid–invalid bit is associated (1 in-memory, 0 not-in-memory) n Initially valid–invalid but is set to 0 on all entries. n Example of a page table snapshot. Frame # valid-invalid bit 1 1 1 1 0  0 0 page table n During address translation, if valid–invalid bit in page table entry is 0 page fault. Operating System Concepts 10.6 Silberschatz, Galvin and Gagne 2002
  7. Page Table When Some Pages Are Not in Main Memory Operating System Concepts 10.7 Silberschatz, Galvin and Gagne 2002
  8. Page Fault n If there is ever a reference to a page, first reference will trap to OS page fault n OS looks at another table to decide: F Invalid reference abort. F Just not in memory. n Get empty frame. n Swap page into frame. n Reset tables, validation bit = 1. n Restart instruction: Least Recently Used F block move F auto increment/decrement location Operating System Concepts 10.8 Silberschatz, Galvin and Gagne 2002
  9. Steps in Handling a Page Fault Operating System Concepts 10.9 Silberschatz, Galvin and Gagne 2002
  10. What happens if there is no free frame? n Page replacement – find some page in memory, but not really in use, swap it out. F algorithm F performance – want an algorithm which will result in minimum number of page faults. n Same page may be brought into memory several times. Operating System Concepts 10.10 Silberschatz, Galvin and Gagne 2002
  11. Performance of Demand Paging n Page Fault Rate 0 p 1.0 F if p = 0 no page faults F if p = 1, every reference is a fault n Effective Access Time (EAT) EAT = (1 – p) x memory access + p (page fault overhead + [swap page out ] + swap page in + restart overhead) Operating System Concepts 10.11 Silberschatz, Galvin and Gagne 2002
  12. Demand Paging Example n Memory access time = 1 microsecond n 50% of the time the page that is being replaced has been modified and therefore needs to be swapped out. n Swap Page Time = 10 msec = 10,000 msec EAT = (1 – p) x 1 + p (15000) 1 + 15000P (in msec) Operating System Concepts 10.12 Silberschatz, Galvin and Gagne 2002
  13. Process Creation n Virtual memory allows other benefits during process creation: - Copy-on-Write - Memory-Mapped Files Operating System Concepts 10.13 Silberschatz, Galvin and Gagne 2002
  14. Copy-on-Write n 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. n COW allows more efficient process creation as only modified pages are copied. n Free pages are allocated from a pool of zeroed-out pages. Operating System Concepts 10.14 Silberschatz, Galvin and Gagne 2002
  15. Memory-Mapped Files n 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. n 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. n Simplifies file access by treating file I/O through memory rather than read() write() system calls. n Also allows several processes to map the same file allowing the pages in memory to be shared. Operating System Concepts 10.15 Silberschatz, Galvin and Gagne 2002
  16. Memory Mapped Files Operating System Concepts 10.16 Silberschatz, Galvin and Gagne 2002
  17. Page Replacement n Prevent over-allocation of memory by modifying page- fault service routine to include page replacement. n Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk. n Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory. Operating System Concepts 10.17 Silberschatz, Galvin and Gagne 2002
  18. Need For Page Replacement Operating System Concepts 10.18 Silberschatz, Galvin and Gagne 2002
  19. Basic Page Replacement n Find the location of the desired page on disk. n 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. n Read the desired page into the (newly) free frame. Update the page and frame tables. n Restart the process. Operating System Concepts 10.19 Silberschatz, Galvin and Gagne 2002
  20. Page Replacement Operating System Concepts 10.20 Silberschatz, Galvin and Gagne 2002
  21. Page Replacement Algorithms n Want lowest page-fault rate. n Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string. n In all our examples, the reference string is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Operating System Concepts 10.21 Silberschatz, Galvin and Gagne 2002
  22. Graph of Page Faults Versus The Number of Frames Operating System Concepts 10.22 Silberschatz, Galvin and Gagne 2002
  23. First-In-First-Out (FIFO) Algorithm n Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 n 3 frames (3 pages can be in memory at a time per process) 1 1 4 5 2 2 1 3 9 page faults 3 3 2 4 n 4 frames 1 1 5 4 2 2 1 5 10 page faults 3 3 2 4 4 3 n FIFO Replacement – Belady’s Anomaly F more frames less page faults Operating System Concepts 10.23 Silberschatz, Galvin and Gagne 2002
  24. FIFO Page Replacement Operating System Concepts 10.24 Silberschatz, Galvin and Gagne 2002
  25. FIFO Illustrating Belady’s Anamoly Operating System Concepts 10.25 Silberschatz, Galvin and Gagne 2002
  26. Optimal Algorithm n Replace page that will not be used for longest period of time. n 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 4 2 6 page faults 3 4 5 n How do you know this? n Used for measuring how well your algorithm performs. Operating System Concepts 10.26 Silberschatz, Galvin and Gagne 2002
  27. Optimal Page Replacement Operating System Concepts 10.27 Silberschatz, Galvin and Gagne 2002
  28. Least Recently Used (LRU) Algorithm n Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 5 2 3 5 4 4 3 n Counter implementation F Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter. F When a page needs to be changed, look at the counters to determine which are to change. Operating System Concepts 10.28 Silberschatz, Galvin and Gagne 2002
  29. LRU Page Replacement Operating System Concepts 10.29 Silberschatz, Galvin and Gagne 2002
  30. LRU Algorithm (Cont.) n Stack implementation – keep a stack of page numbers in a double link form: F Page referenced: 4 move it to the top 4 requires 6 pointers to be changed F No search for replacement Operating System Concepts 10.30 Silberschatz, Galvin and Gagne 2002
  31. Use Of A Stack to Record The Most Recent Page References Operating System Concepts 10.31 Silberschatz, Galvin and Gagne 2002
  32. LRU Approximation Algorithms n Reference bit F With each page associate a bit, initially = 0 F When page is referenced bit set to 1. F Replace the one which is 0 (if one exists). We do not know the order, however. n Second chance F Need reference bit. F Clock replacement. F If page to be replaced (in clock order) has reference bit = 1. then: 4 set reference bit 0. 4 leave page in memory. 4 replace next page (in clock order), subject to same rules. Operating System Concepts 10.32 Silberschatz, Galvin and Gagne 2002
  33. Second-Chance (clock) Page-Replacement Algorithm Operating System Concepts 10.33 Silberschatz, Galvin and Gagne 2002
  34. Counting Algorithms n Keep a counter of the number of references that have been made to each page. n LFU Algorithm: replaces page with smallest count. n MFU Algorithm: based on the argument that the page with the smallest count was probably just brought in and has yet to be used. Operating System Concepts 10.34 Silberschatz, Galvin and Gagne 2002
  35. Allocation of Frames n Each process needs minimum number of pages. n Example: IBM 370 – 6 pages to handle SS MOVE instruction: F instruction is 6 bytes, might span 2 pages. F 2 pages to handle from. F 2 pages to handle to. n Two major allocation schemes. F fixed allocation F priority allocation Operating System Concepts 10.35 Silberschatz, Galvin and Gagne 2002
  36. Fixed Allocation n Equal allocation – e.g., if 100 frames and 5 processes, give each 20 pages. n Proportional allocation – Allocate according to the size of process. Operating System Concepts 10.36 Silberschatz, Galvin and Gagne 2002
  37. Priority Allocation n Use a proportional allocation scheme using priorities rather than size. n If process Pi generates a page fault, F select for replacement one of its frames. F select for replacement a frame from a process with lower priority number. Operating System Concepts 10.37 Silberschatz, Galvin and Gagne 2002
  38. Global vs. Local Allocation n Global replacement – process selects a replacement frame from the set of all frames; one process can take a frame from another. n Local replacement – each process selects from only its own set of allocated frames. Operating System Concepts 10.38 Silberschatz, Galvin and Gagne 2002
  39. Thrashing n If a process does not have “enough” pages, the page- fault rate is very high. This leads to: F low CPU utilization. F operating system thinks that it needs to increase the degree of multiprogramming. F another process added to the system. n Thrashing  a process is busy swapping pages in and out. Operating System Concepts 10.39 Silberschatz, Galvin and Gagne 2002
  40. Thrashing n Why does paging work? Locality model F Process migrates from one locality to another. F Localities may overlap. n Why does thrashing occur?  size of locality > total memory size Operating System Concepts 10.40 Silberschatz, Galvin and Gagne 2002
  41. Locality In A Memory-Reference Pattern Operating System Concepts 10.41 Silberschatz, Galvin and Gagne 2002
  42. Working-Set Model n  working-set window  a fixed number of page references Example: 10,000 instruction n WSSi (working set of Process Pi) = total number of pages referenced in the most recent (varies in time) F if too small will not encompass entire locality. F if too large will encompass several localities. F if = will encompass entire program. n D =  WSSi  total demand frames n if D > m Thrashing n Policy if D > m, then suspend one of the processes. Operating System Concepts 10.42 Silberschatz, Galvin and Gagne 2002
  43. Working-set model Operating System Concepts 10.43 Silberschatz, Galvin and Gagne 2002
  44. Keeping Track of the Working Set n Approximate with interval timer + a reference bit n Example: = 10,000 F Timer interrupts after every 5000 time units. F Keep in memory 2 bits for each page. F Whenever a timer interrupts copy and sets the values of all reference bits to 0. F If one of the bits in memory = 1 page in working set. n Why is this not completely accurate? n Improvement = 10 bits and interrupt every 1000 time units. Operating System Concepts 10.44 Silberschatz, Galvin and Gagne 2002
  45. Page-Fault Frequency Scheme n Establish “acceptable” page-fault rate. F If actual rate too low, process loses frame. F If actual rate too high, process gains frame. Operating System Concepts 10.45 Silberschatz, Galvin and Gagne 2002
  46. Other Considerations n Prepaging n Page size selection F fragmentation F table size F I/O overhead F locality Operating System Concepts 10.46 Silberschatz, Galvin and Gagne 2002
  47. Other Considerations (Cont.) n TLB Reach - The amount of memory accessible from the TLB. n TLB Reach = (TLB Size) X (Page Size) n Ideally, the working set of each process is stored in the TLB. Otherwise there is a high degree of page faults. Operating System Concepts 10.47 Silberschatz, Galvin and Gagne 2002
  48. Increasing the Size of the TLB n Increase the Page Size. This may lead to an increase in fragmentation as not all applications require a large page size. n Provide Multiple Page Sizes. This allows applications that require larger page sizes the opportunity to use them without an increase in fragmentation. Operating System Concepts 10.48 Silberschatz, Galvin and Gagne 2002
  49. Other Considerations (Cont.) n Program structure F int A[][] = new int[1024][1024]; F Each row is stored in one page F Program 1 for (j = 0; j < A.length; j++) for (i = 0; i < A.length; i++) A[i,j] = 0; 1024 x 1024 page faults F Program 2 for (i = 0; i < A.length; i++) for (j = 0; j < A.length; j++) A[i,j] = 0; 1024 page faults Operating System Concepts 10.49 Silberschatz, Galvin and Gagne 2002
  50. Other Considerations (Cont.) n I/O Interlock – Pages must sometimes be locked into memory. n 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. Operating System Concepts 10.50 Silberschatz, Galvin and Gagne 2002
  51. Reason Why Frames Used For I/O Must Be In Memory Operating System Concepts 10.51 Silberschatz, Galvin and Gagne 2002
  52. Operating System Examples n Windows NT n Solaris 2 Operating System Concepts 10.52 Silberschatz, Galvin and Gagne 2002
  53. Windows NT n Uses demand paging with clustering. Clustering brings in pages surrounding the faulting page. n Processes are assigned working set minimum and working set maximum. n Working set minimum is the minimum number of pages the process is guaranteed to have in memory. n A process may be assigned as many pages up to its working set maximum. n When the amount of free memory in the system falls below a threshold, automatic working set trimming is performed to restore the amount of free memory. n Working set trimming removes pages from processes that have pages in excess of their working set minimum. Operating System Concepts 10.53 Silberschatz, Galvin and Gagne 2002
  54. Solaris 2 n Maintains a list of free pages to assign faulting processes. n Lotsfree – threshold parameter to begin paging. n Paging is peformed by pageout process. n Pageout scans pages using modified clock algorithm. n Scanrate is the rate at which pages are scanned. This ranged from slowscan to fastscan. n Pageout is called more frequently depending upon the amount of free memory available. Operating System Concepts 10.54 Silberschatz, Galvin and Gagne 2002
  55. Solar Page Scanner Operating System Concepts 10.55 Silberschatz, Galvin and Gagne 2002