|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。
==例== * 最も効率的なキャッシュアルゴリズムは、今後長期に渡って必要とされないデータを常に捨てていくものである。この理想的アルゴリズムは、Laszlo Belady の最適アルゴリズム、あるいは千里眼置換アルゴリズムなどと呼ばれる。実際には、あるデータを将来に渡ってどれだけ必要としないかを予測することは不可能であり、このアルゴリズムは一般には実装できない。実用上の最適解は実験して初めて得られ、実際のキャッシュアルゴリズムとその最適解との効率を比較することは可能である。 * Least Recently Used (LRU): 最近最も使われていないデータを最初に捨てる。このアルゴリズムでは、どのデータがどの時点で使われたかという情報を保持する必要があり、本当に最近最も使われていないデータを常に捨てるようにしようとすると、かなり手間がかかる。一般的実装では、キャッシュライン毎に世代ビット群（age bits）を持たせ、どのラインが最近最も使われていないかを世代ビット群で判断する。その場合、あるキャッシュラインを使うときには、常に全キャッシュラインの世代ビット群を更新する必要がある。 * Most Recently Used (MRU): 最近最も使われたデータを最初に捨てる。アクセスに局所性を想定できず、LRUの実装が複雑すぎる場合に使われる。MRUの使用例としてはデータベースのメモリキャッシュがある。 * Pseudo-LRU (PLRU): 例えば、キャッシュメモリの連想度が大きい場合（4ウェイ以上）、LRUの実装コストは無視できなくなる。確率的にほぼ常に最近最もつかわれていないデータを捨てれば十分という場合、PLRUアルゴリズムを使う。この場合、キャッシュライン毎に1ビットの情報を保持するだけでよい。 * Least Frequently Used (LFU): 各データが使われた頻度を保持する。そして、頻繁には使われていないデータを最初に捨てる。 * Adaptive Replacement Cache (ARC): LRU と LFU の間でバランスをとり、最適な結果を得る方式。最近キャッシュから消された情報の履歴を保持するように拡張し、その情報を使って、「かつてキャッシュされていたけれど今はキャッシュから消されている」という情報を元に、LRUとLFUの配分を動的に自動的に調整する。以下の4つのキューを使う。 *# LRU (アクセス回数が1回。常にLFUよりも大きな容量を割り当てる。) *# LFU (アクセス回数が2回以上のデータ) *# かつてLRUに入っていた (これ自体もLRU) *# かつてLFUに入っていた (これ自体もLRU) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「キャッシュアルゴリズム」の詳細全文を読む スポンサード リンク
|