Sesión 11

Taller avanzado de memoria virtual y sistemas de archivos

Traducción de direcciones, fallos de página y estructuras de almacenamiento

Unidad 2 · Almacenamiento primario y secundario

En esta sesión resolvemos, paso a paso, ejercicios del tipo: “Analizando memoria virtual y técnicas de administración de memoria” para que puedas enfrentar la tarea de la Unidad 2 con soltura.

Usa ← → para navegar · F para alternar pantalla completa.

¿Qué vamos a hacer en esta sesión?

En esta sesión pasamos de la teoría a la práctica. Trabajaremos con ejercicios resueltos paso a paso sobre los temas de Unidad 2:

Traducir direcciones lógicas a físicas con paginación y segmentación usando números concretos.
Simular algoritmos de reemplazo de páginas (FIFO, LRU, Óptimo) y contar cuántos fallos se producen para una secuencia dada.
Entender cómo los fallos de página afectan el rendimiento real de un sistema (thrashing, working set).
Mapear un byte dentro de un archivo a su bloque físico de disco usando la estructura de inodos.

Al terminar esta sesión serás capaz de resolver ejercicios de memoria virtual y sistemas de archivos con todos los pasos visibles y bien justificados.

Cómo se parte una dirección lógica en página + desplazamiento

Suposiciones del ejercicio base:

Direcciones lógicas de 16 bits (0 a 65.535).
Tamaño de página: 1 KB = 2¹⁰ bytes.
Número de páginas lógicas: 2¹⁶ / 2¹⁰ = 2⁶ = 64.
Cada marco físico también es de 1 KB.

Entonces, una dirección lógica de 16 bits se descompone en:

6 bits más significativos: número de página (p).
10 bits menos significativos: desplazamiento (d).

Ejemplo numérico:

Dirección lógica: 0x2AF3 (hex) = 0010 1010 1111 0011 (bin) Tomamos: p = 6 bits de más peso → 001010 = 0x0A = 10 d = 10 bits restantes → 1011110011 (bin) = 0x2F3 = 755 Interpretación: Página lógica #10, desplazamiento 755 dentro de la página.

Si la tabla de páginas dice que la página 10 está en el marco físico 3, la dirección física será: marco 3 · 1024 + 755.

Método para resolver cualquier ejercicio de paginación:
1) Identifica el tamaño de página y calcula cuántos bits necesita (log₂).
2) Los bits restantes son el número de página (p).
3) Consulta la tabla de páginas con p → obtén el marco físico.
4) Dirección física = marco × tamaño_página + desplazamiento (d).

Paginación simple con tabla de páginas dada

Datos del ejercicio:

Direcciones lógicas de 16 bits, páginas de 1 KB.
Tabla de páginas del proceso P:

Página lógica → Marco físico 0 → 5 1 → 9 2 → 1 3 → (no mapeada, genera fallo de página) 4 → 7

Traduce las siguientes direcciones lógicas:

a) 0x04F2
b) 0x11A0
c) 0x0D10

Resolución a) 0x04F2

0x04F2 = 0000 0100 1111 0010 (bin) p = 6 bits altos: 000001 = 1 d = 10 bits bajos: 0011110010 = 0x1F2 = 498 Tabla de páginas: p = 1 → marco 9 Dirección física: base marco 9 = 9 · 1024 = 9216 física = 9216 + 498 = 9714 (dec) = 0x25F2

Resolución b) y c):

b) 0x11A0 = 4512 dec p = 4512 / 1024 = 4 → marco 7 d = 4512 % 1024 = 416 física = 7 · 1024 + 416 = 7584 c) 0x0D10 = 3344 dec p = 3344 / 1024 = 3 → NO MAPEADA d = 3344 % 1024 = 272 → PAGE FAULT (página 3 no está en RAM)

Buen hábito de examen: escribe primero p y d, luego la fila de la tabla de páginas, y finalmente la dirección física. Evita hacer todo “de cabeza”.

Segmento + desplazamiento con base y límite

Idea clave:

Cada dirección lógica se compone de: <id_segmento, desplazamiento>.
La tabla de segmentos tiene, por entrada: base y límite.
Traducción:

Si desplazamiento < límite: dirección física = base + desplazamiento Si no: error: violación de segmento (segmentation fault)

Ejemplo de tabla de segmentos:

Una referencia lógica <1, 150> se traduce en: física = 2000 + 150 = 2150, siempre que 150 < 200.

