Hiperpaginación y conjunto de trabajo

1. El problema: demasiados procesos, poca RAM

Si se cargan más procesos de los que la RAM puede soportar, cada proceso recibe pocos marcos. Sus páginas se reemplazan constantemente, causando fallos de página. El sistema pasa más tiempo moviendo páginas que ejecutando procesos. Es la hiperpaginación.

La causa raíz es que el grado de multiprogramación (número de procesos en memoria) supera la capacidad de la RAM.

2. Qué es la hiperpaginación

La hiperpaginación (thrashing) es el estado en que el sistema gasta más tiempo en fallos de página y reemplazo que en ejecutar instrucciones. Los síntomas:

• CPU ociosa: la CPU espera al disco (swap).
• Disco saturado: el swap está en uso constante.
• Bajo throughput: los procesos avanzan muy lentamente.
• Alta tasa de fallos: cada proceso genera muchos fallos de página.

La hiperpaginación es catastrófica: el rendimiento cae a casi cero. La única solución es reducir el número de procesos o añadir RAM.

3. Cómo se detecta

Se detecta monitorizando:

• Tasa de fallos de página: si crece bruscamente, hay hiperpaginación.
• Uso de CPU: si la CPU está ociosa pero el disco está saturado.
• Uso de swap: si el swap está en uso constante.
• Throughput: si cae a casi cero.

En Linux, vmstat 1 muestra la actividad de swap (si, so) y la CPU ociosa (id).

4. El modelo del conjunto de trabajo

El conjunto de trabajo (working set) de un proceso es el conjunto de páginas que ha usado en las últimas Δ referencias (ventana de tiempo). Es la "memoria activa" del proceso.

Conjunto de trabajo (WS): WS(t, Δ) = conjunto de páginas referenciadas en el intervalo [t − Δ, t].

Si un proceso tiene suficientes marcos para su conjunto de trabajo, no genera fallos de página (salvo la primera vez). Si no, genera fallos constantemente.

El tamaño del conjunto de trabajo varía con el tiempo: un proceso puede tener un WS pequeño al inicio y grande durante el procesamiento.

5. Asignación de marcos a procesos

El sistema operativo debe decidir cuántos marcos asignar a cada proceso. Las opciones:

• Asignación fija: cada proceso recibe un número fijo de marcos. Simple, pero no se adapta a las necesidades cambiantes.
• Asignación variable: el número de marcos se ajusta según el conjunto de trabajo del proceso.

La asignación variable es mejor: da más marcos a los procesos que los necesitan y menos a los que no.

6. Algoritmos de asignación

7. Ejemplo numérico

Un sistema con 100 marcos de RAM y 3 procesos. Los conjuntos de trabajo son:

Total necesario: 75 marcos. Hay 100 disponibles, así que todos los procesos tienen suficientes marcos. No hay hiperpaginación.

Si se añade un cuarto proceso con WS = 40, el total sería 115 > 100. El sistema entra en hiperpaginación. La solución es suspender un proceso.

8. Experimento en C

El programa siguiente simula el conjunto de trabajo de un proceso y calcula cuántos marcos necesita:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int refs[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, 6, 3, 4};
    int n = 15;
    int delta = 5;  /* ventana de tiempo */
    int paginas[100] = {0};

    for (int t = delta; t <= n; t++) {
        /* reset */
        for (int i = 0; i < 100; i++) paginas[i] = 0;
        int ws = 0;
        for (int i = t - delta; i < t; i++) {
            if (!paginas[refs[i]]) { paginas[refs[i]] = 1; ws++; }
        }
        printf("t=%2d: WS = %d páginas (refs %d..%d)\\n", t, ws, t - delta, t - 1);
    }
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o workingset workingset.c
$ ./workingset
t= 5: WS = 4 páginas (refs 0..4)
t= 6: WS = 4 páginas (refs 1..5)
t= 7: WS = 5 páginas (refs 2..6)
t= 8: WS = 5 páginas (refs 3..7)
t= 9: WS = 5 páginas (refs 4..8)
t=10: WS = 5 páginas (refs 5..9)
t=11: WS = 6 páginas (refs 6..10)
t=12: WS = 6 páginas (refs 7..11)
t=13: WS = 6 páginas (refs 8..12)
t=14: WS = 6 páginas (refs 9..13)
t=15: WS = 5 páginas (refs 10..14)

El conjunto de trabajo varía entre 4 y 6 páginas según la ventana. El sistema debe asignar al menos 6 marcos para evitar fallos.

9. Probar con un simulador

Este simulador calcula el conjunto de trabajo para una secuencia de referencias y un tamaño de ventana Δ.

10. En Linux

Linux no implementa el modelo del conjunto de trabajo directamente. En su lugar:

• OOM killer: cuando la RAM se agota, mata el proceso que más memoria usa.
• swappiness: controla cuánto swap se usa (0-100).
• cgroups: limitan la memoria por grupo de procesos.
• kswapd: demonio que libera páginas cuando la memoria es baja.

$ vmstat 1 5
$ cat /proc/sys/vm/swappiness
$ cat /proc/meminfo | grep -i 'memtotal\|memavailable\|swaptotal'$ cat /proc/meminfo | grep -i 'memtotal\|memavailable\|swaptotal'

• vmstat 1 5: muestra la actividad de swap (si, so) y la CPU ociosa (id) cada segundo.
• swappiness: controla la tendencia a usar swap (0 = evitar, 100 = usar libremente).
• /proc/meminfo: memoria total, disponible y swap.

11. Resumen

• La hiperpaginación es el colapso del sistema por exceso de fallos de página.
• Se detecta por CPU ociosa, disco saturado y bajo throughput.
• El conjunto de trabajo es el conjunto de páginas usadas en una ventana de tiempo.
• La asignación de marcos puede ser igual, proporcional, por prioridad o por conjunto de trabajo.
• Linux usa OOM killer, swappiness y cgroups para gestionar la memoria.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Modifica workingset.c para calcular el WS con Δ = 3 y Δ = 10. ¿Cómo cambia?
2. Simula un sistema con 50 marcos y 3 procesos con WS de 20, 20 y 20. ¿Hay hiperpaginación?
3. Explica por qué añadir más procesos empeora la hiperpaginación.
4. Investiga cómo funciona el OOM killer en Linux.
5. Usa vmstat 1 para observar la actividad de swap en tu sistema.
6. Dibuja la gráfica de throughput vs grado de multiprogramación.
7. Explica la diferencia entre asignación fija y variable de marcos.