ページ置換アルゴリズム（ページちかんアルゴリズム）とは、仮想記憶管理としてページング方式を使用するコンピュータのオペレーティングシステムにおいて、空き物理ページが少ない状態で新たなページを割り当てなければならないときにどのページを「ページアウト（スワップアウト）」するかを決定する方法を意味する。これはページフォールトが発生したときに使用可能なフリーなページが存在しないときに発生する。厳密には発生条件はシステムの種類や設定によって異なるが、フリーなページが全く無い場合か、あらかじめ設定したしきい値よりもフリーなページ数が少ないときに発生する。

以前にページアウトすべきページとして選択され置換されたページに再度アクセスが発生したら、そのページをページインする必要がある。そして、これにはI/Oの完了を待たなければならない。この、ページインを待つ時間の累計が小さいほどページ置換アルゴリズムが優秀であると言える。ページ置換アルゴリズムはページへのアクセスに関するハードウェアからの限られた情報を見て、アルゴリズム自身にかかる時間とページインにかかる時間のバランスをとりつつ、ページミスのなるべく起きない置換をしなければならない。

ページ置換アルゴリズムはオンラインアルゴリズムの一種である。
歴史

ページ置換アルゴリズムは1960年代から1970年代にかけて研究の重要テーマであり、議論が戦わされた。結果として洗練されたLRU推測手法とワーキングセットアルゴリズムが開発されたのである。以来、伝統的なアルゴリズムが前提としていた事柄の一部が否定され、ふたたび研究が行われるようになった。とりわけ、以下のようなハードウェアの動作の変化とユーザーレベルのソフトウェアの動作の変化がアルゴリズムを変えさせてきた。

一次記憶装置の容量はどんどん大きくなっている。主記憶が数ギガバイトということも珍しくない状態では、全メモリページを定期的にチェックするアルゴリズムはどんどん現実味を失いつつある。

メモリ階層が高くなってきた。CPUのキャッシュミスは非常に性能にインパクトがあるため、上記の問題はさらに悪化する。

ユーザーのソフトウェアでの参照の局所性は薄れてきた。オブジェクト指向プログラミングが多く使われるようになったことが原因のひとつである。この場合、小さな関数を数多く使用し、ツリー構造やハッシュテーブルなどの洗練されたデータ構造を使用する。これらは混沌としたメモリ参照パターンを示し、ガベージコレクションがひとたび起きればメモリ参照パターンは劇的に変化してしまう。

また、置換アルゴリズムへの要求もオペレーティングシステムのカーネルアーキテクチャの変化に伴って変わってきた。多くの最近のカーネルは仮想記憶とファイルシステムのキャッシュを統合的に管理している。したがって、置換アルゴリズムはページを選択するにあたって、ユーザプログラムの仮想アドレス空間とキャッシュされたファイルの両方を検討しなければならない。後者のページは特定の属性を持つ。例えば、ファイルキャッシュはロックされる可能性もあるし、ジャーナリングによってディスクへの書き込みを要求されている場合もある。さらに、ページ置換アルゴリズムの目標がメモリ待ちとなる時間を最小化することだとすれば、他のカーネル内サブシステムのメモリ確保要求についても関わっていかなければならない。結果として、最近のカーネル（Linux、FreeBSD、Solaris）では、ページ置換は仮想記憶サブシステムのレベルよりももっと基本的なカーネル内の汎用メモリアロケーション機構の一部となりつつある。
ローカルな置換とグローバルな置換

置換アルゴリズムは「ローカル」と「グローバル」に分けられる。あるプロセスがページフォールトを発生したとき、ローカルなページ置換アルゴリズムではそのプロセス（あるいはそのプロセスが属するメモリ・パーティションを共有するプロセスグループ）が現在使用しているページ群からページを選択して置換する。一方、グローバルなページ置換アルゴリズムではメモリ上の任意のページを選択する。

ローカルなページ置換では、ある種のメモリ・パーティションが前提となっており、プロセスあるいはプロセスグループに対して割り当て可能なメモリページ数を決定している。最も一般的なパーティション手法としては「固定パーティション」とワーキングセットモデルに基づいた「バランスセット」アルゴリズムがある。ローカルなページ置換の利点はスケーラビリティが良いことである。各プロセスはページフォールトに独立して対処できるので、グローバルなデータ構造に必要以上に関わる必要がない。
事前クリーニング

最も教科書的な置換アルゴリズムは、結果としてページを選択して返す。このページが変更されている場合（そのページを再利用する前に内容を二次記憶装置に書き戻す必要があることを意味する）、ページ内容をディスクなどに書き出して クリーンなページにしなければならない。初期の仮想記憶では、このクリーニング処理のオーバーヘッドは問題とはならなかった。というのは、当時のシステムでは全二重チャネルで二次記憶装置を接続していたため、ページインを並行して実行できたのである。最近の商用ハードウェアでは、全二重転送はサポートしていないため、クリーニングが問題となるのである。

これに対処するために、様々な事前クリーニングポリシーが実装された。事前クリーニングとは、間もなく再利用される予定の（内容を変更されている）ページについて I/O を開始する機構である。考え方は、次にページアウト対象として選ばれるページを事前にディスクに書き戻しておけば、実際にページアウト対象として選ばれたときにはI/Oをする必要がないということである。事前クリーニングは次に選択されるページが事前にわかることを前提としている。あまり積極的に行うと、選択されたときにはまたクリーニングが必要な状態になってI/Oバンド幅を浪費することになる。結局、スループットを優先するか、ターンアラウンドタイムを優先するかという選択になり、システムの性格によって最適な落とし所は変わってくる。
先行ページング

デマンドページングを採用しているシステムもあり、実際に要求を受けてからページの内容をRAMにロードする。

一方、RAM上にないどのページが間もなく必要とされるかを推論し、そのようなページを要求される前にRAMへロードするシステムもある。これに事前クリーニングを組合わせることが多く、RAM上にあるページのうちすぐには必要とされないページを推測し、それを事前に二次記憶装置に書き戻しておく。

ページフォールトが発生したとき、「先行ページング」システムでは参照されたページを持ってくるだけでなく、参照のあったページに続く数ページも同時にロードしておく。CPUが命令プリフェッチで数個の命令を事前にフェッチしておくのと同様である。

間もなく必要になると思われるページ群を不連続であっても事前にロードする方式を「スワッププリフェッチ」と呼ぶ。
各種アルゴリズム

ページ置換アルゴリズムには様々なものがある[1]。
理論上最適なページ置換アルゴリズム

理論上最適なページ置換アルゴリズム（OPT、千里眼置換アルゴリズム、Beladyの最適ページ置換アルゴリズムとも呼ばれる）[2][3][1]とは、以下のようなものである。