Revisión del 17:09 21 dic 2011

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, serviría para aproximar la cota media de la tasa de fallos de página. 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 víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:

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 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.

• Solución

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 a la última página víctima seleccionada.

• Solución

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.

• Solución

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.

• Solución

Aproximación discreta LRU

Se tiene un bit R y un contador por cada marco. 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 y su contador se incrementa.
• Si su bit R está a 0: Se incrementa el contador una unidad.

Cuando hay que seleccionar una página víctima, se escoge aquella cuyo contador sea mayor. En caso de empate, habrá que establecer un criterio de desempate.

• Solución

Sustitución por envejecimiento

Se emplea un registro R de N bits. 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.

• 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)