Aproximaciones a LRU

1. Por qué LRU exacto no es implementable

En el tema anterior (tema 37) viste que LRU necesita una lista doblemente enlazada y una tabla hash para saber, en todo momento, cuál es la página que no se usa desde hace más tiempo. Esa estructura hay que actualizarla en cada acceso a memoria. Ese es el problema: entre dos instrucciones cualesquiera, cualquier lectura o escritura puede cambiar el orden de uso, y el sistema operativo tendría que enterarse de todas.

El hardware actual no lo hace. La MMU traduce direcciones a gran velocidad precisamente porque no mantiene estructuras ordenadas: solo consulta la entrada de la tabla de páginas (tema 20). Registrar el orden exacto obligaría a tocar una estructura global en cada acceso, a coordinar varios procesadores sobre ella y a invalidar traducciones en la TLB (tema 24). Demasiado caro para un mecanismo que debe ser casi invisible.

Los sistemas reales hacen un trueque inteligente: aceptan no conocer el orden exacto y usan uno o dos bits por página que el hardware actualiza solo, gratis, en la propia entrada de la tabla de páginas. Con esa información vaga pero barata, el sistema estima qué páginas se usaron recientemente. Es la misma idea de LRU, con menos precisión y muchísimo menos costo.

Aproximación a LRU es cualquier algoritmo de reemplazo que estima qué páginas se usaron recientemente a partir de bits que el hardware mantiene sin costo (referencia y escritura), en lugar de registrar el orden exacto de cada acceso.

2. El bit de referencia

Cada entrada de la tabla de páginas tiene, además de la dirección del marco y los permisos, dos bits que el hardware actualiza automáticamente:

• El bit de referencia (R, referenced; en x86 se llama accessed): la MMU lo pone en 1 cuando la página se lee o se escribe.
• El bit de escritura (M, modified; también dirty): la MMU lo pone en 1 cuando la página se modifica.

El sistema operativo puede leer estos bits y también limpiarlos. Esa es la clave de la aproximación: el núcleo limpia periódicamente todos los bits R (por ejemplo, en cada tick del temporizador) y a partir de ese momento un bit en 1 significa «esta página se usó desde la última limpieza». Con ese dato ya puede decidir a quién dar otra oportunidad.

Limpiar los bits también tiene un costo: si un bit se limpia en una entrada que está copiada en la TLB, esa traducción debe invalidarse para que el hardware no siga usando el valor viejo. Por eso los núcleos reales no limpian bit por bit en cada acceso, sino en tandas, cuando hace falta una estimación fresca.

3. La segunda oportunidad

La segunda oportunidad (second chance) toma a FIFO (tema 35) y le agrega el bit R. La estructura sigue siendo una cola por orden de llegada, pero antes de reemplazar se mira el bit de la víctima más antigua:

1. Mirar la página del frente de la cola: es la más antigua, la candidata natural de FIFO.
2. Si su bit R es 1: se usó desde la última limpieza, así que es «más nueva» de lo que su edad sugiere. Se limpia su bit y se la envía al final de la cola, como si acabara de llegar.
3. Si su bit R es 0: no se usó recientemente. Es la víctima y se reemplaza.
4. Repetir hasta encontrar una página con R = 0.

Segunda oportunidad es la variante de FIFO que, antes de reemplazar la página más antigua, comprueba su bit de referencia: si está en 1, lo limpia y la manda al final de la cola para darle otra oportunidad.

El nombre describe la mecánica: una página que se usó no se sacrifica de inmediato, sino que recibe una segunda ronda. El defecto conocido es que si todas las páginas tienen R = 1, la mano limpia todos los bits, da una vuelta completa y termina reemplazando a la más antigua: en ese caso, degenera exactamente en FIFO y paga una vuelta entera por cada fallo.

4. El algoritmo del reloj

Mover páginas al final de una cola en cada limpieza es trabajo innecesario. La misma idea se implementa mejor con una lista circular y un puntero, la mano del reloj: el puntero recorre los marcos como la aguja de un reloj sobre su esfera. Cuando hay un fallo de página:

1. La mano examina el marco al que apunta.
2. Si el bit R es 1: lo limpia y avanza al marco siguiente. La página acaba de recibir su segunda oportunidad.
3. Si el bit R es 0: reemplaza esa página ahí mismo y avanza la mano al marco siguiente, que queda apuntado como próxima víctima.

