理論上最適なページ置換アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/03/08 15:27 UTC 版)
「ページ置換アルゴリズム」の記事における「理論上最適なページ置換アルゴリズム」の解説
理論上最適なページ置換アルゴリズム（OPT、千里眼置換アルゴリズム、Béládyの最適ページ置換アルゴリズムとも呼ばれる）とは、以下のようなものである。ページをスワップインする必要が生じたとき、オペレーティングシステムが現在メモリ上にあるページを全て調べて、次にページが使われるまでの時間を測る。そして、OSは最も長い期間使われないページをスワップアウトする。たとえば、今後6秒間使われないページをスワップアウトして、今後0.4秒間使われる予定のページに割り当てる。 しかし、このアルゴリズムを実際に（少なくとも汎用の）オペレーティングシステムに実装することは現実的ではない。ただし、実行されるソフトウェアが全て判っていて、それらのメモリ使用パターンも分析済みであるか、実行時に分析することが可能な場合は不可能ではない。とは言うものの、OPT に近い性能を示すアルゴリズムは存在する。あるソフトウェアを最初に動作させたときに、オペレーティングシステムが使われたページを全て記録する。そしてこのデータを使って二度目以降にそのソフトウェアを動作させるときに、このデータを使ってページ置換を行うのである。この手法は OPT に近い性能を保証するが、それは二度目の動作のときであり、初めて動作させるソフトウェアでは無効である。また、動作するたびにメモリ参照パターンが大きく変化するプログラムでは効果がない。 ページング問題の解析はオンラインアルゴリズムの分野の話題である。ページング問題向けの乱択オンラインアルゴリズムの効率はならし解析（英語版）を使って測定される。
※この「理論上最適なページ置換アルゴリズム」の解説は、「ページ置換アルゴリズム」の解説の一部です。
「理論上最適なページ置換アルゴリズム」を含む「ページ置換アルゴリズム」の記事については、「ページ置換アルゴリズム」の概要を参照ください。
- 理論上最適なページ置換アルゴリズムのページへのリンク
