Con
H. M. Deitel. “Introducción a los Sistemas Operativos” (1987). Escribe sobre utilizar las estrategias de reemplazo de página cuando las rutinas de administración de almacenamiento del Sistema operativo deben decidir que página del almacenamiento primario se debe desplazar para dejar espacio a una página entrante. Estas estrategias de las que hace mención H. M. Deitel son:
- Principio de Optimalidad: Para obtener un rendimiento óptimo, la página que se debe reemplazar es aquella que tardará más tiempo en ser utilizada. Esta estrategia óptima de reemplazo se denomina OPT o MIN.
- Reemplazo de Páginas aleatorio: Es una técnica sencilla. Todas las páginas que se encuentran en el almacenamiento principal tienen la misma probabilidad de ser elegidas para el reemplazo. Esta estrategia podría seleccionar cualquier página para ser reemplazada, incluyendo la siguiente página la que se hará referencia. Las decisiones de reemplazo aleatorio se de páginas se pueden tomar rápidamente y con un número significativo de marcos de página. 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 página se registra en el instante que entró en el almacenamiento primario. Cuando se necesita reemplazar una página, se escoge la que ha permanecido en el almacenamiento durante el mayor tiempo.
- Anomalías PEPS: Belady, Nelson y Shelder descubrieron que al utilizar el reemplazo de páginas PEPS, ciertos patrones de referencia a página originan más fallas de páginas cuando aumenta el número de marcos de página asignados a un proceso. Este fenómeno se denomina Anomalía PEPS o anomalía Belady. La columna de la izquierda indica el patrón de referencias a páginas de un proceso. La primera tabla muestra como dicho patrón a referencia de páginas hace que las páginas se carguen a memoria y se reemplacen en secuencia PEPS cuando se asignan tres marcos de páginas a proceso. La segunda tabla muestra como se comporta éste proceso en las mismas circunstancias, pero con cuatro marcos de páginas asignados, a la izquierda de cada tabla se indica si la nueva referencia a una página ocasiona o no una falla de pagina. Cuando el proceso se ejecuta en cuatro páginas, experimenta una falla de página más que cuando se ejecuta con tres.
- Reemplazo de páginas de la menos reciente utilizada: Se selecciona para su reemplazo, a aquella página que no se ha sido utilizada durante mayor tiempo. La estrategia se basa en que la heurística de localidad según en el cual el pasado reciente es un buen indicador del futuro cercano, de modo que LRU exige que se marque cada página 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 páginas de la menos frecuentemente utilizada (LFU): La página 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 páginas corren cierto riesgo de tomar decisiones equivocadas. Esto sucede por el simple hecho de que no se puede predecir con precisión el futuro.
- Reemplazo de páginas de la no utilizada recientemente (NUR): Como es deseable reemplazar una página que no estaba en el almacenamiento primario, la estrategia NUR se lleva a la práctica con la adición dedos bits de hardware por página. Esos bits son:
Bit de Referencia = O si no se ha hecho referencia a la página
= 1 se ha hecho regencia a la página,
Bit de Modificación = O si la página no ha sido modificada
= 1 si la página ha sido modificada.
El bit de modificación se denomina a menudo Bit sucio. La estrategia NUR trabaja: Inicialmente, los bits de referencias de todas las páginas valen cero. Cuando ocurre una referencia a una página, su bit de referencia toma el número uno. Cuando se va a reemplazar una página a la que no se ha hecho referencia .Si una página no ha sido objeto de una referencia se comprueba si ha sido modificada. Si lo ha sido se reemplaza. Pues requiere menos trabajo que el reemplazo de una página modificada, la cual debe escribirse en el almacenamiento secundario. De otro modo hay que reemplazar una página modificada.
Los bits de referencia de las páginas activas cambiarán a 1 casi de inmediato. Según se ha descrito el esquema NUR origina la existencia de cuatro grupos de páginas:
Grupo 1 sin referencia no modificado
Grupo 2 sin referencia modificado
Grupo 3 con referencia no modificado
Grupo 4 con referencia modificado
Las páginas de los dos primeros grupos se reemplazarán primero, y las de los últimos grupos, al final. Las páginas de un grupo se seleccionan aleatoriamente para ser reemplazadas. Obsérvese que el grupo 2 parece describir una situaci6n irreal en la que las páginas han sido modificadas, pero no se ha hecho referencia a ellas; sin embargo, esto es una consecuencia simple de la reiniciación periódica de los bits de referencia (pero no de los bits de modificaci6n) y es perfectamente razonable.
- Modificaciones de PEPS; reemplazo de páginas por reloj y reemplazo de páginas con segunda oportunidad: La estrategia PEPS puede decidir reemplazar una página muy utilizada que ha permanecido en memoria durante mucho tiempo. Esta posibilidad se puede evitar reemplazando sólo aquellas páginas cuyos bits de referencia valgan O.La variante de PEPS denominada "con segunde oportunidad" examina el bit de referencia de la página más antigua; si este bit vale O, se selecciona de inmediato la página para ser reemplazada. Si el bit de referencia vale 1, se le asigna el valor O y la página se pasa al final de la lista y se considera en esencia como una página nueva; gradualmente dicha página se desplaza hacia el principio de la lista, donde será seleccionada para reemplazo sólo si su bit de referencia sigue valiendo O. En esencia, esto da a la página una segunda oportunidad de permanecer en el almacenamiento principal si su bit de referencia cambia a 1 antes de que la página llegue al principio de la lista. La variación 'z' del reloj" del algoritmo de la segunda oportunidad dispone las páginas 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 página toma el valor O, el apuntador se mueve al siguiente elemento de la lista (simulando el movirl1iento de esta página al final de la lista PEPS).
tenido de la nueva página
