Criterios de reemplazo
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 da 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) : página más recientemente usada. 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:
1º- R=0, M=0 .
2º- R=0, M=1 .
3º- R=1, M=0 .
4º- 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 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.
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.
