Criterios de reemplazo

La evaluación se hace en base a la tasa de fallos de página, que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

• Arranque en frío : se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno esta cargado en memoria principal.
• Arranque en caliente : se suponen ya cargadas las páginas de los procesos en memoria principal.

Criterio de página óptima

Este es un criterio teórico que viene a establecer la cota inferior de la tasa de fallos de página. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4

         Suponiendo arranque en frío   
                                        ___1_____2_____3_____4___
                  memoria principal     |     |     |     |     |
                   de 4 marcos          |_____|_____|_____|_____|

• Solución

Criterio de página pésima

Este también es teórico y viene a establecer la cota superior de la tasa de fallos de página, para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

• Solución

Criterio de selección estocástica (aleatoria)

Se trata también de un criterio teórico. Consiste en seleccionar una página al azar.

Criterio MRU(Most Recently Used)

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

• Solución

Criterio por orden de carga FIFO

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

• Solución

Criterio NRU (Not Recently Used)

Ofrece dos bits para cada página:

• Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
• Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

1. R=0, M=0 .
2. R=0, M=1 .
3. R=1, M=0 .
4. R=1, M=1 .

Periódicamente se pone a cero el bit R.

• Solución

Criterio de 2ª oportunidad

Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Consiste en recorrer la cola hasta encontrar una página con R a 0 (si no hay ninguno, pues al que le toque de la cola) y los procesos que vaya encontrando con R a 1 se les pone R a 0 y se les da una segunda oportunidad poniéndolos al final de la cola (al final de todo, el nuevo elemento llegado).

• Solución

Criterio del reloj

Igual que el de 2º oportunidad pero mantenemos un puntero a la ultima pagina examinada; se implementa con una lista circular, y un puntero a la ultima pagina examinada, que sera el 1º elemento que examinaremos para el reemplazo.

• Solución

Criterio LRU (Least Recently Used)

Criterio en contraposición al MRU. En MRU elegíamos aquella página que hubiéramos utilizado más recientemente (la primera de la pila de acceso) mientras que en LRU elegimos como página víctima lo contrario: La última página de la pila. Funciona como una FIFO (por orden de acceso) en la cual se actualizan los valores, poniéndose al final si llegan elementos que ya había en cola.

• Solución

Criterio LFU (Least Frecuently Used)

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

• Solución

Aproximación discreta LRU

Consiste en LFU + LRU. Se usa el bit R. Se itera periódicamente sobre la lista de páginas si R = 0 entonces aumento el contador; si R está activado se desactiva y el contador se pone a cero. Ante una sustitución: prescindir de la que tiene mayor valor en el contador. Ojito! Cuando llega un elemento, el contador se inicializa a 0, puesto que solo se modifica en los checkpoints, no con cada acceso

• Solución

Sustitución por envejecimiento

Se emplea un registro R de n bits que se va desplazando hacia la derecha periódicamente, de forma que la página victima será la que tenga el menor valor en el registro R (en caso de empate se empleao otro criterio). Por cada acceso se pone a 1 el bit más significativo del registro R. Los LSB se pierden al desplazar.

• Solución

Implementaciones

En el Portal de la comunidad se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento. Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --Alexrdp 16:24 6 jun 2011 (UTC)