Page replacement algorithms
Download as pptx, pdf40 likes56,540 views
This document discusses various page replacement algorithms used in operating systems. It begins with definitions of paging and page replacement in virtual memory systems. There are then overviews of 12 different page replacement algorithms including FIFO, optimal, LRU, NRU, NFU, second chance, clock, and random. The goal of page replacement algorithms is to minimize page faults. The document provides examples and analyses of how each algorithm approaches replacing pages in memory.
More Related Content
What's hot (20)
Viewers also liked (11)
Similar to Page replacement algorithms (20)
More from Piyush Rochwani (20)
Recently uploaded (20)
Page replacement algorithms
- 1. Page Replacement Algorithms FIFO, NRU, LRU, NFU...
- 2. Index S. No. Topic 1. Paging 2. Page Replacement 3. Algorithms a. Optimal b. FIFO c. NFU d. NRU e. LRU f. Second Chance g. CLOCK h. Random i. Working Set 4. Conclusion 5. References
- 3. Plan of Action • What is paging? • What is page replacement? • What are the types of page replacement? • Why we need a page replacement algorithm? • What are the algorithms?
- 4. What is Paging? • The OS divides virtual memory and the main memory into units, called pages. • Each used page can be either in secondary memory or in a page frame in main memory. • A frame does not have to comprise a single physically contiguous region in secondary storage.
- 5. What is page replacement? • When memory located in secondary memory is needed, it can be retrieved back to main memory. • Process of storing data from main memory to secondary memory ->swapping out • Retrieving data back to main memory ->swapping in
- 7. What are Page Replacement Algorithms? • Deals with which pages need to be swapped out and which are the ones that need to be swapped in • The efficiency lies in the least time that is wasted for a page to be paged in
- 8. Types • Local Page Replacement Strategy • Global Page Replacement Strategy
- 9. Why we need a page replacement algorithm? • The main goal of page replacement algorithms is to provide lowest page fault rate.
- 11. No. of Page Faults Vs No. of Frames
- 12. Algorithms • First In First Out • Optimal Replacement • Not Recently Used • Second Chance • CLOCK • Not Frequently Used • Least Recently Used • Random Replacement • Working Set Replacement
- 13. First-In First-Out (FIFO) • Pages in main memory are kept in a list • Newest page is in head and the oldest in tail • It does not take advantage of page access patterns or frequency
- 14. Fig: FIFO
- 15. FIFO Example Oldest Hit Hit Hit Newest Fig: FIFO example
- 16. Optimal Replacement (OPT) • When the memory is full, evict a page that will be unreferenced for the longest time • The OS keeps track of all pages referenced by the program • Only if the program's memory reference pattern is relatively consistent
- 17. OPTIMAL Example Referenced last Hit Hit HitHit Hit Hit Fig: OPTIMAL example
- 18. Not Recently Used (NRU) • It favours keeping pages in memory that have been recently used. • The OS divides the pages into four classes based on usage during the last clock tick: 3. Referenced, modified 2. Referenced, not modified 1. Not referenced, modified 0. Not referenced, not modified
- 19. NRU • Pick a random page from the lowest category for removal • i.e. the not referenced, not modified page
- 20. NRU Example Fig: NRU example Recently referenced Hit Hit Hit Hit Hit Hit
- 21. Second Chance • Modified version of FIFO • Instead of swapping out the last page, the referenced bit is checked • Gives every page a "second-chance"
- 23. Clock • Modified version of FIFO • The set of frame candidates for replacement is considered as a circular buffer.
- 24. Fig: CLOCK
- 25. Least Recently Used (LRU) • It swaps the pages that have been used the least over a period of time. • It is free from Belady’s anomaly.
- 26. LRU Example Recently referenced Hit Hit Hit Hit Hit Hit Fig: LRU example
- 27. Not frequently used (NFU) • This page replacement algorithm requires a counter • The counters keep track of how frequently a page has been used • The page with the lowest counter can be swapped out
- 28. reference sequence : 3 2 3 0 8 4 2 5 0 9 8 3 2 P U 3 P U 2 P U 3 P U 0 P U 8 P U 4 +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | | 0 |* | 3 | 1 | | 3 | 1 | | 3 | 1 | | 3 | 1 | | 3 | 1 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | | 0 | | | 0 |* | 2 | 1 | | 2 | 1 | | 2 | 1 | | 2 | 1 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | | 0 | | | 0 | | | 0 |* | | 0 |* | 0 | 1 | | 0 | 1 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | | 0 | | | 0 | | | 0 | | | 0 | | | 0 |* | 8 | 1 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | | 0 | | | 0 | | | 0 | | | 0 | | | 0 | | | 0 |* +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---- P U 2 P U 5 P U 0 P U 9 P U 8 P U 3 +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | 3 | 1 |* | 3 | 1 |* | 5 | 1 | | 5 | 1 | | 5 | 1 | | 5 | 1 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | 2 | 1 | | 2 | 1 | | 2 | 0 |* | 2 | 0 |* | 9 | 1 | | 9 | 1 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | 0 | 1 | | 0 | 1 | | 0 | 0 | | 0 | 1 | | 0 | 1 |* | 0 | 1 |* +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | 8 | 1 | | 8 | 1 | | 8 | 0 | | 8 | 0 | | 8 | 0 | | 8 | 1 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | 4 | 1 | | 4 | 1 | | 4 | 0 | | 4 | 0 | | 4 | 0 | | 4 | 0 | +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---- P U 2 P U +---+---+ +---+---+ * = indicates the pointer which identifies the next location | 5 | 1 |* | 5 | 0 | to scan P = page# stored in that frame U = used flag | 9 | 1 | | 9 | 0 | 0 = not used recently 1 = referenced recently +---+---+ +---+---+ | 0 | 0 | | 2 | 1 | +---+---+ +---+---+ | 8 | 0 | | 8 | 0 |* +---+---+ +---+---+ | 3 | 1 | | 3 | 1 | +---+---+ +---+---+ Fig: NFU example
- 29. Random • This algorithm replaces a random page in memory. • It fares better than FIFO.
- 30. Working set page replacement • The set of pages that a process is currently using is called the working set. • The working set algorithm is based on determining a working set and evicting any page that is not in the current working set upon a page fault.
- 32. Conclusion Algorithm Comment • FIFO • OPTIMAL • LRU • NRU • NFU • Second Chance • CLOCK • Might throw out important pages • Not implementable • Excellent but difficult to implement • Crude approximation of LRU • Crude approximation of LRU • Big improvement over FIFO • Realistic
- 33. References • Web Links www.wikipedia.com www.youtube.com www.vbForum.com • Papers Operating System Page Replacement Algorithms by A. Frank C. Wersberg • Books Computer Organization & Architecture by William Stallings
- 34. Thank You
Editor's Notes
- #5: may exceed the amount of main memory-> virtual memory active part in main memory and the rest in secondary memory Data read in pages
- #9: a local page replacement algorithm selects for replacement some page that belongs to that same process (or a group of processes sharing a memory partition). A global replacement algorithm is free to select any page in memory.
- #12: Belady’s anamoly-page fault inc with no. of frames
- #16: Disadvantage->page that is referenced frequently also gets replaced->doesn’t take care of that belady’s anamoly
- #17: Covers up the disadvantage of FIFO Unreferenced for the longest time->replace that page Os will keep track->pattern should be consistent
- #18: Free of belady’s anamoly
- #19: Covers up the disadvantage of FIFO Instead of
- #21: Free from belady’s anamoly
- #26: LRU keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval.
- #27: Free from belady’s anamoly