検索ページ置換アルゴリズム(ページちかんアルゴリズム)とは、仮想記憶管理としてページング方式を使用するコンピュータのオペレーティングシステムにおいて、空き物理ページが少ない状態で新たなページを割り当てなければならないときにどのページを「ページアウト(スワップアウト)」するかを決定する方法を意味する。これはページフォールトが発生したときに使用可能なフリーなページが存在しないときに発生する。厳密には発生条件はシステムの種類や設定によって異なるが、フリーなページが全く無い場合か、あらかじめ設定したしきい値よりもフリーなページ数が少ないときに発生する。以前にページアウトすべきページとして選択され置換されたページに再度アクセスが発生したら、そのページをページインする必要がある。これにはI/Oの完了を待たなければならない。この、ページインを待つ時間の累計が小さいほどページ置換アルゴリズムが優秀であると言える。ページ置換アルゴリズムはページへのアクセスに関するハードウェアからの限られた情報を見て、アルゴリズム自身にかかる時間とページインにかかる時間のバランスをとりつつ、ページミスのなるべく起きない置換をしなければならない。ページ置換アルゴリズムはオンラインアルゴリズムの一種である。歴史[編集]ページ置換アルゴリズムは1960年代から1970年代にかけて研究の重要テーマであり、議論が戦わされた。結果として洗練されたLRU推測手法とワーキングセットアルゴリズムが開発されたのである。以来、伝統的なアルゴリズムが前提としていた事柄の一部が否定され、ふたたび研究が行われるようになった。以下のようなハードウェアの動作の変化とユーザーレベルのソフトウェアの動作の変化がアルゴリズムを変えさせてきた。一次記憶装置の容量はどんどん大きくなっている。主記憶が数ギガバイトということも珍しくない状態では、全メモリページを定期的にチェックするアルゴリズムはどんどん現実味を失いつつある。メモリ階層が高くなってきた。CPUのキャッシュミスは非常に性能にインパクトがあるため、上記の問題はさらに悪化する。ユーザーのソフトウェアでの参照の局所性は薄れてきた。オブジェクト指向プログラミングが多く使われるようになったことが原因のひとつである。この場合、小さな関数を数多く使用し、ツリー構造やハッシュテーブルなどの洗練されたデータ構造を使用する。これらは混沌としたメモリ参照パターンを示し、ガベージコレクションがひとたび起きればメモリ参照パターンは劇的に変化してしまう。置換アルゴリズムへの要求もオペレーティングシステムのカーネルアーキテクチャの変化に伴って変わってきた。多くの最近のカーネルは仮想記憶とファイルシステムのキャッシュを統合的に管理している。したがって、置換アルゴリズムはページを選択するにあたって、ユーザプログラムの仮想アドレス空間とキャッシュされたファイルの両方を検討しなければならない。後者のページは特定の属性を持つ。ファイルキャッシュはロックされる可能性もあるし、ジャーナリングによってディスクへの書き込みを要求されている場合もある。ページ置換アルゴリズムの目標がメモリ待ちとなる時間を最小化することだとすれば、他のカーネル内サブシステムのメモリ確保要求についても関わっていかなければならない。結果として、最近のカーネル(Linux、FreeBSD、Solaris)では、ページ置換は仮想記憶サブシステムのレベルよりももっと基本的なカーネル内の汎用メモリアロケーション機構の一部となりつつある。ローカルな置換とグローバルな置換[編集]置換アルゴリズムは「ローカル」と「グローバル」に分けられる。あるプロセスがページフォールトを発生したとき、ローカルなページ置換アルゴリズムではそのプロセス(あるいはそのプロセスが属するメモリ・パーティションを共有するプロセスグループ)が現在使用しているページ群からページを選択して置換する。グローバルなページ置換アルゴリズムではメモリ上の任意のページを選択する。ローカルなページ置換では、ある種のメモリ・パーティションが前提となっており、プロセスあるいはプロセスグループに対して割り当て可能なメモリページ数を決定している。一般的なパーティション手法としては「固定パーティション」とワーキングセットモデルに基づいた「バランスセット」アルゴリズムがある。ローカルなページ置換の利点はスケーラビリティが良いことである。各プロセスはページフォールトに独立して対処できるので、グローバルなデータ構造に必要以上に関わる必要がない。事前クリーニング[編集]最も教科書的な置換アルゴリズムは、結果としてページを選択して返す。クリーンなページにしなければならない。初期の仮想記憶では、このクリーニング処理のオーバーヘッドは問題とはならなかった。いうのは、当時のシステムでは全二重チャネルで二次記憶装置を接続していたため、ページインを並行して実行できたのである。最近の商用ハードウェアでは、全二重転送はサポートしていないため、クリーニングが問題となるのである。これに対処するために、様々な事前クリーニングポリシーが実装された。考え方は、次にページアウト対象として選ばれるページを事前にディスクに書き戻しておけば、実際にページアウト対象として選ばれたときにはI/Oをする必要がないということである。事前クリーニングは次に選択されるページが事前にわかることを前提としている。積極的に行うと、選択されたときにはまたクリーニングが必要な状態になってI/Oバンド幅を浪費することになる。結局、スループットを優先するか、ターンアラウンドタイムを優先するかという選択になり、システムの性格によって最適な落とし所は変わってくる。先行ページング[編集]デマンドページングを採用しているシステムもあり、実際に要求を受けてからページの内容をRAMにロードする。RAM上にないどのページが間もなく必要とされるかを推論し、そのようなページを要求される前にRAMへロードするシステムもある。これに事前クリーニングを組合わせることが多く、RAM上にあるページのうちすぐには必要とされないページを推測し、それを事前に二次記憶装置に書き戻しておく。ページフォールトが発生したとき、「先行ページング」システムでは参照されたページを持ってくるだけでなく、参照のあったページに続く数ページも同時にロードしておく。CPUが命令プリフェッチで数個の命令を事前にフェッチしておくのと同様である。間もなく必要になると思われるページ群を不連続であっても事前にロードする方式を「スワッププリフェッチ」と呼ぶ。各種アルゴリズム[編集]ページ置換アルゴリズムには様々なものがある[1]。理論上最適なページ置換アルゴリズム[編集]理論上最適なページ置換アルゴリズム(OPT、千里眼置換アルゴリズム、Béládyの最適ページ置換アルゴリズムとも呼ばれる)[2][3][1]とは、以下のようなものである。ページをスワップインする必要が生じたとき、オペレーティングシステムが現在メモリ上にあるページを全て調べて、次にページが使われるまでの時間を測る。OSは最も長い期間使われないページをスワップアウトする。今後6秒間使われないページをスワップアウトして、今後0.4秒間使われる予定のページに割り当てる。このアルゴリズムを実際に(少なくとも汎用の)オペレーティングシステムに実装することは現実的ではない。実行されるソフトウェアが全て判っていて、それらのメモリ使用パターンも分析済みであるか、実行時に分析することが可能な場合は不可能ではない。近い性能を示すアルゴリズムは存在する。あるソフトウェアを最初に動作させたときに、オペレーティングシステムが使われたページを全て記録する。このデータを使って二度目以降にそのソフトウェアを動作させるときに、このデータを使ってページ置換を行うのである。近い性能を保証するが、それは二度目の動作のときであり、初めて動作させるソフトウェアでは無効である。動作するたびにメモリ参照パターンが大きく変化するプログラムでは効果がない。ページング問題の解析はオンラインアルゴリズムの分野の話題である。ページング問題向けの乱択オンラインアルゴリズムの効率はならし解析(英語版)を使って測定される。Used)[編集]NRU(最近使われていない)ページ置換アルゴリズムは、最近使われたページを残すことを主眼としたアルゴリズムである。このアルゴリズムは以下のように働く。ページが参照されたとき、そのページの参照ビットを立てて参照があったことを示す。同様にページが変更(書き込み)された場合、変更ビットを立てる。これらビットのセットは通常ハードウェア(MMU)が行うが、ソフトウェアレベルで行うことも可能である。ある一定の時間間隔でクロック割り込みをトリガーとして全ページの参照ビットをクリアする。すると、その時間間隔内で参照されたページだけが参照ビットが立った状態になる。ページを置換する必要が生じたとき、オペレーティングシステムはページを4種類に分類する。参照あり、変更あり参照されていないのに変更されているページというのは矛盾しているように思われるが、これはカテゴリ3のページの参照ビットをクロック割り込みの際にクリアした場合に生じる。アルゴリズムでは、単純にカテゴリ番号の小さい方のページを選択する。変更があるかどうかよりも参照があるかどうかを重視することに注意されたい。First-Out)[編集]FIFOページ置換アルゴリズムはオーバヘッドの少ないアルゴリズムのひとつで、OS内でちょっとした記録をとる。名前からもわかるとおり、プロセスに割り当てたページを割り当てた順番にキューに載せる。ページ置換が必要になったとき、キューの先頭のページ(最も古いページ)を選択する。FIFO構造はコストがかからないし簡単なのだが、実際のアプリケーションにこのアルゴリズムを適用すると性能は悪くなる。そのため、そのままの形で使われることはない。このアルゴリズムではBéládyの例外(英語版)と呼ばれる状況が発生しうる。FIFOページ置換アルゴリズムはVAX/VMSで、若干修正された形で使われている[4]。有効な変換テーブル参照において限定された数のエントリをスキップすることで、後述のセカンドチャンス方式を部分的に取り入れている[5]。置換されたページをプロセスのワーキングセットからシステム全体のプールに移すが、そういったページが再利用される前に再び当該ページの内容が必要になった場合は、そのまま使える。セカンドチャンス[編集]これは、FIFOページ置換アルゴリズムを少し改善したものである。このアルゴリズムでもFIFOの先頭のページをまず調べるが、即座にスワップアウトするのではなく、参照ビットが立っているかどうかを調べる。立っていなかったら、そのページをスワップアウトする。なくば、そのページの参照ビットをクリアしてFIFOの最後尾につなぎ直す。この処理を繰り返すのである。全てのページの参照ビットが立っていたら、元の先頭ページがFIFOの先頭に出てきた時点で、それをスワップアウトする(参照ビットがクリアされているため、元にもどったかどうかを判断する必要はない)。全ページの参照ビットが立っている場合、純粋なFIFOと同じことになる。セカンドチャンスが何をしているかと言えば、古いページの参照ビットを見てチャンスを一度あげるのである。ページ置換が必要になったとき、キュー上の全ページを見て回る(しかもキューを操作し続ける)可能性があることに注意。大容量のメモリを持ち、応答性能を重視されるシステムでは予想外の遅延が生じる可能性がある。クロック[編集]クロック(時計)とは、FIFOをセカンドチャンスよりも効率化した方式で、ページを定期的にリストの後方に押しやる必要がなく、セカンドチャンスと同等の機能を実現するものである。クロックアルゴリズムではページを円環状のリストとして扱い、そのリスト上の最も古いページを指す「針」を使用する。ページフォールトが発生して空きがないとき、針が指している位置から参照ビットのチェックを行う。ないなら参照ビットをクリアして針をインクリメントする。置換可能なページが見つかるまでこれを繰り返す[6]。最近参照されたページに関する情報の環状リストにおいて、メモリ上の全Mページだけでなく、最近ページアウトされたMページも保持しておく。ARCのようにページアウトされたページについての情報を使うことで、多数のページでのLRUよりも効率が良くなる[8]。ARCと同等の性能を発揮するページ置換アルゴリズムで、LRUやクロック方式よりも性能が高い[12]。CARアルゴリズムは自律的に調整するので、ユーザーがパラメータを具体的に指定する必要がない。NRUと名前は似ているが、LRUでは短期間のページ使用履歴を保持している点が異なる。NRUではクロック割り込み間隔の使用/不使用で判断していた。最近よく使われているページはその後の短時間でもよく使われるだろうという判断に基づいている。近い性能を発揮するはずだが、実際に実装するとコストがやや高い。このコストを抑える試みをした実装手法がいくつか存在している。コストの高い手法はメモリ上の全ページを含むリンクリストを使う方法である。このリストの最後尾はLRUページであり、先頭は逆に最近使われているページである。この実装のコストはメモリ参照の度にリスト上のアイテムを移動させなければならない点であり、これには非常に時間がかかる。別の方法はハードウェアのサポートを必要とする。64ビットのカウンタを命令実行毎にカウントアップする。ページにアクセスがあったときは、その時点のカウンタの値をページに与える。ページを置換するとき、オペレーティングシステムは単純に最も小さなカウンタ値を持つページを選択する。現在のハードウェアにはそのような機構はないので、OSが全ページについてカウンタを調べる必要があり、現実的ではない。アルゴリズムの重要な利点は、完全な統計分析を修正できる余地がある点である。N回以上ページフォールトが多くなることはない、ということが証明されている。管理対象のページ数に比例した値である。実装コストがかかるため、LRUに似ているがより実装コストの低いアルゴリズムを考慮することもある。欠点は、一般的な参照パターンで性能を低下させてしまう傾向があることである。ページにまたがる配列にアクセスしながらループしているとき、インデックスの進みと共にページフォールトが発生してしまう(つまり、配列が大きすぎるので必ずページ置換は必要だが、LRUを使うと次にアクセスするページが必ずページアウトされてしまう)。大きなループを使うのは一般的なので、このような場合に対応できるようにLRUを改善する試みは多く行われてきた。Used)に切り替えるのである。おける時間局所性を改善した方式。