Least Recently Used algorithm - Revision history

Jnc: Used in more places than just replacement

2024-01-15T12:01:20Z

Used in more places than just replacement

← Older revision		Revision as of 12:01, 15 January 2024
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 most recently used the longest time ago, since the ones used since then are more likely to be used again soon.		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.		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.
Line 5:		Line 7:
	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.		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]] systems); and [[cache]]s of all kinds.		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]]

Jnc: Jnc moved page Least Recently Used replacement algorithm to Least Recently Used algorithm: Used for more things than replacement

2024-01-15T11:45:39Z

Jnc moved page Least Recently Used replacement algorithm to Least Recently Used algorithm: Used for more things than replacement

← Older revision		Revision as of 11:45, 15 January 2024
(No difference)

Jnc: Clarify

2023-11-17T18:45:44Z

Clarify

← Older revision		Revision as of 18:45, 17 November 2023
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 ~~last~~ used the longest time ago, since the ~~others~~ are more likely to be used again soon.		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]]

Jnc: Jnc moved page LRU to Least Recently Used replacement algorithm: Full name

2023-11-14T15:58:16Z

Jnc moved page LRU to Least Recently Used replacement algorithm: Full name

← Older revision	Revision as of 15:58, 14 November 2023
(No difference)

Jnc: A bit stubby, but not too bad

2023-11-14T15:57:10Z

A bit stubby, but not too bad

New page

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 last used the longest time ago, since the others 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.

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.

LRU algorithms are used in many circumstances: disk buffers (as above); [[page frame]]s (in [[virtual memory]]); and [[cache]]s of all kinds.

{{semi-stub}}

[[Category: Theory]]