El algoritmo óptimo

1. El algoritmo óptimo

El algoritmo óptimo (OPT, también llamado MIN o Bélády) reemplaza la página que no se usará por más tiempo en el futuro (o que no se usará nunca). Es la estrategia que minimiza el número de fallos de página.

Algoritmo óptimo (OPT): en cada fallo de página, reemplaza la página cuyo próximo uso está más lejos en el futuro (o que no se usará).

Es imposible de implementar en la práctica porque requiere conocer el futuro (la secuencia completa de referencias). Pero se usa como referencia (cota inferior) para evaluar otros algoritmos.

2. Cómo funciona

Para cada fallo de página:

1. Identificar las páginas en memoria.
2. Para cada página, buscar su próximo uso en la secuencia restante.
3. Reemplazar la página cuyo próximo uso es más lejano (o que no se usará).

Si una página no se usará nunca más, es la mejor candidata (se reemplaza primero).

3. Por qué es óptimo

OPT es óptimo porque reemplaza la página que menos se necesitará en el futuro. Cualquier otro algoritmo que reemplace una página que se usará antes generará al menos el mismo número de fallos. Esto se demuestra por intercambio (exchange argument): si un algoritmo reemplaza una página que se usará antes que otra, se puede intercambiar las decisiones y no aumentar los fallos.

4. Cómo calcularlo

Para cada fallo:

• Para cada página en memoria, buscar la posición de su próximo uso en la secuencia restante.
• Si una página no aparece, su próximo uso es "infinito".
• Reemplazar la página con el próximo uso más lejano (o infinito).

El cálculo requiere conocer toda la secuencia de referencias por adelantado.

5. Ejemplo paso a paso

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

Total: 7 fallos (el mínimo posible para esta cadena con 3 marcos).

6. Implementación en C

El programa siguiente implementa OPT sobre una cadena de referencias:

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

int main(void)
{
    int marcos = 3;
    int seq[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int nseq = 12;
    int mem[16]; int n = 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 {
                /* encontrar la víctima: la que se usa más lejos */
                int victim = 0, farthest = -1;
                for (int j = 0; j < marcos; j++) {
                    int nextUse = 999999;
                    for (int k = i + 1; k < nseq; k++) {
                        if (seq[k] == mem[j]) { nextUse = k; break; }
                    }
                    if (nextUse > farthest) { farthest = nextUse; victim = j; }
                }
                printf("pág %d: MISS (reemplaza %d, próximo uso en %d)\\n", p, mem[victim], farthest);
                mem[victim] = p;
            }
        }
    }
    printf("\\nFallos: %d de %d (%.1f%%)\\n", fallos, nseq, 100.0 * fallos / nseq);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o optimal optimal.c
$ ./optimal$ ./optimalpág 1: MISS (marco libre)
pág 2: MISS (marco libre)
pág 3: MISS (marco libre)
pág 4: MISS (reemplaza 3, próximo uso en 9)
pág 1: HIT
pág 2: HIT
pág 5: MISS (reemplaza 4, próximo uso en 10)
pág 1: HIT
pág 2: HIT
pág 3: MISS (reemplaza 5, próximo uso en 999999)
pág 4: MISS (reemplaza 2, próximo uso en 999999)
pág 5: HIT

Fallos: 7 de 12 (58,3%)

7. Propiedades

• Óptimo: minimiza el número de fallos de página.
• No sufre la anomalía de Belady: más marcos nunca aumentan los fallos.
• Imposible de implementar: requiere conocer el futuro.
• Usado como referencia: para evaluar otros algoritmos (FIFO, LRU, etc.).
• Cota inferior: ningún algoritmo puede hacer menos fallos que OPT.

8. Probar con un simulador

Este simulador ejecuta FIFO, LRU y Óptimo sobre la misma cadena y compara los resultados.

9. En Linux

Linux no usa OPT (es imposible), pero se usa como referencia en la investigación y el diseño de algoritmos. Los algoritmos reales (reloj, LRU aproximado) se comparan con OPT para medir su eficiencia.

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

• Linux no implementa OPT, pero se usa como referencia.
• Los algoritmos reales se comparan con OPT para medir su eficiencia.

10. Resumen

• OPT reemplaza la página cuyo próximo uso es más lejano.
• Es óptimo: minimiza el número de fallos de página.
• No sufre la anomalía de Belady.
• Es imposible de implementar (requiere conocer el futuro).
• Se usa como referencia para evaluar otros algoritmos.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Calcula a mano el OPT para la cadena 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 con 3 marcos.
2. Modifica optimal.c para aceptar la cadena y el número de marcos como argumentos.
3. Compara OPT con FIFO y LRU para 5 cadenas diferentes.
4. Explica por qué OPT es la cota inferior.
5. Investiga qué algoritmos se aproximan a OPT en la práctica.
6. Dibuja el estado de la memoria tras cada acceso del ejemplo.
7. Explica por qué LRU es una buena aproximación a OPT.