Reemplazo LRU

1. El algoritmo LRU

LRU reemplaza la página que no se ha usado por más tiempo. La idea es que las páginas que se usaron recientemente probablemente se usarán de nuevo (localidad temporal). Es una aproximación al algoritmo óptimo, que usa el futuro en lugar del pasado.

LRU (Least Recently Used) es el algoritmo de reemplazo que reemplaza la página que no se ha referenciado por más tiempo.

2. Cómo funciona

Para cada acceso a una página:

1. Si la página está en la RAM: acierto (hit). Se actualiza su tiempo de último uso.
2. Si no está (fallo): si hay marco libre, se carga. Si no, se reemplaza la página menos usada recientemente.

El reto es implementar eficientemente el tracking del "último uso" de cada página.

3. Implementación exacta

La implementación exacta de LRU requiere una estructura de datos que permita:

• Buscar si una página está en memoria (O(1)).
• Actualizar el tiempo de último uso (O(1)).
• Encontrar la página menos usada (O(1)).

La solución es una lista doblemente enlazada combinada con una tabla hash:

• La lista enlazada mantiene las páginas en orden de uso (más reciente al final).
• La tabla hash mapea número de página → nodo en la lista.
• Al acceder a una página, se mueve al final de la lista (O(1)).
• La víctima es el primer nodo de la lista (O(1)).

Esta implementación es O(1) por acceso, pero requiere memoria adicional para la lista y la tabla.

4. Costo de LRU

El costo de LRU es O(1) por acceso, pero la complejidad de hardware es alta. Por eso los sistemas reales usan aproximaciones (tema 38).

5. Propiedades

• No sufre la anomalía de Belady: más marcos nunca aumentan los fallos.
• Se aproxima al óptimo: usa el pasado como predicción del futuro.
• Costo O(1): con la implementación adecuada.
• Complejidad de hardware alta: requiere tracking en cada acceso.

6. Comparación con FIFO y óptimo

LRU tiene más fallos que FIFO en esta cadena, pero no sufre la anomalía. En general, LRU es mejor que FIFO para la mayoría de las cargas de trabajo.

7. Ejemplo paso a paso

Cadena: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Marcos: 3.

Total: 10 fallos (de 12 accesos).

8. Implementación en C

El programa siguiente implementa LRU con una lista enlazada simple:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int page; struct Node *prev, *next; } Node;

int main(void)
{
    int marcos = 3;
    Node *head = NULL, *tail = NULL;
    int n = 0;
    int seq[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int nseq = 12;
    int fallos = 0;

    for (int i = 0; i < nseq; i++) {
        int p = seq[i];
        /* buscar en la lista */
        Node *cur = head;
        int found = 0;
        while (cur) { if (cur->page == p) { found = 1; break; } cur = cur->next; }

        if (found) {
            printf("pág %d: HIT\\n", p);
            /* mover al final */
            if (cur != tail) {
                if (cur->prev) cur->prev->next = cur->next;
                else head = cur->next;
                if (cur->next) cur->next->prev = cur->prev;
                cur->prev = tail;
                cur->next = NULL;
                if (tail) tail->next = cur;
                tail = cur;
                if (!head) head = cur;
            }
        } else {
            fallos++;
            if (n < marcos) {
                Node *node = malloc(sizeof *node);
                node->page = p; node->prev = tail; node->next = NULL;
                if (tail) tail->next = node;
                tail = node;
                if (!head) head = node;
                n++;
                printf("pág %d: MISS (marco libre)\\n", p);
            } else {
                printf("pág %d: MISS (reemplaza %d)\\n", p, head->page);
                head->page = p;
                /* mover head al final */
                Node *old = head;
                head = head->next;
                if (head) head->prev = NULL;
                old->prev = tail;
                old->next = NULL;
                if (tail) tail->next = old;
                tail = old;
            }
        }
    }
    printf("\\nFallos: %d de %d (%.1f%%)\\n", fallos, nseq, 100.0 * fallos / nseq);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o lru lru.c
$ ./lru$ ./lrupá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: HIT
pág 5: MISS (reemplaza 3)
pág 1: HIT
pág 2: HIT
pág 3: MISS (reemplaza 5)
pág 4: MISS (reemplaza 1)
pág 5: MISS (reemplaza 2)

Fallos: 9 de 12 (75,0%)

9. Probar con un simulador

Este simulador ejecuta LRU sobre una cadena de referencias y muestra el estado de la memoria tras cada acceso.

10. En Linux

Linux no implementa LRU exacto (demasiado costoso en hardware). Usa el algoritmo de reloj (clock), que es una aproximación. Las herramientas para observar:

$ grep -E 'pgpgin|pgpgout|pswpin|pswpout' /proc/vmstat

• Linux usa el algoritmo de reloj, no LRU exacto.
• El bit accessed (A) del PTE se usa para aproximar LRU.

11. Resumen

• LRU reemplaza la página menos usada recientemente.
• Se implementa con lista doblemente enlazada + tabla hash (O(1) por acceso).
• No sufre la anomalía de Belady.
• Se aproxima al óptimo (usa el pasado como predicción).
• El costo de hardware es alto; los sistemas usan aproximaciones.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta lru.c y compara los fallos con FIFO para la misma cadena.
2. Modifica lru.c para usar una tabla hash (array de punteros) para búsqueda O(1).
3. Explica por qué LRU no sufre la anomalía de Belady.
4. Investiga cómo implementa Linux el algoritmo de reloj.
5. Compara LRU con el algoritmo óptimo para 5 cadenas diferentes.
6. Dibuja la lista enlazada tras cada acceso del ejemplo.
7. Explica la diferencia entre LRU exacto y LRU aproximado.