El problema del reemplazo

1. El problema: no quedan marcos libres

Cuando la RAM está llena y se produce un fallo de página, el sistema no puede cargar la nueva página sin liberar un marco. Debe elegir una página existente (la víctima) para reemplazarla.

La elección de la víctima es crítica: si se reemplaza una página que se va a usar pronto, se generará otro fallo inmediatamente (thrashing). Si se reemplaza una página que no se usará por un tiempo, el impacto es mínimo.

2. La idea: reemplazar una página

El reemplazo de páginas consiste en:

1. Elegir una víctima: una página que esté en la RAM.
2. Si la víctima está sucia (dirty): escribirla al disco (swap o archivo).
3. Liberar el marco: marcar la entrada de la tabla como no presente.
4. Cargar la nueva página: leerla del disco al marco liberado.
5. Actualizar la tabla: P=1, marco=f, bits actualizados.

El objetivo es elegir la víctima que minimice el número de fallos futuros.

3. La víctima

La víctima es la página que se reemplaza. La elección depende del algoritmo de reemplazo (FIFO, LRU, óptimo, etc.), que se estudia en los temas 35-38. Pero independientemente del algoritmo, hay consideraciones:

• Páginas compartidas: si una página es compartida por varios procesos, reemplazarla afecta a todos.
• Páginas sucias: reemplazar una página sucia requiere escribirla al disco (costoso).
• Páginas limpias: si la página no se ha modificado, se puede descartar sin escribir.

4. El bit sucio (dirty bit)

El bit dirty (D) de la PTE indica si la página se ha modificado desde que se cargó en la RAM. El hardware lo pone a 1 en cada escritura.

• Dirty = 0 (limpia): la página no se ha modificado. Se puede descartar sin escribir al disco.
• Dirty = 1 (sucia): la página se ha modificado. Hay que escribirla al disco antes de reemplazarla.

El bit dirty es crucial para el rendimiento: reemplazar una página limpia es mucho más barato que reemplazar una sucia.

Los algoritmos de reemplazo suelen preferir víctimas limpias cuando es posible (NRU, tema 38).

5. La cadena de referencias

La cadena de referencias es la secuencia de accesos a páginas que un proceso realiza. Es la entrada para los algoritmos de reemplazo. Por ejemplo:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Los algoritmos procesan esta cadena y deciden qué página reemplazar en cada fallo. La calidad del algoritmo se mide por el número de fallos que genera sobre una cadena dada.

6. El costo del reemplazo

El costo de reemplazar una página depende de si está sucia:

El costo de reemplazar una página sucia es el doble que el de una limpia (escritura + lectura).

7. Ejemplo numérico

Un sistema con 3 marcos de RAM. La cadena de referencias es: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Con algoritmo FIFO:

Total: 9 fallos de página (de 12 accesos). La tasa de fallos es 9/12 = 75 %.

8. Experimento en C

El programa siguiente simula el reemplazo con FIFO sobre una cadena de referencias:

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

int main(void)
{
    int marcos = 3;
    int mem[3] = {-1, -1, -1};  /* -1 = vacío */
    int seq[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int nseq = 12;
    int fifo = 0;  /* índice FIFO */
    int fallos = 0;

    for (int i = 0; i < nseq; i++) {
        int p = seq[i];
        int found = 0;
        for (int j = 0; j < marcos; j++)
            if (mem[j] == p) { found = 1; break; }
        if (found) {
            printf("pág %d: HIT  (mem: %d %d %d)\\n", p, mem[0], mem[1], mem[2]);
        } else {
            fallos++;
            if (mem[fifo] != -1) printf("pág %d: MISS (reemplaza %d)\\n", p, mem[fifo]);
            else printf("pág %d: MISS (marco libre)\\n", p);
            mem[fifo] = p;
            fifo = (fifo + 1) % marcos;
            printf("         mem: %d %d %d\\n", mem[0], mem[1], mem[2]);
        }
    }
    printf("\\nFallos: %d de %d (%.1f%%)\\n", fallos, nseq, 100.0 * fallos / nseq);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o reemplazo reemplazo.c
$ ./reemplazo$ ./reemplazo

9. Probar con un simulador

Este simulador muestra el proceso de reemplazo: cada fallo elige una víctima, la escribe si está sucia, y carga la nueva página.

10. En Linux

Linux gestiona el reemplazo de páginas mediante el algoritmo de reloj (clock) sobre las páginas activas e inactivas. Las herramientas para observar:

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

• pgpgin/pgpgout: páginas leídas/escritas en el page cache.
• pswpin/pswpout: páginas leídas/escritas en el swap.
• La proporción de pswpout indica cuántas víctimas sucias se escriben al disco.

11. Resumen

• El reemplazo elige una víctima cuando no hay marcos libres.
• El bit sucio (dirty) indica si hay que escribir la víctima al disco.
• Reemplazar una página limpia es más barato que una sucia.
• La cadena de referencias es la entrada para los algoritmos de reemplazo.
• El costo depende de si la víctima está sucia (escritura + lectura vs solo lectura).

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Modifica reemplazo.c para contar las víctimas sucias (simular el bit dirty).
2. Calcula el costo total de reemplazar 10 páginas (5 limpias, 5 sucias) con costos de 10 y 20 ms.
3. Explica por qué los algoritmos de reemplazo prefieren víctimas limpias.
4. Investiga cómo Linux implementa el algoritmo de reloj (clock).
5. Usa vmstat para observar la actividad de swap en tu sistema.
6. Dibuja el flujo de reemplazo de una página sucia.
7. Compara el costo de reemplazar una página limpia vs sucia.