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