Least Recently Used (LRU) page
replacement algorithm
The idea behind LRU page replacement is to use
recent past as an approximation of the near future. Replace the page that has
not been used for the longest period of time.
LRU is considered a good replacement policy, and is
often used. The problem is how exactly to implement it. There are two simple
approaches commonly used:
- Counters. Every
memory access increments a counter, and the current value of this counter
is stored in the page table entry for that page. Then finding the LRU page
involves simple searching the table for the page with the smallest counter
value. Note that overflowing of the counter must be considered.
- Stack. Another
approach is to use a stack, and whenever a page is accessed, pull that
page from the middle of the stack and place it on the top. The LRU page
will always be at the bottom of the stack. Because this requires removing
objects from the middle of the stack, a doubly linked list is the
recommended data structure.
Note that both implementations of LRU require
hardware support, either for incrementing the counter or for managing the
stack, as these operations must be performed for every memory
access.
Neither LRU or OPT exhibit Belady's anomaly. Both
belong to a class of page-replacement algorithms called stack
algorithms, which can never exhibit Belady's anomaly.
A stack algorithm is one in which the pages kept in
memory for a frame set of size N will always be a subset of the pages kept for
a frame size of N + 1.
No comments:
Post a Comment