Page Replacement Algorithms

When a page fault occurs, the operating system has to choose a page to remove from memory to make space for the page that has to be brought in.
If the page to be removed has been modified in memory, it must be rewritten to the disk to bring the disk copy up-to-date.
If, however, the page has not been changed (eg., a page contains program text), the disk copy is already up-to-date, so no rewrite is needed. The page to be read in just overwrites the page being replaced.
Thus, a page replacement algorithm is the logic or the policy regarding how to select a page to be swapped out from the main memory to create space for the page that has caused a page fault.
Several different page replacement algorithms exist. The algorithm that results in the lowest page fault rate is selected.
The various algorithms are evaluated by running then on a particular string of memory references and calculating the number of page faults. Such an ordered list of page numbers accessed by a program is called its reference string.
The various page replacement algorithm used are discussed in subsequent sections.

1. Optimal page replacement algorithm

Optimum page replacement algorithm is considered the best page replacement algorithm in a virtual memory theoretically but is difficult to implement.
This algorithm is also called OPT or MIN.
In this algorithm, we replace the page that will not be used for the longest period of time i.e. the page in the main memory, which will not be referred to for the longest time is swapped out from the main memory to create space for the requested page.
Therefore, this algorithm is based on the strategy of looking forward in time.
This algorithm is impossible to implement because it would require the operating system to have perfect knowledge of future events.
For example, we consider a reference string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 and a system with three frames to implement optimum page replacement algorithm.
Figure shows that the optimal page replacement algorithm results in six page faults.
The first two references causes faults that fill the two empty frame. The fourth reference also results in page fault to fill empty frames.
The reference to page 5 replaces page 1, because page 1 will not be used until end.

The reference to page 4 replaces page 2 as it will be the last of the three pages in memory to be referenced again.
Thus, optimal page replacement results only in six page faults and the use of this algorithm guarantees the lowest possible page fault rate for a fixed number of frames.

Advantages of optimal page replacement

It has the lowest rate of occurrence of page faults.
Hypothetically, it improves the system performance by reducing overhead for numbering of page faults and swapping pages in and out, when a page fault occurs.
It does not suffer from the Be lady’s anomaly (discussed in next section).

Disadvantage of optimal page replacement

It is difficult to implement, because it requires future knowledge of the reference string.

2. First-In, first out (FIFO) page replacement algorithm

It is simplest page replacement algorithm and associates with each page the time when that page was brought into memory.
In this algorithm, whenever a page is to be replaced, the oldest page is chosen i.e., that page is swapped out, which has been in the main memory for the longest period of time.
It is implemented by creating a FIFO queue that holds all the pages in memory. The page at the head of the queue is replaced and when a page is brought into memory, it is inserted at the tail of the queue.
The main difference between FIFO and OPT algorithm is that the FIFO algorithm uses the time when a page was brought into memory; the OPT algorithm uses the time when a page is to be used.
The first, second and fourth reference, results in page fault to fill in the empty frames.

Reference to page 5 replace page 2, because page 2 was brought in first. Thereafter reference to page 2 replaces page 3 and reference to page 4 replaces page 1.
Next reference is to page 5; which is already in memory, so no fault occurs for this reference.
There are total of nine page faults in this example.

Belady’s anomaly

It would seem reasonable that when more page frames are allocated to a process, the fewer page faults will occur.

However, in year 1970, Belady, Nelson and Shedler discovered that in FIFO page replacement, certain page reference patterns actually cause more page faults when the number of page frames allocated to a process is increased. This phenomenon is called the FIFO anomaly or Belady’s anomaly.
Figure shows this anomaly, using the same reference string and four page frames, the number of page fault does not decrease and remains same.
Consider another reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Figure(a) shows the number of page faults are nine when number of page frames are three.

Figure(b) shows that the number of page faults increases and becomes ten when number of page frames are increased (i.e. four).

Advantage of FIFO page replacement

It is simple and easy to implement.
It can easily be coded.

Disadvantage of FIFO page replacement