A diferencia de la paginación, aquí los segmentos tienen significado semántico (código, datos, pila). Implicaciones: seguridad, protección, posibilidad de compartir código entre procesos.

Decidir si un acceso es válido y obtener la dirección física

Tabla de segmentos del proceso Q:

Evalúa las siguientes referencias lógicas:

a) <0, 120>
b) <1, 150>
c) <2, 199>

Resolución a):

<0, 120> → segmento = 0, desplazamiento = 120 Tabla: base(0) = 400 límite(0) = 300 Verificación: 120 < 300 → acceso VÁLIDO Dirección física: 400 + 120 = 520

Resolución b):

<1, 150> → segmento = 1, desplazamiento = 150 Tabla: base(1) = 1000 límite(1) = 100 Verificación: 150 >= 100 → acceso INVÁLIDO Conclusión: El proceso intenta leer/escribir fuera del segmento de datos. Esto genera una violación de segmento (segmentation fault).

Pide al grupo que discuta qué tipo de bugs en C/C++ se modelan como accesos fuera de segmento (overflows de buffer, escribir más allá de un array, etc.).

Cuánto “cuesta” realmente un fallo de página

Costos típicos de acceso:

Acceso a registro CPU: orden de nanosegundos.
Acceso a RAM: decenas de nanosegundos.
Acceso a disco SSD: microsegundos a milisegundos.
Acceso a disco HDD: varios milisegundos.

Un fallo de página implica al menos una lectura de bloque de disco (4 KB), muchas veces también una escritura si hay que expulsar una página sucia.

Modelo simplificado de tiempo:

Supón: T_hit_RAM = 100 ns T_pagefault = 8 ms = 8 000 000 ns Si tasa de fallos = 0.1% (0.001): T_efectivo ≈ 0.999 · 100 ns + 0.001 · 8 000 000 ns ≈ 100 ns + 8 000 ns ≈ 8 100 ns (81× más lento) Si tasa de fallos = 1%: T_efectivo ≈ 0.99 · 100 ns + 0.01 · 8 000 000 ns ≈ 100 ns + 80 000 ns ≈ 80 100 ns (801× más lento)

Pequeños incrementos en la tasa de fallos disparan el tiempo medio de acceso.

Esta es la base teórica para justificar, en tu informe, por qué un patrón de acceso “malo” (por ejemplo aleatorio sobre una estructura grande) degrada tanto el rendimiento.

FIFO, Óptimo y LRU sobre la misma secuencia

Datos:

Marcos de página disponibles: 3.
Secuencia de referencias (en términos de número de página):

Referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Marcos: [ _ , _ , _ ]

FIFO (First In, First Out):

Paso | Ref | Marcos | Fallo? -----+-----+------------- +-------- 1 | 1 | [1, _, _] | F 2 | 2 | [1, 2, _] | F 3 | 3 | [1, 2, 3] | F 4 | 4 | [4, 2, 3] | F (expulsa 1) 5 | 1 | [4, 1, 3] | F (expulsa 2) 6 | 2 | [4, 1, 2] | F (expulsa 3) 7 | 5 | [5, 1, 2] | F (expulsa 4) 8 | 1 | [5, 1, 2] | - 9 | 2 | [5, 1, 2] | - 10 | 3 | [3, 1, 2] | F (expulsa 5) 11 | 4 | [3, 4, 2] | F (expulsa 1) 12 | 5 | [3, 4, 5] | F (expulsa 2) Total fallos FIFO = 10

Óptimo (para comparar):

Idea: En un fallo, expulsar la página cuyo PRÓXIMO uso esté más lejos en el futuro, o que no se vuelva a usar. Se puede construir una tabla similar, pero indicando en cada expulsión qué página se usará más tarde. Actividad: - Rellenar la tabla para Óptimo. - Luego, comparar el número de fallos con FIFO. - Finalmente, discutir por qué LRU se acerca a Óptimo usando sólo información del pasado, no del futuro.

Este tipo de tabla es exactamente lo que se espera cuando se pide: “simula un algoritmo simple de reemplazo de páginas con pseudocódigo o trazas” en el nivel extendido de la tarea.

Pseudocódigo de LRU basado en contador de “último uso”

