Ejercicios resueltos: Virtual Memory

💡 En simple

Casi todas estas preguntas se resuelven con tres ideas:

1. La dirección se parte en dos: «qué página» (los bits altos) y «dónde dentro de la página» (el offset, los bits bajos). El offset no cambia al traducir.
2. Contar bits es sacar logaritmos en base 2: 1 KB = $2^{10}$, así que el offset tiene 10 bits.
3. Una tabla tiene una entrada por página, y su tamaño es entradas × bytes por entrada.

🎯 Al terminar podrás

1. Calcular los bits de VPN, PFN, offset y PTE de un esquema de paginación.
2. Traducir direcciones por segmentación (con segfault) y por paginación (con page fault), en decimal y en binario.
3. Contar los page faults de un recorrido de matriz según el orden (filas o columnas).
4. Diseñar un esquema de varios niveles y calcular accesos a memoria y EAT con TLB.

Antes necesitas: Paginación · Segmentación · TLB y EAT

• Examen cronométrate y no abras la solución hasta terminar
• Laboratorio sube la escalera: resuelto → completa → solo → variante

Modo examen

Estas son hojas de análisis como las del LC3 (3 pts cada pregunta). Hazlas cronometradas (unos 12 minutos por pregunta), en papel y sin abrir la solución hasta terminar. Al corregir, clasifica cada error: ¿conceptual (no sabías la regla), procedimental (sabías la regla pero te saltaste un paso) o de interpretación (leíste mal el enunciado)? Repasa según el tipo: si es conceptual, vuelve a la página del tema; si es procedimental, a la escalera de práctica.

Resueltas en la clase del 10/10

La profesora resolvió P1 a P5 en vivo, y sus resultados coinciden con los de esta página. Su método paso a paso, sus advertencias (segmentation fault vs page fault, revisar siempre la tabla antes de traducir) y sus pistas para el LC3 están en Clase del 10/10.

Pregunta 1 · Paginación simple

$2^{32}$ bytes de memoria física, páginas de $2^{10}$ bytes y $2^{16}$ páginas virtuales.

Solución

Pregunta	Cálculo	Respuesta
Bits de la dirección virtual	16 bits de página + 10 de offset	26 bits
Bytes de un frame	igual que la página	$2^{10}$ = 1024 B
Bits de frame en la dirección física	32 − 10	22 bits
Entradas de la tabla	una por página virtual	$2^{16}$ = 65 536
Bits por PTE (con bit de validez)	22 de frame + 1 V	23 bits (en la práctica se redondea a 3 B o 4 B)

Peldaño 4 · Variantecambia una condición: ¿sigue valiendo lo anterior?

Variante de P1: la misma memoria y el mismo espacio virtual, pero con páginas de 4 KB

El espacio virtual sigue siendo de 2²⁶ bytes (26 bits) y la RAM de 2³². ¿Qué cambia?

Comparar

• Offset: 2¹² → 12 bits. Páginas virtuales: 2²⁶ / 2¹² = 2¹⁴ = 16 384 entradas.
• Bits de frame: 32 − 12 = 20. PTE con V: 21 bits.
• Lección: con páginas 4 veces más grandes, la tabla tiene 4 veces menos entradas y cada PTE ocupa 2 bits menos. Es el compromiso del tamaño de página: tablas más chicas a cambio de más fragmentación interna.

Pregunta 2 · Segmentación

Segmento	Base	Longitud
0	660	248
1	1752	422
2	222	198
3	996	604

Regla: si offset < longitud, la dirección física es base + offset; si no, segmentation fault.

Solución

Dirección (seg, offset)	¿offset < longitud?	Física
1. (0, 198)	198 < 248 ✔	858
2. (2, 156)	156 < 198 ✔	378
3. (1, 530)	530 ≥ 422 ✘	segfault
4. (3, 444)	444 < 604 ✔	1440
5. (0, 222)	222 < 248 ✔	882

Ojo con el borde: el offset válido va de 0 a longitud − 1. Con (0, 248) ya sería segfault.

Peldaño 4 · Variantecambia una condición: ¿sigue valiendo lo anterior?

Variante de P2: (2, 198) y (3, 603)

Comparar

• (2, 198): 198 no es menor que 198 → segmentation fault. Es el borde: el último offset válido es 197.
• (3, 603): 603 < 604 → física = 996 + 603 = 1599.

Prueba otras direcciones en el traductor (carga tu propia tabla):

Traducción con segmentación (dirección de 16 bits)

Los 2 bits altos eligen el segmento y los 14 bajos son el offset. La MMU comprueba offset < limit y calcula física = base + offset. Es la tabla de la diapositiva 37.

Dirección virtual (hex)

0x02400x02440x03600x40500x80100x0900

0

1

0

0

0

0

0

0

0

1

0

1

0

0

0

0

segmento = 01₂ = 1offset = 0x0050

Seg	Nombre	Base	Límite
0	code	0x4000	0x0800
1	data	0x4800	0x1400
2	shared	0xF000	0x1000
3	stack	0x0000	0x3000

