FIFO, LRU, OPTIMAL Page Replacement Algorithm

Page Replacement is a very important topic in memory management. It is a part of the Operating System as well as Computer Architecture. There are so many page replacement algorithms. These 3 are too important algorithms. If you have any doubt regarding this, then you can mail me at - [email protected]
Youtube Channel Link - https://youtu.be/BoXrIOs2itc
Facebook Page Link - https://www.facebook.com/byte2bytelearn/
Twitter Link - https://twitter.com/bytes_learning
Stay tuned with Learning Bytes. I will upload more videos and slides.

1. PAGE REPLACEMENT ALGORITHMS ( FIFO / LRU / OPT ) A PRESENTATION BY ARIJIT ROY COMPUTER SCIENCE & ENGG. DEPT., 2 ND YEAR HOOGHLY ENGINEERING & TECHNOLOGY COLLEGE

2. FIFO PAGE REPLACEMENT ALGORITHM Suppose, all the page frames are filled with different pages. Now a new page request occurs. This required page is not present in any frame. Then the page which came first, that will swap out from the frame. New page will swap in to that empty frame.

3. Q. Suppose there are page requests 5,2,3,2,7,1,3,4,5,1. Assume there are 3 frames in RAM. Show the page replacement by FIFO algorithm and calculate – number of page hits and page faults, Hit ratio and miss ratio. 5 2 3 2 7 1 3 4 5 1

4. Q. Suppose there are page requests 5,2,3,2,7,1,3,4,5,1. Assume there are 3 frames in RAM. Show the page replacement by FIFO algorithm and calculate – number of page hits and page faults, Hit ratio and miss ratio. 5 2 3 2 7 1 3 4 5 1 5 5 2 5 2 3 5 2 3 7 2 3 7 1 3 3 1 7 7 1 4 4 1 5 5 1 4 Page Hit Page Fault No. of Page Hit = 3 No. of Page Fault = 7 Hit Ratio = (No. of Page Hit / Total Pages) = 3/10 Miss Ratio = (No. of Page Fault / Total Pages) = 1- Hit Ratio = 7/10

5. LRU PAGE REPLACEMENT ALGORITHM Suppose, all the page frames are filled with different pages. Now a new page request occurs. This required page is not present in any frame. Then the page which is least recently used that will swap out. New page will swap in to that empty frame.

6. Q. Suppose there are page requests 2,3,1,2,4,1,6,2,5,4. Assume there are 3 frames in RAM. Show the page replacement by LRU algorithm and calculate – number of page hits and page faults, Hit ratio and miss ratio. 2 3 1 2 4 1 6 2 5 4

7. Q. Suppose there are page requests 2,3,1,2,4,1,6,2,5,4. Assume there are 3 frames in RAM. Show the page replacement by LRU algorithm and calculate – number of page hits and page faults, Hit ratio and miss ratio. 2 3 1 2 4 1 6 2 5 4 2 2 2 2 2 2 6 6 6 4 2 5 5 1 1 1 1 1 1 3 3 3 4 4 4 2 2 No. of Page Hit = 2 No. of Page Fault = 8 Hit Ratio = (No. of Page Hit / Total Pages) = 2/10 = 1/5 Miss Ratio = (No. of Page Fault / Total Pages) = 1 – Hit Ratio = 8/10 = 4/5 Page Hit Page Fault

8. OPTIMAL PAGE REPLACEMENT ALGORITHM Suppose, all the page frames are filled with different pages. Now a new page request occurs. This required page is not present in any frame. Then the page which is used most later that will swap out. New page will swap in to that empty frame.

9. Q. Suppose there are page requests 2,1,5,3,4,2,5,1,2,5. Assume there are 3 frames in RAM. Show the page replacement by Optimal page replacement algorithm and calculate – number of page hits and page faults, Hit ratio and miss ratio. 2 1 5 3 4 2 5 1 2 5

10. Q. Suppose there are page requests 2,1,5,3,4,2,5,1,2,5. Assume there are 3 frames in RAM. Show the page replacement by Optimal p age replacement algorithm and calculate – number of page hits and page faults, Hit ratio and miss ratio. 2 1 5 3 4 2 5 1 2 5 Page Fault Page Hit 2 2 1 5 2 1 5 2 3 5 4 2 2 4 5 2 4 5 2 1 5 2 1 5 2 1 5 3 is not present. So it will use in far future. 4 is not present. So it will use in further future. No. of Page Hit = 4 No. of Page Fault = 6 Hit Ratio = (No. of Page Hit / Total Pages) = 4 /10 = 2/5 Miss Ratio = (No. of Page Fault / Total Pages) = 1 – Hit Ratio = 6 /10 = 3 /5

11. THAT’S ALL FOR THE DAY There is a set of problems from this algorithms are already given. You can download it from the link given below. Link - https://drive.google.com/open?id=10kDzksl-aaPcAESSTB3f30nnxBDhftvL Link is also given in description box. You can mail me the answer sheet on [email protected]

12. HOPE YOU GUYS ENJOY THIS SLIDE. SEE YOU IN THE NEXT VIDEO. STAY HO ME, ST AY SAFE.