もしページインを行う際に物理メモリに空き容量がない場合は、現在物理メモリ上にあるページの中から、どれかを補助記憶装置に追い出す（ページアウトする）必要があります。どのページを追い出して空きを作るかという決定を行うアルゴリズムを「ページ置換アルゴリズム」と呼びます。代表的なものには、メモリに読み込まれた順序が最も古いページを追い出す「FIFO（First In First Out）」や、最も長い間参照されていないページを追い出す「LRU（Least Recently Used）」、最も参照回数が少ないページを追い出す「LFU（Least Frequently Used）」などがあります。一般的に、過去の使用履歴に基づいて判断するLRUの方が人間の利用パターンに近いため、効率的なアルゴリズムとして広く採用されています。
試験においてページフォールトに関する問題は、「仮想記憶システムにおける実効アクセス時間」を求める計算問題として頻出です。「ページフォールト率がpのとき、平均アクセス時間はいくつか」といった問題では、物理メモリへのアクセス時間と、ページフォールト発生時の補助記憶装置へのアクセス時間（ページ入れ替え処理時間を含む非常に長い時間）を加重平均して計算します。ミリ秒とナノ秒といった単位の違いに注意して計算する力が求められます。
また、前述のページ置換アルゴリズム（FIFO、LRU、LFUなど）の違いと特徴を問う問題も定番中の定番です。「最も長い間使われていないページを置き換え対象とする方式はどれか」といった問題文が出た場合、即座にLRUと答えられるようにキーワードを紐付けておきましょう。
さらに、搭載メモリ量が少なすぎるなどの理由でページフォールトが頻発し、OSがページの入れ替え処理にばかり時間を取られて、本来のアプリケーションプログラムの実行がほとんど進まなくなる致命的な状態である「スラッシング」も、関連する超頻出キーワードです。ページフォールト率が高まるとシステム性能が急激に低下するグラフの形などもイメージできるようにしておくと完璧です。
ページ置換アルゴリズム、LRU、FIFO、スラッシング