Proyecto: simulador de memoria virtual

1. Qué debe resolver el proyecto

Un simulador integrado de memoria virtual mantiene un único estado de páginas, marcos y traducciones. Cada acceso modifica ese estado según reglas explícitas y produce una explicación verificable de su resultado.

La integración evita una incoherencia frecuente: contar un acierto de TLB sobre un marco que ya fue reutilizado para otra página. También obliga a distinguir un fallo de traducción en la caché de un fallo de página, y a actualizar el estado de escritura incluso cuando no se consulta la tabla.

El proyecto recibe una configuración y una traza. Produce una fila por acceso con página, desplazamiento, marco, dirección física, resultado de TLB, fallo de página, víctima, escritura de expulsión y costo. Al final presenta totales y el estado residente.

Se utilizan los conceptos de los temas 19, traducción, 20, tabla de páginas, 27, TLB y 39, reemplazo. Aquí la dificultad no está en sumar algoritmos aislados, sino en hacer que compartan una especificación coherente.

2. Especificación del modelo

La página pequeña y las pocas entradas facilitan revisar las cuentas. No representan tamaños habituales de Linux. Una dirección física calculada es un número del simulador: no es un puntero que el programa vaya a desreferenciar.

Una página no presente sigue perteneciendo al espacio virtual válido y se puede cargar. No se simulan permisos, SIGSEGV, páginas compartidas ni un swap con capacidad finita. Tampoco clasificamos los fallos como menores o mayores: todos reciben un servicio abstracto de carga definido en la sección de costos.

3. Formato de la traza

Cada línea contiene una operación y una dirección decimal en bytes. R representa lectura y W escritura. Se permiten líneas vacías y comentarios completos cuyo primer carácter no blanco sea #. No se permiten comentarios al final de un acceso ni operandos extra.

# Dos primeros accesos dentro de la misma página
R 0
W 1
R 256
R 512
R 0
R 768
W 513
R 256

página = dirección_virtual / 256           (división entera)
desplazamiento = dirección_virtual % 256
dirección_física = marco × 256 + desplazamiento

W 513 -> página 2, desplazamiento 1
Si la página está en el marco 2: dirección física = 2 × 256 + 1 = 513

La coincidencia numérica de esa última dirección es accidental. Si la página 2 pasa a otro marco, su dirección física cambia y su desplazamiento continúa siendo 1.

Las líneas admiten hasta 158 caracteres sin contar el salto final, y el operando hasta 63 dígitos, suficiente para este formato. Una dirección negativa, hexadecimal, fraccionaria, fuera del espacio o una operación diferente se rechaza. La traza debe contener al menos un acceso; los errores no se convierten en referencias a la página cero.

4. Estructuras y estado inicial

Necesitamos representar relaciones diferentes sin confundirlas:

Usamos -1 para indicar marco o página no asignados. Los instantes son el número de acceso, que aumenta una vez por operación. No son nanosegundos: sirven para ordenar cargas y usos sin empates entre páginas distintas.

En la TLB, una entrada válida debe referirse a una página presente y al mismo marco que indica la tabla. En los marcos, cada página residente aparece una sola vez. Esas relaciones se comprobarán como invariantes.

5. El camino completo de un acceso

1. Separar dirección. Obtener número de página y desplazamiento de una referencia ya validada.
2. Buscar en TLB si está habilitada. Un acierto entrega el marco. Un fallo obliga a consultar la tabla.
3. Consultar la tabla cuando corresponde. Si la página está presente, se utiliza su marco sin cargarla de nuevo.
4. Resolver una ausencia. Se obtiene un marco libre o se elige una víctima, se atiende la posible escritura de expulsión y se instala la nueva página.
5. Instalar la traducción en TLB. Solo si la TLB está habilitada y la búsqueda inicial no fue un acierto.
6. Registrar el acceso. Actualizar último uso, bit R y, si es escritura, bit sucio.
7. Calcular dirección física y costo. Emitir la fila con los eventos de esta operación.

