Cuando un proceso necesita una página de memoria que no está cargada en RAM, ocurre un fallo de página. Si todos los marcos están ocupados, el sistema operativo debe elegir qué página retirar. Esta decisión determina el rendimiento global del sistema. Los algoritmos de reemplazo intentan minimizar los fallos futuros, pero ninguno (salvo el óptimo, irrealizable) es perfecto: cada uno tiene compromisos entre coste hardware, complejidad y comportamiento.
Comparativa de Algoritmos
| Algoritmo | Criterio de víctima | Coste hardware | Rendimiento | Anomalía Belady | Cuándo usar |
|---|
| FIFO | La cargada hace más tiempo | Muy bajo (cola) | Mediocre | Sí, posible | Sistemas con poca memoria, simplicidad extrema |
| LRU | La menos usada recientemente | Alto (timestamp por acceso) | Muy bueno | No (algoritmo de pila) | Cuando hay buena localidad temporal |
| Optimal | La que más tarde se referenciará | Imposible (necesita futuro) | Cota mínima teórica | No | Solo como referencia académica |
| Clock | Bit de uso = 0 en recorrido circular | Bajo (1 bit por marco) | Cercano a LRU | No en la práctica | Implementación real (Linux, BSD) |
| LFU | La menos referenciada en total | Medio (contador por página) | Bueno si patrón estable | No | Trabajos con conjuntos de páginas estables |
Casos de Uso Reales
El kernel de Linux usa un Clock con dos listas (active/inactive) y bits de uso múltiples. Aproxima LRU sin pagar el coste de actualizar timestamps en cada acceso.
💡 Usar LRU puro en hardware moderno costaría más que ahorra en fallos.
PostgreSQL y MySQL combinan ideas de LRU y LFU en sus buffer pools (ej. ARC, 2Q, LRU-K) para distinguir páginas calientes de fríos sin penalizar accesos esporádicos.
💡 LRU puro sufre con escaneos secuenciales largos (cache pollution).
Cloudflare, Akamai y Fastly usan LRU con segmentación o variantes (S3-FIFO, TinyLFU) para servir contenido a millones de usuarios manteniendo objetos virales en memoria.
💡 El reemplazo eficiente es el corazón del rendimiento de un CDN.
En FP de Informática y Sistemas Operativos universitarios se piden ejercicios manuales con FIFO, LRU y Optimal. Saber dibujar la tabla y contar fallos es competencia básica.
💡 La cadena de Belady (1,2,3,4,1,2,5,1,2,3,4,5) es ejemplo clásico.
Preguntas Frecuentes
¿Qué es la anomalía de Belady?
Es el fenómeno por el que aumentar el número de marcos asignados a un proceso provoca más fallos de página, no menos. Lo descubrió László Bélády en 1969 estudiando FIFO. Sucede porque FIFO no respeta la propiedad de pila: la página retirada con N marcos puede ser distinta de la que se retiraría con N+1.
💡 Algoritmos como LRU u Optimal cumplen la propiedad de pila y nunca empeoran al añadir marcos.
¿Por qué Optimal no se implementa en la práctica?
Porque requiere conocer el futuro: para decidir qué página retirar mira las referencias que vendrán. Un sistema operativo no puede predecir accesos a memoria de programas arbitrarios. Solo es útil como cota inferior para evaluar otros algoritmos.
💡 Si tu algoritmo da el doble de fallos que Optimal, sabes que tienes margen.
¿LRU vs Clock: cuál es mejor?
LRU produce menos fallos en teoría, pero requiere actualizar metadatos en cada acceso a memoria (carísimo). Clock aproxima LRU con un solo bit por página y un puntero circular: casi tan bueno y muchísimo más barato. Por eso los sistemas reales (Linux, FreeBSD) usan variantes de Clock, no LRU puro.
💡 La diferencia es de 5-10% de fallos pero 100x menos sobrecarga.
¿Cómo se aproxima LRU eficientemente?
Con bits de referencia que el hardware MMU pone a 1 cuando se accede a una página. El SO los lee y resetea periódicamente. Con varios bits (NFU/aging) se puede simular un orden temporal aproximado sin actualizar nada en cada acceso.
💡 La MMU de x86 ofrece un bit Accessed por entrada de tabla de páginas.
¿Diferencia entre fallo de página y trap?
Un fallo de página es un tipo concreto de trap (excepción de hardware). El procesador detecta que una página no está mapeada o no está en RAM y transfiere control al kernel, que decide si traerla del disco, mapearla, o terminar el proceso (segfault).
💡 No todo trap es fallo de página: hay traps por división por cero, instrucciones inválidas, etc.
¿Qué algoritmos usan los SO modernos?
Linux: dos listas LRU aproximadas (active/inactive) con bit de acceso. Windows: working set por proceso con FIFO local en cada uno. macOS: LRU aproximada con cola activa/inactiva. Casi nadie usa FIFO ni Optimal: el primero rinde mal y el segundo es imposible.
💡 Las decisiones reales mezclan reemplazo + working set + paginación bajo demanda.
Cómo Resolver un Ejercicio Paso a Paso
1
Lee la cadena y el número de marcosAnota cada referencia y cuántos marcos hay. Dibuja una tabla con tantas filas como marcos y una columna por referencia.
2
Recorre cada referencia en ordenPara cada referencia: ¿está la página en algún marco? Si sí, es HIT. Si no, FAULT (y si todos los marcos están llenos, hay reemplazo).
3
Aplica el criterio del algoritmoFIFO: la cargada antes. LRU: la usada hace más tiempo. Optimal: la que tarda más en volver a aparecer. Clock: recorre el puntero buscando bit=0. LFU: la menos referenciada.
4
Marca cada paso H o FDebajo de cada columna escribe H (hit) o F (fallo). Distingue F* si hubo reemplazo. Esto te da el conteo final.
5
Calcula métricas finalesTasa de fallos = fallos / total. Hit ratio = hits / total. Compara con Optimal para evaluar la eficiencia del algoritmo elegido.
Mejores Prácticas
📋Dibuja siempre la tabla completaAunque pienses que sabes el resultado, escribir cada paso reduce errores y te hace ver qué páginas conviven en memoria.
🎯Para Optimal, mira hacia delanteNo es un algoritmo causal: para decidir hoy hay que ver mañana. Anota junto a cada página su próxima aparición.
🔄En LRU usa una pila auxiliarLista ordenada por uso. Al hit, mueve la página al final (más reciente). Al evict, sale la del principio (menos reciente).
⏱️En FIFO basta una colaNo importa si una página se usa mucho: lo único relevante es cuándo se cargó por primera vez. Mantén la cola estricta.
🧭En Clock, mueve el punteroDespués de cada reemplazo, el puntero avanza una posición. Si todos los bits son 1, dará una vuelta entera poniéndolos a 0.
📈Compara siempre con OptimalEl cociente fallos_optimal / fallos_algoritmo te dice qué tan lejos estás del techo. Por debajo de 70% indica algoritmo mediocre o cadena hostil.
- Confundir LRU (último uso) con LFU (frecuencia total) — son criterios distintos.
- En FIFO, mover la página de posición al hacer HIT — los hits no afectan a la cola FIFO.
- En Optimal, contar la referencia actual como "futura" — solo cuentan las posteriores al instante actual.
- Olvidar resetear el bit de uso en Clock al pasar el puntero por una página con bit=1.
- Cargar 2 páginas en el primer instante — solo se carga una por referencia, aunque haya marcos vacíos.
- Suponer que más marcos siempre da menos fallos — la anomalía de Belady demuestra que en FIFO no es así.