Algoritmos de reemplazo de página

De Departamento de Informatica
Saltar a: navegación, buscar

Los Algoritmos de reemplazo de página son aquellos algoritmos de sistemas operativos que están diseñados para solucionar el problema de decidir qué página de las que reside en memoria bajo un frame o marco debe salir para dejar entrar a otra que está siendo referenciada. Al ser los reemplazos de página fundamentales para la paginación bajo demanda, es importante que los sistemas operativos implementen los algoritmos más efectivos. Algunos de los presentados son algoritmos creados para concretizar la idea de reemplazo, otros son ideales pero imposibles o difíciles de implementar y están aquellos que con ciertos costos son perfectamente implementables, pero todo algoritmo debe apuntar a tener la menor cantidad de fallos de página, lo que implica, por ejemplo, la reducción sustancial de I/O a memoria secundaria.

Los algoritmos son evaluados con cadenas de referencias, que son cadenas de números que indican las páginas que son referenciadas. La idea es simular cómo actúan los distintos algoritmos para estas cadenas, de forma tal de conocer su eficiencia.

Contenido

Paginación

Véanse también: Paginación, Paginación por demanda y Fallos de Páginas

Figura 1: Reemplazo de página
Figura 2: Pasos para tratar un fallo de página. El hardware necesario para soportar los mecanismos de paginación e intercambio. Tablas de paginas (bit valido-invalido); memoria secundaria (almacena aquellas paginas que no están presentes en la memoria principal).

La paginación consiste en considerar el espacio de direcciones lógicas de cada proceso como un conjunto de bloques de tamaño consistente llamados páginas. Es un esquema de gestión de memoria que permite que el espacio de direcciones físicas de un proceso no sea contiguo. Ésta divide un programa en pequeñas partes de tamaño fijo llamados páginas y a nivel de memoria, ésta es dividida en pequeños bloques de tamaño fijo llamados marcos o frames de páginas. La paginación evita el considerable problema de encajar fragmentos de memoria de tamaño variable en el almacén de respaldo.

Memoria virtual

Cuando la memoria física de un computador se hace insuficiente, el sistema operativo puede emular una memoria de mayor tamaño que la memoria real, haciendo que parte de los procesos se mantengan en el disco. A este tipo de memoria se le denomina memoria virtual, pues es una memoria inexistente, pero que para cualquier proceso es indistinguible de la memoria real. El mecanismo que implementa la memoria virtual se denomina paginación bajo demanda y consiste en que se lleva al disco las páginas virtuales de un proceso que tienen poca probabilidad de ser referenciadas en el futuro cercano. Un proceso puede continuar corriendo con parte de sus páginas en disco, pero con la condición de no accesar esas páginas. Quien se encarga de realizar una estimación de que paginas que serán utilizadas y cargarlas en memoria es el paginador o pager.

Bit válido-inválido

En el contexto de paginación, el concepto de válido indica que la página está en memoria; mientras que inválido indica que la página no se encuentra en el espacio lógico de direcciones de proceso o es válida pero no esta actualmente en el disco.

Las páginas residentes en disco se marcan en la tabla de páginas del proceso con el bit valido-invalido como invalida (figura 1), de modo que si el proceso las referencia se produce una interrupción de fallo de página. En la rutina de atención de esta interrupción, se cargará en memoria la página que causó la pagina de falla, por lo que el proceso queda suspendido mientras se realiza la lectura del disco. Cuando esta operación concluye, el proceso se retoma en forma transparente sin que perciba la ausencia temporal de esa página. Los pasos para tratar un fallo de pagina están presentes en la figura 2.

La duración de la suspensión del proceso es del orden del tiempo de acceso del disco, es decir entre 8 a 20 milisegundos.

Sustitución de Páginas

Si incrementamos la multiprogramación, estamos sobrecargando nuestra memoria o sobreasignado, lo que puede eventualmente que nos quedemos falta de marcos o frames disponibles para cargar las páginas. En estos casos, la solución mas común es la sustitución de paginas. En este sentido el procedimiento de reemplazo es:

  1. Encontrar la ubicación en disco de la página deseada.
    1. Buscar un marco libre:
    2. si hay un frame o marco libre, utilizarlo.
    3. De lo contrario, utilizar un Algoritmo de Reemplazo de Página con el fin de seleccionar un marco víctima.
    4. Escribir la página víctima en disco; ajustar las tablas de marcos y páginas.
  2. Traer la pagina al nuevo frame libre. Actualizar la tabla de pagina.
  3. Reiniciar el proceso de usuario.