Muchos textos usan «segunda oportunidad» y «reloj» como sinónimos: es el mismo criterio con dos implementaciones. La cola mueve páginas; la mano solo se mueve a sí misma. El costo por fallo es O(1) amortizado y solo se necesita un bit extra por marco: por eso el reloj es la aproximación más usada en sistemas operativos reales.

Veamos cómo se comporta en la cadena que ya conoces (1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 con 3 marcos):

En esta cadena el reloj empata con FIFO y hasta queda por delante del LRU exacto (10 fallos): es una cadena particularmente adversa para LRU. La lección no es que el reloj sea peor que LRU, sino que logra un comportamiento razonable con un bit y un puntero, es decir, con lo único que el hardware regala.

5. NRU y el reloj mejorado

Otra aproximación clásica es NRU (Not Recently Used, «no usada recientemente»). Combina los dos bits en una clasificación de cuatro clases y, ante un fallo, elige la víctima de la clase más baja que no esté vacía:

Dentro de una clase NRU elige una página al azar, porque no distingue cuál se usó más recientemente: es más grueso que LRU, pero baratísimo. Los bits R se limpian periódicamente, así que «no usada» siempre significa «no usada en la última ventana de tiempo».

El reloj mejorado (enhanced second chance) reemplaza el azar por la mano del reloj con una prioridad entre clases. En cada fallo, la mano busca en este orden: (0, 0) → (0, 1) → (1, 0) → (1, 1). Durante el recorrido limpia los bits R que va encontrando, de modo que una página del grupo (1, 0) pasa a ser candidata (0, 0) si la mano vuelve a pasar. En el peor caso da tres vueltas. La ventaja es evidente: preferir (0, 0) y (0, 1) sobre (1, 0) y (1, 1) elige páginas no usadas, y entre las no usadas prefiere las limpias, que se descartan sin escribir nada al disco.

6. Envejecimiento (aging)

Con un solo bit apenas se distingue «usada en la última ventana». El envejecimiento guarda más historia con un contador por página —por ejemplo, de 8 bits— y en cada tick del temporizador hace dos cosas:

1. Desplaza el contador un bit a la derecha, para que las referencias antiguas pierdan peso.
2. Inserta el bit R actual en el bit más significativo, para que la referencia más nueva sea la que más pesa.

Al reemplazar, la víctima es la página con el contador más bajo: en él se acumula un historial ponderado, donde lo reciente vale más que lo viejo. Cuantos más bits tenga el contador, mejor aproxima LRU. Con cuatro páginas y contadores de 8 bits se ve así:

Al final del tick 4, A no se toca desde el tick 2, B desde el 3, y C y D se usaron en el 4. Mirando los contadores: A = 00110000, B = 01100000, C = 10010000 y D = 10100000. El menor es el de A, así que A es la próxima víctima: exactamente lo que elegiría LRU. Con más bits por contador, el historial es más largo y la estimación más fina.

El costo del envejecimiento es mayor que el del reloj: hay que mantener un contador por página y recorrerlos todos en cada tick. Por eso se usa sobre todo en simulación y en sistemas que pueden dedicarle ese trabajo; la idea de ponderar el pasado reciente, en cambio, está en el corazón de las listas LRU que usa Linux (lo verás en la sección 10).

7. Ejemplo paso a paso

Cadena: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Marcos: 3. Algoritmo: reloj (segunda oportunidad), con la mano empezando en el marco 0 y todos los bits R en 0. Los bits se muestran entre corchetes en el orden de los marcos, y la mano, con su índice.

Total: 9 fallos de 12 accesos. Observa el patrón: cada vez que todas las páginas tienen R = 1 (accesos 4, 7 y 10), la mano limpia los tres bits y reemplaza la más antigua, igual que FIFO. Cuando hay páginas sin usar, en cambio, el reloj acierta al elegir una de ellas.

8. Implementación en C

El programa siguiente implementa el reloj con un arreglo de páginas, otro de bits R y un índice para la mano:

#include <stdio.h>

