El principal objetivo de un algoritmo de reemplazo es retener aquellos bloques que se requerirán en un futuro cercano desplazando aquellos que ya no son útiles y aquellos cuyas próximas referencias se encuentran en el futuro más distante. Prácticamente todos los computadores usan el algoritmo LRU (Least Recently Used) para el manejo de los bloques en la memoria cache; las otras alternativas dignas de ser consideradas son FIFO (First Input First Output) y Random.
Óptimo
Este algoritmo tiene como finalidad retirar la página que vaya a ser referenciada más tarde, por ejemplo si hay una página A que será usada dentro de 10000 instrucciones, y una página B que será usada dentro de 2800 instrucciones, se debería eliminar de la memoria la página A. Como se puede deducir, para esto el sistema operativo debería ver en cuánto tiempo será usada cada página en memoria y elegir la que está más distante. El problema de este método es que necesita conocimiento del futuro, por lo que es imposible su implementación. Es un algoritmo teórico. Se utiliza a los efectos comparativos con los algoritmos factibles de ser implementados para ver cuál se aproxima más a éste.
Segunda oportunidad
Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor que que el fifo. En este caso cuando una página debe ser sacada se toma la primera en la cola, y en vez de sacarla, consulta el valor de un bites de referencia. En caso de estar fijado (en 001) se cambia el bites a 99 y se lo coloca al final de la obstrucción, autorizando su tiempo de carga como si recién hubiera llegado al procesador. De esta forma, se le da una segunda oportunidad. Si el bites se encuentra sin fijar(en 99 ), la página se saca de memoria. Cada vez que la M.U.U accede a una página, fija su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por hardware.
Reloj
Existe una variante de este algoritmo que sobre la misma idea presenta una mejora en la implementación. Es el algoritmo del reloj, que lo que hace es tener una lista circular, de forma que al llegar al último elemento de la lista, pasa automáticamente al primero. Los elementos no se mueven al final de la cola cuando son accedidos, simplemente se pone su bit de referencia a 1. Esto nos evita tener que hacer movimientos de punteros en el caso de implementarlo con una lista enlazada. De hecho, se puede implementar con un array perfectamente, ahorrando así memoria.
No usada recientemente (Not Recently Used, NRU)
Este algoritmo favorece a las páginas que fueron usadas recientemente. Funciona de la siguiente manera: cuando una página es referenciada, fija el bit de referencia para esa página. Similarmente, cuando una página es modificada, fija su bit de modificación. Usualmente estas operaciones son realizadas por el hardware, aunque puede hacerse también por software. En un tiempo fijo, el sistema operativo pone en 0 los bits de referencia de todas las páginas, de modo que las páginas con su bit de referencia en 1 son las que fueron referenciadas dentro del último intervalo de reloj. Cuando una página debe ser reemplazada, el sistema operativo divide las páginas en cuatro categorías:
- Categoría 0: no referenciada, no modificada
- Categoría 1: no referenciada, modificada
- Categoría 2: referenciada, no modificada
- Categoría 3: referenciada, modificada
Las mejores páginas para cambiar son las que se encuentran en la categoría 0, mientras que las peores son las de la categoría 3. Se desaloja al azar una página de la categoría más baja que no esté vacía. Este algoritmo se basa en la suposición de que es mejor desalojar una página modificada a la que no se ha hecho referencia en al menos un tic de reloj, en vez de una página limpia que se está usando mucho.
Algoritmo Random:
Un bloque bi es elegido al azar entre bloques que forman el conjunto en el cual se ha producido un desacierto. Esta política es contraria al principio de localidad por lo cual no es recomendada; sin embargo, algunos resultados de simulaciones indican que al utilizar el algoritmo Random se obtienen razones de acierto superiores a los algoritmos FIFO y LRU.8 Posee las ventajas de que por un lado su implementación requiere un mínimo de hardware y no es necesario por otro lado almacenar información alguna para cada bloque.
Algoritmo FIFO:
En este caso los bloques dentro del conjunto están ordenados de acuerdo a la secuencia con que son cargados. Cuando se debe reemplazar un bloque se elimina de la memoria cache aquel que fue cargado en primer lugar; los bloques siguientes son removidos en el mismo orden. El principal problema del algoritmo FIFO se presenta cuando un bloque es
requerido repetidamente, para ejemplificar esta situación, consideremos un conjunto formado por cuatro bloques y la siguiente secuencia de bloques que son requeridos sobre ese conjunto:
a b a d g a f d g a f c a h a
Después de 5 referencias (y 4 desaciertos) los bloques que constituyen el conjunto son (a, b, d, g). La sexta referencia “ a ” es satisfecha por la memoria cache. En la séptima referencia “ f ” se produce un desacierto y un bloque del conjunto debe eliminarse; el algoritmo FIFO elimina el bloque “ a “ (el primero que entró) y deja dentro el bloque “ b “ que no es usado más, contraviniendo el principio básico de un algoritmo de reemplazo.
Una variación del algoritmo FIFO, conocida como "Clock” o FINUFO (First In Not Used First Out), soluciona el problema de reemplazar un bloque frecuentemente usado y consiste en agregar por un lado un bit de ‘uso’, que es puesto en '1' cuando un bloque es usado con posterioridad a su carga inicial. Adicionalmente los bloques dentro del conjunto se ordenan en forma de una cola circular con un puntero que apunta al bloque que será reemplazado. Al producirse un desacierto se examina el bit de uso del bloque apuntado por el puntero. Si está en '0' se reemplaza ese bloque; si está en uno, se borra el bit de uso y se avanza el puntero una posición continuando este procedimiento hasta encontrar un bloque cuyo bit de uso esté en '0'.
Algoritmo LRU:
El algoritmo más usado es el algoritmo LRU. Tiene la ventaja de que luego de cada referencia, se actualiza una lista que indica cuan reciente fue la última referencia a un bloque determinado. Si se produce un desacierto, se reemplaza aquel bloque cuya última referencia se ha producido en el pasado más lejano, diversas simulaciones indican que las mejores razones de acierto se producen aplicando este algoritmo.
