c




  



En sistemas operativos que utilizan paginación para el manejo de memoria, los

algoritmos de reemplazo de páginas son usados para decidir qué páginas pueden
ser sacadas de memoria cuando se necesita cargar una nueva y ya no hay
espacio.



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.






 

En este método el sistema operativo sólo tiene que guardar en qué orden las
páginas fueron cargadas, de modo que al necesitar hacer espacio pueda
fácilmente elegir la primera página cargada. Se usa una cola, al cargar una página
nueva se ingresa en el último lugar. Aunque las colas FIFO son simples e
intuitivas, no se comportan de manera aceptable en la aplicación práctica, por lo
que es raro su uso en su forma simple. Uno de los problemas que presentan es la
llamada Anomalía FIFO o Anomalía de Belady. Belady encontró ejemplos en los
que un sistema con un número de marcos de páginas igual a tres tenía menos
fallos de páginas que un sistema con cuatro marcos de páginas. El problema
consiste en que podemos quitar de memoria una página de memoria muy usada,
sólo porque es la más antigua.



   

Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor 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 bit de referencia. En caso de
estar fijado (en 001) se cambia el bit 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 bit se encuentra sin fijar(en 99
), la página se saca de memoria. Cada vez que la MMU accede a una página, fija
su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por
hardware.

±


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.

 




±

 
±

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.

 





±

 
±

Este algoritmo difiere del de 'No usada recientemente' en el hecho de que aquel
sólo se fija en el intervalo de tiempo desde que se pusieron en 0 los bits de
referencia de las páginas, mientras que el algoritmo de 'Menos usada
recientemente' intenta proveer un comportamiento casi óptimo mediante la
observación de las páginas que menos fueron usadas recientemente. Este tipo de
páginas, estadísticamente son las que tienen menor probabilidad de ser usadas
nuevamente.

Aunque este algoritmo provee un buen comportamiento en teoría, es caro de

implementar, en cuanto a recursos consumidos. Hay varias implementaciones que
intentan mantener bajo el costo y lograr un rendimiento considerable. Un método
consiste en tener una lista enlazada y ordenada de todas las páginas en memoria.
En el final de la lista está la página menos usada recientemente, y al principio la
más usada recientemente. El costo alto de este método es porque cada vez que
se referencia una página debe ser movida en la lista, algo que consume mucho
tiempo. Otra forma, que requiere soporte de hardware, consiste en tener un
contador que es incrementado en cada instrucción del CPU. Cada vez que una
página es accedida, gana el número del contador en ese momento. Cuando una
página debe ser retirada de memoria, simplemente hay que buscar cuál es la que
tiene el menor número, que es la que fue usada hace más tiempo. En el presente
no existen contadores tan grandes para permitir esto. Debido al alto costo del
LRU, se proponen algoritmos similares, pero que permiten implementaciones
menos costosas, como los que siguen.


 c



Este algoritmo es un descendiente del algoritmo "No usada frecuentemente", con

algunas modificaciones necesarias para tener en cuenta en qué momento fue
usada frecuentemente una página, y no solamente cuántas veces fue
referenciada.

En vez de sólo incrementar el contador de la página cuando es referenciada,

primero se desplaza a la derecha (se divide por 2) y después sí se suma 1. Por
ejemplo, si los bits de referencia de una página fueron 1, 0, 0, 1, 1 y 0 en los
últimos 6 ticks del reloj, el contador se verá así: 10000000, 01000000, 00100000,
10010000, 11001000, 01100100.

De esta forma, cuando se necesite eliminar una página de memoria, se eliminará

la que tenga el número más pequeño en su contador.

Este algoritmo provee una buena aproximación al desempeño del algoritmo

óptimo, por un módico precio.
 !c"

Algoritmos de reemplazo de páginas

En un sistema operativo que utiliza paginación para manejar la memoria, los
algoritmos de reemplazo de páginas se utilizan para decidir que páginas se
sacarán de la memoria cuando se necesita cargar una nueva y no hay más
espacio.

Óptimo
Para obtener un rendimiento óptimo, la página que se debe reemplazar es aquella
que tardará más tiempo en ser utilizada. Este algoritmo es el mejor de todos pero
es imposible de realizar en la práctica. Es muy teórico.

Primera en entrar, primera en salir (FIFO, First In, FirstOut)

Este algoritmo es el más sencillo de todos. Sustituye la página que lleva más
tiempo en memoria mediante el uso de colas. Es un algoritmo sencillo de entender
e implementar, pero tiene sus inconvenientes como la aparición de la Anomalía de
Belady que es un aumento del número de fallos de página al aumentar el número
de marcos

Segunda oportunidad
Es una modificación del algoritmo FIFO hecha para que tenga un mejor
funcionamiento. Cuando una página ha sido seleccionada para reemplazo, se
revisa el bit de referencia

Reloj
Este algoritmo organiza las páginas en una lista circular, al llegar el último
elemento de la lista, esta pasa al primero
No usada recientemente (NotRecentlyUsed, NRU)

Favorece a las páginas que fueron usadas recientemente. Funciona así: cuando
una página es referenciada, esta guarda un bit de referencia, y cuando es
modificada guarda un bit de modificación. Estas operaciones las realiza el
hardware, pero también pueden hacerse por software. 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.

Menos usada recientemente (LeastRecentlyUsed, LRU)

Es contrario al de 'No usada recientemente'. Consiste en reemplazar aquella
página que no haya sido referenciada en el mayor periodo de tiempo. La idea es
que las páginas que no se han referenciado en un buen periodo de tiempo
difícilmente serán referenciadas en un tiempo cercano. Este algoritmo provee un
buen comportamiento en teoría, pero es caro de implementar, en cuanto a
recursos consumidos.

Ejemplos (Aging)
Modificación del algoritmo "No usada frecuentemente", para tener en cuenta en
qué momento fue usada frecuentemente una página, y no solamente cuántas
veces fue referenciada.Este algoritmo provee una buena aproximación al
desempeño del algoritmo óptimo, por un módico precio.