Estrategias Avanzadas de Sustitución de Páginas y Gestión de Fragmentación en Sistemas Operativos

Sustitución de Páginas Basada en Contadores

Podemos mantener un contador del número de referencias que se hayan hecho a cada página y desarrollar los siguientes esquemas:

• Algoritmo de Sustitución LFU (Least Frequently Used)

  El algoritmo de sustitución de páginas LFU (Least Frequently Used) requiere sustituir la página que tenga el valor más pequeño de contador. La razón para esta selección es que las páginas más activamente utilizadas deben tener un valor grande en el contador de referencias.

  Sin embargo, puede surgir un problema cuando una página se utiliza con gran frecuencia durante la fase inicial de un proceso y luego ya no se la vuelve a utilizar. Como se la emplea con gran frecuencia, tendrá un valor de contador grande y permanecerá en memoria a pesar de que ya no sea necesaria. Una solución consiste en desplazar una posición a la derecha los contenidos del contador (reduciendo su peso histórico).

• Algoritmo de Sustitución MFU (Most Frequently Used)

  El algoritmo de sustitución de páginas MFU (Most Frequently Used) se basa en el argumento de que la página que tenga el valor de contador más pequeño acaba probablemente de ser cargada en memoria y todavía tiene que ser utilizada (es decir, se asume que las páginas recién cargadas tienen un alto potencial de uso futuro).

Funcionamiento de los Algoritmos de Búfer de Páginas (Page-Buffering)

Los sistemas suelen mantener un conjunto compartido de marcos libres. Cuando se produce un fallo de página, se selecciona un marco víctima. Sin embargo, la página deseada se lee en un marco libre extraído de ese conjunto compartido, antes de escribir en disco la víctima. Este procedimiento permite que el proceso se reinicie lo antes posible, sin tener que esperar a que se descargue la página víctima. Cuando la víctima se descarga por fin, su marco se añade al conjunto compartido de marcos libres.

Ampliación 1: Gestión de Páginas Modificadas

Una posible ampliación consiste en mantener una lista de páginas modificadas. Cada vez que el dispositivo de paginación está inactivo, se selecciona una página modificada y se la escribe en el disco, desactivando su bit de modificación. Esto incrementa la probabilidad de que una página esté limpia en el momento de seleccionarla para sustitución, con lo que no será necesario descargarla.

Ampliación 2: Reutilización de Marcos Libres

Otra modificación consiste en mantener un conjunto compartido de marcos libres, pero recordando qué página estaba almacenada en cada marco. Puesto que el contenido de un marco no se modifica después de escribir el marco en el disco, la página antigua puede reutilizarse directamente a partir del conjunto compartido de marcos libres en caso de que fuera necesaria y si dicho marco todavía no ha sido reutilizado. En este caso, no sería necesaria ninguna operación de E/S. Cuando se produce un fallo de página, primero comprobamos si la página deseada se encuentra en el conjunto compartido de marcos libres. Si no está allí, deberemos seleccionar un marco libre y cargar en él la página deseada.

Fragmentación de Memoria

Fragmentación Externa

A medida que se cargan procesos en memoria y se los elimina, el espacio de memoria libre se descompone en una serie de fragmentos de pequeño tamaño. El problema de la fragmentación externa aparece cuando hay un espacio de memoria total suficiente como para satisfacer la solicitud, pero esos espacios disponibles no son contiguos.

Fragmentación Interna

La fragmentación interna consiste en descomponer la memoria física en bloques de tamaño fijo y asignar la memoria en unidades basadas en el tamaño de bloque. La memoria asignada a un proceso puede ser ligeramente superior a la memoria solicitada. La diferencia entre los dos valores será la fragmentación interna, es decir, la memoria que es interna a una partición pero que no está siendo utilizada.