24 Page Replacement Algorithms – II

Mary Anitha Rajam

 

27.1 Introduction

 

In this module, we learn what is meant by page replacement and two algorithms used for page replacement. In an earlier module, we learnt what demand paging is. In demand paging, pages are brought into memory only when the pages are needed. All the pages of a process need not be kept in the main memory at the same time. Only the pages that are used currently need to be kept in the main memory. Suppose a page is brought into the main memory and if there is no free frame in the main memory, a victim page is chosen from the main memory, the victim page is moved out to the backing store and the required page is brought into the main memory. Choosing a victim page for replacement is done by the page replacement algorithms. In the previous module we learnt the working of the First-In-First-Out (FIFO) page replacement algorithm, in which the page that was brought into the memory first is chosen for replacement first. But, FIFO suffers from Belady’s anomaly.

 

In this module, we learn the working of two more page replacement algorithms, Optimal page replacement (OPT) and Least recently used (LRU) page replacement algorithms.

 

27.2 Optimal (OPT) Page Replacement Algorithm

 

The optimal page replacement algorithm replaces the page that will not be used for longest period of time in future. This algorithm has the lowest page-fault of all algorithms. The OPT algorithm does not suffer from Belady’s anomaly.

 

Figure 27.1 shows an example of how page replacement is done using the OPT page replacement algorithm. The reference string 7, 0, 1, …, 1 is shown in the figure. There are three free frames in the physical memory. The first reference is to page 7 and 7 is brought into one of the free frames. The second reference is to page 0. Since there is a free frame, that page is also brought into the physical memory. The next reference is to page 1. Page 1 is also brought into the physical memory as there is a free frame.

 

The next reference is to page 2. Page 2 is not present in the physical memory and there is no free frame in the physical memory. Therefore a page that is already present in the main memory is to be chosen for replacement. Of the three pages (7, 0, 1) present in the main memory, the one that will not be used in the near future is chosen for replacement. Page 7 is the one that will not be used in the near future (this can be seen by observing the reference string). Before 7 will be used, pages 0 and 1 will be used. Therefore, page 7 is moved out to the disk and page 2 is brought into that place.

 

The next reference is to page 0. Page 0 is already present in the main memory. Therefore it is a hit and page 0 is used from the main memory. The next reference is to page 3. Page 3 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 0 and 1 present in the main memory, page 1 is the one that will not be used in the near future. Before 1 will be used, pages 2 and 0 will be used. Therefore, page 1 is moved out to the disk and page 3 is brought into that place.

 

The next reference is to page 0. Page 0 is already present in the main memory. Therefore it is a hit and page 0 is used from the main memory. The next reference is to page 4. Page 4 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 0 and 3 present in the main memory, page 0 is the one that will not be used in the near future. Before 0 will be used, pages 2 and 3 will be used. Therefore, page 0 is moved out to the disk and page 4 is brought into that place.

Fig. 27.1 Example for OPT page replacement (Source: [1])

 

The next reference is to page 2. Page 2 is already present in the main memory. Therefore, it is a hit and page 2 is used from the main memory. The next reference is to page 3. Page 3 is already present in the main memory. Therefore it is a hit and page 3 is used from the main memory.

 

The next reference is to page 0. Page 0 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 4 and 3 present in the main memory, page 4 is the one that will not be used in the near future. Before 4 will be used, pages 2 and 3 will be used. Therefore, page 4 is moved out to the disk and page 0 is brought into that place.

 

The next reference is to page 3. Page 3 is already present in the main memory. Therefore, it is a hit and page 3 is used from the main memory. The next reference is to page 2. Page 2 is already present in the main memory. Therefore it is a hit and page 2 is used from the main memory.

 

The next reference is to page 1. Page 1 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 0 and 3 present in the main memory, page 3 is the one that will not be used in the near future. Therefore, page 3 is moved out to the disk and page 1 is brought into that place.

 

The next reference is to page 2. Page 2 is already present in the main memory. Therefore, it is a hit and page 2 is used from the main memory. The next reference is to page 0. Page 0 is already present in the main memory. Therefore it is a hit and page 0 is used from the main memory. The next reference is to page 1. Page 1 is already present in the main memory. Therefore, it is a hit and page 1 is used from the main memory.

 

The next reference is to page 7. Page 7 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 0 and 1 present in the main memory, page 2 is the one that will not be used in the near future. Therefore, page 2 is moved out to the disk and page 7 is brought into that place.

 

