上海交通大学：《操作系统 Operating System》课程教学资源（课件讲稿）OS-Lec20_virtual memory

CHAPTER 9:VIRTUAL MEMORY

CHAPTER 9: VIRTUAL MEMORY

REVIEW o Virtual Memory o Demand Paging o Page fault o Page replacement

REVIEW  Virtual Memory  Demand Paging  Page fault  Page replacement

o Page Replacement o Copy-on-Write o Allocation of Frames o Thrashing o Memory-Mapped Files o Allocating Kernel Memory o Other Considerations o Operating-System Examples

 Page Replacement  Copy-on-Write  Allocation of Frames  Thrashing  Memory-Mapped Files  Allocating Kernel Memory  Other Considerations  Operating-System Examples

WHAT HAPPENS IF THERE IS NO FREE FRAME? o 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 o Same page may be brought into memory several times

WHAT 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

PAGE REPLACEMENT o Prevent over-allocation of memory by modifying page-fault service routine to include page replacement o Use modify (dirty)bit to reduce overhead of page transfers-only modified pages are written to disk o Page replacement completes separation between logical memory and physical memory-large virtual memory can be provided on a smaller physical memory

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 provided on a smaller physical memory

NEED FOR PAGE REPLACEMENT valid-invalid 0 H frame bit 0 monitor 7 load M 1 PC 3v 2 J 2 D 5 V 3 M i 3 H B logical memory page table 4 load M for user 1 for user 1 5 J 6 A M valid-invalid E 0 A frame bit physical 1 B memory 2 D i 3 E logical memory page table for user 2 for user 2

NEED FOR PAGE REPLACEMENT

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.Bring the desired page into the (newly)free frame; update the page and frame tables 4.Restart the process

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. Bring the desired page into the (newly) free frame; update the page and frame tables 4. Restart the process

PAGE REPLACEMENT frame valid-invalid bit swap out change victim 0 2) to invalid page ① f 4 f victim reset page page table table for new page swap desired page in physical memory

PAGE REPLACEMENT

PAGE REPLACEMENT ALGORITHMS o Want lowest page-fault rate o Evaluate algorithm by running it on a particular string of memory references (reference string)and computing the number of page faults on that string o In all our examples,the reference string is 1,2,3,4,1,2,5,1,2,3,4,5

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

GRAPH OF PAGE FAULTS VERSUS THE NUMBER OF FRAMES 6412 0 8 6 4 2 1 2 3 4 5 6 number of frames

GRAPH OF PAGE FAULTS VERSUS THE NUMBER OF FRAMES