Difference between revisions of "Least Recently Used algorithm"
m (Jnc moved page LRU to Least Recently Used replacement algorithm: Full name) |
(Clarify) |
||
| Line 1: | Line 1: | ||
| − | The '''Least Recently Used replacement algorithm''' (usually abbreviated as '''LRU''') is an algorithm for choosing which entry to 'recycle' first in an [[array]] of resources, when a need arises for a free resource, and they are already all in use. It says, as the name implies, that one should recycle the entry which was | + | The '''Least Recently Used replacement algorithm''' (usually abbreviated as '''LRU''') is an algorithm for choosing which entry to 'recycle' first in an [[array]] of resources, when a need arises for a free resource, and they are already all in use. It says, as the name implies, that one should recycle the entry which was most recently used the longest time ago, since the ones used since then are more likely to be used again soon. |
| − | The reasoning is that freeing a resource likely involves some effort (e.g. writing a modified [[disk]] block from a [[buffer]] back onto [[secondary storage]]), so that effort should be expended are rarely as possible. | + | The reasoning behind minimizing the number of times entries are freed is that freeing a resource likely involves some effort (e.g. writing a modified [[disk]] block from a [[buffer]] back onto [[secondary storage]]), so that effort should be expended are rarely as possible. |
| − | Providing the information needed to determine the least recently used entry may require some effort, in both [[hardware]] and [[software]] systems. There are thus algorithms which approximate 'true' LRU, but use less overhead. | + | Providing the information needed to determine which entry is the least recently used entry may require some effort, in both [[hardware]] and [[software]] systems. There are thus algorithms which approximate 'true' LRU, but use less overhead. |
| − | LRU algorithms are used in many circumstances: disk buffers (as above); [[page frame]]s (in [[virtual memory]]); and [[cache]]s of all kinds. | + | LRU algorithms are used in many circumstances: disk buffers (as above); [[page frame]]s (in [[virtual memory]] systems); and [[cache]]s of all kinds. |
{{semi-stub}} | {{semi-stub}} | ||
[[Category: Theory]] | [[Category: Theory]] | ||
Revision as of 20:45, 17 November 2023
The Least Recently Used replacement algorithm (usually abbreviated as LRU) is an algorithm for choosing which entry to 'recycle' first in an array of resources, when a need arises for a free resource, and they are already all in use. It says, as the name implies, that one should recycle the entry which was most recently used the longest time ago, since the ones used since then are more likely to be used again soon.
The reasoning behind minimizing the number of times entries are freed is that freeing a resource likely involves some effort (e.g. writing a modified disk block from a buffer back onto secondary storage), so that effort should be expended are rarely as possible.
Providing the information needed to determine which entry is the least recently used entry may require some effort, in both hardware and software systems. There are thus algorithms which approximate 'true' LRU, but use less overhead.
LRU algorithms are used in many circumstances: disk buffers (as above); page frames (in virtual memory systems); and caches of all kinds.
