Memoria virtual: hardware y fallo de página

💡 En simple

Piensa en una biblioteca enorme (el disco) y un escritorio pequeño (la RAM). No traes todos los libros al escritorio: solo los que estás usando ahora. Si necesitas uno que no está, te levantas a buscarlo (fallo de página), y si el escritorio está lleno devuelves otro (reemplazo). Funciona porque casi siempre trabajas con los mismos pocos libros por un rato: eso es la localidad. La memoria virtual es exactamente eso: cada programa cree que tiene toda la memoria para él, pero en la RAM solo están los pedazos que está usando.

🎯 Al terminar podrás

1. Explicar por qué la memoria virtual funciona a pesar de que el disco es miles de veces más lento (localidad).
2. Decir qué hace cada bit de la PTE (P, M, R) y qué pasa cuando P = 0.
3. Seguir el orden TLB → tabla → page fault y calcular el EAT con k niveles, con y sin fallos de página.
4. Enumerar los 6 pasos del page fault y distinguir page fault de segmentation fault.

Antes necesitas: Paginación simple: VPN y offset · Estados de un proceso (Bloqueado y Listo)

• Visual mira el diagrama o la tabla y explica qué cambia en cada paso
• Laboratorio sube la escalera: resuelto → completa → solo → variante
• Feynman explícalo en voz alta sin mirar y compara con la lista

Esta página cubre la parte de hardware y estructuras (Stallings §8.1). Lo básico de paginación, segmentación y la calculadora de tablas ya está en Paginación y Segmentación; aquí está lo que cambia cuando la memoria es virtual.

Las dos ideas que lo hacen posible

Stallings parte de dos características de la paginación y la segmentación:

1. Todas las referencias se traducen en tiempo de ejecución. Un proceso puede moverse de lugar en la RAM (o salir a disco y volver a otro sitio) sin que el programa lo note.
2. El proceso no necesita estar contiguo: se parte en páginas o segmentos repartidos por la memoria.

Juntas permiten algo que antes no se podía: ejecutar un proceso sin tener todas sus páginas en RAM. La parte que sí está cargada se llama el conjunto residente (resident set).

Lo que se gana:

• Más procesos en memoria a la vez: cada uno ocupa solo lo que usa, así que es más probable que siempre haya alguno listo para ejecutar.
• Un proceso puede ser más grande que toda la RAM. El programador ya no se preocupa por los overlays.

Por eso se habla de memoria real (la RAM) y memoria virtual (lo que ve cada proceso, respaldado en disco).

Localidad: por qué no colapsa

💡 En simple: cocinar en una zona de la cocina

Cuando cocinas no usas toda la cocina: usas la tabla, el cuchillo y la olla que tienes al lado, una y otra vez. Los programas hacen lo mismo:

• Localidad temporal: lo que usaste recién lo vuelves a usar pronto (la variable i de un for).
• Localidad espacial: lo que está al lado también lo vas a usar (a[0], a[1], a[2]…).

Por eso basta con tener en RAM pocas páginas: las de la «zona» actual.

Si cada referencia cayera en una página distinta, el sistema pasaría todo el tiempo trayendo páginas del disco. Eso se llama thrashing (hiperpaginación): el procesador está ocupado intercambiando páginas en vez de ejecutar instrucciones.

No pasa gracias al principio de localidad: las referencias de un proceso se agrupan. Durante un intervalo, el programa usa unas pocas páginas: un bucle, una función, un arreglo. Así el SO puede adivinar qué páginas van a hacer falta pronto.

Cómo leerlo: cada punto es una referencia a memoria. El eje horizontal es el tiempo y el vertical, la página tocada. Los puntos no se reparten por todo el eje: se amontonan en franjas de pocas páginas (las zonas sombreadas) y saltan de franja cada tanto. Mientras dura una franja, basta con tener esas 4 o 5 páginas en RAM.

