Las rutinas de administracion de almacenamiento del Sistema operativo deben decidir que pagina del almacenamiento primario se debe desplazar para dejar espacio a una pagina entrante .

Principio de Optimalidad
Para obtener un rendimiento optimo, la pagina que se debe reemplazar es aquella que tardara mas tiempo en ser utilizada. Esta estrategia optima de reemplazo se denomina OPT o MIN.

Reemplazo de Páginas aleatorio
Es una tecnica sencilla. Todas las paginas que se encuentran en el almacenamiento principal tienen la misma probabilidad de ser elegidas para el reemplazo. Esta estrategia podria seleccionar cualquier pagina para ser reemplazada, incluyendo la siguiente pagina la que se hara referencia. Las decisiones de reemplazo aleatorio se de paginas se pueden tomar rapidamente y con un numero significativo de marcos de pagina. Es un esquema que casi no se utiliza por su enfoque aleatorio de acertar o errar.

Reemplazo de páginas de primeras entradas-primeras salidas (PEPS)
Cada pagina se registra en el instante que entro en el almacenamiento primario. Cuando se necesita reemplazar una pagina, se escoge la que ha permanecido en el almacenamiento durante el mayor tiempo.

Anomalias PEPS
Belady, Nelson y Shelder descubrieron que al utilizar el reemplazo de paginas PEPS, ciertos patrones de referencia a pagina originan mas fallas de paginas cuando aumenta el numero de marcos de pagina asignados a un proceso. Este fenomeno se denomina Anomalia PEPS o anomalia Belady. La columna de la izquierda indica el patron de referencias a paginas de un proceso. La primera tabla muestra como dicho patron a referencia de paginas hace que las paginas se carguen a memoria y se reemplacen en secuencia PEPS cuando se asignan tres marcos de paginas a proceso.
La segunda tabla muestra como se comporta este proceso en las mismas circunstancias, pero con cuatro marcos de paginas asignados, a la izquierda de cada tabla se indica si la nueva referencia a una pagina ocasiona o no una falla de pagina. Cuando el proceso se ejecuta en cuatro paginas, experimenta una falla de pagina mas que cuando se ejecuta con tres.

Reemplazo de páginas de la menos reciente utilizada
Se selecciona para su reemplazo, a aquella pagina que no se ha sido utilizada durante mayor tiempo. La estrategia se basa en que la heuristica de localidad segun en el cual el pasado reciente es un buen indicador del futuro cercano, de modo que LRU exige que se marque cada pagina con el instante en que .se hace referencia a ella. Por el trabajo adicional que requiere no se usa a menudo en los sistemas actuales; lo que se hace es utilizar estrategias que ese aproximen a la LRU y que no ocasionen grandes costos.

Reemplazo de paginas de la menos frecuentemente utilizada (LFU)
La pagina por remplazar es aquella que ha sido utilizada menos frecuentemente o a la que se ha hecho referencia con menos frecuencia.
Al parecer estos esquemas de reemplazo de paginas corren cierto riesgo de tomar decisiones equivocadas. Esto sucede por el simple hecho de que no se puede predecir con precision el futuro.

Modificaciones de PEPS; reemplazo de paginas por reloj y reemplazo de paginas con segunda oportunidad
La estrategia PEPS puede decidir reemplazar una pagina muy utilizada que ha permanecido en memoria durante mucho tiempo. Esta posibilidad se puede evitar reemplazando solo aquellas paginas cuyos bits de referencia valgan O.
La variante de PEPS denominada "con segunde oportunidad" examina el bit de referencia de la pagina mas antigua; si este bit vale O, se selecciona de inmediato la pagina para ser reemplazada. Si el bit de referencia vale 1, se le asigna el valor O y la pagina se pasa al final de la lista y se considera en esencia como una pagina nueva; gradualmente dicha pagina se desplaza hacia el principio de la lista, donde sera seleccionada para reemplazo solo si su bit de referencia sigue valiendo O. En esencia, esto da a la pagina una segunda oportunidad de permanecer en el almacenamiento principal si su bit de referencia cambia a 1 antes de que la pagina llegue al principio de la lista. La variacion 'z' del reloj" del algoritmo de la segunda oportunidad dispone las paginas en una lista circular, en lugar de en una lista lineal.

Un apuntador a la lista se desplaza alrededor de la lista circular en la misma forma que gira la manecilla de un reloj. Cuando el bit de referencia de una pagina toma el valor O, el apuntador se mueve al siguiente elemento de la lista (simulando el movirl1iento de esta pagina al final de la lista PEPS).