もしページインを行う際に物理メモリに空き容量がない場合は、現在物理メモリ上にあるページの中から、どれかを補助記憶装置に追い出す（ページアウトする）必要があります。どのページを追い出して空きを作るかという決定を行うアルゴリズムを「ページ置換アルゴリズム」と呼びます。代表的なものには、メモリに読み込まれた順序が最も古いページを追い出す「FIFO（First In First Out）」や、最も長い間参照されていないページを追い出す「LRU（Least Recently Used）」、最も参照回数が少ないページを追い出す「LFU（Least Frequently Used）」などがあります。一般的に、過去の使用履歴に基づいて判断するLRUの方が人間の利用パターンに近いため、効率的なアルゴリズムとして広く採用されています。