Requisito	Por qué
Soporte de hardware para la paginación o segmentación	traducir cada dirección en software sería impracticable
Software del SO para mover páginas entre disco y RAM	las políticas de la página siguiente

La PTE cuando la memoria es virtual

💡 En simple: tres preguntas por página

Con memoria virtual, la ficha de cada página responde:

• P: ¿está en el escritorio (RAM)? Si es 0, hay que ir a buscarla a la estantería (disco): fallo de página.
• M: ¿la rayaste? Si sí, antes de devolverla hay que guardar los cambios en el disco. Si no, se descarta sin más: el disco ya tiene una copia idéntica.
• R: ¿la miraste hace poco? Sirve para decidir qué devolver cuando el escritorio está lleno.

Con paginación simple, la tabla solo decía «la página k está en el frame f». Con memoria virtual, la entrada necesita bits de control:

Bit	Nombre	Para qué
P	presente / válido	¿la página está en RAM? Si es 0, el acceso provoca un page fault
M	modificado (dirty)	¿se escribió desde que se cargó? Si sí, hay que escribirla al disco antes de reemplazarla; si no, se descarta sin costo
R / U	referenciado / uso	¿se accedió hace poco? Lo usa el algoritmo Clock y sus variantes
—	protección, compartición, bloqueo	lectura/escritura/ejecución, páginas compartidas, frames bloqueados (frame locking)
PFN	número de frame	dónde está, si P = 1

La dirección virtual se parte en nº de página | offset, y el nº de página elige una de estas entradas. Arriba de cada campo va la pregunta que responde y abajo, quién la usa.

Las tablas son enormes. Por ejemplo, Stallings toma la arquitectura VAX: 2 GB de espacio virtual con páginas de 512 B dan $2^{22}$ entradas por proceso. Por eso la tabla también vive en memoria virtual y aparecen dos estructuras:

• Tabla de dos (o más) niveles: un directorio raíz que siempre está en RAM y tablas de usuario que pueden estar en disco. Ejemplo típico: 32 bits con páginas de 4 KB y PTE de 4 B dan 10 | 10 | 12.
• Tabla invertida: una entrada por frame físico (no por página virtual). Se busca con un hash de (nº de página, PID), y las colisiones se encadenan. Su tamaño depende de la RAM, no del espacio virtual. La usan PowerPC, UltraSPARC e IA-64.

Las fórmulas y la calculadora están en Paginación § multinivel.

🔮 Predice antes de seguir

Una referencia falla en la TLB. ¿Significa eso que hay un page fault? Responde sí o no y justifica antes de seguir.

Ya tengo mi respuesta: comparar

No. Un fallo de TLB solo significa que la traducción no está en la caché. Se lee la PTE de la tabla en memoria:

• si P = 1, la página sí está en RAM: se carga la PTE en la TLB y se reintenta. Cuesta k accesos más a memoria, nada de disco;
• solo si P = 0 hay page fault, y recién ahí interviene el SO y el disco.

Confundir los dos es uno de los errores más comunes en las preguntas de EAT.

TLB: la caché de traducciones

💡 En simple: el orden en que se pregunta

1. ¿Está la traducción en la TLB (los favoritos)? → listo, en un paso.
2. Si no, se mira la tabla de páginas en RAM. ¿P = 1? → se arma la dirección y se anota en la TLB para la próxima.
3. Si P = 0 → fallo de página: el SO va al disco.

Cada paso es mucho más lento que el anterior: TLB en nanosegundos, RAM en ~100 ns, disco en milisegundos, es decir, decenas de miles de veces más lento.

Cada referencia a memoria virtual podría costar dos accesos: uno para leer la PTE y otro para el dato. Con tablas de k niveles, son k + 1. La TLB (Translation Lookaside Buffer) es una caché pequeña y asociativa con las PTE usadas hace poco.

Flujo completo (Stallings fig. 8.8):

