25 Page Replacement Algorithms – III

Mary Anitha Rajam

 

28.1 Introduction

 

In this module, we learn few 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 modules we learnt the working of the First-In-First-Out (FIFO) page replacement algorithm, optimal page replacement algorithm and least recently used page replacement algorithm. In this module, we learn the working of few more page replacement algorithms.

 

28.2 LRU approximation algorithms

 

In LRU page replacement, the page that is least recently used is chosen for replacement. There are many algorithms that approximate the LRU algorithm. To implement the LRU algorithm, many systems provide the support using a reference bit. There is a reference bit for each entry in the page table. Initially all the reference bits are set to zero. The hardware sets the reference bit for a page whenever that page is referenced.

 

If a page is not referenced, then the reference bit remains as zero. When a page is to be chosen for replacement, the page for which, the reference bit is zero, is chosen. But, when the reference bit is set for many pages, the order of reference is not known. That is, if the reference bit is set for four pages, we do not know which of these four pages was least recently used. We only know whether the page was used or not using this single reference bit.

 

28.2.1 LRU Approximation – Additional-Reference-Bits Algorithm 

 

Since a single reference bit is not sufficient to know the least recently used entry, additional bits are added to each page table entry. All the bits are used together to find the least recently used page. Whenever a page is referenced, the already existing bits are shifted to the right. The page with the lowest number is the least recently used page and is chosen for replacement. If two page table entries have the same number, there is a tie and FIFO can be used. The number of additional bits used in the history can be varied.

 

Consider the example shown in Figure 28.1. Assume that there are 5 pages. Initially, the reference bit is zero for all the pages. There are 8 additional bits for each page. Therefore, for each page, it is possible to store the history of eight memory references. Initially, the reference bits and the bits in the history are set to zero.

 

The reference bits are saved regularly in the 8-bit byte. The bits already present in the byte are shifted to the right. Periodically, a timer interrupts and the operating system copies the reference bits to the higher order bit of the 8-bit byte. As this is done periodically, the 8-bit byte provides a history of the memory references.

Fig. 28.1 Example – Additional reference bits

 

Figure 28.2 shows that the reference bits of page 1 and page 3 are set.

 

Fig. 28.2 Example – Additional reference bits

 

Figure 28.3 shows that the reference bits have been moved to the higher order bit of the 8-bit byte. The reference bits of page 1 and page 3 are cleared.

 

Fig. 28.3 Example – Additional reference bits

 

In Figure 28.4, it is seen that there are memory references to page 1 and page 2.

Fig. 28.4 Example – Additional reference bits

 

Page 28.5 shows that the bits in the 8-bit byte are shifted to the right and the reference bits are copied to the leftmost bit of the byte. Thus, in due course of time, the 8-bit byte will have a history of the memory references made.

Fig. 28.5 Example – Additional reference bits

 

To find the least recently used page, the page that has the smallest value in the 8-bit byte is chosen. If two pages have the same value, the tie is broken using FIFO. In Figure 28.5, the pages that can be chosen for replacement are page 0 and page 4. The page that will be least preferred for replacement is page 1, because page 1 has the highest value in the 8-bit byte.

 

28.2.2  LRU Approximation – Second Chance Algorithm (Clock algorithm) 

 

In this algorithm, the number of bits of history is reduced to zero and the reference bit alone is used. While selecting a page for replacement, reference bit of the page is checked. If the reference bit = 0, it means that the page was not referenced. This page can be chosen for replacement. If the reference bit = 1, then the reference bit of that page is set back to 0 and the arrival time of the page is reset to the current time. If the reference bits of all the pages are 1, then in the first round, all the reference bits are reset to 0. The reference bits of the pages are checked again the second time. If the reference bit is zero now, the page is chosen for replacement. But if the reference bit has changed to 1, indicating a memory reference, the reference bit is again changed back to zero. Thus, if a page is used often to keep its reference bit set, it will never be replaced. The second chance algorithm is also called the clock algorithm.

 