FIFO replacement algorithm replaces heavily used pages.
It suffers from Belady’s anomaly.

3. Least Recently Used (LRU) page replacement algorithm

The LRU algorithm uses information about the pages accessed in recent past to predict the near future.
In this algorithm, whenever a page is to be replaced, we select the page that has not been used for the longest period of time.

This algorithm keeps track of the last time each page was used, not when it was brought into the main memory :

Whenever a page fault occurs, LRU algorithm swaps out that page which has not been used for the longest period of time out of the main memory in order to create space for the requested page that has caused the page fault.

Thus, LRU algorithm is based on the strategy of looking backward in time.
Using the same reference string, LRU algorithm produces seven page faults. The first three faults are same as the optimaj replacement. When the reference to page 5 occurs, LRU replacement sees that of the three frames in memory (2, 3,1), page 3 was used least recently. The most recently used page is 1, and just before that page 2 was used. Thus, the LRU algorithm replaces page 3, not knowing that page 3 is about to be used.

Implementation of LRU page replacement

The LRU algorithm can be implemented in various ways. Such an implementation may require hardware or software assistance. The various implementations are :

a. Using Counters

In this method a counter or clock is used.
A counter field is associated with each page table entry.
Whenever a reference to a particular page is made, its counter is incremented and this value is copied to the counter field of page table for that entry.
In this way, we always have the time of last reference to each page.
The LRU algorithm searches the page table for entry with the lowest counter value and selects that page for replacement.

b. Using matrix

On a system with n page frames, an n x n matrix can be used to implement LRU algorithm.
The matrix is initialized to contain all 0’s.
When page frame k is accessed, all bits in row k are set to 1.
Then all bits in column k are set to 0.
At any instant, the row whose binary value is lowest is least recently used, the row whose value is next lowest is next least recently used and so on.
Figure shows the matrix for a system with four page frames given references to pages in the order 0, 1, 2 and 3. After page 0 is referenced, we have situation as shown in figure(a). After page 1 is referenced, we have situation of figure (b) and so on. At this stage page 0 (fig. (d)) is least recently used as it is having lowest binary value. So this page will be replaced.

c. Using Linked List

LRU can also be implemented using a linked list that contains one entry for each occupied page frame.
Whenever a page frame is referenced, the entry for that page is placed at the head of the list.
Older entries move towards the tail of the list.
Whenever a page is to be replaced, the entry at the tail of the list is selected for replacement.
As a result, the corresponding frame is freed and the incoming or requested page is placed in that frame.
This new frame is then placed at the head of the list. Because this page is now the one that has been most recently used.
Although this scheme implement LRU effectively, it incurs substantial overhead.

Advantages of LRU page replacement

It does not suffer from Belady’s anomaly.
It is feasible to implement and is less complicated as compared to optimal page replacement algorithm.

Disadvantages of LRU page replacement

It requires an additional data structure such as linked list to implement it. The difficulty is that the list must be updated on every memory reference. Moreover, finding a page in the list, deleting it, and moving it to the front is a very time consuming operation.
It requires expensive hardware support to implement such a structure.

4. Least Frequently Used (LFU) page replacement algorithm

Least frequently used (LFU) page replacement algorithm is the approximation of LRU algorithm.
Here, we are concerned with how intensive the use of each page has been.

A counter is used that counts the number of references that have been made to each page.
Whenever a page is to be replaced, that page is chosen that is least frequently used or least intensively referenced i.e. the page with smallest count is replaced.
The reason for this selection is that an actively used page should have a large reference count.
However, this algorithm is expensive to implement and does not approximate OPT page replacement.

5. Most Frequently Used (MFU) page replacement algorithm

MFU is just the reverse of LFU.
This algorithm also is an approximation of LRU and uses a counter to count the number of references made to each page.
Whenever a page is to be replaced that page is chosen which has been used most frequently i.e. the page with largest count.
It is based on the argument that the page with smallest count is probably just brought in and has yet to be used.
Like LFU, this algorithm also is expensive to implement and does not approximate OPT page replacement.

