Difference between revisions of "Least Recently Used algorithm"
(A bit stubby, but not too bad) |
(Used in more places than just replacement) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | The '''Least Recently Used | + | The '''Least Recently Used algorithm''' (usually abbreviated as '''LRU''') is an algorithm for choosing which entity to deal with first; be it the entry to 'recycle' in an [[array]] of resources, when a need arises for a free resource (and one has to be replaced); or for some other situation. |
| − | + | In replacement situations it says, as the name implies, that when the entries are all already in use, 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. | |
| − | LRU algorithms are used in many circumstances: disk buffers (as above); [[page frame]]s (in [[virtual memory]]); and [[cache]]s of all kinds. | + | 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 replacement algorithms are used in many circumstances: disk buffers (as above); [[page frame]]s (in [[virtual memory]] systems); and [[cache]]s of all kinds. | ||
| + | |||
| + | In other situations (such as [[arbitration]] for use of a [[bus]]), a similar [[algorithm]] is used - pick whichever was most recently picked the longest time ago. | ||
{{semi-stub}} | {{semi-stub}} | ||
[[Category: Theory]] | [[Category: Theory]] | ||
Latest revision as of 13:01, 15 January 2024
The Least Recently Used algorithm (usually abbreviated as LRU) is an algorithm for choosing which entity to deal with first; be it the entry to 'recycle' in an array of resources, when a need arises for a free resource (and one has to be replaced); or for some other situation.
In replacement situations it says, as the name implies, that when the entries are all already in use, 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 replacement algorithms are used in many circumstances: disk buffers (as above); page frames (in virtual memory systems); and caches of all kinds.
In other situations (such as arbitration for use of a bus), a similar algorithm is used - pick whichever was most recently picked the longest time ago.