Un miss de TLB puede ser una consulta resuelta por una página ya residente. Un fallo de página requiere ausencia en la tabla. Si se mantienen las invariantes del proyecto, un hit de TLB nunca puede coincidir con un fallo de página.

Con cero entradas no se inventan misses: la TLB está desactivada, todos los accesos consultan la tabla y se contabilizan cero hits y cero misses. Esto permite comparar la consulta directa con una caché real del modelo.

6. FIFO, LRU y reloj

El reemplazo solo se ejecuta cuando no quedan marcos libres. Las tres políticas reciben la misma secuencia, pero consultan información diferente:

En reloj, la mano comienza en el marco 0 y no se mueve al ocupar marcos libres. Cuando hace falta reemplazar, gira limpiando bits R iguales a uno, elige el primer cero y queda en el marco siguiente. Esta convención se aplica en ambas implementaciones.

La TLB usa siempre su propio LRU, independientemente de la política de páginas. No hay dos colas FIFO conectadas ni una mano compartida. Elegir FIFO para páginas no convierte la TLB en FIFO.

7. TLB, expulsiones y páginas sucias

Al expulsar la página P del marco F, toda traducción TLB que conserve P → F debe invalidarse antes de reutilizar ese marco. De lo contrario, una referencia posterior a P podría acceder a la página que ahora ocupa F.

Configuración: 1 marco, 2 entradas TLB
R 0       carga página 0 en marco 0
R 256     expulsa página 0 y coloca página 1 en marco 0
R 0       debe fallar de nuevo: la traducción anterior se invalidó

Resultado: 3 fallos de página, 3 misses de TLB y 0 hits.

La suciedad también se actualiza cuando la traducción viene de TLB. Una W pone D = 1 en la entrada de página correspondiente. Al expulsarla, se cuenta una escritura de respaldo y se cobra su costo. La página que entra comienza limpia y se marca sucia si el acceso que provocó la carga era una escritura.

Las escrituras del programa y las escrituras de expulsión son eventos distintos. Diez operaciones W en una página pueden producir una sola escritura de respaldo al expulsarla. Si la traza termina con páginas sucias residentes, no se vacían automáticamente: el contador solo incluye expulsiones ocurridas durante la traza.

8. Contadores y costo del modelo

Para comparar rutas definimos costos ficticios, expresados en nanosegundos del modelo. No son medidas de un equipo real:

Hit de TLB:                              10 + 100 = 110 ns
Miss con página residente:          10 + 50 + 100 = 160 ns
Fallo sin expulsión sucia:   10 + 50 + 5000 + 100 = 5160 ns
Fallo con expulsión sucia:   10 + 50 + 5000 + 8000 + 100 = 13160 ns

Con TLB desactivada se eliminan los 10 ns de búsqueda.
Media = costo acumulado / accesos completados.

El servicio de fallo no vuelve a cobrar una segunda búsqueda ni otro acceso al dato. Es una decisión para evitar doble conteo. No se modelan los ciclos exactos de reejecución de una instrucción, varios niveles de tablas o tiempos reales de E/S.

Con TLB habilitada se cumple hits + misses = accesos y consultas = misses. Sin TLB se cumple consultas = accesos. Siempre debe cumplirse fallos ≤ consultas, expulsiones ≤ fallos y escrituras de respaldo ≤ expulsiones.

9. Implementación completa en C

Guarda el siguiente bloque como memoria_virtual.c. No accede a la memoria virtual real del sistema: administra arreglos que representan el modelo. Utiliza C17 y la biblioteca estándar, sin requerir Linux para simular.

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

#define PAGINAS 16
#define TAM_PAGINA 256
#define MAX_MARCOS 8
#define MAX_TLB 8
#define MAX_ACCESOS 256

struct Pagina { int presente, marco, sucia; };
struct Marco { int pagina, r; unsigned long carga, uso; };
struct Entrada { int pagina, marco; unsigned long uso; };
struct Acceso { char op; unsigned direccion; };
enum Politica { FIFO, LRU, RELOJ };

