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.
Contenido
- 1 Criterio de página óptima
- 2 Criterio de página pésima
- 3 Criterio de selección estocástica (aleatoria)
- 4 Criterio MRU(Most Recently Used)
- 5 Criterio por orden de carga FIFO
- 6 Criterio NRU (Not Recently Used)
- 7 Criterio de 2ª oportunidad
- 8 Criterio LRU (Least Recently Used)
- 9 Criterio LFU (Least Frecuently Used)
- 10 Aproximación discreta LRU
- 11 Sustitución por envejecimiento
- 12 Implementaciones
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 |_____|_____|_____|_____|
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.
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.
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.
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:
- R=0, M=0 .
- R=0, M=1 .
- R=1, M=0 .
- R=1, M=1 .
Periódicamente se pone a cero el bit R.
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).
- 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.
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.
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.
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
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.
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)