estructura Marco { entero pagina; entero ultima_vez_usada; } procedimiento simular_LRU(secuencia, num_marcos): marcos ← arreglo de tamaño num_marcos, inicializado con pagina = -1 tiempo ← 0 fallos ← 0 para cada ref en secuencia: tiempo ← tiempo + 1 // 1. ¿La página ya está en algún marco? si existe i tal que marcos[i].pagina = ref entonces marcos[i].ultima_vez_usada ← tiempo continuar con la siguiente ref fin si // 2. Fallo de página: buscar marco libre o expulsar LRU fallos ← fallos + 1 si existe i tal que marcos[i].pagina = -1 entonces // hay marco libre marcos[i].pagina ← ref marcos[i].ultima_vez_usada ← tiempo si no // seleccionar LRU idx_LRU ← índice i que minimiza marcos[i].ultima_vez_usada marcos[idx_LRU].pagina ← ref marcos[idx_LRU].ultima_vez_usada ← tiempo fin si fin para devolver fallos

En la parte extendida de la tarea, no es necesario implementar este pseudocódigo en un lenguaje real, pero sí mostrar que entiendes la lógica de cómo se elegiría la página a expulsar en cada paso.

Inodos, bloques de datos y estructuras indexadas

Componentes conceptuales:

Inodo: estructura que guarda metadatos (tamaño, propietario, tiempos) y punteros a bloques.
Bloques de datos: donde realmente se almacena el contenido del archivo.
Bloques de índices: usados para punteros indirectos (árboles, listas, etc.).
Bitmap de bloques libres: vector de bits para saber qué bloques están disponibles.

Sistemas modernos (ext4, NTFS) usan combinaciones de punteros directos, indirectos y estructuras tipo árbol B+ para soportar archivos enormes con buen rendimiento.

Ejemplo de inodo con punteros directos + indirectos:

Inodo #500: tamaño = 80 KB direct[0..11] = [1000, 1001, ..., 1011] indirect_simple = 2000 Bloque 2000 (indirecto): [3000, 3001, 3002, 3003, ...] Significado: - Los primeros 12 bloques de datos (48 KB) están en 1000–1011. - El resto de bloques se consultan a través del bloque 2000, que actúa como una “tabla extra” de punteros.

En ejercicios, te pueden pedir: “Dado un desplazamiento dentro del archivo, determina qué bloque de datos se usa y qué número de bloque físico corresponde”.

Mapear un desplazamiento lógico a un bloque de disco

Datos:

Tamaño de bloque de sistema de archivos: 4 KB.
Estructura de inodo:

Inodo #800: direct[0..2] = [500, 501, 502] (hasta 3 * 4KB = 12 KB) indirect_simple = 900 (tabla con más bloques) tamaño archivo = 20 KB

Pregunta: ¿en qué bloque físico se encuentra el byte en posición 16.000 (desplazamiento 16 KB)?

Resolución conceptual:

Calcula qué bloque lógico del archivo contiene ese desplazamiento: bloque_log = 16000 / 4096.
Calcula el desplazamiento dentro de ese bloque: off_bloque = 16000 % 4096.
Decide si ese bloque lógico está cubierto por punteros directos o indirectos.
Si es indirecto, localiza la entrada adecuada en el bloque índice.

Cálculo numérico rápido:

16000 / 4096 ≈ 3 con resto: 4096 * 3 = 12288 16000 - 12288 = 3712 → bloque_lógico = 3 → off_bloque = 3712 Bloques lógicos: 0 → direct[0] = 500 1 → direct[1] = 501 2 → direct[2] = 502 3 → (primera entrada de indirecto_simple) Por tanto: - El bloque físico es la primera entrada del bloque 900. - Dentro de ese bloque, el byte está a desplazamiento 3712.

Este tipo de razonamiento es el análogo, en archivos, a traducir direcciones lógicas en esquemas de paginación/segmentación.

Checklist para “Analizando memoria virtual y técnicas de administración de memoria”

Parte de la tarea	Qué debes entregar	De qué slide sacar ideas
1) Traducción en paginación	Tabla con varias direcciones, indicando p, d y dirección física o fallo.	Slides 3 y 4 (modelo + ejercicio guiado).
2) Ejemplo con segmentación	Tabla con base/límite, varios accesos; marcar válidos y fallos.	Slides 5 y 6 (modelo + ejercicio).
3) Escenario de fallos de página	Descripción de qué ocurre, conteo aproximado, impacto en T_efectivo.	Slide 7 (análisis de tiempos), Slide 8 si comparas algoritmos.
4) Comparación paginación vs segmentación	Texto corto (media página) con ventajas y desventajas.	Lo ya visto más tabla mental que puedes construir en clase.
5) Nivel extendido	Pseudocódigo de un algoritmo de reemplazo simple (LRU, FIFO).	Slide 9 (pseudocódigo LRU comentado).

