Paginación y tablas multinivel

Nota

La diapositiva de memoria de 2026-II termina en segmentación («more about pages in next session»). Aun así, la paginación cayó en el E1 2022 y en el E1 2025-2, así que conviene dominar el cálculo.

🎯 Al terminar podrás

1. Partir una dirección en VPN | offset (offset = log₂ del tamaño de página) y traducirla a física concatenando el PFN.
2. Calcular bits de VPN y PFN, número de entradas y tamaño de la tabla (entradas × tamaño de PTE).
3. Diseñar una tabla de dos niveles (cuántos bits por nivel) y decir cuándo ocupa menos que la de un nivel.
4. Reconocer cuándo la respuesta es page fault (P = 0) en vez de una dirección física.

Antes necesitas: Potencias de 2 y conversión binario ↔ hexadecimal · MMU y dirección lógica vs física

• Visual mira el diagrama o la tabla y explica qué cambia en cada paso
• Laboratorio sube la escalera: resuelto → completa → solo → variante
• Examen cronométrate y no abras la solución hasta terminar

Paginación simple (Stallings §7.3)

💡 En simple: un libro cortado en hojas iguales

Cortas el programa en hojas del mismo tamaño (páginas) y la RAM en casillas del mismo tamaño (marcos). Cada hoja va en cualquier casilla libre, aunque no estén juntas. Una lista (la tabla de páginas) dice en qué casilla quedó cada hoja.

Ejemplo trivial con números decimales (en la realidad son potencias de 2, pero la idea es la misma): páginas de 100 posiciones.

• La dirección 250 es la página 2 (250 ÷ 100) y el offset 50 (el resto).
• La tabla dice que la página 2 está en el marco 7.
• Física = 7 × 100 + 50 = 750.

Fíjate: el offset (los dos últimos dígitos, «50») no cambia. Solo se reemplaza el número de página por el de marco. Con potencias de 2 pasa lo mismo, pero con bits en lugar de dígitos.

La memoria física se divide en marcos (frames) pequeños y de tamaño fijo, y cada proceso en páginas del mismo tamaño. Un proceso ocupa marcos no contiguos, cualesquiera que estén libres.

Ejemplo (fig. 7.9), con 15 marcos:

1. A ocupa los marcos 0–3, B los 4–6 y C los 7–10.
2. B sale (swap out).
3. Llega D, que necesita 5 páginas: recibe los marcos 4, 5, 6, 11 y 12, que no son contiguos, y no importa.

Cómo leerlo: cada fila de la tabla de D es una flecha hacia un marco. Las páginas de D son consecutivas (0, 1, 2, 3, 4), pero sus marcos no (4, 5, 6, 11, 12). Nadie lo nota: el programa solo ve sus páginas, y la tabla se encarga del resto. Como cualquier marco libre sirve, nunca queda un hueco «demasiado chico»: no hay fragmentación externa.

• Sin fragmentación externa, porque cualquier marco sirve. La interna se limita a una fracción de la última página.
• El SO mantiene una lista de marcos libres y una tabla de páginas por proceso (página → marco).
• Es transparente para el programador, el ensamblador y el linker: la dirección lógica (página, offset) es la dirección relativa.

Antes de calcular: bytes para tamaños, bits para direcciones

Este es el error de unidades más común. Las dos cosas aparecen juntas («páginas de 4 KB, 12 bits»), pero miden cosas distintas:

• Los tamaños (de página, de RAM, de tabla) se miden en bytes. La memoria es una fila de casillas de 1 byte, cada una con su número.
• Los campos de una dirección (offset, VPN, PFN) se miden en bits: cuántos bits hacen falta para escribir el número de una casilla.
• La relación: si algo tiene 2ⁿ bytes, numerarlos necesita n bits. Es decir, bits = log₂(tamaño en bytes).

Cómo leerlo: a la izquierda, cuánto mide cada cosa; a la derecha, cuántos bits hacen falta para elegir un byte dentro de ella. Se pasa de un lado al otro con log₂. Una frase como «4 GB son 32 bits» es una abreviatura de «un espacio de 4 GB necesita direcciones de 32 bits».

¿GB o GiB? En rigor, 1 GB decimal son 10⁹ B y 1 GiB son 2³⁰ B, un 7 % más. En este curso, como en Stallings, KB, MB y GB significan siempre potencias de 2: 4 KB = 4096 B, no 4000. Si un enunciado no aclara, asume potencias de 2.