offset 0x0050 < límite 0x1400 ✔ → física = 0x4800 + 0x0050 = 0x4850

Pregunta 3 · Traducción binaria de 0001010010111010

La dirección tiene 16 bits y vale 5306 en decimal.

(1) Paginación con páginas de 256 B y frame = página / 4

• 256 B = $2^8$, así que el offset tiene 8 bits y la página los 8 bits altos.

0001 0100 | 1011 1010
 página        offset
 = 20          = 186

• Frame = 20 / 4 = 5 = 00000101.
• Dirección física = frame ‖ offset = 00000101 10111010, que vale 5 · 256 + 186 = 1466.

(2) Segmentación con segmentos de hasta 1 kB y base = 22 + 4096·n

• 1 kB = $2^{10}$, así que el offset tiene 10 bits y el segmento los 6 bits altos.

000101 | 0010111010
 seg       offset
 = 5       = 186

• Base del segmento 5 = 22 + 4096 · 5 = 20 502.
• Dirección física = 20 502 + 186 = 20 688 = 0101000011010000.
• Como la base no es múltiplo de una potencia de 2, aquí sí hay que sumar, no concatenar. Es la diferencia clave con la paginación.

Cómo leerlo: arriba, la dirección cortada para paginación (8 | 8); abajo, para segmentación (6 | 10). Los colores marcan qué bits son número de página o segmento y cuáles son offset.

Pregunta 4 · Tabla de páginas con V/R/M

Páginas de 1024 bytes.

Página	Valid	Ref	Modify	Frame
0	1	1	0	4
1	1	1	1	7
2	0	0	0	—
3	1	0	0	2
4	0	0	0	—
5	1	0	1	0

Cómo se traduce (descripción detallada)

1. La CPU genera la dirección virtual v. La MMU la divide en página p = v / 1024 (los bits altos) y offset d = v mod 1024 (los 10 bits bajos).
2. Busca p en la TLB. Si no está, lee la PTE p de la tabla, que está en memoria y se ubica con el registro base de la tabla del proceso.
3. Si Valid = 0 → page fault. El SO verifica que la dirección sea legal, busca un frame (reemplazando si hace falta, y escribiendo la víctima si tiene M = 1), trae la página del disco, actualiza la PTE y reinicia la instrucción.
4. Si Valid = 1 → dirección física = frame × 1024 + d. El hardware pone Ref = 1, y Modify = 1 si es una escritura.

Solución: 1052 → 7196 · 2221 → page fault · 5499 → 379

Virtual	Página = v / 1024	Offset	PTE	Física
1052	1	28	V = 1, frame 7	7 · 1024 + 28 = 7196
2221	2	173	V = 0	page fault (no hay dirección física hasta traer la página)
5499	5	379	V = 1, frame 0	0 · 1024 + 379 = 379

Pregunta 5 · Recorrido por columnas

#define Size 64
int A[Size][Size], B[Size][Size], C[Size][Size];
for (j = 0; j < Size; ++j)
    for (i = 0; i < Size; ++i)
        C[i][j] = A[i][j] + B[i][j];

Datos:

• Páginas de 1 KB = 256 enteros = 4 filas de la matriz, que se guarda por filas: la página k contiene las filas 4k a 4k + 3.
• Cada matriz ocupa 16 páginas.
• Hay 4 frames: uno para el código y 3 para los datos.

1. ¿Con qué frecuencia hay page faults?

Con j afuera e i adentro, el bucle interno baja por una columna: cambia de fila en cada iteración y de página cada 4 iteraciones. Con solo 3 frames de datos, cada vez que i entra a una página nueva de A, de B y de C, las 3 páginas anteriores ya no sirven y hay que traer las 3 nuevas:

• 3 fallos cada 4 iteraciones.
• Por columna: 16 grupos de filas × 3 = 48 fallos.
• En total: 64 columnas × 48 = 3072 fallos en 64 × 64 = 4096 iteraciones, es decir 12 288 referencias. Un fallo cada 4 referencias.

Al pasar a la columna siguiente se vuelve a la fila 0, cuya página ya fue expulsada, así que nunca se reaprovecha nada entre columnas.

Lo verifiqué simulando las 12 288 referencias con 3 frames: 3072 fallos, tanto con LRU como con FIFO.

2 y 3. Modificación y nueva frecuencia

Intercambiar los bucles para recorrer por filas:

for (i = 0; i < Size; ++i)
    for (j = 0; j < Size; ++j)
        C[i][j] = A[i][j] + B[i][j];

Ahora se recorren las 256 posiciones de cada página seguidas (4 filas × 64 columnas) antes de pasar a la siguiente:

• 3 fallos cada 256 iteraciones;
• 16 páginas × 3 matrices = 48 fallos en total, uno cada 256 referencias.

La simulación confirma 48. Es una mejora de 64×: la misma localidad espacial que hace rápida a la caché.

