Copyright

Page Replacement: Definition & Algorithms

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: What is an Access Violation Error?

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:04 What is Paging?
  • 0:56 Page Replacement Algorithms
  • 7:01 Lesson Summary
Save Save Save

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed

Recommended Lessons and Courses for You

Lesson Transcript
Instructor: Avinash Srinivasan
This lesson will introduce you to the concept of page replacement, which is used in memory management. You will understand the definition and the algorithms related to page replacement. We will also discuss briefly their relative usefulness.

What Is Paging?

Virtual memory is the lifeline of modern computer operating systems (OS). An OS makes use of a process called paging for virtual memory management (VMM). Paging is a process of reading data from, and writing data to, the secondary storage. Whenever a process refers to a page that is not present in memory, a page fault occurs. Subsequently, the OS replaces one of the existing pages with the referred page. Page replacement algorithms are an important part of virtual memory management and it helps the OS to decide which memory page can be moved out, making space for the currently needed page.

However, the ultimate objective of all page replacement algorithms is to reduce the number of page faults. A page fault is a computer hardware raised interrupt or an exception when a running program accesses a memory page that is not currently mapped into the virtual address space of the program.

Page Replacement Algorithms

In this section, we shall discuss some of the important page replacement algorithms that can be used by OS:

First-In-First-Out (FIFO)

With the FIFO algorithm, the OS maintains a queue to keep track of all the pages in memory, with the most recent arrival at the back (tail of the queue), and the oldest arrival in front (head of the queue). When the system needs space, a page will be replaced. With FIFO, the page at the front of the queue (the oldest page) is selected for replacement. However, FIFO is known to suffer from a problem known as Belady's anomaly, which occurs when increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.

Example

Assume there are 5 pages (0, 1, 2, 3, 4) in the secondary storage. A process references these pages in the order (1, 3, 4, 0, 2). Also, assume that the page buffer can hold up to 3 pages at a time. At the start of the system, the 3-page buffer is completely empty and we can denote it as | - | - | - |. The first 3 references made by the process will be to pages 1, 3, and 4, respectively. All three pages will be moved into the page buffer.

Reference to Page 1 --> | 1 | - | - |

Reference to Page 3 --> | 1 | 3 | - |

Reference to Page 4 --> | 1 | 3 | 4 |

At this time, the buffer is full. The next call by the process is for page 0, which is not in the page buffer. Therefore, FIFO will replace the oldest page, which is page 1.

Reference to Page 0 --> | - | 3 | 4 | --> | 3 | 4 | - | --> | 3 | 4 | 0 |

The next call by the process is for page 2, which is not in the page buffer. Therefore, FIFO will replace the oldest page, which is page 3.

Reference to Page 2 --> | - | 4 | 0 | --> | 4 | 0 | - | --> | 4 | 0 | 2 |

The pros and cons of FIFO algorithm are:

Pros Cons
Low-overhead algorithm Poor performance in its original form
Simple and easy to implement Simply replaces the oldest page; doesn't consider the frequency of use, last use time, etc.
Very intuitive Modified version of FIFO used by the VAX/VMS OS.

Least Recently Used (LRU)

The LRU page replacement algorithm keeps track of the usage of pages over a defined time-window. When its time to replace a page, it replaces the page that is least recently used.

Example

Assume there are 5 pages (0, 1, 2, 3, 4) in the secondary storage. A process references these pages in the order (4, 0, 1, 2, 0, 3, 0, 2). Also, assume the page buffer can hold 3 pages at a time. At the start of the system, the 3-page buffer is completely empty and we can denote it as | - | - | - |. The first 3 references made by the process will be to pages 4, 0, and 1, respectively. All three pages will be moved into the page buffer.

Reference to Page 4 --> | 4 | - | - |

Reference to Page 0 --> | 4 | 0 | - |

Reference to Page 1 --> | 4 | 0 | 1 |

At this time, the buffer is full. The next call by the process is for page 2, which is not in the page buffer. Therefore, LRU will replace the least recently used page, which is page 4.

Reference to Page 2 --> | - | 0 | 1 | --> | 0 | 1 | - | --> | 0 | 1 | 2 |

The next call by the process is to page 0, which is in memory. LRU will not replace any page since the request is satisfied without a page fault.

Reference to Page 0 --> | 0 | 1 | 2 |

The next call by the process is for page 3, which is not in memory. Therefore, LRU will replace the least recently used page, which in this example, is page 1.

Reference to Page 3 --> | 0 | - | 2 | --> | 0 | 3 | 2 |

The next call by the process is for page 0, which is in memory. LRU will not replace any page since the request is satisfied without a page fault.

Reference to Page 0 --> | 0 | 3 | 2 |

The next call by the process is for page 2, which is in memory. LRU will not replace any page since the request is satisfied without a page fault.

Reference to Page 2 --> | 0 | 3 | 2 |

The pros and cons of LRU algorithm are:

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support