1. La CPU genera la dirección virtual y busca la página en la TLB.
2. Acierto en la TLB: se arma la dirección física. Si el bloque está en la caché de datos, se lee de ahí; si no, de RAM.
3. Fallo en la TLB: se lee la PTE de la tabla en memoria.
   • Si P = 1, se actualiza la TLB y se reintenta.
   • Si P = 0, hay page fault. El SO toma el control, lee la página del disco, actualiza la tabla y el proceso vuelve a intentar la instrucción.

Asociativa quiere decir que el hardware compara el número de página con todas las entradas a la vez, porque la TLB no está indexada por página como la tabla.

Si la tabla de páginas cambia (cambio de proceso), la TLB se vacía, o cada entrada lleva un identificador de espacio de direcciones (ASID).

Cómo leerlo: son los tres caminos de la fig. 8.8. Hit (verde, arriba): la TLB da el marco. Miss: se lee la tabla en RAM y, si P = 1, la traducción se copia a la TLB (punteada). P = 0 (rojo): page fault. Los tiempos del dibujo (10 ns y 100 ns) son los de la página de paginación; el peldaño 1 de abajo usa una TLB de 20 ns.

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.

Fórmula del curso, con k niveles de tabla y TLB consultada siempre:

$$\text{EAT} = h\,(t_{TLB} + t_m) + (1-h)\,(t_{TLB} + k\,t_m + t_m)$$

Peldaño 1 · Resueltolee cada paso y su porqué

Resuelto: 1 nivel, TLB de 20 ns, memoria de 100 ns y h = 0.9

1. Acierto (90 %): TLB y luego el dato, 20 + 100 = 120 ns.
2. Fallo de TLB (10 %): TLB, luego la PTE (1 nivel) y luego el dato, 20 + 100 + 100 = 220 ns.
3. EAT = 0.9 · 120 + 0.1 · 220 = 108 + 22 = 130 ns.
4. Interpretación: sin TLB cada acceso costaría 200 ns (PTE + dato). La TLB ahorra un 35 %.

Cómo leerlo: es el peldaño 1 dibujado a escala. Cada barra suma lo que se paga, y un fallo de TLB agrega una lectura de la PTE (la parte del medio). El EAT es un promedio ponderado: queda mucho más cerca de la barra de acierto (130 ns) porque el acierto ocurre el 90 % de las veces.

Peldaño 2 · Complétalofaltan pasos clave: llénalos tú

Complétalo: 2 niveles, TLB de 10 ns, memoria de 100 ns y h = 0.95

El acierto cuesta 10 + 100 = 110 ns. Completa: ¿cuánto cuesta un fallo de TLB con dos niveles?, ¿y el EAT?

Comparar

Fallo: 10 + 2 · 100 + 100 = 310 ns, porque hay que leer dos PTE (directorio y tabla) antes del dato. EAT = 0.95 · 110 + 0.05 · 310 = 104.5 + 15.5 = 120 ns.

Peldaño 3 · Solosin ayuda; luego compara

Solo: 3 niveles, TLB de 5 ns, memoria de 80 ns y h = 0.98

Comparar

Acierto: 5 + 80 = 85 ns. Fallo: 5 + 3 · 80 + 80 = 325 ns. EAT = 0.98 · 85 + 0.02 · 325 = 83.3 + 6.5 = 89.8 ns. Aunque hay 3 niveles, el EAT queda cerca del acierto porque h es alto.

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

Variante: el mismo sistema del peldaño 1, pero con page faults

Supón que uno de cada millón de accesos (p = 10⁻⁶) produce un page fault que cuesta 8 ms en total. ¿Cuánto sube el EAT? ¿Qué p máxima permite que el EAT suba menos de un 10 %?

Comparar

• EAT ≈ (1 − p) · 130 ns + p · 8 000 000 ns ≈ 130 + 8 = 138 ns. Un solo fallo por millón de accesos encarece todo un 6 %.
• Para subir menos de un 10 % (EAT < 143 ns), se necesita p · 8 000 000 < 13, es decir, p < 1.6 · 10⁻⁶.
• Lección: el disco domina todo. Por eso importan tanto la localidad y una buena política de reemplazo, mucho más que unos nanosegundos de TLB.

Tamaño de página: un compromiso

Página más pequeña	Página más grande
✅ menos fragmentación interna	✅ la tabla es más chica (menos entradas)
✅ más páginas en RAM: se aprovecha mejor la localidad	✅ transferir un bloque grande del disco es más eficiente
❌ tablas más grandes, que pueden caer en disco	❌ más fragmentación interna; con páginas muy grandes, la página trae mucho que no se usa

La curva de fallos según el tamaño de página no es monótona (Stallings fig. 8.11):

• Con páginas muy chicas, caben muchas en RAM y hay pocos fallos.
• Al crecer, cada página trae datos lejanos a lo que se usa y los fallos suben.
• Cuando la página se acerca al tamaño del proceso, los fallos vuelven a bajar.

Cómo leerlo: con una cantidad fija de RAM, al agrandar la página primero suben los fallos (cada página trae datos que no se usan y desplaza a otras). En el extremo P, cuando una página es todo el proceso, vuelven a bajar.

Los tamaños típicos son 4 KB (x86), 8 KB (UltraSPARC) y las páginas grandes (2 MB o 1 GB en x86-64), que se usan para bases de datos y para reducir los fallos de TLB.

Segmentación con memoria virtual, y combinada

💡 En simple: un cuaderno con secciones, cada una en hojas sueltas

La versión combinada junta lo mejor de ambas:

• el programador ve secciones con sentido (código, datos, pila), como en la segmentación;
• cada sección se guarda en hojas iguales (páginas), así que no quedan huecos raros en la RAM.

Para traducir se pregunta dos veces: primero «¿qué sección?» (tabla de segmentos), y luego «¿qué hoja de esa sección?» (la tabla de páginas de esa sección).

• Segmentación sola: cada entrada de la tabla de segmentos también lleva un bit P y un bit M. Sirve para estructuras que crecen, para compilar módulos por separado, para compartir y para proteger.
• Segmentación + paginación (Stallings §8.1, «Combined Paging and Segmentation»):
  • El programador ve segmentos.
  • Cada segmento se divide en páginas del tamaño de un frame.
  • La dirección es (segmento, página, offset): la tabla de segmentos apunta a la tabla de páginas de ese segmento, y esa tabla da el frame.
  • Se ganan las ventajas de ambos: segmentos lógicos protegibles y compartibles, y sin fragmentación externa.
  • Lo usaba x86 en modo protegido. Linux de 64 bits deja la segmentación casi apagada (ver Segmentación § procesadores modernos).

Cómo leerlo: la dirección tiene tres partes. El segmento elige una fila de la tabla de segmentos, pero esa fila ya no da una base: da dónde está la tabla de páginas de ese segmento. La página elige el marco en esa tabla y el offset se copia, como en la paginación normal.

Paginación por demanda y el page fault paso a paso

💡 En simple: el fallo de página como pedido a bodega

Estás en la caja de una tienda y el producto no está en el mostrador (P = 0):

1. Avisas al encargado (trap al SO) y el cliente espera (el proceso queda bloqueado).
2. El encargado revisa que el producto exista en el catálogo. Si no existe, se cancela la venta (segmentation fault).
3. Si el mostrador está lleno, retira algo (la víctima). Si ese algo estaba abierto o modificado (M = 1), primero lo guarda en bodega.
4. Trae el producto de la bodega (el disco). Mientras tanto atiende a otro cliente (otro proceso).
5. Anota que ya está en el mostrador (P = 1) y el cliente repite la compra (se reinicia la instrucción).

Que un programa nuevo tenga muchos fallos al principio es normal: el mostrador empieza vacío.

Paginación por demanda (demand paging): una página se trae a RAM solo cuando se referencia por primera vez. El proceso arranca con casi nada cargado y acumula fallos al inicio; después la localidad los vuelve raros.

Qué hace el SO en un page fault (clase 09, diap. 76):

1. Trap. La referencia encuentra P = 0 y el hardware genera una interrupción hacia el SO. El proceso queda bloqueado.
2. ¿Es válida? El SO mira otra tabla (la del espacio de direcciones del proceso). Si la dirección es inválida, aborta el proceso (segmentation fault). Si es válida pero la página no está en memoria, sigue.
3. Busca un frame libre. Si no hay ninguno, la política de reemplazo elige una víctima. Si la víctima tiene M = 1, primero se escribe al disco.
4. Lee la página del disco al frame. Es una operación de E/S que tarda milisegundos, así que mientras tanto el SO ejecuta otro proceso.
5. Actualiza la tabla: P = 1 y el número de frame.
6. Reinicia la instrucción que falló. El proceso vuelve a Listo; cuando se ejecuta, la referencia ahora sí encuentra la página.

Cómo leerlo: sigue los números. ① El proceso referencia M. ② La tabla dice P = 0 y el hardware hace trap al SO. ③ El SO comprueba que M sea válida y la busca en el disco. ④ El disco la copia a un frame libre (si no hay, antes se elige una víctima). ⑤ El SO pone P = 1 y el frame en la tabla. ⑥ La instrucción se reinicia y ahora sí encuentra la página.

Fallo menor vs mayor

Linux distingue dos tipos:

• Fallo menor (minor fault): la página ya está en RAM (por ejemplo, la primera escritura sobre memoria recién pedida, que el kernel resuelve asignando un frame en ceros) o se puede reutilizar sin leer del disco.
• Fallo mayor (major fault): hay que leer del disco. Es el que cuesta milisegundos.

🔮 Predice antes de seguir

El programa reserva PAGESIZE × N bytes con malloc, después escribe un byte en cada página y finalmente las vuelve a leer todas. ¿En cuál de las tres fases aparecen unos N page faults?

Ya tengo mi respuesta: comparar

En la escritura. malloc solo reserva memoria virtual, así que no trae páginas a la RAM. La primera escritura sobre cada página produce un fallo por página: eso es la paginación por demanda. La lectura posterior no falla, porque las páginas ya están residentes. La medición de abajo lo confirma.

Medición: la paginación por demanda en acción

Basado en la actividad «Paging y TLB» de la guía de Valgrind. El programa reserva PAGESIZE × N bytes, los escribe y luego los lee, contando los fallos con getrusage (es lo mismo que mide perf stat -e page-faults). Página de 4096 B; resultado de la ejecución de prueba:

N=     1  malloc:+3  escribir:+0      leer:+0
N=     8  malloc:+3  escribir:+7      leer:+0
N=    32  malloc:+3  escribir:+31     leer:+0
N=    64  malloc:+3  escribir:+64     leer:+0
N=  1024  malloc:+3  escribir:+1024   leer:+0
N= 16384  malloc:+3  escribir:+16384  leer:+0

Cómo se lee:

• malloc no provoca fallos proporcionales a N: reservar memoria virtual no trae páginas a la RAM. Los 3 fallos fijos son de la propia biblioteca.
• La primera escritura sobre cada página provoca un fallo por página. Esa es la paginación por demanda: los frames se asignan recién cuando se tocan.
• Leer después no provoca ningún fallo, porque las páginas ya están residentes.
• Con N pequeño sale N − 1: la primera página ya estaba en RAM porque el heap se había inicializado antes. Desde unos 128 KB (N ≥ 32), malloc usa mmap (ver memoria de un proceso) y los fallos son exactamente N.

Son los números de la fila N = 1024 de la medición. Reservar no cuesta fallos; tocar cada página por primera vez cuesta uno; volver a tocarla, ninguno.

Pregunta de análisis: ¿por qué la segunda pasada no falla nunca?