Para implementar cualquier algoritmo que realice la elección del marco víctima (y por supuesto de la página que será enviada a memoria secundaria) se tienen ciertas consideraciones:

  • Para referirnos a una página se habla de su número de página, por ejemplo página 1, p1 o simplemente 1.
  • Por otra parte, siempre que se haya referenciado a una página e inmediatamente se referencie de nuevo, no hay fallo de página.
  • Se debe conocer el número de frames disponibles. A mayor cantidad de marcos, menos fallas de página.

Algoritmo FIFO

El algoritmo FIFO reemplaza las páginas de la forma que el primero que entra es el primero que sale. Asocia a cada página el instante en el que se trajo a la memoria, así cuando se tenga que reemplazar una página, se elige la más antigua.

AlgoritmoFIFO.png


En la imagen vemos 19 páginas entrando en una memoria de tres frames. El resultado obtenido fueron 15 fallos de página.

A pesar de que es un algoritmo fácil de comprender y programar, su rendimiento no siempre es bueno. Un ejemplo claro es cuando la página puede contener una variable cuyo valor inicial se asignó hace tiempo pero que se utiliza constantemente por lo que puede prescindir de páginas que accede con frecuencia.

Anomalía de Belady

Ésta anomalía fue descubierta y demostrada en 1969 por el científico de la computación Laszlo Belady y consiste en que al aumentar el número de marcos en la memoria física, es posible tener más fallos de página. En la siguiente imagen vemos la diferencia, con el mismo orden de páginas, con tres y cuatro marcos en la memoria.

Libro2-page-001.jpg
Comparación con diferente cantidad de marcos y su cantidad de fallas con un algoritmo en específico.

Notamos que con tres marcos solo tiene nueve fallos y que con cuatro marcos tiene diez. Aunque el ejemplo solo trata con pocos marcos, es sorprendente el comportamiento que se podría ver con muchos más. Antes de éste descubrimiento se creia que FIFO era el mejor algoritmo para el manejo de páginas, pero se tuvo que buscar alternativas a causa de esta sorprendente anomalía. Actualmente esta anomalía es más bien utilizada como una simple coriosidad que demuestra que los sistemas pueden tener a veces comportamientos inesperados.

Algoritmo Óptimo

El Algoritmo Óptimo, también conocido como OPT se originó luego del descubrimiento de la Anomalía de Belady en la búsqueda de un algoritmo mucho más óptimo. El algoritmo elige la página de la memoria que vaya a ser referenciada más tarde, las páginas se rotulan con el número de instrucciones que se ejecutarán antes de que se haga la primera referencia a ella y, cuando se presenta un fallo de página, se reemplaza la que más instrucciones falten para referenciarla para así ir aplazando lo más que se pueda los fallos de página. Por desgracia, este algoritmo es irrealizable, ya que no hay una forma de predecir qué páginas referenciará un proceso en el futuro.

Libro3-page-001.jpg

En la imagen vemos la cadena de referencias para una página y cómo se usa la memoria (en este caso de 3 frames o marcos). Se comienza tal como el algoritmo FIFO ingresando las páginas a la memoria; el primer caso de memoria llena sucede cuando entra la página 1 y quiere entrar la página 2. La víctima debe ser decidida de tal forma que la página no sea referenciada mas o sea referenciada mucho después. En este caso la página 5 no es referenciada más, por lo que es reemplazada por la página 2. El algoritmo genera finalmente 7 fallos de página, versus por ejemplo los 10 fallos que FIFO genera.

Como es un algoritmo que no se puede poner en práctica, se ejecuta en simuladores en los cuales se demuestra que es un muy buen algoritmo que reduce mucho las fallas y que se encuentra entre los algoritmos con mejor eficiencia por lo que es el algoritmo utilizado para estudios comparativos.

Algoritmo LRU

La estrategia consiste en llevar a disco la página que ha permanecido por más tiempo sin ser accesada. El fundamento de esta estrategia es que estadísticamente se observa que mientras más tiempo permanece una página sin ser accesada, menos probable es que se accese en el futuro inmediato. Desventaja: El alto costo de implementación en cuanto a los recursos. Pese a ser un buen algoritmo en teoría, su implementación no lo es tanto. Esta puede ser llevada a cabo por una lista enlazada con todas las paginas ordenadas, pero al momento de ser referenciada una pagina esta tiene que cambiar de lugar, lo cual involucra un alto costo asociado. Otro mecanismo es llevar un contador por medio de hardware, el cual es incrementado cada vez que la pagina es accedida.

LRU.png

De acuerdo con el string entregado, podemos apreciar que cuando se llega al numero 3 en el string, el numero al que reemplaza es el 8, ya que fue el ultimo en ser accedido, previo a el esta el 2 y previo a el el 1, de esta manera se continua completando el marco hasta el termino del string++.