Traducción sin sumas: como el tamaño de página es una potencia de 2, basta concatenar el marco con el offset:

$$\underbrace{\text{VPN}}_{n_v - o \text{ bits}} \;\big|\; \underbrace{\text{offset}}_{o = \log_2 \text{página}} \;\xrightarrow{\text{tabla}}\; \underbrace{\text{PFN}}_{n_f - o \text{ bits}} \;\big|\; \text{offset}$$

Ejemplo del libro: direcciones de 16 bits y páginas de 1 KB, así que el offset tiene 10 bits y la página 6 bits (64 páginas).

• La dirección relativa 1502 = 000001 0111011110 es la página 1, offset 478.
• Si la tabla dice página 1 → marco 6 (000110), la dirección física es 000110 0111011110 = 6·1024 + 478 = 6622.

Cómo leerlo: la dirección se corta en dos. La parte alta (página) entra a la tabla y sale cambiada por el marco. La parte baja (offset) baja derecho, sin tocarse. Pegar marco y offset es lo mismo que calcular marco · tamaño + offset, pero sin sumar: solo se concatenan bits.

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

Resuelto: el ejemplo del libro (1502 → 6622)

Es el ejemplo de arriba. Repásalo con este orden fijo, que sirve para cualquier traducción:

1. Bits de offset = log₂(página) = log₂(1024) = 10.
2. Partir la dirección: VPN = 1502 ÷ 1024 = 1 y offset = 1502 mod 1024 = 478.
3. Mirar la tabla: página 1 → marco 6, con P = 1. Si P = 0, la respuesta sería page fault y aquí terminaría.
4. Armar la física: 6 · 1024 + 478 = 6622. En binario es solo concatenar 000110 | 0111011110.

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

Complétalo: direcciones de 16 bits, páginas de 512 B, dirección 0x1A3C; la tabla dice página 13 → marco 5

El paso 1 ya está: el offset tiene 9 bits (2⁹ = 512). Completa los pasos 2 a 4: calcula el VPN, el offset y la dirección física, en decimal y en hexadecimal.

Comparar

• 0x1A3C = 0001 1010 0011 1100 = 6716.
• Los 9 bits bajos son 0 0011 1100, así que el offset = 60. Los 7 bits altos son 0001101, así que el VPN = 13. Comprobación: 6716 = 13 · 512 + 60.
• Física = 5 · 512 + 60 = 2620 = 0000101 | 000111100 = 0x0A3C.

Ojo: como 9 no es múltiplo de 4, el límite entre VPN y offset corta un dígito hexadecimal. Por eso conviene pasar a binario.

Peldaño 3 · Solosin ayuda; luego compara

Solo: 32 bits y páginas de 4 KB

La tabla tiene: VPN 0x12345 → PFN 0x00ABC con P = 1, y VPN 0x00010 con P = 0. Traduce 0x12345678 y 0x00010FFF.

Comparar

• Offset de 12 bits = 3 dígitos hexadecimales. 0x12345678 → VPN 0x12345, offset 0x678 → física 0x00ABC678.
• 0x00010FFF → VPN 0x00010, que tiene P = 0 → page fault. No se calcula ninguna dirección física. Es la trampa que marcó la profesora: «primero la página, después la tabla, después la física».

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

Variante: la misma dirección 0x12345678, pero con páginas de 8 KB

¿Sigue siendo 0x12345 el VPN? Calcula el VPN y el offset nuevos.

Comparar

No. Ahora el offset tiene 13 bits, no 12, así que el corte ya no cae entre dígitos hexadecimales. Offset = 0x12345678 & 0x1FFF = 0x1678 y VPN = 0x12345678 >> 13 = 0x91A2 (37282). Lección: el VPN depende del tamaño de página. Primero calcula los bits de offset y después corta.

La entrada de la tabla (PTE)

💡 En simple: la ficha de cada página

Cada fila de la tabla es una ficha con datos de una página:

• ¿Dónde está? El número de marco.
• ¿Está en RAM ahora? El bit P (si es 0, hay que traerla del disco).
• ¿La modificaste? El bit M (si no la tocaste, al sacarla no hace falta guardarla).
• ¿La usaste hace poco? El bit R (sirve para decidir a quién sacar).
• ¿Qué se puede hacer con ella? Los permisos de lectura, escritura y ejecución.