Sugerencia para la sesión: trabajar en equipos pequeños, y luego socializar las soluciones para refinar el nivel de detalle y rigor que se espera en la entrega.

Cómo tus decisiones de E/S afectan a la memoria virtual

Patrón ineficiente (forzando fallos de página):

// Leer archivo de 1 GB en memoria de una sola vez (C#) byte[] buffer = File.ReadAllBytes("datos_grandes.bin"); // Procesar buffer de forma aleatoria Random r = new Random(); for (int i = 0; i < 10_000_000; i++) { int idx = r.Next(buffer.Length); byte b = buffer[idx]; // ... }

Cargar todo en un array gigante y acceder de forma aleatoria aumenta la probabilidad de expulsar constantemente páginas de ese array cuando la RAM es limitada.

Patrón eficiente (minimizando fallos):

// Leer y procesar el archivo en bloques de 4 KB (streaming) using (FileStream fs = new FileStream("datos_grandes.bin", FileMode.Open)) { byte[] bloque = new byte[4096]; int leidos; while ((leidos = fs.Read(bloque, 0, bloque.Length)) > 0) { // Procesar sólo los 'leidos' bytes de este bloque for (int i = 0; i < leidos; i++) { byte b = bloque[i]; // ... } } }

Aquí el working set se mantiene pequeño, compatible con pocos marcos, y los accesos son secuenciales, favoreciendo caches y TLB.

Conectar estas decisiones con experiencias reales: scripts que “se comen toda la RAM”, consultas de bases de datos mal diseñadas, etc.

Explorando sistemas de archivos con Python

Ejecuta este script en tu terminal: python explorar_fs.py

explorar_fs.py

import os, stat, time # Ruta a explorar (cambia a tu carpeta de proyecto) ruta = "." print(f"{'Nombre':<25} {'Tamaño (B)':>12} {'Tipo':<6} {'Últ. modificación'}") print("-" * 65) for entrada in sorted(os.scandir(ruta), key=lambda e: e.name): info = entrada.stat() tipo = "DIR " if entrada.is_dir() else "FILE" tamanio = info.st_size mod = time.strftime("%Y-%m-%d %H:%M", time.localtime(info.st_mtime)) print(f"{entrada.name:<25} {tamanio:>12} {tipo:<6} {mod}") print() # Calcular inodo (en Linux/macOS) o ID de archivo (Windows) for entrada in os.scandir(ruta): info = entrada.stat() print(f"Inodo/FileID de '{entrada.name}' : {info.st_ino}")

¿Qué observarás?

Nombre, tamaño en bytes y tipo de cada entrada del directorio.
Última fecha de modificación (metadato guardado en el inodo).
st_ino: el número de inodo real del sistema de archivos (en Linux/macOS; en Windows es el File Index del NTFS).

Desafío grupal:

Modifica el script para mostrar sólo archivos con extensión .py o .cs.
Ordena el resultado de mayor a menor por tamaño.
Calcula el tamaño total de la carpeta en KB.

Conexión con la teoría: cada llamada a os.stat() consulta al SO el inodo del archivo, que contiene los mismos campos de metadatos que vimos en el slide de sistemas de archivos.

Algoritmo de reemplazo LRU — código ejecutable en Python

Guarda como lru_sim.py y ejecuta: python lru_sim.py

lru_sim.py

def simular_lru(secuencia, num_marcos): marcos = {} # pagina -> tiempo_ultimo_uso fallos = 0 tiempo = 0 print(f"{'Paso':>4} {'Ref':>4} {'Marcos':<30} {'¿Fallo?'}") print("-" * 55) for ref in secuencia: tiempo += 1 if ref in marcos: marcos[ref] = tiempo # hit: actualiza tiempo estado = list(marcos.keys()) print(f"{tiempo:>4} {ref:>4} {str(estado):<30} (hit)") else: fallos += 1 if len(marcos) >= num_marcos: # expulsar la LRU (menor tiempo de último uso) lru_pag = min(marcos, key=marcos.get) del marcos[lru_pag] marcos[ref] = tiempo estado = list(marcos.keys()) print(f"{tiempo:>4} {ref:>4} {str(estado):<30} FALLO") print(f"\nTotal de fallos de página: {fallos}") return fallos # Misma secuencia del ejercicio de clase secuencia = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] simular_lru(secuencia, num_marcos=3)

