Políticas de reemplazo de páginas

Cuando se presenta una falla de página, el sistema operativo tiene que escoger la página que desalojará de la memoria para hacer espacio y colocar la página que traerá del disco. Si la página a desalojar fue modificada mientras estaba en la memoria, deberá reescribirse en el disco para actualizar la copia.

En cambio, si la página no se ha modificado no será necesario reescribirla. La nueva página sobrescribe la que está desalojando. Aunque es posible escoger una página al azar para desalojarla cuando existe una falla de página, el desempeño del sistema mejora mucho si se escoge una página que no se usa con frecuencia. Si se desaloja una página muy utilizada, lo más seguro es que pronto se tenga que volver a traer a la memoria, con el consiguiente gasto extra. Entre las políticas de los algoritmos de reemplazo que se han considerado se incluyen los siguientes:

1. Óptima.

2. Usada menos recientemente (LRU, Least Recently Used).

3. Primera en entrar, primera en salir (FIFO).

4. Reloj.42

1. La política óptima “selecciona para reemplazar la página que tiene que esperar una mayor cantidad de tiempo hasta que se produzca la referencia siguiente”. Este algoritmo es imposible de implementar, ya que requiere que el sistema operativo tenga un conocimiento exacto de los sucesos futuros. Sin embargo sirve como un estándar para comparar otros algoritmos.

2. La política usada menos recientemente (LRU) “reemplaza la página de memoria que no ha sido referenciada desde hace más tiempo. Debido al principio de cercanía, esta debería ser la página con menor probabilidad de ser referenciada en un futuro cercano”, el problema de esta política es su método de implementación. “Una solución sería etiquetar cada página con el momento de su
última referencia”43; esto tendría que hacerse con cada referencia a la memoria, tanto para instrucciones como datos. Incluso si el hardware respaldara este esquema, la sobrecarga sería muy fuerte.

3. La política de primera en entrar primero en salir (FIFO) “trata los marcos asignados a un proceso como un buffer circular y las páginas se suprimen de la memoria según la técnica de turno rotatorio (round-robin)”. Todo lo que se requiere es un apuntador que circule a través de los marcos del proceso. Esta es una de las políticas de reemplazo más sencillas de implementar, ya que su lógica es sencilla y consiste en reemplazar la página que ha estado más tiempo en la memoria.

4. La política de reloj es aquella que requiere “asociar un bit adicional a cada marco, denominado bit de uso. Cuando se carga una página por primera vez en un marco de memoria, el bit de uso de dicho marco se pone en cero. Cuando se hace referencia a la página posteriormente (después de la referencia que genero la falla en la página), el bit de uso se pone en 1”.44 El algoritmo de reloj puede hacerse más potente incrementando el número de bits empleados.

En todos los procesadores que ofrecen paginación se asocia un bit de modificación con cada página en la memoria principal y, por lo tanto con cada marco. Este bit es necesario para que, cuando se modifique una página, no se reemplace hasta volverla a escribir en la memoria secundaria.

Fuente: Apuntes de la materia Sistemas Operativos Multiusuario de la FCA – UNAM