Campo	Para qué
P / V (presente o válido)	¿la página está en RAM? Si no, se produce un page fault
M / D (modificado o dirty)	¿se escribió? Si no, al reemplazarla no hace falta escribirla a disco
R / A (referenciado)	lo usan los algoritmos de reemplazo
Protección y compartición	lectura, escritura, ejecución y usuario/kernel
Número de marco (PFN)	la traducción propiamente dicha

Cada caja es un campo de la misma fila. Arriba va la pregunta que responde y abajo quién la usa. El hardware mira primero P: si vale 0, los demás campos no sirven.

Normalmente el número de página (n bits) es más largo que el número de marco (m bits): n > m, porque un proceso puede tener más páginas que marcos haya en la RAM.

Cuánto mide una PTE: de bits a bytes

La PTE es el único lugar donde se pasa de bits a bytes. Se arma en bits, juntando sus campos (PFN + bits de estado), pero la tabla se mide en bytes: tamaño de la tabla = número de entradas × bytes por PTE. Por eso se divide entre 8 (1 byte = 8 bits).

• Se redondea hacia arriba (⌈ ⌉): la memoria se lee por bytes enteros, no hay «2,6 bytes». Si sobran bits, se rellenan: eso es el pad (padding), bits que no guardan nada.
• En hardware real el diseño va al revés: primero se fija el tamaño de la PTE (4 B en x86 de 32 bits, 8 B en x86-64) y después se reparten los campos. Los bits que sobran no se llaman pad sino libres (available, AVL), y el SO puede usarlos.
• En los ejercicios cada enunciado inventa una máquina y dice cuántos bits de estado hay. Algunos redondean al byte (21 bits → 3 B) y otros a la potencia de 2 (21 bits → 4 B). Si no lo dice, aclara qué supuesto usas.

Cómo leerlo: arriba, los 21 bits que de verdad se usan. En el medio, la misma PTE guardada en 3 bytes: los 3 bits rayados del final son el pad. Abajo, la variante de 4 bytes: sobran 11 bits, que una máquina real dejaría libres para el SO.

Tablas grandes: multinivel e invertidas

💡 En simple: el índice de un libro en dos niveles

Una tabla de páginas de un solo nivel tiene una fila por cada página posible, aunque el proceso no use casi ninguna. Es como imprimir una guía telefónica con todos los números posibles, aunque la mayoría no exista.

Multinivel es como edificio → piso → oficina: primero un índice chico (los pisos), y solo se crean las hojas de los pisos que de verdad se usan.

Ejemplo trivial (32 bits, páginas de 4 KB, PTE de 4 B):

• Un nivel: 2²⁰ filas × 4 B = 4 MB de tabla por proceso, siempre, aunque el programa sea diminuto.
• Dos niveles (10 | 10 | 12): cada tabla de segundo nivel cubre 1024 páginas × 4 KB = 4 MB de memoria. Un proceso que usa 2 MB necesita la raíz (4 KB) más una tabla de segundo nivel (4 KB) = 8 KB, en lugar de 4 MB.

La tabla invertida da vuelta la pregunta: en vez de «¿dónde está cada página de cada proceso?» guarda «¿quién ocupa cada marco?», como la lista de asientos de un cine. Si la RAM tiene 8 marcos, la tabla tiene 8 filas, haya los procesos que haya.

Cómo leerlo: el mismo proceso de 2 MB (512 páginas) con las dos organizaciones. Con un nivel, la tabla trae una fila para cada una de las 2²⁰ páginas posibles; solo la franja verde de arriba se usa, pero todo lo rayado también ocupa memoria. Con dos niveles, los primeros 10 bits eligen una fila de la raíz y solo la fila 0 apunta a algo: a una tabla de 2.º nivel, que cubre 4 MB y alcanza para los 2 MB del proceso. Las otras 1023 filas de la raíz quedan vacías y sus tablas no se crean. Abajo, las dos cantidades dibujadas a la misma escala.

Cómo leerlo: a la izquierda, cada proceso tiene su propia tabla enorme, casi vacía. A la derecha, la tabla invertida es la lista de asientos del cine: una fila por butaca (marco), que dice qué proceso y qué página la ocupa. Su tamaño solo depende de cuántas butacas hay. Los procesos y páginas son un ejemplo propio.