Cómo leerlo: cada franja horizontal es una página de la matriz (4 filas). Por columnas, la flecha roja atraviesa las 16 páginas en cada columna, y con 3 marcos ninguna sobrevive hasta la columna siguiente. Por filas, se termina la página verde entera antes de pasar a la siguiente.

Pregunta 6 · 8 GB de RAM, páginas de 8 kB, PTE de 4 B y direcciones de 46 bits

1 y 2. Niveles y esquema de la tabla

• Offset: 8 kB = $2^{13}$, así que 13 bits.
• VPN: 46 − 13 = 33 bits.
• Entradas por tabla (cada tabla ocupa una página): 8 kB / 4 B = $2^{11}$, así que 11 bits por nivel.
• Niveles: ⌈33 / 11⌉ = 3 niveles.

Arriba de cada campo van sus posiciones de bit. Cada campo de 11 bits elige una de las 2048 entradas de la tabla de su nivel.

• Frames: 8 GB / 8 kB = $2^{33}/2^{13}$ = $2^{20}$, así que el número de frame tiene 20 bits.
• Campos de la PTE (32 bits): 20 bits de frame + valid/presente + referenciado (uso) + modificado (dirty) + protección (R/W/X) + usuario/supervisor + caché deshabilitada + global… Quedan bits libres para el SO.

3 y 4. Accesos a memoria por cada lectura o escritura de una palabra

• Sin TLB: 3 accesos a las tablas (un nivel cada uno) + 1 al dato = 4 accesos.
• Con TLB:
  • mejor caso, acierto en la TLB: 1 acceso (solo el dato);
  • peor caso, fallo en la TLB: 4 accesos;
  • si además la página no está en RAM, hay un page fault con E/S de disco, de un orden de magnitud distinto.

5. TLB de 10 ns, memoria de 50 ns: ¿qué hit ratio da 61 ns?

Según el enunciado, todo acceso consulta la TLB (10 ns) y accede al dato (50 ns). Un fallo de TLB agrega la caminata por la tabla:

$$\text{EAT} = 10 + 50 + (1-h)\cdot(3 \cdot 50) = 60 + 150\,(1-h)$$

• Para 61 ns: $150(1-h) = 1$, así que $h = 1 - \tfrac{1}{150} \approx$ 0.9933 (99.3 %).
• Con h = 0.5: EAT = 60 + 75 = 135 ns, frente a 200 ns sin TLB (4 × 50). Aun con la mitad de aciertos, la TLB ahorra un 32.5 %.

Nota: si se modela la tabla como un solo acceso en el fallo de TLB (lo que suele hacer el material de clase), EAT = 60 + 50(1 − h). Entonces h = 0.98 para 61 ns, y con h = 0.5 da 85 ns frente a 100 ns sin TLB. Con los 3 niveles del inciso 1, la respuesta coherente es 0.9933. Declara el modelo.

TLB: tiempo efectivo de acceso

Sin TLB, cada referencia cuesta k accesos a la tabla + 1 al dato. Con TLB: $\text{EAT} = h\,(t_{TLB} + t_m) + (1-h)\,(t_{TLB} + k\,t_m + t_m)$

Hit ratio TLB h: 0.98t TLB: 1 nst memoria: 100 nsNiveles de tabla k: 1

Sin TLB

200.0 ns

Con TLB (EAT)

103.0 ns

Ideal (solo el dato)

100.0 ns

Acierto TLB101 ns

Fallo TLB (página en RAM)201 ns

Penalización vs ideal+3.0 %

Si la página no está en RAM (bit P = 0), hay un page fault: el SO bloquea al proceso, lee la página de disco (milisegundos, órdenes de magnitud más que todo lo anterior), actualiza la tabla y lo pasa a Listo.

⚠️ Errores que cuestan puntos

• Traducir sin revisar el bit de validez de la tabla.Primero la página, después la tabla (¿válida?) y recién después la física. P4 tiene un page fault escondido.
• Aceptar offset = longitud como válido en segmentación.Es válido solo si offset < longitud.
• Dar el EAT sin decir cuántos accesos cuesta un fallo de TLB.Declara el modelo (1 acceso o k niveles). En P6 cambia la respuesta: 0.9933 contra 0.98.

📈 ¿Qué tan bien lo dominas?

Elige pensando en lo que hiciste, no en lo que leíste. Para marcar 3 tienes que haber resuelto un ejercicio nuevo sin pistas y haberlo justificado. Si solo lo leíste y sientes que «ya entendí», todavía es un 1.

0No lo reconozco o lo confundo con otro tema1Lo entiendo leyendo, pero no lo aplico solo2Resuelvo ejercicios parecidos a los vistos, con alguna pista3Resuelvo uno nuevo sin ayuda y justifico cada paso4Lo transfiero: comparo alternativas y veo casos límite

Fuente ·sem_9/11-OSL-Ejercicios_Virtual_Memory.pdf · Soluciones propias; P3, P4 y P5 verificadas con un script (simulación de las 12 288 referencias de P5 con LRU y FIFO)