6. Not Frequently used (NFU) page replacement algorithm

NRU is an approximation of LRU.
In addition to dirty bit, each page table entry contains a reference bit.

The dirty bit is also called modified bit,

Modified bit = 0 if the page has not been modified

= 1 if the page has been modified

The reference bit is set, whenever a page is accessed

reference bit = 0 if the page has not been referenced

= 1 if the page has been referenced

When a page is loaded, the operating system sets the reference bit to 0. When a page is accessed, the hardware sets the bit to 1.
In addition, at periodic intervals the operating system will set all reference bits in the page table back to 0. A value of 0 in the reference bit means it has not been referenced “recently”; a 1 means it has.

Depending upon the value of reference bit and dirty bit all the entries of page table can be divided into 4 sets :

Group 1: unreferenced unmodified

Group 2: unreferenced modified

Group 3: referenced unmodified

Group 4: referenced modified

The pages in the lowest number group should be replaced first and those in the highest numbered groups should be replaced last.
Pages within a group are selected randomly for replacement.
There is another approximation of LRU called aging. It make use of a reference byte in the page table entries.
When a page is accessed, the hardware sets the most significant bit in the reference byte. For example, suppose the reference bits for pages 0 to 5 have the values 1, 0, 1, 0, 1 and 1 respectively after the first clock tick i.e. between tick 0 and tick 1, pages 0, 2, 4 and 5 were referenced (reference bit = 1) and the most significant bit in reference byte is set (fig.(a)). The four remaining columns show the six counters after the next four clock ticks.
At each clock tick, operating system shifts all the bits right by one in the reference byte (fig. (b)).
As a result, a page with lowest binary value in its reference byte is selected for removal.
However, the operating system can pick any page from among all the pages with the lowest value.

7. Second chance page replacement algorithm

The second chance replacement algorithm is a combination of the FIFO and NRU algorithms.
In this algorithm, the page present for the longest time in the memory is given second chance to remain loaded in the main memory. In this way, this algorithm avoids the problem of throwing out a heavily used page.
When a page is selected, its reference bit is checked. If it is 0, the page is both old and unused, so it is replaced immediately. If reference bit is 1, we give that page a second chance and move on to select the next FIFO page.
In this case i.e. when a page gets a second chance, its reference bit is cleared, its arrival time is set to the current time and is put onto the end of the list of pages.
This implies that this algorithm searches for an old page that has not been referenced. If a page is oldest but has been referenced, it will not be considered for replacement.
This figure shows the pages A through H kept on a linked list and sorted by the time they arrived in the memory.
Suppose that a page fault occurs at time 20. The oldest page is A, which arrived at time 0, when the process started. If A has the reference bit cleared, it is replaced from memory either by being written to the disk (if its modify bit is set), or just removed (if modified bit is not set). On the other hand if reference bit is set, A is put onto the end of the list and its load time is reset to the current time (20).
Thus second chance algorithm looks for an old page that has not been referenced in the previous clock interval.

If all the pages have been referenced (i.e. have their reference bit set) second chance degenerates into pure FIFO. Specifically imagine that all the pages in fig.(a) have their reference bit set. One by one, the operating system moves the pages to the end of the list, clearing the reference bit each time its appends a page to the end of the list. Ultimately, it comes back to page A, which now has its reference bit cleared. At this point, A is replaced.

8. Clock page replacement Algorithm

It is the variation of second chance page replacement algorithm.
It uses a circular queue to contain all the pages in form of a clock.
It make use of a pointer to indicate the position of the page to be replaced.
If the reference bit of this page is 0, the page is evicted the new page is inserted into the clock in its place and the pointer is advanced one position ahead. When a page fault occurs, the page being point is inspected.
If the reference bit 1, it is cleared and the pointer is advanced to next page.
This process is repeated until a page is found with reference bit = 0.

In worst case, when all the reference bits are set, the pointer cycles through the whole circular queue, giving each page a second chance. It clears all the reference bits before selecting the next page for replacement.