Salida esperada (extracto):

Paso Ref Marcos ¿Fallo? ------------------------------------------------------- 1 1 [1] FALLO 2 2 [1, 2] FALLO 3 3 [1, 2, 3] FALLO 4 4 [2, 3, 4] FALLO 5 1 [3, 4, 1] FALLO 6 2 [4, 1, 2] FALLO 7 5 [1, 2, 5] FALLO 8 1 [1, 2, 5] (hit) 9 2 [1, 2, 5] (hit) 10 3 [2, 5, 3] FALLO 11 4 [5, 3, 4] FALLO 12 5 [5, 3, 4] (hit) Total de fallos de página: 9

Desafío: cambia num_marcos=4 y compara. ¿Cuántos fallos se producen? ¿Mejora respecto a FIFO (10 fallos)?

C# · ReadAllBytes vs. streaming por bloques

Crea un proyecto: dotnet new console -n benchmark_io · luego ejecuta: dotnet run

Program.cs

using System; using System.Diagnostics; using System.IO; // 1. Genera un archivo de prueba de ~5 MB string ruta = "test_5mb.bin"; if (!File.Exists(ruta)) { var rng = new Random(42); var data = new byte[5 * 1024 * 1024]; rng.NextBytes(data); File.WriteAllBytes(ruta, data); Console.WriteLine("Archivo de 5 MB creado.\n"); } var sw = new Stopwatch(); // --- Patrón INEFICIENTE: carga completa en RAM --- sw.Restart(); byte[] buffer = File.ReadAllBytes(ruta); long suma1 = 0; foreach (byte b in buffer) suma1 += b; sw.Stop(); Console.WriteLine($"ReadAllBytes → suma={suma1}, tiempo={sw.ElapsedMilliseconds} ms"); // --- Patrón EFICIENTE: streaming por bloques de 4 KB --- sw.Restart(); long suma2 = 0; using (FileStream fs = new FileStream(ruta, FileMode.Open, FileAccess.Read, FileShare.Read, bufferSize: 4096, useAsync: false)) { byte[] bloque = new byte[4096]; int leidos; while ((leidos = fs.Read(bloque, 0, bloque.Length)) > 0) { for (int i = 0; i < leidos; i++) suma2 += bloque[i]; } } sw.Stop(); Console.WriteLine($"Streaming 4KB → suma={suma2}, tiempo={sw.ElapsedMilliseconds} ms");

¿Por qué los tiempos difieren?

ReadAllBytes: el SO carga todo el archivo en RAM de una vez. Con archivos grandes, esto aumenta la presión sobre los marcos de página disponibles y puede provocar fallos si otros procesos también necesitan memoria.
Streaming 4 KB: el working set del proceso se mantiene pequeño (1 bloque activo). El SO puede mantener el resto en disco sin afectar la ejecución.

Desafío grupal:

Aumenta el archivo a 50 MB y repite. ¿Cambia la diferencia?
Mide con dotnet-counters:
dotnet-counters monitor --process-id <PID>
Observa GC Heap Size en cada patrón.

El comportamiento de GC Heap Size y los tiempos que miden conectan directamente con el modelo de fallos de página del slide 7.

Qué deberías ser capaz de hacer al terminar esta sesión

Traducir con seguridad direcciones lógicas en esquemas de paginación y segmentación con los datos de un enunciado.
Estimar el impacto de diferentes tasas de fallos de página sobre el tiempo medio de acceso a memoria.
Ejecutar la simulación LRU en Python y comparar los fallos obtenidos ante distintas cantidades de marcos.
Medir en C# la diferencia de tiempo entre leer un archivo completo vs. procesarlo por streaming, y relacionarlo con los modelos de memoria virtual vistos en clase.
Inspeccionar metadatos reales de archivos (inodos, tamaños, tiempos) desde la terminal con Python.

Los scripts explorar_fs.py, lru_sim.py y el proyecto benchmark_io (C#) son puntos de partida: modifícalos, experimenta con los parámetros y documenta tus observaciones en la tarea de Unidad 2.