Cómo leerlo: cada cuadradito es una página de tabla (4 KB, con 1024 PTE) y cubre 4 MB del espacio virtual. Hay 1024 cuadraditos para cubrir los 4 GB. Con un nivel existen todos (gris), aunque el proceso solo use el primero (verde). Con dos niveles, la raíz marca cuáles existen y los vacíos ni se crean (contorno). Supuesto: el proceso usa 2 MB contiguos, así que le basta una tabla. Si usara código abajo y pila arriba, serían dos tablas: 12 KB, que sigue siendo poquísimo.

🔮 Predice antes de seguir

Antes de seguir: ¿una tabla de dos niveles ocupa siempre menos memoria que una de un nivel? Piensa en un proceso pequeño y en uno que usa todo su espacio virtual.

Ya tengo mi respuesta: comparar

No siempre. Para un proceso pequeño o disperso ocupa mucho menos: la raíz más una o dos tablas hoja, unos 8 KB en vez de 4 MB. Pero si el proceso usa todo su espacio, se necesitan todas las tablas hoja más la raíz: 4 MB + 4 KB, un poco más que un nivel. Además, cada traducción cuesta un acceso a memoria más. La ventaja depende de que los procesos usen solo una parte de su espacio, que es lo habitual.

El problema: la tabla es proporcional al espacio virtual. En una VAX: 2 GB con páginas de 512 B dan $2^{22}$ PTE por proceso. Por eso las tablas se guardan en memoria virtual (también se paginan) y se usan jerarquías.

Dos niveles, 32 bits (fig. 8.3), típico del Pentium:

• Con páginas de 4 KB hay $2^{20}$ páginas. Con PTE de 4 B, la tabla de usuario ocupa 4 MB = $2^{10}$ páginas.
• Esas páginas se mapean con una tabla raíz (page directory) de $2^{10}$ PTE = 4 KB, que siempre está en RAM.
• La dirección se divide en | 10 bits: raíz | 10 bits: tabla de usuario | 12 bits: offset |. Si la página de la tabla de usuario no está en RAM, hay un page fault antes de llegar al dato: un doble fallo posible.

Cómo leerlo: es la misma dirección 0x12345678 de la práctica de arriba, ahora con dos niveles. Los primeros 10 bits (72) eligen una fila de la raíz, que dice dónde está la tabla de 2.º nivel. Los 10 siguientes (837) eligen una fila de esa tabla, que da el marco. El offset baja sin tocarse, como antes. Los marcos 0x00200 y 0x00ABC son valores de ejemplo (el segundo coincide con la práctica nivel 3).

¿Para qué sirven los primeros 10 bits si los segundos ya eligen la fila? Porque hay hasta 1024 tablas de 2.º nivel y todas tienen una fila 837. Los primeros 10 bits dicen en cuál de ellas buscar; los segundos, qué fila leer dentro de ella. Es como «piso 72, oficina 837»: el número de oficina se repite en cada piso. Juntos forman el número de página virtual (los 20 bits altos): con un nivel se usaría entero como índice de una tabla de 2²⁰ filas; con dos, se parte en «qué tabla» y «qué fila».

🔮 Predice antes de seguir

Otra dirección tiene los mismos primeros 10 bits (72), pero los siguientes valen 5. ¿Qué tabla de 2.º nivel usa y qué fila lee?

Ya tengo mi respuesta: comparar

Usa la misma tabla de 2.º nivel (la del marco 0x00200, porque la fila 72 de la raíz no cambió) y lee su fila 5 en vez de la 837. Direcciones con el mismo «qué tabla» caen en la misma tabla de 2.º nivel: es la localidad que hace barato el multinivel.

¿Y en la memoria física? No hay ninguna distribución especial:

Cómo leerlo: no hay una zona especial para las tablas. La raíz, la tabla de 2.º nivel y el dato son marcos comunes de 4 KB, en cualquier lugar y sin orden. Cada tabla ocupa justo un marco (1024 filas × 4 B = 4 KB): por eso se eligieron 10 bits por nivel. Los números en círculos son el orden de los accesos.

Tabla de páginas invertida (PowerPC, UltraSPARC, IA-64):