The next reference is to page 0. Page 0 is already present in the main memory. Therefore, it is a hit and page 0 is used from the main memory. The next reference is to page 1. Page 1 is already present in the main memory. Therefore it is a hit and page 1 is used from the main memory.

 

The number of times when a page is brought into the main memory from the disk is the number of page faults. In the example shown above, the number of page faults is 9. This is less compared to the FIFO page replacement algorithm.

 

The disadvantage of the optimal page replacement algorithm is that it is difficult to implement. The OPT algorithm requires future knowledge of the replacement string. That is, the algorithm needs to know which pages will be referred to in future, which is practically impossible. This is similar to the situation in the SJF CPU scheduling algorithm. But, it is used mainly for comparison studies. When you devise your own page replacement algorithm, the performance of the devised algorithm can be compared with the performance of OPT.

 

We now learn another algorithm for page replacement called the least recently used (LRU) page replacement algorithm.

 

27.3 Least Recently Used (LRU) Algorithm 

 

Since the optimal algorithm is not practically feasible, an approximation to optimal algorithm was devised called the LRU algorithm. FIFO uses the time when a page was brought into memory. OPT uses the time when the page will be used in the future. In the LRU page replacement algorithm, recent past is looked at as an approximation of the near future. Here, the page that has not been used for the longest period of time in the past is chosen for replacement.

 

To implement LRU page replacement, the time of last use is associated with each page. Whenever a page is used, the time of use is updated. The page that has not been used for the longest period of time is chosen for replacement. Compared to OPT, this is looking backward in time, rather than looking forward in time.

Fig. 27.2 Example for LRU page replacement (Source: [1])

 

Figure 27.1 shows an example of how page replacement is done using the LRU page replacement algorithm. The reference string 7, 0, 1, …, 1 is shown in the figure. There are three free frames in the physical memory. The first reference is to page 7 and 7 is brought into one of the free frames. The second reference is to page 0. Since there is a free frame, that page is also brought into the physical memory. The next reference is to page 1. Page 1 is also brought into the physical memory as there is a free frame.

 

The next reference is to page 2. Page 2 is not present in the physical memory and there is no free frame in the physical memory. Therefore a page that is already present in the main memory is to be chosen for replacement. Of the three pages (7, 0, 1) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 7 is the one that was not used in the recent past. Page 7 was used before pages 0 and 1 were used. Therefore, page 7 is moved out to the disk and page 2 is brought into that place.

 

The next reference is to page 0. Page 0 is already present in the main memory. Therefore it is a hit and page 0 is used from the main memory. The next reference is to page 3. Page 3 is not present in the physical memory and there is no free frame in the physical memory. Therefore a page that is already present in the main memory is to be chosen for replacement. Of the three pages (2, 0, 1) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 1 is the one that was not used in the recent past. Page 1 was used before pages 2 and 0 were used. Therefore, page 1 is moved out to the disk and page 3 is brought into that place.

 

The next reference is to page 2. Page 2 is not present in the physical memory and there is no free frame in the physical memory. Therefore, of the three pages (4, 0, 3) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 3 is the one that was not used in the recent past. Page 3 was used before pages 4 and 0 were used. Therefore, page 3 is moved out to the disk and page 2 is brought into that place.The next reference is to page 0. Page 0 is already present in the main memory. Therefore it is a hit and page 0 is used from the main memory. The next reference is to page 4. Page 4 is not present in the physical memory and there is no free frame in the physical memory. Therefore, of the three pages (2, 0, 3) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 2 is the one that was not used in the recent past. Page 2 was used before pages 0 and 3 were used. Therefore, page 2 is moved out to the disk and page 4 is brought into that place.

 

The next reference is to page 3. Page 3 is not present in the physical memory and there is no free frame in the physical memory. Therefore, of the three pages (4, 0, 2) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 0 is the one that was not used in the recent past. Page 0 was used before pages 4 and 2 were used. Therefore, page 0 is moved out to the disk and page 3 is brought into that place.

 

The next reference is to page 0. Page 0 is not present in the physical memory and there is no free frame in the physical memory. Therefore, of the three pages (4, 3, 2) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 4 is the one that was not used in the recent past. Page 4 was used before pages 3 and 2 were used. Therefore, page 4 is moved out to the disk and page 0 is brought into that place.

 

The next reference is to page 2. Page 2 is already present in the main memory. Therefore it is a hit and page 2 is used from the main memory.

 

The next reference is to page 1. Page 1 is not present in the physical memory and there is no free frame in the physical memory. Therefore, of the three pages (0, 3, 2) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 0 is the one that was not used in the recent past. Page 0 was used before pages 3 and 2 were used.

 

Therefore, page 0 is moved out to the disk and page 1 is brought into that place.

 

The next reference is to page 2. Page 2 is already present in the main memory. Therefore it is a hit and page 2 is used from the main memory.

 

The next reference is to page 0. Page 0 is not present in the physical memory and there is no free frame in the physical memory. Therefore, of the three pages (1, 3, 2) present in the main memory, the one that was not used in the recent past is chosen for replacement. Page 3 is the one that was not used in the recent past. Page 3 was used before pages 1 and 2 were used. Therefore, page 3 is moved out to the disk and page 0 is brought into that place.

 

The next reference to page 1 is a hit. The next reference is to page 7. Page 7 is not present in the physical memory and there is no free frame in the physical memory. Therefore, of the three pages (1, 0, 2) present in the main memory, page 2 is the one that was not used in the recent past. Page 2 was used before pages 0 and 2 were used. Therefore, page 2 is moved out to the disk and page 7 is brought into that place. The next two references to pages 0 and 1 are hits.

 

In this example, the number of page faults is 12. It is seen that the number of page faults for LRU is less than that for FIFO (15 page faults) and greater than that for OPT (9 page faults) for the same reference string. The LRU algorithm is a good page replacement algorithm and is used often.

 

The LRU algorithm does not suffer from Belady’s anomaly. It is a type of stack algorithm. In stack algorithms, the set of pages in memory for n pages is always a subset of the set of pages in memory for n+1 pages. Because the algorithm looks at recently used pages, the pages that were used in the last ‘n’ references will be a subset of the pages that were used in the last ‘n+1’ memory references.

 

27.4  Implementation of LRU 

 

The implementation of LRU requires hardware support to determine the order of use based on the time of last use. There are two methods to implement the LRU algorithm: Counter implementation and Stack implementation.

 

27.4.1 LRU Algorithm – Counter Implementation 

 

Every page entry has a time-of use field. A counter is added to the CPU and the counter is initialized to zero. The counter is incremented for every memory reference. Every time page is referenced, the counter is copied into the time-of-use field. Therefore, the counter shows when the page was last referenced. When a page needs to be replaced, the page with the least value in the time-of-use field is picked.

 

The overheads involved in this method are:

 

(i)    It is required to search the page table to find the LRU page.

(ii)   It is required to write to the memory (Updating time-of-use field) for each memory access.

(iii)  The overflow of the clock must be considered. Since the clock is incremented for each memory reference, there is a possibility for the clock to overflow. This must be handled.

(iv) Times must be maintained when page tables are changed (CPU scheduling).

 

Even when a process is moved out of ready state during CPU scheduling, and later, is given the CPU, the same times should be maintained.

 

27.4.2 LRU Algorithm – Stack implementation 

 

In this method, a stack of page numbers is kept in a doubly linked list form. Whenever a page referenced, the page is moved to the top of stack. Then, the bottom of the stack has the LRU page. But this requires 6 pointers to be changed, if the page number that is moved is currently in the middle of the list. The  advantage  is  that there is no  need to search for replacement. It is enough to select the page whose number is kept in the bottom of the stack.

 

Figure 27.3 shows an example of how a stack can be used for implementing the LRU algorithm. The recently used page number is kept in the top of the stack. The stack before position ‘a’ is shown. Then there is a reference to page 7. Therefore, the entry in the stack corresponding to page 7 is moved to the top of the stack. The contents of the stack, after the reference to page 7 (at position ‘b’), are also shown in the figure.

Fig. 27.3 Use of a stack to record the most recent page references

 

27.5 Summary

 

In this module, we learnt the implementation of two page replacement algorithms, the optimal page replacement and the least recently used page replacement algorithms. In optimal page replacement algorithm the page that will not be used in the near future is chosen for replacement. In least recently used page replacement algorithm, the page that was not used in the recent past is chosen for replacement. We also learnt the counter and the stack methods used for implementing the LRU algorithm.

 

 

References

  1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Sixth Edition, John Wiley & Sons Inc., 2003.
  2. Andrew S. Tanenbaum, Herbert Bos, “Modern Operating Systems”, Fourth Edition, Pearson Education, 2014.
  3. Gary Nutt, “Operating Systems”, Third Edition, Pearson Education, 2009.