Go Back

A Quick Abstract:

1. Introduction to Page Replacement:

Page replacement algorithms are critical in managing memory efficiently in virtual memory systems. Both LFU and MFU focus on the frequency of page usage to determine which page to replace when a page fault occurs.

2. LFU (Least Frequently Used) Page Replacement Algorithm:

Working:

Maintain a count of how often each page is referenced.

When a page fault occurs:

Replace the page with the lowest usage count.

Advantages:

Effective in capturing both temporal and spatial locality.

Disadvantages:

Requires additional mechanisms to maintain usage counts, which can be resource-intensive.

3. MFU (Most Frequently Used) Page Replacement Algorithm:

Working:

Maintain a count of how often each page is referenced.

When a page fault occurs:

Replace the page with the highest usage count.

Advantages:

Simplicity in implementation.

Suitable for environments where frequently used pages are likely to continue being used.

Disadvantages:

May struggle in scenarios with changing access patterns.

4. Example Scenario:

Consider a memory system with three frames (A, B, C) and a sequence of page requests: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3.

LFU:

Initial state: | - | - | - |

Page 1 is requested: | 1 | - | - |

Page 2 is requested: | 1 | 2 | - |

Page 3 is requested: | 1 | 2 | 3 |

Page 4 is requested: | 4 | 2 | 3 | (Page 1 is the least frequently used, so it is replaced)

... and so on.

MFU:

Initial state: | - | - | - |

Page 1 is requested: | 1 | - | - |

Page 2 is requested: | 1 | 2 | - |

Page 3 is requested: | 1 | 2 | 3 |

Page 4 is requested: | 1 | 2 | 4 | (Page 3 is the most frequently used, so it is replaced)

... and so on.

5. Conclusion:

LFU and MFU are page replacement algorithms that focus on the frequency of page usage. While LFU is effective in capturing both temporal and spatial locality, it requires additional mechanisms for maintaining usage counts. MFU, on the other hand, is simpler but may struggle in scenarios with changing access patterns.

Notes From The Slides:

Counting Algorithms (LFU/MFU)

• Keep a counter of the number of references that have been made to each page

• Not common

• Least Frequently Used (LFU) Algorithm:

• Replaces page with smallest count
• Based on the argument that the page with the smallest count was probably just brought in and has yet to be used

• Most Frequently Used (MFU) Algorithm:

• Replaces page with highest count
• Based on the argument that the page with the highest count was probably just brought in and has yet to be used

Least Frequently Used (LFU) Algorithm

f(7)=1 ; f(0)=1 ; f(1)=1 ;  all the same => use FIFO

Number of Frames =3, https://www.youtube.com/watch?v=uL0xP57negc

Least Frequently Used (LFU) Algorithm

f(7)=0 ; f(0)=1 ; f(1)=1 ;  f(2)=1;

f(7)=0 ; f(0)=2 ; f(1)=1 ;  f(2)=1;

Least Frequently Used (LFU) Algorithm

f(7)=1 ; f(0)=4 ; f(1)=0 ; f(2)=1 ; f(3)=2 ; f(4)=0 ;  

TOTAL number of page faults = 10

Least Frequently Used (LFU) Algorithm

Another Example: TOTAL number of page faults = 7

Most Frequently Used (MFU) Algorithm

Victim (the page we’ll replace) is the page that has been used MOST

TOTAL number of page faults = 9

Page-Buffering Algorithms

• Keep a pool of free frames, always

• Then frame available when needed, not found at fault time
• Read page into free frame and select victim to evict and add to free pool
• When convenient, evict victim

• Possibly, keep list of modified pages

• When backing store otherwise idle, write pages there and set to non-dirty

• Possibly, keep free frame contents intact and note what is in them

• If referenced again before reused, no need to load contents again from disk
• Generally useful to reduce penalty if wrong victim frame selected  

Applications and Page Replacement

• All of these algorithms have OS guessing about future page access
• Some applications have better knowledge – i.e. databases
• Memory intensive applications can cause double buffering

• OS keeps copy of page in memory as I/O buffer
• Application keeps page in memory for its own work

• Operating system can given direct access to the disk, getting out of the way of the applications

• Raw disk mode

• Bypasses buffering, locking, etc.