• Tiene una entrada por marco físico, no por página virtual. Su tamaño es fijo, proporcional a la RAM, sin importar cuántos procesos ni cuántas páginas virtuales haya.
• Se busca con un hash del número de página, con encadenamiento para las colisiones (cadenas típicas de 1 a 2 entradas).
• Cada entrada tiene el número de página, el PID del dueño, bits de control y un puntero de cadena.

Cómo leerlo: se busca al revés que en la tabla normal. El hash de (PID, página) da una fila candidata. Si esa fila no es la buscada (aquí la 2), se sigue el puntero de cadena hasta encontrarla (la 5). El número de la fila es el marco. El hash y el contenido de la tabla son un ejemplo propio.

TLB (Translation Lookaside Buffer)

💡 En simple: los favoritos del navegador

Buscar en la tabla de páginas cuesta un acceso extra a memoria cada vez. La TLB es una libretita con las últimas traducciones usadas, como los favoritos del navegador: si está ahí, no buscas.

Ejemplo trivial: leer la TLB cuesta 10 ns y la RAM 100 ns, con una tabla de un nivel.

• Sin TLB: 100 (leer la tabla) + 100 (leer el dato) = 200 ns por acceso.
• Con TLB y 90 % de aciertos:
  • si acierta: 10 + 100 = 110 ns;
  • si falla: 10 + 100 + 100 = 210 ns;
  • en promedio: 0.9 × 110 + 0.1 × 210 = 120 ns.

Casi se recupera la velocidad de la RAM sola, gracias a la localidad: el programa repite las mismas páginas una y otra vez.

Sin ayuda, cada referencia virtual cuesta dos accesos a memoria (la PTE y el dato), es decir, duplica el tiempo. El TLB es una caché de PTEs recientes.

1. Se busca la página en el TLB. En un hit, se obtiene el marco y la dirección real al instante.
2. En un miss, se indexa la tabla de páginas del proceso. Si P = 1, se forma la dirección y se actualiza el TLB.
3. Si P = 0, hay un page fault: se sale del hardware y entra el SO, que carga la página (E/S de disco; el proceso queda Blocked), actualiza la tabla y lo pasa a Ready.

El TLB solo contiene algunas entradas, así que no se puede indexar por número de página. Cada entrada guarda el número de página y la PTE completa, y el hardware compara todas a la vez: es un mapeo asociativo, frente al mapeo directo (indexado) de la tabla. Después del TLB se consulta la caché con la dirección real.

Cómo leerlo: hay tres caminos. Verde arriba (hit): la TLB ya sabe el marco y se va directo a la física. Miss: se lee la tabla en RAM (un acceso más). Si P = 1, se arma la física y la traducción se copia a la TLB para la próxima vez (flecha punteada). Rojo abajo: si P = 0, es page fault y el SO toma el control. Los tiempos son los del ejemplo trivial de arriba.

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.

Tamaño de página: el compromiso

💡 En simple: cajas de mudanza

• Cajas chicas: se aprovecha mejor el espacio (poca fragmentación interna), pero necesitas muchas cajas y una lista larguísima para saber qué hay en cada una (tabla grande).
• Cajas grandes: pocas cajas y lista corta, pero cada caja trae cosas que no necesitabas (más desperdicio y, a veces, más fallos).

Por eso no hay un tamaño perfecto: 4 KB es el compromiso típico.

Página pequeña	Página grande
✔ menos fragmentación interna	✔ tablas más chicas y cada entrada del TLB cubre más memoria
✔ con muchas páginas en RAM, la localidad hace que falle poco	✔ transferencias de disco más eficientes
✘ tablas enormes, que pueden tener que estar en memoria virtual (con doble fallo)	✘ cada página incluye datos lejos de la referencia reciente, así que la localidad pierde efecto y suben los fallos, hasta que la página es tan grande como el proceso (fig. 8.10)

Cómo leerlo (con una cantidad fija de RAM para el proceso): con páginas chicas caben muchas, y la localidad hace que casi siempre esté la que hace falta. Al agrandarlas, cada página trae datos que no se van a usar pronto y ocupa espacio de otras que sí: suben los fallos. En el extremo P, una sola página es todo el proceso y, una vez cargada, ya no falla. Es la forma de la curva, no datos medidos.

La tasa de fallos también baja al dar más marcos al proceso (tamaño del working set). Los tamaños reales van de 512 B (VAX) a 4 KB (x86); Pentium e Itanium soportan de 4 KB a 1 GB. Varios procesadores admiten varios tamaños de página (por ejemplo, páginas grandes para el código y chicas para las pilas), pero la mayoría de los SO usan uno solo.

