|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
ページ置換アルゴリズム（ページちかんアルゴリズム）とは、仮想記憶管理としてページング方式を使用するコンピュータのオペレーティングシステムにおいて、空き物理ページが少ない状態で新たなページを割り当てなければならないときにどのページを「ページアウト（スワップアウト）」するかを決定する方法を意味する。これはページフォールトが発生したときに使用可能なフリーなページが存在しないときに発生する。厳密には発生条件はシステムの種類や設定によって異なるが、フリーなページが全く無い場合か、あらかじめ設定したしきい値よりもフリーなページ数が少ないときに発生する。 以前にページアウトすべきページとして選択され置換されたページに再度アクセスが発生したら、そのページをページインする必要がある。そして、これにはI/Oの完了を待たなければならない。この、ページインを待つ時間の累計が小さいほどページ置換アルゴリズムが優秀であると言える。ページ置換アルゴリズムはページへのアクセスに関するハードウェアからの限られた情報を見て、アルゴリズム自身にかかる時間とページインにかかる時間のバランスをとりつつ、ページミスのなるべく起きない置換をしなければならない。 ページ置換アルゴリズムはオンラインアルゴリズムの一種である。 == 歴史 == ページ置換アルゴリズムは1960年代から1970年代にかけて研究の重要テーマであり、議論が戦わされた。結果として洗練されたLRU推測手法とワーキングセットアルゴリズムが開発されたのである。以来、伝統的なアルゴリズムが前提としていた事柄の一部が否定され、ふたたび研究が行われるようになった。とりわけ、以下のようなハードウェアの動作の変化とユーザーレベルのソフトウェアの動作の変化がアルゴリズムを変えさせてきた。 * 一次記憶装置の容量はどんどん大きくなっている。主記憶が数ギガバイトということも珍しくない状態では、全メモリページを定期的にチェックするアルゴリズムはどんどん現実味を失いつつある。 * メモリ階層が高くなってきた。CPUのキャッシュミスは非常に性能にインパクトがあるため、上記の問題はさらに悪化する。 * ユーザーのソフトウェアでの参照の局所性は薄れてきた。オブジェクト指向プログラミングが多く使われるようになったことが原因のひとつである。この場合、小さな関数を数多く使用し、ツリー構造やハッシュテーブルなどの洗練されたデータ構造を使用する。これらは混沌としたメモリ参照パターンを示し、ガベージコレクションがひとたび起きればメモリ参照パターンは劇的に変化してしまう。 また、置換アルゴリズムへの要求もオペレーティングシステムのカーネルアーキテクチャの変化に伴って変わってきた。多くの最近のカーネルは仮想記憶とファイルシステムのキャッシュを統合的に管理している。したがって、置換アルゴリズムはページを選択するにあたって、ユーザプログラムの仮想アドレス空間とキャッシュされたファイルの両方を検討しなければならない。後者のページは特定の属性を持つ。例えば、ファイルキャッシュはロックされる可能性もあるし、ジャーナリングによってディスクへの書き込みを要求されている場合もある。さらに、ページ置換アルゴリズムの目標がメモリ待ちとなる時間を最小化することだとすれば、他のカーネル内サブシステムのメモリ確保要求についても関わっていかなければならない。結果として、最近のカーネル（Linux、FreeBSD、Solaris）では、ページ置換は仮想記憶サブシステムのレベルよりももっと基本的なカーネル内の汎用メモリアロケーション機構の一部となりつつある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ページ置換アルゴリズム」の詳細全文を読む スポンサード リンク
|