Go Back

A Quick Abstract:

1. Introduction to Page Replacement:

Page replacement algorithms play a vital role in managing memory in virtual memory systems. Both LRU and MRU are strategies that consider the recent usage history of pages to determine which one to replace when a page fault occurs.

2. LRU (Least Recently Used) Page Replacement Algorithm:

Working:

Maintain a record of the order in which pages are accessed.

When a page fault occurs:

Replace the page that has not been used for the longest period.

Advantages:

Effective in capturing temporal locality.

Disadvantages:

Requires a mechanism to track page access history, which can be resource-intensive.

3. MRU (Most Recently Used) Page Replacement Algorithm:

Working:

Maintain a record of the order in which pages are accessed.

When a page fault occurs:

Replace the page that has been used most recently.

Advantages:

Simplicity in implementation.

Suitable for environments where recently used pages are more likely to be used again.

Disadvantages:

May not perform optimally in scenarios with temporal locality.

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.

LRU:

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 recently used, so it is replaced)

... and so on.

MRU:

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 recently used, so it is replaced)

... and so on.

5. Conclusion:

LRU and MRU are page replacement algorithms that focus on the recency of page usage. While LRU is effective in capturing temporal locality, it requires additional mechanisms for maintaining access history. MRU, on the other hand, is simpler but may not perform optimally in scenarios with temporal locality.

Notes From The Slides:

Least Recently Used (LRU) Algorithm

• Use past knowledge rather than future
• Replace page that has not been used in the most amount of time
• Associate time of last use with each page

• 12 faults – better than FIFO but worse than OPT
• Generally good algorithm and frequently used
• But how to implement?

Least Recently Used (LRU) Algorithm

• Use past knowledge rather than future
• Replace page that has not been used in the most amount of time
• Associate time of last use with each page

• 12 faults – better than FIFO but worse than OPT
• Generally good algorithm and frequently used
• But how to implement?

LRU Algorithm (Cont.)

• Counter implementation

• Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter
• When a page needs to be changed, look at the counters to find smallest value

• Search through table needed

• Stack implementation

• Keep a stack of page numbers in a double link form:
• Page referenced:

• move it to the top
• requires 6 pointers to be changed

• But each update more expensive
• No search for replacement

LRU Algorithm (Cont.)

• LRU and OPT are cases of stack algorithms that don’t have Belady’s Anomaly
• Use Of A Stack to Record Most Recent Page References

LRU Approximation Algorithms

• LRU needs special hardware and still slow
• Reference bit

• With each page associate a bit, initially = 0
• When page is referenced bit set to 1
• Replace any with reference bit = 0 (if one exists)

• We do not know the order, however

LRU Approximation Algorithms (cont.)

• Second-chance algorithm

• Generally FIFO, plus hardware-provided reference bit
• Clock replacement
• If page to be replaced has

• Reference bit = 0 -> replace it
• reference bit = 1 then:

• set reference bit 0, leave page in memory
• replace next page, subject to same rules

Second-chance Algorithm

Enhanced Second-Chance Algorithm

• Improve algorithm by using reference bit and modify bit (if available) in concert
• Take ordered pair (reference, modify):

• (0, 0) neither recently used not modified – best page to replace
• (0, 1) not recently used but modified – not quite as good, must write out before replacement
• (1, 0) recently used but clean – probably will be used again soon
• (1, 1) recently used and modified – probably will be used again soon and need to write out before replacement

• When page replacement called for, use the clock scheme  but use the four classes replace page in lowest non-empty class

• Might need to search circular queue several times

Most Recently Used (MRU) Algorithm

• Use past knowledge rather than future
• Replace page that has been used in the least amount of time
• Associate time of last use with each page
• Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
• 3 frames (3 pages can be in memory at a time per process)