static struct Pagina tabla[PAGINAS];
static struct Marco marcos[MAX_MARCOS];
static struct Entrada tlb[MAX_TLB];
static int cantidad_marcos, cantidad_tlb, mano;
static enum Politica politica;
static unsigned long accesos, hits, misses, consultas, fallos, expulsiones, escrituras, tiempo;

static int entero(const char *texto, unsigned long maximo, unsigned long *valor)
{
    if (*texto == '\0') return 0;
    for (const char *p = texto; *p; p++)
        if (!isdigit((unsigned char) *p)) return 0;
    char *fin;
    errno = 0;
    unsigned long n = strtoul(texto, &fin, 10);
    if (errno || *fin || n > maximo) return 0;
    *valor = n;
    return 1;
}

static int leer_traza(const char *ruta, struct Acceso salida[])
{
    FILE *f = fopen(ruta, "r");
    if (f == NULL) { perror(ruta); return -1; }
    char linea[192];
    int cantidad = 0, numero = 0, error = 0;
    while (fgets(linea, sizeof linea, f) != NULL) {
        numero++;
        if ((strchr(linea, '\n') == NULL && !feof(f)) ||
            strcspn(linea, "\r\n") > 158) { error = 1; break; }
        char *p = linea;
        while (isspace((unsigned char) *p)) p++;
        if (*p == '\0' || *p == '#') continue;
        char op, texto[64], extra;
        unsigned long direccion;
        if (!isspace((unsigned char) p[1]) ||
            sscanf(p, "%c %63s %c", &op, texto, &extra) != 2 ||
            (op != 'R' && op != 'W') ||
            !entero(texto, PAGINAS * TAM_PAGINA - 1, &direccion) ||
            cantidad == MAX_ACCESOS) { error = 1; break; }
        salida[cantidad++] = (struct Acceso) { op, (unsigned) direccion };
    }
    if (ferror(f)) error = 1;
    if (fclose(f) != 0) error = 1;
    if (error || cantidad == 0) {
        fprintf(stderr, "Traza inválida o vacía; revisar línea %d y límites.\n", numero);
        return -1;
    }
    return cantidad;
}

static void iniciar(void)
{
    for (int p = 0; p < PAGINAS; p++) tabla[p].marco = -1;
    for (int f = 0; f < MAX_MARCOS; f++) marcos[f].pagina = -1;
    for (int i = 0; i < MAX_TLB; i++) tlb[i].pagina = -1;
}

static int elegir_marco(void)
{
    for (int f = 0; f < cantidad_marcos; f++)
        if (marcos[f].pagina == -1) return f;
    if (politica == RELOJ) {
        while (marcos[mano].r) {
            marcos[mano].r = 0;
            mano = (mano + 1) % cantidad_marcos;
        }
        int elegido = mano;
        mano = (mano + 1) % cantidad_marcos;
        return elegido;
    }
    int elegido = 0;
    for (int f = 1; f < cantidad_marcos; f++) {
        unsigned long a = politica == FIFO ? marcos[f].carga : marcos[f].uso;
        unsigned long b = politica == FIFO ? marcos[elegido].carga : marcos[elegido].uso;
        if (a < b) elegido = f;
    }
    return elegido;
}

static void instalar_tlb(int pagina, int marco)
{
    if (cantidad_tlb == 0) return;
    int elegido = 0;
    for (int i = 0; i < cantidad_tlb; i++) {
        if (tlb[i].pagina == -1) { elegido = i; break; }
        if (tlb[i].uso < tlb[elegido].uso) elegido = i;
    }
    tlb[elegido] = (struct Entrada) { pagina, marco, accesos };
}

