SO Microprocesamiento

Algoritmos de reemplazo de páginas: segunda oportunidad, reloj y menos usadas recientemente (LRU)

Ejercicio 1: Breve historia del algoritmo (1.0)

Autores, universidad o entidad donde se creó, fecha…

Los algoritmos de reemplazo de páginas eran un tema candente de investigación y debate en los años 1960 y 1970. Se desarrollaron sofisticadas aproximaciones LRU (Least Recently Used) y algoritmos de ajuste de trabajo. En particular, las siguientes tendencias en el comportamiento de hardware subyacente y del software a nivel de usuario han afectado el rendimiento de los algoritmos de sustitución de páginas :

• El tamaño de almacenamiento primario ha aumentado en varios órdenes de magnitud. Con varios gigabytes de memoria principal, los algoritmos que requieren una revisión periódica.

• Las jerarquías de memoria han crecido más. El costo de un error de caché de CPU es mucho más caro.

• La localidad de referencia de software de usuario se ha debilitado. Esto se atribuye principalmente a la difusión de las técnicas de programación orientada a objetos que favorecen a un gran número de pequeñas funciones.

Ejercicio 2: Características (1.5)

Enumerar las características más relevantes del algoritmo y explicar en qué consiste cada una.

Algoritmo de reemplazo de páginas: segunda oportunidad

1. Es básicamente un FIFO en el que además se tiene en cuenta el bit de referencia.

2. Implementación muy sencilla: cola circular con las paginas en la que se almacena también el bit de referencia.

3. Cuando hay que reemplazar se mira el índice que indica la página siguiente a reemplazar; Si el bit de referencia esta a 0 se reemplaza, Si el bit de referencia esta a 1, se pone a 0 y se avanza el índice a la siguiente.

Algoritmo de reemplazo de páginas: reloj

1. La manecilla apunta a la página más antigua.

2. Cuando ocurre un fallo de página, la página a la que apunta la manecilla se inspecciona.

3. R (bit de referencia) = 0: Desaloja la página.

4. R = 1: Desactiva R y avanza la manecilla.

Algoritmo de reemplazo de páginas: menos usadas recientemente (LRU)

1. Reemplaza la página menos usada recientemente (Least Recently Used).

2. Es como el óptimo pero con la cadena de referencias invertida en el tiempo.

3. Produce buenos resultados puesto que por el principio de localidad temporal, paginas referenciadas recientemente es probable que sean referenciadas próximamente.

4. Se adapta muy bien a la localidad del programa.

5. Dos posibles implementaciones:

• Contadores: Se asocia a cada página un contador que representa el instante en que fue referenciada, pudiendo determinar la que hace más tiempo que no se referencia por el valor del contador.

...