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.
Tasa fallos página = total fallos de pagina/total accesos a pagina
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 está 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 (OPT, MIN)
- 2 Criterio de página pésima (MAX)
- 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 de la 3ª oportunidad (Método Multics)
- 9 Criterio LRU (Least Recently Used)
- 10 Criterio LFU (Least Frecuently Used)
- 11 Aproximación discreta LRU
- 12 Sustitución por envejecimiento
- 13 Implementaciones
Criterio de página óptima (OPT, MIN)
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
Marco Marco Marco Marco
1 2 3 4
Memoria principal +-----+-----+-----+-----+
de 4 marcos | | | | |
+-----+-----+-----+-----+
Otra forma de evaluar la eficiencia de un criterio de selección de página víctima es observando su curva paracorde, que relaciona el nº de fallos de página con el nº de marcos. La de un buen criterio se aproximará a la curva del criterio óptimo, y la de uno malo, a la del criterio al azar, o incluso pésimo.
En el siguiente ejemplo real se compara la efectividad de varios criterios en varios programas:
Criterio de página pésima (MAX)
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. También implica tener conocimiento de futuro, por lo que no es implementable en la práctica.
Criterio de selección estocástica (aleatoria)
Se trata también de un criterio teórico, serviría para aproximar la cota media de la tasa de fallos de página. Consiste en seleccionar una página al azar.
Dado que su implementación es trivial, cualquier algoritmo que dé resultados similares a este será un mal criterio, pues seguro que su eficiencia será menor que la de no implementar ningún criterio y 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. Es una aproximación implementable en la práctica del criterio MAX, pudiendo así compararlo con otros criterios. Según el principio de localidad, mientras más recientemente se haya accedido a una página, más probable es que vuelva a accederse a ella. Por ello, este criterio es muy deficiente, siendo su curva cercana a la pésima:
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.
El inconveniente de este criterio es que las páginas más usadas son las que más tiempo deberían permanecer en memoria, y son las más atacadas. No se debe suponer que, si las páginas “dejarán de ser necesarias”, implica que “ya no sean necesarias”. Además, se produce la anomalía de Belady, efecto que consiste en la posibilidad de tener más fallos de página al aumentar el número de marcos en la memoria física:
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, el bit R se pondrá a 1 ante cualquier tipo de acceso, y el bit M se pondrá a 1 sólo ante eventos de escritura.
Para seleccionar la página víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:
- 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 combinación de los criterios FIFO y NRU, pero sin emplear el bit M de NRU. Cuando hay que seleccionar una página víctima, se recorre la lista de páginas por orden de carga en memoria hasta encontrar alguna que tenga el bit R a 0. Durante la iteración, si se encuentra una cuyo bit R valga 1, se pone a 0, se retira de la lista y se añade al final (para darle una segunda oportunidad). Cuando se añade una nueva página, se añade al final de la cola con el bit R a 1. Añadir que, en este caso, no se pone el bit R a 0 periódicamente, ya que se hace directamente con la 2ª oportunidad.
- Criterio del reloj
- Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente de la última página víctima seleccionada, de manera que, para dar la 2ª oportunidad a una página, sólo hemos de poner su bit R a 0 y pasar al siguiente.
Criterio de la 3ª oportunidad (Método Multics)
Es otra variante del criterio NRU, en la que se mantiene una lista ordenada por orden de carga. Ante una sustitución, la primera candidata es la más antigua.
Si dicha página tiene el bit R a 1, se pone a 0.
Si dicha página tiene el bit R a 0, existen dos casos:
- Si tiene el bit M a 1, se pone a 0.
- Si tiene el bit M a 0, se selecciona como página víctima.
Criterio LRU (Least Recently Used)
Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el orden de acceso a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.
Criterio LFU (Least Frecuently Used)
Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero. Es inviable en la práctica, pues supone mantener contadores de tamaños muy grande, uno por cada página en memoria, y por cada acceso a memoria podría ser necesario ejecutar una rutina que actualice la lista.
Aproximación discreta LRU
Se tiene un bit R y un contador por cada página. Cuando una página es cargada a un marco, se carga con su bit R a 1 y su contador inicial a 0. Cuando pasa un período determinado de tiempo (viene dado en el enunciado) se itera sobre toda la lista de páginas, y pueden ocurrir dos cosas:
- Si su bit R está a 1: Se ponen su bit R a cero y su contador se incrementa.
- Si su bit R está a 0: No se hace nada.
Cuando hay que seleccionar una página víctima, se escoge aquella cuyo contador sea más pequeño. En caso de empate, habrá que establecer un criterio de desempate.
Sustitución por envejecimiento
Se emplea un registro R de N bits, asociado a cada página. Por cada acceso se pone a 1 el bit más significativo. Periódicamente se desplaza hacia la derecha el registro R. La página víctima será la que tenga el menor valor en el registro R (en caso de empate se emplea otro criterio). La información que contienen los bits menos significativos se pierden al realizar desplazamientos. Este criterio permite mantener un historial de acceso a las páginas, para seleccionar como víctima aquella que lleve más tiempo sin ser accedida.
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)