static void ejecutar(struct Acceso a)
{
    accesos++;
    int p = (int) (a.direccion / TAM_PAGINA);
    unsigned desplazamiento = a.direccion % TAM_PAGINA;
    int marco = -1, acierto = 0, fallo = 0, victima = -1, escritura = 0;
    unsigned long costo = 100;
    if (cantidad_tlb > 0) {
        costo += 10;
        for (int i = 0; i < cantidad_tlb; i++) {
            if (tlb[i].pagina == p) {
                marco = tlb[i].marco;
                tlb[i].uso = accesos;
                acierto = 1;
                break;
            }
        }
        if (acierto) hits++; else misses++;
    }
    if (!acierto) {
        consultas++;
        costo += 50;
        if (!tabla[p].presente) {
            fallo = 1;
            fallos++;
            costo += 5000;
            marco = elegir_marco();
            victima = marcos[marco].pagina;
            if (victima != -1) {
                expulsiones++;
                if (tabla[victima].sucia) {
                    escritura = 1; escrituras++; costo += 8000;
                }
                for (int i = 0; i < cantidad_tlb; i++)
                    if (tlb[i].pagina == victima) tlb[i].pagina = -1;
                tabla[victima] = (struct Pagina) { 0, -1, 0 };
            }
            tabla[p] = (struct Pagina) { 1, marco, 0 };
            marcos[marco] = (struct Marco) { p, 0, accesos, accesos };
        } else {
            marco = tabla[p].marco;
        }
        instalar_tlb(p, marco);
    }
    marcos[marco].uso = accesos;
    marcos[marco].r = 1;
    if (a.op == 'W') tabla[p].sucia = 1;
    tiempo += costo;
    unsigned fisica = (unsigned) marco * TAM_PAGINA + desplazamiento;
    printf("%lu %c %u %d %u %d %u %s %d %d %d %lu\n",
           accesos, a.op, a.direccion, p, desplazamiento, marco, fisica,
           cantidad_tlb == 0 ? "OFF" : (acierto ? "HIT" : "MISS"),
           fallo, victima, escritura, costo);
}

int main(int argc, char *argv[])
{
    unsigned long nm, nt;
    if (argc != 5 || !entero(argv[1], MAX_MARCOS, &nm) || nm == 0 ||
        !entero(argv[2], MAX_TLB, &nt) ||
        (strcmp(argv[3], "fifo") && strcmp(argv[3], "lru") && strcmp(argv[3], "reloj"))) {
        fprintf(stderr, "Uso: %s marcos(1..8) tlb(0..8) fifo|lru|reloj traza.txt\n", argv[0]);
        return 1;
    }
    cantidad_marcos = (int) nm;
    cantidad_tlb = (int) nt;
    politica = strcmp(argv[3], "fifo") == 0 ? FIFO : (strcmp(argv[3], "lru") == 0 ? LRU : RELOJ);
    struct Acceso traza[MAX_ACCESOS];
    int n = leer_traza(argv[4], traza);
    if (n < 0) return 1;
    iniciar();
    puts("n op virtual pagina offset marco fisica tlb fallo victima wb costo_ns");
    for (int i = 0; i < n; i++) ejecutar(traza[i]);
    printf("TOTAL accesos=%lu hits=%lu misses=%lu consultas=%lu fallos=%lu expulsiones=%lu wb=%lu ns=%lu\n",
           accesos, hits, misses, consultas, fallos, expulsiones, escrituras, tiempo);
    printf("MEDIA %.2f ns del modelo\n", (double) tiempo / accesos);
    puts("MARCO pagina D R carga uso");
    for (int f = 0; f < cantidad_marcos; f++) {
        int p = marcos[f].pagina;
        printf("%d %d %d %d %lu %lu\n", f, p, p == -1 ? 0 : tabla[p].sucia,
               marcos[f].r, marcos[f].carga, marcos[f].uso);
    }
    return 0;
}

Los arreglos estáticos comienzan a cero y se ejecuta una sola traza por proceso. La función iniciar prepara los valores -1; si conviertes el programa en una biblioteca reutilizable, debes reiniciar también todos los flags, contadores e instantes entre ejecuciones.

La separación entre elegir marco, instalar TLB y ejecutar un acceso permite revisar decisiones independientes. Invalidar la víctima no significa limpiar toda la TLB: las traducciones de otras páginas residentes siguen siendo válidas.

10. Compilar y verificar una ejecución

