A política de alocação de páginas da técnica de memória virtual por paginação determina quantos frames cada processo pode manter na memória principal. Em algumas situações, quando um processo atinge o seu limite de alocação de frames e necessita alocar novas páginas na memória principal, o sistema operacional deve selecionar, dentre as diversas páginas alocadas, qual deverá ser liberada com base numa política de substituição de páginas. O algoritmo de substituição de páginas tem por objetivo selecionar os frames que tenham as menores chances de serem referenciados em um futuro próximo.
Em particular, o algoritmo Least-Recently-Used (LRU)
-
A usa apenas uma lista de páginas alocadas e seleciona o frame que foi utilizado primeiro e que está há mais tempo na memória.
-
B usa um contador de referências em cada frame e seleciona o frame que foi menos referenciado.
-
C usa um marcador de tempo da última referência em cada frame e seleciona o frame que está há mais tempo sem ser referenciado.
-
D combina uma lista de páginas alocadas (LPA) com uma lista de páginas livres (LPL) e seleciona o frame em uso há mais tempo na memória, movendo-o da LPA para a LPL.
-
E usa um bit de referência e um bit de modificação em cada frame e classifica os frames em função desses bits em quatro categorias, selecionando o frame classificado na categoria inferior.