int main(void)
{
    int marcos = 3;
    int seq[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int nseq = 12;
    int pagina[16], ref[16];
    int usados = 0, mano = 0, fallos = 0;

    for (int i = 0; i < nseq; i++) {
        int p = seq[i], found = 0, pos = -1;
        for (int j = 0; j < usados; j++)
            if (pagina[j] == p) { found = 1; pos = j; break; }

        if (found) {
            ref[pos] = 1;                  /* se usó: otra oportunidad */
            printf("pág %d: HIT\n", p);
        } else {
            fallos++;
            if (usados < marcos) {
                pagina[usados] = p; ref[usados] = 1; usados++;
                printf("pág %d: MISS (marco libre)\n", p);
            } else {
                while (ref[mano] == 1) {   /* la mano da segunda oportunidad */
                    ref[mano] = 0;
                    mano = (mano + 1) % marcos;
                }
                printf("pág %d: MISS (reemplaza %d)\n", p, pagina[mano]);
                pagina[mano] = p;
                ref[mano] = 1;
                mano = (mano + 1) % marcos;
            }
        }
    }
    printf("\nFallos: %d de %d (%.1f%%)\n", fallos, nseq, 100.0 * fallos / nseq);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o reloj reloj.c
$ ./reloj
pág 1: MISS (marco libre)
pág 2: MISS (marco libre)
pág 3: MISS (marco libre)
pág 4: MISS (reemplaza 1)
pág 1: MISS (reemplaza 2)
pág 2: MISS (reemplaza 3)
pág 5: MISS (reemplaza 4)
pág 1: HIT
pág 2: HIT
pág 3: MISS (reemplaza 1)
pág 4: MISS (reemplaza 2)
pág 5: HIT

Fallos: 9 de 12 (75,0%)

9. Probar con un simulador

Este simulador ejecuta el reloj sobre una cadena de referencias, muestra los bits y la mano tras cada acceso, y compara el total de fallos con FIFO y LRU.

10. En Linux

Linux tampoco registra el orden exacto de uso. Su gestor de páginas (el PFRA, Page Frame Reclaim Algorithm) aproxima LRU con dos listas por zona de memoria: active e inactive. Una página que llega a memoria entra a la lista inactive; si vuelve a tocarse mientras está allí, el bit PG_referenced la promueve a active: esa es su segunda oportunidad. Cuando falta memoria, el núcleo desactiva páginas de active, y primero se expulsan las de inactive que nadie volvió a tocar. El resultado es un reloj de dos listas, barato y muy parecido a LRU en la práctica.

$ grep -E 'pgscan|pgsteal|pgactivate|pgdeactivate' /proc/vmstat
pgdeactivate 214563
pgscan_kswapd 918234
pgscan_direct 15872
pgsteal_kswapd 642118
pgsteal_direct 12045
pgactivate 331245
$ grep -E '^(Active|Inactive|MemFree)' /proc/meminfo
MemFree:         1893244 kB
Active:          6234512 kB
Inactive:        2791832 kB

• pgscan y pgsteal cuentan páginas examinadas y expulsadas; el sufijo kswapd es el escaneo de fondo y direct el que hace un proceso cuando la presión es urgente.
• pgactivate y pgdeactivate miden los movimientos entre las listas active e inactive: son la segunda oportunidad en acción.
• En núcleos recientes (6.1 y posteriores) puede estar activo MGLRU, una variante con varias generaciones en lugar de dos listas: se consulta en /sys/kernel/mm/lru_gen/enabled.
• El intercambio con el disco (swap) tiene su propio ajuste, vm.swappiness, que se estudia en el tema 40.

11. Resumen

• LRU exacto es demasiado costoso de implementar: exige registrar el orden de uso en cada acceso.
• El hardware regala dos bits por página: referencia (R) y escritura (M), que el sistema limpia en tandas.
• La segunda oportunidad es FIFO que rescata páginas con R = 1; degenera en FIFO cuando todas lo tienen.
• El reloj implementa lo mismo con una mano circular: O(1) por fallo y un bit por marco.
• NRU clasifica con (R, M) en cuatro clases; el reloj mejorado las recorre en orden y prefiere víctimas limpias.
• El envejecimiento usa un contador por página que desplaza el historial y pesa más lo reciente.
• Linux aproxima LRU con listas active/inactive y el bit PG_referenced como segunda oportunidad.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta reloj.c y compara los fallos con FIFO y LRU para la misma cadena.
2. Prueba la cadena 1, 2, 3, 1, 2, 3, … y observa que casi no hay fallos y la mano casi no limpia bits.
3. Modifica reloj.c para imprimir los bits R de los tres marcos tras cada acceso.
4. Agrega el bit de escritura y prueba el reloj mejorado con el orden (0,0) → (0,1) → (1,0) → (1,1).
5. Implementa el envejecimiento con contadores de 8 bits y verifica a mano la tabla de la sección 6.
6. Explica con tus palabras por qué la segunda oportunidad con todos los bits en 1 se comporta como FIFO.
7. Observa pgscan y pgsteal en /proc/vmstat mientras abres programas que consumen memoria.