*Implementación con Contador. Es asociada a cada tabla de página un campo de tiempo y el CPU lleva un contador o reloj el cual se incrementa en cada referencia a memoria que se realiza. Al momento de realizar el llamado a una página, este contador es copiado en el campo de tiempo que esta en su tabla correspondiente. Temas a tener en cuenta:

  • siempre se tiene la última referencia a cada pagina.
  • Esta implementación hace necesaria la búsqueda en las tablas de página de la página menos utilizada.
  • Se hacen necesario incorporar grandes contadores en el CPU, y tener un cuidado con el probable desbordamiento que pudiera tener.

*Implementación con Pila. Se mantiene una pila, con los números en una lista doblemente enlazada. Con esta modalidad ya no se hace necesario realizar una búsqueda, como lo es con el contador, pero se tiene que realizar el cambio en los punteros de la lista. Para ir estructurando la pila, cada página referenciada se va colocando al tope de ésta.

  • De acuerdo a la figura 3, se presenta una representación de cada cambio en la pila siendo la posición de la izquierda el tope de ésta.
Figura 3: Reemplazo de página

1-[4|_|_|_|_].

2-[7|4|_|_|_].

3-[0|7|4|_|_].

4-[7|0|4|_|_].

5-[1|7|0|4|_].

6-[0|1|7|4|_].

7-[1|0|7|4|_].

8-[2|1|0|7|4].

9-[1|2|0|7|4].

10-[2|1|0|7|4].

11-[7|2|1|0|4].

12-[2|7|1|0|4].

Aproximaciones a LRU

Bit de referencia

Al no existir en todos los computadores soporte de hardware para implementar al costoso LRU, se usan otros algoritmos modificados para acercarse (como por ejemplo modificar FIFO). Otros sistemas intentan dar soporte a LRU con un bit de referencia o bit R, el cual es activado y desactivado por el hardware cuando una página es referenciada, siendo cada bit de referencia asociado con una sola página en la tabla de páginas. Cada bit es iniciado en 0 por el sistema operativo. Cuando hay una referencia el bit es puesto en 1. Luego de un tiempo se puede determinar cuales páginas han sido usadas y cuales no, sin conocer su orden. Ésta implementación es la base para otras aproximaciones a LRU, pues da uso al bit de referencia.

Algoritmo de Segunda Oportunidad

Este es un algoritmo que deriva del algoritmo FIFO. El Algoritmo de Segunda Oportunidad evita deshacerse de una página de uso frecuente, hace uso del bit R inspeccionándolo de tal forma que, si es 0, la página es antigua y no utilizada, por lo que, en caso de fallo de página, es reemplazada de manera inmediata. En caso de que dicho bit sea 1, es cambiado a cero y se cambia al final de la lista de páginas como si hubiera llegado en ese momento a la memoria. Luego continua la búsqueda siguiendo lo que avanza en la lista.

Libro5-page-001.jpg

En la imagen vemos como se ejecuta el algoritmo, las páginas fueron identificadas, a modo de este ejemplo, con letras de la A a la H según el orden de llegada y mostradas en una lista enlazada. A es la primera página cargada y la que con menos frecuencia se ocupa mientras que H es la página más reciente cargada. Supongamos que ocurre un fallo de página. La página más antigua en nuestro ejemplo es A, si éste tiene el bit R a cero, se saca de la memoria. Por el contrario, si R vale 1, A se coloca al final de la lista, poniéndose a cero el bit R. Dejando como búsqueda adecuada de página con B.

Lo principal de este algoritmo de segunda oportunidad es ir viendo las páginas antiguas sin referencias, si es que todas tienen más de una referencia entonces se aplica normalmente el algoritmo FIFO.

Algoritmo NRU

El algoritmo Not Recently Used (NRU), No utilizado recientemente, Enhanced second-chance o Segunda oportunidad mejorado[1] es uno de los esquemas que intentan aproximarse al algoritmo LRU. Específicamente es una modificación del algoritmo de segunda oportunidad, el cual considera el bit de referencia R y el bit de modificación M como un par ordenado (R, M) respectivamente. Existen cuatro clases de páginas descritas por este par que se mencionan a continuación.

  • Clase 0 (0, 0) La página no ha sido ni usada ni modificada recientemente. Ésta página es la mejor candidata a ser reemplazada.
  • Clase 1 (0, 1) La página no ha sido recientemente usada pero sí fue modificada. No es tan buena como la primera opción, pues la página deberá ser escrita antes de ser reemplazada.
  • Clase 2 (1, 0) La página fue recientemente usada y no modificada. El argumento de este algoritmo es que ésta página probablemente vuelva a ser usada.
  • Clase 3 (1, 1) La página fue usada y modificada. Considerando las descripciones anteriores se aprecia que la página podría volver a ser usada y además escrita al disco.

