Page Replacement Algorithms

The page replacement algorithms decide which page will be replaced in the main memory. The process of replacing the pages is known as swapping. Page replacement algorithms are used when the referred page is not in the main memory. If a page fault occurs, then page replacement algorithms are used.

Virtual memory works under the two basic concepts  as given in the diagram,

Page-Replacement-algorithms-in-os

1. Frame allocation: It tells how many frames will be allocated to the process. If a higher number of frames is assigned to the process, then the page fault rate will be the minimum.

2. Page Replacement: It tells which page is to be replaced. It depends on several page replacement algorithms explained below.

Importance of page replacement algorithms

The page replacement algorithms are used to decide the page number to replace to make some space for the requested page.

 If the page replacement algorithms are not used, there may be many problems like page faults. Due to the high page fault rate, thrashing comes into the picture. In this way, the performance of the system is decreased.

For high-performance systems, page replacement algorithms are the key point. Page replacement algorithms try to ensure that replaced pages will not be used soon. So, the hit rate of pages is maximum, and page fault is minimum.

Types of Page Replacement Algorithms

Different methods are used to replace the pages in the main memory.

1. Optimal Page Replacement Algorithm: This algorithm is not practically implantable but is used as a benchmark. According to this algorithm, replace those pages that will not be requested for long. However, it cannot be practically implemented because the OS cannot decide in advance which page should be used in the future.

2. Least Recent Used (LRU): This algorithm looks at the past instead of the future. It replaces those pages which have not been used for a long time. It is the opposite form of the Optimal Page Replacement algorithm.

3. FIFO:  According to this algorithm, the page given the frame in main memory will be replaced first. For this purpose, a queue is used.

Question Practice

Question. Consider a reference string with values 1,2,3,4,1,2,5,1,2,3,4 and 5. The number of frames in the memory is 3. Find the number of page misses (page faults) and page hits respective to:

  1. Optimal Page Replacement Algorithm
  2. FIFO Page Replacement Algorithm
  3. LRU Page Replacement Algorithm

1. Optimal Page Replacement Algorithm

Optimal-page-replacement-algorithm

As the main memory is empty, when the CPU requests the first pages, the OS must load it first from the main memory from the secondary memory. So it will be the first-page fault. Now, CPU requests for pages number 2 and 3. “As neither of these pages currently exist in the main memory.” So, again, two page faults occur.

Look at the point when the CPU requests the 4th page; the main memory is full with three pages (1, 2, and 3). Now, CPU request for page 4. We will see this in the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, and 5. Check the string after the 4th page toward the end of the string. We conclude that pages 1 and 2 are requested soon after page 4. Page no 3 will requested later by the CPU than the other two pages (1 and 2) through the Reference string. So, page number 3 is replaced with page number 4. And So on…

  • Number of Page Faults in Optimal Page Replacement Algorithm = 07
  • Number of Page Hit in Optimal Page Replacement Algorithm = 05

2. LRU Page Replacement Algorithm

least-recently-used in OS

Like optimal page replacement, look at when the CPU requests the 4th page and the main memory is full with three pages (1, 2, and 3). OS will see the past of the reference string, which is 1,2,3,4,1,2,5,1,23,4 and 5. By checking the reference string from the 4th page toward the start of a string, OS decides that pages 3 and 2 are recently used, and CPU may request these pages very soon, so don’t replace pages 1 and 2. But Page number 1 is the least recently used than the other two pages (2 and 3) in memory. So, page number 1 is replaced with page number 4. And So on…

  • Number of Page Faults in LRU = 10
  • Number of Page Hit in LRU = 2

3. FIFO Page Replacement Algorithm

FIFO page-replacement-algorithm

As OS requests for the 4th-page number, 4 in the reference string, to execute, it is replaced with page 1 because it first came in memory, so it is replaced first.

In the same way, upcoming 2 is replaced with 1, and 3 is replaced with 2 because they first came in the main memory. as shown in the above picture.

Now, page 5 at the 7th position in the reference string is replaced with page 4 because page 4 first came as compared to other pages (1 and 2), which are still in the main memory.

Next, OS demands pages 1 and 2. Both of these already exist in the main memory. So, it is a case of page Hit.

After two consecutive page hits, the CPU requests page 3, and page 3 is replaced with page 1. Because page 1 came first as compared to two other pages (5 and 2) in the main memory. And so on.

  • Number of Page Faults in FIFO = 09
  • Number of Page Hit in FIFO = 03

Belady’s Anomaly

In the case of LRU and optimal page replacement algorithms, it can be seen that if we increase the number of frames, page faults will be reduced.

However, Balady introduced the strange behavior of FIFO. According to this, if we increase the number of frames, then page faults will also increase in the FIFO page replacement algorithm. It is called the Belady’s Anomaly.

Let’s explain with an example:

Let’s suppose the same reference string just like the FIFO as 1,2,3,4,1,2,5,1,2,3,4 and 5. And the number of frames in the memory is 4.

Belady's-Anomaly in os

Now, analyze the behavior of the FIFO algorithm in the case when the number of frames is 3 and 4.

Case 1: Number of frames = 3

Number of Page Faults = 09. It is already covered in the FIFO page replacement algorithm.

Case 2: Number of frames = 4

Number of Page Faults = 10

As an example shows, if the number of page frames increases, the number of page faults will also increase. It is a Belady’s Anomaly.