Reemplazo FIFO y la anomalía de Belady

1. El algoritmo FIFO

FIFO reemplaza la página que lleva más tiempo en la RAM, independientemente de si se ha usado recientemente. Es la estrategia más simple: se mantiene una cola de las páginas en orden de llegada, y cuando hay que reemplazar, se saca la del frente.

FIFO (First In, First Out) es el algoritmo de reemplazo que reemplaza la página que lleva más tiempo en la memoria, usando una cola.

2. Cómo funciona

Para cada acceso a una página:

1. Si la página está en la RAM: acierto (hit). No se cambia nada.
2. Si no está (fallo): si hay marco libre, se carga. Si no, se reemplaza la página más antigua (la del frente de la cola).
3. Se actualiza la cola: la nueva página se añade al final.

La cola se gestiona con un puntero circular (índice módulo número de marcos).

3. Implementación en C

El programa siguiente implementa FIFO sobre una cadena de referencias:

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

int main(int argc, char **argv)
{
    int marcos = argc > 1 ? atoi(argv[1]) : 3;
    int seq[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int nseq = 12;
    int mem[16]; int n = 0;  /* marcos ocupados */
    int fifo = 0;
    int fallos = 0;

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

$ gcc -std=c17 -Wall -Wextra -o fifo fifo.c
$ ./fifo 3
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 5)
pág 4: MISS (reemplaza 1)
pág 5: HIT
Marcos=3 Fallos=9 Tasa=75,0%
$ ./fifo 4$ ./fifo 4pág 1: MISS (marco libre)
pág 2: MISS (marco libre)
pág 3: MISS (marco libre)
pág 4: MISS (marco libre)
pág 1: HIT
pág 2: HIT
pág 5: MISS (reemplaza 1)
pág 1: MISS (reemplaza 2)
pág 2: MISS (reemplaza 3)
pág 3: MISS (reemplaza 4)
pág 4: MISS (reemplaza 5)
pág 5: HIT
Marcos=4 Fallos=10 Tasa=83,3%

Con 3 marcos: 9 fallos. Con 4 marcos: 10 fallos. ¡Más memoria produjo más fallos! Esta es la anomalía de Belady.

4. La anomalía de Belady

La anomalía de Belady es el fenómeno por el cual aumentar el número de marcos de memoria puede aumentar el número de fallos de página con el algoritmo FIFO. Es contraintuitivo: más memoria debería dar menos fallos.

Anomalía de Belady: con FIFO, para ciertas cadenas de referencias, aumentar el número de marcos aumenta el número de fallos de página.

5. Por qué ocurre

La anomalía ocurre porque FIFO no considera el uso reciente: reemplaza la página más antigua, que puede ser una que se va a usar pronto. Con más marcos, la página antigua permanece más tiempo y puede "empujar" a otra página útil a ser reemplazada antes.

Es una propiedad específica de FIFO (y de algunas políticas similares). Los algoritmos basados en el uso reciente (LRU, óptimo) no sufren la anomalía.

6. Ejemplo numérico

La cadena clásica que demuestra la anomalía es: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Con FIFO, 4 marcos producen más fallos que 3. Con LRU y óptimo, más marcos producen menos fallos (comportamiento esperado).

7. Experimento en C

El programa anterior ya demuestra la anomalía. Para verificar con otras cadenas:

$ ./fifo 3  # con la cadena clásica
$ ./fifo 4  # más marcos, más fallos

8. Probar con un simulador

Este simulador compara FIFO, LRU y óptimo sobre la misma cadena de referencias, con distintos números de marcos.

9. En Linux

Linux no usa FIFO puro para el reemplazo de páginas; usa el algoritmo de reloj (clock), que es una aproximación a LRU. La anomalía de Belady no ocurre con LRU ni con el reloj.

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

• Linux usa el algoritmo de reloj, no FIFO puro.
• La anomalía de Belady no ocurre con LRU ni con el reloj.

10. Resumen

• FIFO reemplaza la página más antigua, usando una cola.
• Es simple de implementar pero no considera el uso reciente.
• La anomalía de Belady: más marcos pueden producir más fallos con FIFO.
• LRU y óptimo no sufren la anomalía.
• Linux usa el algoritmo de reloj, no FIFO puro.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta fifo.c con 3 y 4 marcos. ¿Se reproduce la anomalía?
2. Modifica fifo.c para implementar LRU y compara los resultados.
3. Busca otra cadena que produzca la anomalía de Belady.
4. Explica por qué LRU no sufre la anomalía.
5. Investiga cómo implementa Linux el algoritmo de reloj.
6. Dibuja el estado de la cola FIFO tras cada acceso de la cadena clásica.
7. Compara FIFO con LRU para 5 cadenas diferentes.