Sempre que uma página (endereço virtual) não estiver em uma moldura de página, uma interrupção ocorre e ela deve ser carregada para uma moldura antes de ser executada. No entanto, alguma página que está atualmente em uma moldura deve ser retirada (gravada em disco). Os algoritmos de substituição de páginas se preocupam em escolher a melhor página a ser retirada da moldura. Existem várias alternativas:
algoritmo de substituição de página ótimo: deve ser retirada a página que só será referenciada o mais tarde possível. Apesar de, teoricamente, ser um algoritmo interessante, é extremamente difícil prever quando uma página será referenciada;
algoritmo de substituição de página não recentemente utilizada (NUR): o S.O. e o hardware mantêm uma coleção de estatísticas sobre as páginas referenciadas e/ou modificadas (através dos bits de referência e modificação das entradas da tabela de páginas) e dão preferência para a troca de páginas não referenciadas e/ou não modificadas;
algoritmo de substituição de página “primeira a entrar, primeira a sair (FIFO – first-in first-out): a página mais antiga é removida.No entanto, pode estar sendo removida uma página bastante utilizada;
algoritmo de substituição de página de segunda chance(SC): uma modificação do algoritmo FIFO, que busca não substituir uma página antiga e, no entanto, bastante utilizada. A solução é inspecionar o bit R (referenciada) da página mais antiga; se o bit for 1 (foi referenciada) o bit será limpo e a pesquisa continua. Se todas as páginas tiverem sido referenciadas, o algoritmo FIFO acaba sendo executado e a página mais antiga (que agora estará com o bit R limpo) será substituída;
algoritmo de substituição de página menos recentemente utilizada (LRU – least recently used): a idéia é que as páginas que foram intensamente utilizadas nas últimas instruções provavelmente serão utilizadas de forma intensa no futuro próximo. Desta forma, deve ser removida a página que não foi utilizada por mais tempo.