$ gcc -std=c17 -Wall -Wextra -Wpedantic -O2 memoria_virtual.c -o memoria_virtual
$ ./memoria_virtual 3 2 lru traza.txt
n op virtual pagina offset marco fisica tlb fallo victima wb costo_ns
1 R 0 0 0 0 0 MISS 1 -1 0 5160
2 W 1 0 1 0 1 HIT 0 -1 0 110
3 R 256 1 0 1 256 MISS 1 -1 0 5160
4 R 512 2 0 2 512 MISS 1 -1 0 5160
5 R 0 0 0 0 0 MISS 0 -1 0 160
6 R 768 3 0 1 256 MISS 1 1 0 5160
7 W 513 2 1 2 513 MISS 0 -1 0 160
8 R 256 1 0 0 0 MISS 1 0 1 13160
TOTAL accesos=8 hits=1 misses=7 consultas=7 fallos=5 expulsiones=2 wb=1 ns=34230
MEDIA 4278.75 ns del modelo
MARCO pagina D R carga uso
0 1 0 1 8 8
1 3 0 1 6 6
2 2 1 1 4 7

El paso 5 es la distinción clave: la TLB ya no recuerda la página 0, pero sigue en RAM, así que solo cuesta 160. En el paso 6, LRU expulsa la página 1. En el paso 8 expulsa la 0, que quedó sucia por la escritura del paso 2, aunque aquella escritura fue un hit.

La página 2 queda sucia al final y no aporta otra escritura al contador. El costo de 34 230 se obtiene sumando cinco cargas de 5160, dos misses residentes de 160, un hit de 110 y un recargo de 8000 por la víctima sucia.

11. Simulador integrado paso a paso

Prepara la configuración y pulsa Iniciar traza. Después puedes avanzar un acceso o ejecutar lo que falta. Cambiar los controles o el texto no modifica una ejecución ya iniciada hasta volver a iniciarla; la etiqueta de ejecución activa permite distinguir ambas cosas.

La ejecución inicial está preparada pero no completada. Con tres marcos, dos entradas y LRU, Ejecutar resto debe reproducir la salida anterior. Prueba después cero entradas de TLB: los fallos de página permanecen iguales para esa configuración de marcos y política, pero cambian las consultas y los costos.

El navegador utiliza las mismas reglas que C para los accesos y comentarios. Si hay una línea inválida se conserva la ejecución activa anterior y se informa el problema. Para garantizar que una misma traza textual sea aceptada por ambas versiones, mantén las líneas cortas, operaciones separadas por blancos y caracteres del formato indicado.

12. Invariantes y pruebas necesarias

Probar solo el total de fallos puede ocultar una dirección física equivocada o una TLB obsoleta. Después de cada acceso se deben revisar estas relaciones:

• Cada página presente apunta a un marco ocupado por ella, y cada marco ocupado apunta a una página presente.
• No hay dos páginas residentes en un mismo marco ni dos entradas TLB válidas para una misma página.
• Toda entrada TLB válida coincide con la tabla y con su marco actual.
• Una página ausente no conserva un marco válido ni suciedad pendiente en esta representación.
• La dirección física conserva el desplazamiento y queda dentro de los marcos configurados.
• Los contadores cumplen las identidades definidas y el costo coincide con los eventos registrados.

Conviene comparar filas completas entre C y JavaScript, además de los totales. Para una prueba más fuerte se puede crear una referencia independiente con estructuras distintas y generar trazas reproducibles que incluyan lecturas y escrituras, marcos escasos y TLB mayores que la RAM.

La versión interactiva verifica las invariantes de coherencia después de cada acceso. Si una modificación rompe una, se detiene con un error interno en vez de continuar mostrando cifras aparentemente válidas.

13. Comparar configuraciones

Cada comparación empieza desde el mismo estado vacío. Conserva la traza y cambia una variable por vez: marcos, capacidad TLB o política de páginas. No compares una ejecución a medias con otra completa.

En este modelo, cambiar solo la capacidad de TLB no cambia las decisiones de reemplazo ni la cantidad de fallos de página: FIFO, LRU y reloj reciben todos los accesos, incluidos los hits. Si el número de fallos cambia, hay que revisar si se olvidó actualizar información al acertar en TLB.

