FIRST-IN-FIRST-OUT FIFO)ALGORITHM o Reference string:1,2,3,4,1,2,5,1,2,3,4,5 o 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 24 o 4 frames 1 1 5 4 2 2 1 5 10 page faults 3 3 2 4 3 o Belady's Anomaly:more frames=>more page faults
FIRST-IN-FIRST-OUT (FIFO) ALGORITHM Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process) 4 frames Belady’s Anomaly: more frames more page faults 1 2 3 1 2 3 4 1 2 5 3 4 9 page faults 1 2 3 1 2 3 5 1 2 4 5 10 page faults 4 4 3
FIFO PAGE REPLACEMENT reference string 7 0120304230321201701 2 4 0 0 0 7 0 3 3 3 2 2 1 1 1 0 0 1 0 0 3 3 3 2 2 2 page frames
FIFO PAGE REPLACEMENT
FIFO ILLUSTRATING BELADY'S ANOMALY 16 siine,ebed jo Jequnu 4120 8 6 4 2 1 2 3 4 6 6 number of frames
FIFO ILLUSTRATING BELADY’S ANOMALY
OPTIMAL ALGORITHM o Replace page that will not be used for longest period of time 。4 frames example 1,2,3,4,1,2,5,1,2,3,4,5 1 4 6 page faults 2 3 4 5 o How do you know this? o Used for measuring how well your algorithm performs
OPTIMAL ALGORITHM Replace page that will not be used for longest period of time 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 How do you know this? Used for measuring how well your algorithm performs 1 2 3 4 6 page faults 4 5
OPTIMAL PAGE REPLACEMENT reference string 7012 03 0423032120170 1 2 2 2 2- 7- 0 20 0 0 3 43 3 1 page frames
OPTIMAL PAGE REPLACEMENT