Cuando una página se debe reemplazar, se usa la misma lógica que el algoritmo de reloj, pero en vez de revisar si el bit de referencia de la página es un 1, se examina la clase a la que pertenece la víctima. Dependiendo de la implementación la página (aleatoria o la primera que se encuentre) con la clase más pequeña es reemplazada. Para encontrarla es posible que se deba revisar la cola circular varias veces antes de encontrar la víctima.

Una duda interesante que surge es cómo pueden haber páginas modificadas pero no usadas (clase 1). Esto sucede cuando páginas de clase 3, luego de una interrupción de reloj el bit de referencia es puesto en 0 pero los cambios aún deben ser escritos en disco por lo que el bit de modificación sigue en 1.

La diferencia más grande entre éste algoritmo y el de segunda oportunidad es que en este se da preferencia a aquellas páginas que han sido modificadas, de tal forma de reducir el I/O de disco asociado a éstas. Es un algoritmo eficiente de implementar con rendimiento bueno mas no óptimo, además de que se debe hacer una búsqueda a través de cada par de bits.

Algoritmos basados en conteo

En este caso la idea es mantener un contador del numero de referencias que se han hecho a cada página. Acá se enmarcan dos algoritmos que definen a estos contadores: el LFU centrado en reemplazar las páginas menos usadas y el MFU, que reemplaza las páginas mas usadas.

Algoritmo LFU

El algoritmo Least frequently used (LFU) o Menos frecuentemente utilizado pide que la página con el menor contador sea reemplazada. Esto se justifica en que una página usada con mucha frecuencia tendrá un contador mas grande. Un problema de este esquema es cuando una página es usada intensamente durante la fase inicial de un proceso y luego no vuelve a ser usada, lo cual genera un contador mucho mayor y la página permanece en memoria sin poder ser sacada. Una solución a lo anterior es realizar un corrimiento de 1 bit del contador a intervalos regulares de tiempo de tal forma de nivelar los contadores de forma exponencial y así no habrán páginas estancadas.

AlgoritmoLFU.png

El ejemplo en la imagen muestra una cadena de bits de referencias. Las invocaciones de las páginas figuran con sus respectivos frames y cada uno tiene un contador que indica la cantidad de veces que se ha llamado a una página. Así, páginas cuya frecuencia es la mas baja son reemplazadas por otras, (En este caso la página #3 de frecuencia 1 es reemplazada por la pagina #28). Finalmente se observa el balance entre páginas traídas y páginas retiradas.

Aging

Este algoritmo desciende del NFU, mejorándolo al realizar un corrimiento de 1 bit a la derecha antes de aumentar el contador de uso en 1 bit a la izquierda en su forma binaria. Esto provoca que las páginas cuyas referencias son más actuales tengan más importancia que aquellas que fueron referidas hace tiempo, asegurando que páginas usadas recientemente pero no frecuentemente tengan mayor prioridad frente a páginas usadas hace tiempo pero con mayor referencia. Así la página con el menor contador es elegida para ser reemplazada.

AlgoritmoAging.png

En el ejemplo de la imagen se presentan dos páginas con sus bits de referencia y contadores (en formato binario). La página 1 tiene los bits de referencia 1,1,1,0,0,0 que indican una alta frecuencia de uso pero estos no son actuales; la página 2 tiene bits 0,0,0,0,1,1 lo que indica poca frecuencia de uso pero muy actual. Siguiendo el algoritmo, se toma el contador en binario y se efectúa un corrimiento de 1 bit a la derecha y se le adjunta el bit de referencia a la izquierda, todo esto por cada tick de reloj. Finalmente el contador de la página 1 es 0001110, versus el de la página 2 que es 11000000, reflejando que la página 1 tiene menor importancia que la página 2 pues esta última es mas reciente, por lo que la página 1 eventualmente debe ser reemplazada.

Algoritmo MFU

El algoritmo Most frequently used (MFU) o Mas frecuentemente utilizado, que al contrario del LFU está basado en el argumento de que la página con el menor contador fue probablemente traída hace poco y aún no ha sido usada, por lo que la página con el mayor contador será la «víctima» en este caso.

AlgoritmoMFU.png

El ejemplo en la imagen presenta los frames y contadores para una cadena de referencias dada. En caso de que dos o mas contadores fueran iguales, se reemplaza la página que haya llegado primero. En el ejemplo ocurren 10 reemplazos de página considerando llenar frames vacíos y reemplazos efectivos de página.

Ninguno de estos algoritmos es utilizado comunmente. La implementación que requieren es cara, y no se aproximan lo suficiente al algoritmo óptimo.

Referencias

  1. Algoritmo mencionado en Silberschatz, Abraham (2009) Operating Systems Concepts (Eight Edition). Capítulo 9 «Virtual Memory Management» Sección 9.4.5.3 «Enhanced Second-Chance Algorithm» Página 379

Bibliografía

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas