エル‐アール‐ユー【LRU】
LRU
別名:LRU方式
LRUとは、キャッシュアルゴリズムなどで用いられる、置換対象のデータを定める方式のうち、参照されていない時間が最も長いデータを置換対象にする方式のことである。
例えば、仮想記憶管理におけるページング方式では、主記憶装置(メインメモリ)上で補助記憶装置へ退避させるデータ単位(ページ)を選ぶ方式としてLFUを用いることがある。主記憶装置で扱うことのできる容量には限度があるため、主記憶装置の記憶容量を超えるデータを扱う場合は、データの一部を補助記憶装置へと置換することで空き容量を確保する。このとき、LRUでは、それぞれのデータが参照された時間に基づき、その時間が最も古い(least recently)データを置換対象とする。
LRUに対して、LFU(Least Frequently Used)と呼ばれる方式では、データが使用された頻度(frequently)に関する情報に基づき、最も頻度が少なかった情報を置換する。
【列線交換ユニット】(れっせんこうかんゆにっと)
Line Replaceable Unit (LRU)
航空機の部品のうち、アビオニクス等の機器類が納められ、自己診断装置で異常が見られた場合に即座に取替え可能な装置のこと。
航空機の稼働率を高める事を目的として作られており、通常ならば列線における機体の整備において異常が見られた場合、修理が完了するまで稼動不能になるが、この装置を搭載した航空機はその部分の列線交換ユニットを引き抜き、新たな列線交換ユニットを装着することにより、直ちに稼動状態になれる。
引き抜かれた列線交換ユニットは後方で修理され、再び列線に送られる。
LRU
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2013/08/04 22:52 UTC 版)
LRU
- Least Recently Used - アルゴリズムの一種
- 列線交換ユニット (Line Replaceable Unit) - 航空機の装置
このページは曖昧さ回避のためのページです。一つの語句が複数の意味・職能を有する場合の水先案内のために、異なる用法を一覧にしてあります。お探しの用語に一番近い記事を選んで下さい。このページへリンクしているページを見つけたら、リンクを適切な項目に張り替えて下さい。 |
LRU (Least Recently Used)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/03/08 15:27 UTC 版)
「ページ置換アルゴリズム」の記事における「LRU (Least Recently Used)」の解説
LRU(最近使われていない)ページ置換アルゴリズムは NRUと名前は似ているが、LRUでは短期間のページ使用履歴を保持している点が異なる。NRUではクロック割り込み間隔の使用/不使用で判断していた。LRU は、最近よく使われているページはその後の短時間でもよく使われるだろうという判断に基づいている。LRU は理論上は OPT に近い性能を発揮するはずだが、実際に実装するとコストがやや高い。このコストを抑える試みをした実装手法がいくつか存在している。 最もコストの高い手法はメモリ上の全ページを含むリンクリストを使う方法である。このリストの最後尾はLRUページであり、先頭は逆に最近使われているページである。この実装のコストはメモリ参照の度にリスト上のアイテムを移動させなければならない点であり、これには非常に時間がかかる。 別の方法はハードウェアのサポートを必要とする。ハードウェアで 64ビットのカウンタを命令実行毎にカウントアップする。ページにアクセスがあったときは、その時点のカウンタの値をページに与える。ページを置換するとき、オペレーティングシステムは単純に最も小さなカウンタ値を持つページを選択する。ただし、現在のハードウェアにはそのような機構はないので、OSが全ページについてカウンタを調べる必要があり、現実的ではない。 LRU アルゴリズムの重要な利点は、完全な統計分析を修正できる余地がある点である。たとえば、OPT アルゴリズムに比較して N回以上ページフォールトが多くなることはない、ということが証明されている。ここで、N は管理対象のページ数に比例した値である。 実装コストがかかるため、LRUに似ているがより実装コストの低いアルゴリズムを考慮することもある。 一方 LRU の欠点は、一般的な参照パターンで性能を低下させてしまう傾向があることである。たとえば、LRU 対象のページが N 個あったとして、あるアプリケーションが N + 1 ページにまたがる配列にアクセスしながらループしているとき、インデックスの進みと共にページフォールトが発生してしまう(つまり、配列が大きすぎるので必ずページ置換は必要だが、LRUを使うと次にアクセスするページが必ずページアウトされてしまう)。大きなループを使うのは一般的なので、このような場合に対応できるようにLRUを改善する試みは多く行われてきた。最も多い手法はループしてアクセスしているパターンを検出して、適した置換アルゴリズム(たとえば、MRU(Most Recently Used)に切り替えるのである。
※この「LRU (Least Recently Used)」の解説は、「ページ置換アルゴリズム」の解説の一部です。
「LRU (Least Recently Used)」を含む「ページ置換アルゴリズム」の記事については、「ページ置換アルゴリズム」の概要を参照ください。
LRU (Least Recently Used)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/11/05 14:09 UTC 版)
「キャッシュメモリ」の記事における「LRU (Least Recently Used)」の解説
最も古くアクセスされたラインをリフィルする方法。時間的局所性に鑑みれば、過去最もアクセスのなかったラインは将来にわたってもアクセスされる可能性は少ないと言える。従ってこの方法はヒット率がかなり高い方法としてよく採用されている。ただし各ラインごとにアクセス順履歴を持ちアクセスがある度に頻繁に履歴を入替えるため、複雑な構成となりアクセス性能に影響が出る場合がある。
※この「LRU (Least Recently Used)」の解説は、「キャッシュメモリ」の解説の一部です。
「LRU (Least Recently Used)」を含む「キャッシュメモリ」の記事については、「キャッシュメモリ」の概要を参照ください。
- LRUのページへのリンク