Algoritmos de reemplazo de páginas: FIFO, LRU, Working Set y PFF

Reemplazo Aleatorio

Un proceso (pi) es elegido en forma aleatoria de conjunto de trabajo (Ct) cuando se necesita un reemplazo. No hace análisis alguno, válido solo si la aplicación lo alimenta. Para este algoritmo no es necesario hardware extra y el trabajo del Sistema Operativo (SO) es mínimo.

Primero en Entrar, Primero en Salir (FIFO)

Las páginas en Ct son ordenadas de acuerdo al orden de llegada. Cuando se llena Ct, la primera página cargada es la primera en ser reemplazada. No es necesario hardware extra, el SO debe mantener una cola de las páginas cargadas. El overhead de un page fault, que es la inserción y borrado de la cola, es mínimo comparado con el tiempo que toma traer una página de memoria secundaria. Un problema de este es que una página que es referenciada muchas veces puede ser reemplazada con demasiada frecuencia.

Segundo en Entrar, Último en Usar (FINUFO)

Este trata de resolver el problema que tiene el FIFO. Mantenemos una cola FIFO como antes con la adición de un bit de uso y una cola circular. Cuando ocurre un fault nos fijamos en la cola la primera página con el bit de uso apagado. Si no lo está, se apaga y se posiciona en la siguiente en la lista, así hasta encontrar una página que tenga el bit apagado. Para implementar este algoritmo necesitaremos un bit en hardware para cada frame. Este bit es seteado en cada referencia a memoria de este frame. Esto puede ser hecho durante el proceso de mapeo, si el bit es colocado en las tablas de mapeo. Por lo tanto, no habrá un overhead de tiempo y el hardware extra es poco. La función del SO es simple. Si bien toma en consideración si fue o no referenciada, no analiza en qué tiempo.

Última Referenciada en Usarse (LRU)

Podemos lograr esto mediante el uso de una pila, la cual es reordenada en cada referencia. Cuando se referencia una página que se encuentra en memoria, se busca en la pila, se saca, se mueven todas las páginas una posición para abajo y se coloca esta al tope de la pila. Si la página referenciada no se encuentra en la pila, la página del fondo de esta es la elegida para el reemplazo, se elimina de la pila, se mueven todas las restantes una posición hacia abajo y la página traída a memoria se coloca al tope. El algoritmo LRU puro es impráctico, ya que el orden en la pila cambiará con cada referencia a memoria. Cada movimiento en la pila implica un acceso a memoria y el overhead es inaceptable, a menos que la pila sea almacenada en un buffer de memoria rápido. En este caso el corrimiento de la pila puede ser hecho en paralelo con la referencia a memoria.

Reemplazo Óptimo en Particiones Fijas

Es teórico, no practicable dado que se basa en conocer en futuro. Lo que hay que optimizar en general es el producto espacio*tiempo. Como el PMA (Partición de Memoria Asignada) es fijo nuestro factor a optimizar es el tiempo, luego la optimalidad es definida como el mínimo número de page fault. Cuando ocurre un page fault y el Ct está completo, hay que elegir una página para reemplazar, ya que usamos particiones fijas para el Ct. Nos valemos de la información del futuro próximo y elegimos aquella página perteneciente a Ct que sea la última en ser referenciada de las demás en este futuro próximo. Tanto este algoritmo como LRU satisfacen la propiedad stack. Asegura que si aumenta el PMA, con estos algoritmos el mínimo de page fault en un dado instante será menor (o igual) del que se tenía previamente nunca superior, cumplen con el principio de inclusión. Naturalmente esto no es aplicable en tiempo real y es de interés para proveer una medida para los otros algoritmos.

Reemplazo Working Set

Ha tenido el mismo impacto sobre las políticas variables como LRU ha tenido sobre las fijas. Sea T el tamaño de una ventana, o sea, un intervalo (virtual) de tiempo expresado en número de referencias. La página es reemplazada (borrada de MP (Memoria Principal)) en el tiempo t si no pertenece a WS(t, T). Notar que una página no es necesariamente reemplazada en un fallo de página.

Reemplazo por Frecuencia de Fallo de Página (PFF)

Esta regla es un intento de tener una alocación de memoria principal que siga las variaciones en las localidades. Está definida como la recíproca de T´, y monitorea el tiempo de fallo entre páginas (T´ expresado en las mismas unidades que la ventana T del algoritmo WS). En un page fault, si la PFF es más grande que un valor predefinido P, no hay reemplazos y el PMA se aumenta en uno para cargar la página faltante. De otra manera, si la PFF es más chica que P, se descargan todas las páginas no referenciadas desde el último page fault. La principal diferencia entre PFF y WS está en el lugar en que se toman las acciones cuando ocurre un fallo de página, ya que en esencia T representa el límite inferior del tamaño (variable) de la ventana.

Problemas con la Tabla de Páginas

• Muchos recursos de memoria principal empleados por la página de páginas.
• Problema de fragmentación externa a nivel de tabla. En el sentido de que es un área contigua en la cual se indexa con VPN (Número Virtual de Página). Se requiere un espacio contiguo de tamaño suficiente.

Lo primero se maneja permitiendo que la tabla de páginas se encuentre paginada, esto es, parte en memoria y parte en disco. El otro punto queda resuelto organizando la tabla de páginas en forma jerárquica, no en único nivel. Otra solución a los temas planteados es el empleo de una tabla de páginas invertida. De lo que se trata es de englobar en una única estructura la información de todas las páginas, sin distinción de procesos, residentes en memoria. La tabla estará acotada por el tamaño de la memoria principal del sistema y el tamaño de página, no existiendo tampoco el problema de manejar áreas contiguas. Se usa una técnica de almacenamiento a través de una técnica de hash y se realiza una búsqueda en forma asociativa.