Figure 28.6 shows an example of the second-chance algorithm. In this example, the second-chance algorithm is implemented as a circular queue. A pointer is maintained which indicates the position of the page that has to be replaced next. When a page is needed, the pointer is moved till a page with reference bit = 0 is found. While moving the pointer, if there are pages with reference bit =1, the reference bit is reset to 0. When a victim page is found (a page with reference bit = 0), the page is replaced and the new page is replaced in that position. In the worst case, if the reference bit = 1 for all the pages, the reference bit is reset for all the pages in the first round. In the second round the page for replacement is chosen, If all the reference bits are set, then the algorithm behaves like a FIFO algorithm.

Fig. 28.6 Second-Chance (Clock) Algorithm (Source:[1])

 

28.3 Enhanced Second Chance Algorithm

 

In this algorithm, an additional bit called the modify bit is used along with the reference bit to decide the victim page. The modify bit is set for a page if the page is modified after bringing the page into the main memory. When a page that is not modified is chosen as the victim page, that page need not be written to the disk before the new page is brought into the victim page’s place.

 

Let R be the reference bit and M be the modify bit.

 

If for a page (R = 0, M = 0), the page is neither recently used nor modified and hence is the best page to replace.

 

If for a page (R = 0, M = 1), the page is not recently used but modified and hence the page needs to be written before replacement

 

If for a page (R = 1, M = 0), the page is recently used but clean (not recently modified) and probably will be used again soon

 

If for a page (R = 1, M = 1), the page is recently used and modified. Hence, the page may be used again and has to be written to disk if chosen as the victim page for replacement. This page is the least preferred page for replacement.

 

28.4 Counting Algorithms 

In this type of algorithms, the number of times a page is referenced is maintained. A counter iis maintained for each page and is incremented every time the page is referenced. There are two algorithms that use this count of the number of times a page is referenced – Least Frequently Used (LFU) algorithm and Most Frequently Used (MFU) algorithm.

 

28.4.1 Least Frequently Used Algorithm (LFU)

 

This algorithm replaces the page with the smallest count. That is, the page that was used the least number of times is chosen for replacement. The reason for this selection is that a page that is actively used has a large count. Suppose a page was used heavily initially and then never used. Still, this page is not chosen for replacement since the count is high. The algorithm fails in this situation.

 

28.4.2 MFU Algorithm

 

This algorithm replaces the page with the highest count. That is, the page that was used the most number of times is chosen for replacement. This algorithm is based on the argument that the page with the smallest count was probably just brought in and has yet to be used.

 

28.5 Page Buffering Algorithms

 

The page buffering algorithms are used in addition to the page replacement algorithms.

 

Algorithm 1: Systems keep a pool of free frames. That is, a minimum number of frames is always kept as free frames. When a page fault occurs, a victim frame is chosen and the desired page is read into a free frame. The victim frame is written out later and the victim frame is added to the pool of free frames. This removes the time needed to move out a victim page before moving in a new page.

 

Algorithm 2: The system maintains a list of modified pages. The modify bit can be used to identify the modified pages. Whenever the paging device is idle (disk I/O is not happening), a modified page is selected and written to the disk. The modify bit is then reset. This increases the probability that a page is clean (not modified) when chosen for replacement. Writing the page to the disk when the page is chosen for replacement is avoided.

 

Algorithm 3: Keep a pool of free frames and remember which page was in each frame. If the same page is needed again, it is taken from the pool of free frames and used. If the required page is not in the pool of free frames, another free frame is selected. The new page is read into free frame.

 

For example, suppose page 4 of process P1 is freed and the corresponding frame where this page was present in main memory is added to the pool of free frames. During this time, even though the frame is added to the list of free frames, the system also remembers that the contents of page 4 of P1, was kept in this frame earlier. If there is a reference to page 4 of P1 the next time, the page can be taken from the pool of free frames.

 

28.6  Summary

 

In this module we learnt different LRU approximation algorithms (Additional reference bits algorithm, Second-chance    algorithm    and    Enhanced    second    chance    algorithm), Count-based algorithms (Least frequently algorithm) and Most frequently algorithm (MFU) and page-buffering algorithms.

 

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.