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 esta descargada en disco.
nº fallos pág.
tasa fallos pág = -----------------
nº accesos pág.
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.
Criterios
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 |_____|_____|_____|_____|
- 1. 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.
- 2. 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.
- 3. 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.
- 4. Criterio de selección estocástica (aleatoria)
- Consiste en seleccionar una página al azar.
- 5. 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.
- 6.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).
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 .
Claramente deben realizarse periodos de puesta a 0, que no tienen porque ser simultáneamente en R y M.
- 7.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).
- 8.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 del reloj
- Igual que el de 2º oportunidad (FIFO + NRU sin bit M) pero mantenemos un puntero a la ultima pagina examinada.
- 9.Criterio LFU (Least Frecuently Used)
- Se incrementa un contador de uso por cada acceso. La víctima será la que tenga el contador menor.
- 10.Aproximación discreta LRU
- Consiste en LRU + LFU. Se usa el bit R. Se itera periódicamente sobre la lista de páginas si R = 1 entonces aumento el contador y pongo R a 0.
- 11.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.
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)