Porque después de la primera pasada todas las páginas del arreglo están en el conjunto residente, y la máquina tiene RAM de sobra (no hay presión para reemplazarlas). Si el arreglo fuera más grande que la RAM disponible, la segunda pasada sí fallaría. Con un recorrido secuencial y reemplazo LRU, de hecho fallaría en cada página: es el peor caso de LRU con un patrón cíclico más grande que la memoria.

⚠️ Errores que cuestan puntos

• Decir «fallo de TLB, entonces page fault».Fallo de TLB significa ir a la tabla. Solo si ahí P = 0 hay page fault.
• En el EAT, olvidar sumar t_TLB en el caso de fallo, o contar un solo acceso a tabla con k niveles.Fallo de TLB = t_TLB + k · t_m + t_m. Escribe la fórmula, define cada variable y recién después sustituye.
• Responder page fault cuando la dirección no pertenece al proceso.Si la dirección es inválida, el resultado es segmentation fault y el proceso se aborta. El page fault es para direcciones válidas que no están en RAM.
• Creer que una víctima con M = 0 también se escribe al disco.Con M = 0 el disco ya tiene una copia idéntica: se descarta sin E/S.
• Decir que la tabla invertida crece con el espacio virtual.Tiene una entrada por frame, así que su tamaño depende de la RAM.

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. ¿Qué permite ejecutar un proceso sin cargar todas sus páginas?

a) Que las direcciones se traduzcan en ejecución y el proceso no necesite estar contiguob) El buddy systemc) La compactaciónd) Los overlays

2. El bit M (dirty) de una página víctima vale 0. Al reemplazarla…

a) hay que escribirla al discob) se puede descartar sin escribirlac) se bloquea el framed) se produce un page fault

3. Una tabla de páginas invertida tiene una entrada por…

a) página virtual de cada procesob) frame de memoria físicac) segmentod) entrada de TLB

4. En un page fault, ¿qué hace el proceso mientras se lee la página del disco?

a) Sigue ejecutandob) Queda bloqueado; el SO ejecuta otro procesoc) Hace busy waitingd) Se aborta

5. Thrashing es…

a) tener muchas páginas compartidasb) pasar más tiempo intercambiando páginas que ejecutandoc) un fallo de TLBd) fragmentación externa

6. ¿Por qué funciona la memoria virtual pese a que el disco es miles de veces más lento?

a) Porque la TLB es grandeb) Por el principio de localidad: las referencias se agrupanc) Porque el disco es SSDd) Porque no hay page faults

7. Páginas más grandes implican…

a) tablas más grandesb) más fragmentación interna y tablas más chicasc) menos fragmentación internad) más entradas en la TLB

🗣️ Explícalo tú (Feynman)

Explica a un amigo que no estudia computación por qué un programa de 8 GB puede correr en una máquina con 4 GB de RAM, y qué pasa exactamente cuando toca una parte que no está cargada.

Dilo en voz alta o escríbelo en 4–5 líneas, sin mirar la página. Después revisa qué te faltó.

Tu explicación debería mencionar…

• Solo hace falta en RAM la parte que se usa ahora, porque por la localidad el programa trabaja con pocas páginas a la vez.
• Cada página tiene un bit P. Si vale 0, el hardware hace un trap al SO: eso es el page fault.
• El SO verifica que la dirección sea válida, busca un marco (o una víctima, que se escribe solo si M = 1), lee la página del disco, pone P = 1 y reinicia la instrucción.
• Mientras el disco trabaja (milisegundos), el proceso está bloqueado y corre otro.

Error típico al explicarlo: decir que la memoria virtual «usa el disco como RAM» sin explicar que funciona solo porque la localidad hace que los fallos sean raros.

📈 ¿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 ·Stallings 9e §8.1 (Hardware and Control Structures) · sem_9/Sem9_09-OST-Memory.pdf (diap. 9–14, 48–76) · sem_9/10-OSL-Valgrind.pdf («Paging y TLB») · Prueba propia: pagefaults.c (getrusage, ejecución de prueba)