Memoria virtual: la idea que lo cambia todo

Con traducción en ejecución y un proceso partido en trozos no contiguos, ¡no hace falta que todo el proceso esté en RAM!

• El conjunto residente (resident set) es la parte del proceso que está en RAM. Si se referencia algo fuera de él, se produce una interrupción por fallo de acceso, el proceso pasa a Blocked, se pide la E/S al disco y se despacha otro proceso. Cuando la página llega, una interrupción de E/S lo pasa a Ready.
• Dos consecuencias:
  1. caben más procesos en RAM, así que es más probable que alguno esté listo;
  2. un proceso puede ser más grande que toda la RAM, lo que elimina los overlays.
• Memoria real es la RAM. Memoria virtual es la que percibe el programa, del tamaño del disco.
• Funciona gracias a la localidad: en poco tiempo se usan pocas páginas. Si el SO expulsa páginas que se van a necesitar enseguida, el sistema pasa más tiempo trayendo páginas que ejecutando: thrashing.

	Paginación simple	Paginación con MV	Segmentación simple	Segmentación con MV
Partición	marcos fijos	marcos fijos	sin particionar	sin particionar
¿Quién divide?	compilador o SO	compilador o SO	programador	programador
Fragmentación	interna	interna	externa	externa
El SO mantiene	tabla de páginas + marcos libres	ídem	tabla de segmentos + huecos libres	ídem
¿Todo en RAM?	sí (salvo overlays)	no, bajo demanda	sí	no, bajo demanda

Calculadora

Calculadora de paginación

Mueve los parámetros o carga un examen. Todo se deriva de tres logaritmos: bits de dirección virtual, bits físicos y bits de offset.

E1 2025-2 (2⁵⁰ B, 2 GiB, 4 KiB, V+D)E1 2022 (38 bits, 32 bits, 16 KB, PTE 4 B, 2 niveles)x86-64 típico (48 bits, 4 KiB, PTE 8 B)

Dir. virtual: 50 bits (1 PiB)Memoria física: 2 GiB (31 bits)Página: 4 KiB (12 bits)Bits de estado por PTE: 2

Dirección virtual (50 bits)

VPN · 38b

offset · 12b

50

Dirección física (31 bits)

PFN · 19b

offset · 12b

31

Entrada de la tabla (PTE): 21 bits → 3 B

estado · 2b

PFN · 19b

pad · 3b

24

(a) bits dir. física31log₂(2 GiB)

(b) páginas virtuales$2^{38}$$2^{50}$ / $2^{12}$

(c) marcos físicos$2^{19}$$2^{31}$ / $2^{12}$

(d) bits VPN / PFN38 / 19

(e) entradas de la tabla$2^{38}$una por página virtual

(f) bytes por PTE3 B⌈(19 + 2) / 8⌉

(g) tamaño de la tabla768 GiB$2^{38} \times 3\,\text{B}$

Tabla multinivel (cada tabla ocupa exactamente 1 página)

E1 2025-2 · Pregunta 2 (3.5 pts)

Espacio virtual de $2^{50}$ bytes, 2 GiB de memoria física, páginas de 4 KiB, PTE con PFN + V + D.

Solución paso a paso

	Cálculo	Resultado
(a) bits de dirección física	$2\,\text{GiB} = 2^{31}$	31 bits
(b) páginas virtuales	$2^{50} / 2^{12}$	$\mathbf{2^{38}}$
(c) páginas físicas (marcos)	$2^{31} / 2^{12}$	$\mathbf{2^{19}}$ (524 288)
(d) bits de VPN / PFN	$50 - 12$ / $31 - 12$	38 / 19
(e) entradas de la tabla	una por página virtual	$\mathbf{2^{38}}$
(f) bytes por PTE	$19 + 1 + 1 = 21$ bits → $\lceil 21/8 \rceil$	3 bytes
(g) tamaño de la tabla	$2^{38} \times 3$ B	$3 \cdot 2^{38}$ B = 768 GiB

(g) Layout: la tabla es un arreglo indexado por VPN (de 0 a $2^{38}-1$). Cada entrada ocupa 24 bits: | V (1) | D (1) | PFN (19) | relleno (3) |. Conclusión: una tabla de un nivel para 50 bits es absurda (768 GiB > 2 GiB de RAM), y por eso existen las tablas multinivel e invertidas.