Más entradas de TLB no hacen que quepan más páginas en RAM. Pueden evitar consultas de tabla, pero no conservar una página que el reemplazo expulsó. De igual modo, aumentar marcos puede reducir fallos sin evitar todos los misses de una TLB pequeña.

Para las políticas de páginas, LRU conserva sus propiedades bajo el modelo definido y FIFO o reloj pueden mostrar comportamientos diferentes. El mejor resultado en una traza no convierte una política en óptima para todas las cargas. Además, una política con menos fallos puede diferir en escrituras sucias y costo total.

La media de nanosegundos es una comparación del costo especificado. No corresponde a medir el tiempo de ejecución del programa con time, que incluye el simulador, el parser y la impresión y depende del equipo anfitrión.

14. Límites y extensiones del proyecto

Esta versión termina la integración mínima sin pretender emular Linux. Sus páginas tienen respaldo abstracto, no se modelan bytes y las escrituras de expulsión solo son eventos. No hay dispositivo, caché de archivos, swap finito, copy-on-write ni asignación NUMA.

Para ampliar el proyecto conviene elegir una sola extensión y definir antes sus invariantes:

1. Permisos. Agregar lectura y escritura permitidas, distinguiendo una violación de un fallo recuperable.
2. Contenido. Modelar bytes y valores escritos, conservarlos en el respaldo y verificar lecturas después de expulsar y recargar.
3. Varios procesos. Incluir identificadores en tablas y traducciones, definir asignación de marcos y aislamiento.
4. Respaldo limitado. Definir capacidad y fallos de asignación en lugar de suponer cargas siempre exitosas.
5. Mediciones exportables. Guardar CSV de eventos y comparar trazas con una herramienta independiente.

Si agregas contenido, no basta con incrementar un contador de escritura: hay que conservar el valor correcto. Si agregas procesos, invalidar solo por número de página deja de ser suficiente. Cada ampliación modifica qué significa mantener la coherencia.

El proyecto siguiente integrará asignación y pruebas sobre el heap. Aquí la unidad principal fue la página; allí volverán los bloques de usuario, su alineación y las listas libres.

15. Resumen

• Una sola traza debe actualizar de forma coherente tabla, marcos, TLB y contadores.
• Un miss de TLB no implica que la página esté ausente de RAM.
• La TLB tiene su propio LRU, distinto de la política que elige páginas víctimas.
• Los hits también actualizan último acceso, referencia y suciedad cuando corresponde.
• Expulsar una página exige invalidar sus traducciones antes de reutilizar el marco.
• Una víctima sucia agrega una escritura; las páginas sucias finales no se vacían automáticamente.
• La TLB desactivada se registra como consulta directa, sin inventar misses.
• Las identidades de contadores y las relaciones entre estructuras permiten detectar errores de integración.
• El costo del modelo no es una medida de hardware ni el tiempo que tarda el simulador en imprimir.
• Dos implementaciones y una referencia independiente permiten contrastar filas completas y casos límite.

16. Preguntas de repaso y desafíos

Intenta responder antes de desplegar cada explicación.

Para practicar

1. Reproduce las ocho filas de la traza predeterminada a mano y explica cada expulsión de LRU.
2. Ejecuta los casos mínimos de la sección de pruebas y compara cada dirección física, no solo los totales.
3. Prueba la misma traza con cero, una, dos y ocho entradas de TLB. Verifica la estabilidad de fallos de página para una misma política y cantidad de marcos.
4. Compara FIFO, LRU y reloj desde cero. Registra fallos, escrituras y costo, y explica qué cambia.
5. Construye una traza donde LRU de TLB elimine una traducción cuya página siga presente.
6. Construye una traza que actualice R mediante un hit y cambie una decisión posterior del reloj.
7. Comprueba el rechazo de líneas vacías como única entrada, operandos extra, direcciones negativas y la dirección 4096.
8. Agrega pruebas automáticas que comparen C con una referencia independiente y fijen la semilla de trazas aleatorias.
9. Extiende el modelo con contenido y demuestra que una escritura se conserva tras expulsar y recargar su página.