E1 2022 · Pregunta 3 (4 pts)

Direcciones virtuales de 38 bits y físicas de 32. (1) Ventaja o desventaja de multinivel frente a un nivel; (2) diseñar dos niveles con páginas de 16 KB y PTE de 4 bytes.

Solución (notas del profesor en el solver)

(1) Ventaja: reduce la memoria usada por la tabla, porque solo se crean las tablas de segundo nivel de las regiones usadas. Un proceso pequeño necesita 1 tabla raíz + 1 o 2 tablas hoja. Desventaja: más accesos a memoria por traducción (uno por nivel), lo que se mitiga con el TLB.

(2)

• Offset: $16\,\text{KB} = 2^{14}$ → 14 bits. VPN: $38 - 14 =$ 24 bits. PFN: $32 - 14 = 18$ bits (caben en la PTE de 4 B junto con los bits de estado).
• PTEs por página: $2^{14} / 2^2 = 2^{12}$ → cada nivel indexa 12 bits.
• Dirección virtual: | L1: 12 | L2: 12 | offset: 14 | = 38 bits ✔.
• Tabla raíz: $2^{12}$ entradas × 4 B = 16 KB = 1 página. Cada tabla de segundo nivel también ocupa 1 página.
• Máximo (todo el espacio mapeado): $16\,\text{KB} + 2^{12} \times 16\,\text{KB} = 64\,\text{MB} + 16\,\text{KB}$. Con un nivel serían siempre $2^{24} \times 4\,\text{B} = 64\,\text{MB}$.
• Dibujo: el registro base de la tabla (CR3/PTBR) apunta a la raíz; L1 elige una PTE que apunta a una tabla hoja; L2 elige la PTE con el PFN; PFN ‖ offset = dirección física.

⚠️ Errores que cuestan puntos

• Sacar los bits de offset del tamaño de la RAM.El offset sale del tamaño de página. La RAM determina los bits de PFN.
• Usar 1 KB = 1000.Todo es en base 2: 1 KB = 2¹⁰ = 1024.
• Calcular la física como PFN + offset.Es PFN × tamaño de página + offset, es decir, concatenar. Sumar base + offset es la regla de la segmentación.
• Calcular el número de entradas con los marcos.Una tabla convencional tiene una entrada por página virtual. Una entrada por marco es la tabla invertida.
• Dar 21 bits de PTE como tamaño en bytes sin redondear.Redondea a bytes enteros: 21 bits ocupan 3 B. Tamaño de la tabla = entradas × bytes por PTE.
• Traducir sin mirar el bit de validez.Primero la página, después la tabla (¿P = 1?) y recién después la física.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. Dirección virtual de 32 bits, páginas de 4 KiB. ¿Bits de offset y de VPN?

a) 12 y 20b) 10 y 22c) 4 y 28d) 12 y 32

2. 8 GiB de RAM y marcos de 4 KiB. ¿Bits de PFN?

a) 33b) 21c) 20d) 12

3. La paginación elimina…

a) la fragmentación internab) la fragmentación externac) ambasd) ninguna

4. Principal desventaja de una tabla de 4 niveles:

a) Ocupa más memoria que la de 1 nivelb) Hasta 4 accesos extra a memoria por traducción (sin TLB)c) No permite compartir páginasd) Fragmentación externa

🗣️ Explícalo tú (Feynman)

Explica por qué en paginación el offset «pasa igual» de la dirección virtual a la física, y qué pasaría si el tamaño de página no fuera una potencia de 2.

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…

• La página y el marco tienen el mismo tamaño: el byte k de la página es el byte k del marco.
• Como el tamaño es 2^o, el offset son exactamente los o bits bajos, y basta reemplazar los bits altos (VPN → PFN).
• Si no fuera potencia de 2, habría que dividir y multiplicar de verdad en cada acceso, y el hardware sería mucho más lento.
• Un ejemplo con números, como 1502 → 6622.

Error típico al explicarlo: decir que «el offset se suma a la base». Eso es segmentación.

📈 ¿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 ·for_partial/E1_OS_20252.pdf (P2) · for_partial/E1_OS_2021_2022_Solver.pdf (E1 2022 P3) · sem_6/Class 1.md