Gestión de memoria — teoría con tu portátil repartiendo la RAM entre gcc, spotify, el campus y onedrive (y los 4 KiB que yo creía que eran 4000 bytes)

En el simulacro de IC2 me tocó una pregunta de paginación que parecía regalada: páginas de 4 KiB, la dirección lógica 6700 y una tabla en la que la página 1 estaba en el marco 9. La hice de cabeza: «4 KiB son 4000 bytes, así que 6700 es la página 1 con desplazamiento 2700», y escribí con toda la seguridad del mundo 9 · 4000 + 2700 = 38700. Cero puntos. Un KiB son 1024 bytes, así que una página de 4 KiB tiene 4096: 6700 = 1 · 4096 + 2604, y la física era 9 · 4096 + 2604 = 39468. Tenía bien la página y el marco, y aun así fallé por no saber de qué tamaño es una página.

Hoy vamos a entender cómo reparte el sistema operativo la RAM entre los procesos sin que se pisen: la memoria contigua (con sus registros base y límite y sus huecos), la segmentación y la paginación, la TLB que hace que todo esto no sea lentísimo y el problema de lo que ocupa la tabla de páginas. El ejemplo de siempre: tu portátil una noche de estudio, con gcc compilando, spotify sonando, el campus abierto en el navegador y onedrive subiendo tus apuntes. Venimos de Concurrencia y sincronización, donde los procesos compartían variables a propósito; aquí el SO se encarga de que no compartan memoria por accidente. Cuando acabes, practica con los ejercicios tipo examen de gestión de memoria.

Por qué hay que gestionar la memoria

La memoria principal (RAM) es un conjunto de celdas que se referencian por una dirección lineal: la primera es la 0, la siguiente la 1, y así hasta la última. Para que un programa se ejecute, su código y sus datos tienen que estar cargados en la RAM, al menos en parte. Y el núcleo del SO también vive ahí.

Con un solo programa sería fácil. Pero tu portátil es un sistema multitarea: la memoria hay que repartirla entre todos los procesos, y cada uno tiene su propio espacio de memoria (instrucciones, datos y pila).

Fíjate en el dibujo: gcc, spotify y el campus ya están dentro, y onedrive quiere entrar. De ahí salen los dos problemas de la gestión de memoria:

1. Capacidad: puede que la RAM no tenga sitio para todos los procesos que quieren ejecutarse.
2. Protección: un proceso podría acceder, por error o a propósito, a la zona de otro proceso o a la del SO.

Requisitos, objetivos y conceptos clave

El SO tiene tres requisitos que cumplir:

Requisito	Qué significa
Controlar el solapamiento	Que los procesos no choquen en memoria, pero que puedan compartir zonas cuando quieran
Protección	Que un proceso no lea la memoria privada de otro ni los datos del SO
Reubicación	Convertir las direcciones lógicas del proceso en direcciones físicas

Y dos bloques de objetivos, que en el examen se preguntan por separado:

• Rendimiento: aprovechar al máximo la memoria principal, tener varios procesos cargados sin que el sistema se venga abajo y permitir que un programa se ejecute sin estar entero en la RAM.
• Protección y compartición: proteger al SO de accesos indebidos, proteger el espacio de cada proceso y permitir que varios procesos compartan zonas de memoria (para comunicarse o para no repetir código, como una biblioteca).

Por último, tres conceptos clave que van a salir en todo el tema:

• Reubicación: que un programa pueda residir en cualquier zona de la memoria física.
• Fragmentación: los huecos libres que van quedando al asignar y liberar memoria, y que a veces no sirven para nada.
• Tiempo de acceso: los mecanismos de gestión de memoria no pueden hacer mucho más lento cada acceso.

De practica.c a la memoria: la vinculación de direcciones

Cuando escribes int cont; en practica.c, cont es una dirección simbólica: un nombre. En algún momento ese nombre tiene que convertirse en un número de celda de la RAM. ¿Cuándo? Depende de en qué etapa del ciclo de vida del programa se haga.

El compilador produce el módulo objeto, el enlazador lo junta con otros objetos y bibliotecas en un ejecutable, y el cargador lo pone en memoria. En cualquiera de esas etapas se pueden fijar las direcciones:

Cuándo se fijan	Tipo	Consecuencia
Al compilar	Direcciones absolutas	El programa solo funciona en una zona fija de la RAM: no es reubicable
Al cargar	Reubicación estática	El cargador ajusta las direcciones una vez; después el proceso ya no se puede mover
Al ejecutar	Reubicación dinámica	El hardware traduce en cada acceso; el proceso se puede mover cuando haga falta

Lo que interesa es que el compilador no genere direcciones definitivas, sino reubicables, que se resuelven más tarde. Cuanto más tarde, más libertad.

Direcciones lógicas, físicas y la MMU

La reubicación dinámica necesita dos tipos de dirección y un traductor:

• Dirección lógica (o virtual): la que genera la CPU al ejecutar el programa.
• Dirección física: la que llega al chip de memoria.
• MMU (unidad de manejo de memoria): el dispositivo hardware que traduce direcciones lógicas a físicas.

La MMU más sencilla es un registro base: se suma a cada dirección lógica. Imagina que gcc está cargado a partir de los 300 KiB de la RAM (300 · 1024 = 307200):

gcc cree que su memoria empieza en 0. Cuando pide la dirección 1500, la MMU calcula 307200 + 1500 = 308700, y esa es la que llega a la RAM. Si mañana el SO mueve gcc a otro sitio, solo tiene que cambiar el registro base: gcc ni se entera.

Protección con base y límite

Con el registro base ya tenemos reubicación. Para la protección se añade un registro límite: el tamaño de la zona que el proceso puede usar. En modo usuario, un circuito comprueba cada dirección antes de que salga al bus:

Si gcc tiene una zona de 210 KiB (215040 bytes), la dirección lógica 1500 pasa la comprobación (1500 < 215040) y se convierte en 308700. La 250000 no la pasa: salta una excepción y el acceso nunca llega a la memoria. Ya viste estos registros en el tema del hardware; aquí entiendes por qué existen.

Enlace dinámico e intercambio

Dos trucos más para ahorrar memoria antes de entrar en las técnicas de asignación.

Enlace dinámico (bibliotecas compartidas). La carga de un módulo de código se retrasa hasta que se usa por primera vez. En Windows son las DLL (dynamic link libraries) y en Unix y GNU/Linux, las bibliotecas compartidas (libc.so, libm.so). La biblioteca se carga cuando algún proceso llama a una de sus funciones, y las llamadas pasan por una tabla indirecta que gestiona el SO. Si diez procesos usan libc, solo hay una copia en memoria. Y si la RAM va muy justa, el SO puede quitar las que nadie referencia.

Intercambio (swapping). Si un proceso lleva mucho tiempo bloqueado, su memoria está ocupada sin servir para nada. Idea: volcar su imagen al disco (swap out) y recuperarla cuando haya que reanudarlo (swap in).

Históricamente fue la forma de tener multiprogramación con muy poca RAM (en el caso extremo, un solo proceso en memoria y un intercambio en cada cambio de contexto). Su problema es el tiempo de copiar imágenes enteras. Para suavizarlo, mientras se intercambia un proceso los demás siguen ejecutándose, y se pueden usar varias áreas de intercambio en discos distintos para hacer varias copias a la vez.

Memoria contigua: MFT y MVT

La forma más simple de repartir la RAM: cada proceso ocupa un único bloque seguido. Hay dos variantes:

• MFT (particiones de tamaño fijo): las particiones se deciden al arrancar el SO y no cambian. Técnica muy rígida, pero muy eficiente.
• MVT (particiones de tamaño variable): evolución de MFT. El espacio libre se reparte a medida, con una lista dinámica de huecos. Más flexible, pero más compleja.

Con MVT, el SO maneja dos estructuras:

• Una tabla de zonas reservadas: por cada zona, dirección inicial, tamaño y proceso al que pertenece.
• Una lista de huecos libres: por cada hueco, dirección inicial y tamaño.

Cuando un proceso pide memoria, pide un tamaño concreto. El SO busca un hueco suficientemente grande, se lo da y lo que sobra vuelve a la lista de huecos. La protección sigue siendo la misma pareja base y límite.

Primer, mejor y peor ajuste

Cuando hay varios huecos que sirven, ¿cuál se da? Hay tres políticas de asignación:

• Primer ajuste (first-fit): se recorre la lista y se da el primer hueco mayor o igual que lo pedido.
• Mejor ajuste (best-fit): se da el hueco que deja el menor resto libre. Riesgo: va dejando restos tan pequeños que no sirven.
• Peor ajuste (worst-fit): se da siempre el hueco más grande.

En el portátil hay cinco huecos libres de 120, 480, 210, 300 y 560 KiB, y llegan, en este orden, gcc (210), spotify (430), campus (110) y onedrive (470). El simulador de Compruébalo con Python aplica las tres políticas a los mismos datos:

Sigue la fila del primer ajuste: gcc entra en el primer hueco que le cabe, el de 480 (le sobran 270). spotify (430) no cabe ni en 270 ni en 210 ni en 300, y va al de 560. campus, al de 120. Cuando llega onedrive (470), el mayor hueco que queda es de 300: no cabe. El peor ajuste fracasa igual, porque gcc rompe el hueco de 560. Solo el mejor ajuste coloca a los cuatro: gcc entra justo en el de 210 y deja intacto el de 560 para onedrive.

Política	Busca	Ventaja	Inconveniente
Primer ajuste	El primero que cabe	Rápida: no recorre toda la lista	Va troceando los huecos del principio
Mejor ajuste	El que deja menos resto	Conserva los huecos grandes	Recorre toda la lista; deja restos diminutos
Peor ajuste	El más grande	Deja restos grandes (en teoría útiles)	Rompe los huecos grandes muy pronto

Fragmentación externa, interna y compactación

Mira cómo queda la memoria tras el primer ajuste:

Hay 920 KiB libres y onedrive solo pide 470, pero están repartidos en trozos de 10, 270, 210, 300 y 130. Ninguno sirve. Eso es la fragmentación externa: memoria libre que existe pero no está seguida.

Una solución es la compactación: mover los procesos para juntar todos los huecos en uno. Tiene dos pegas:

• Solo es posible con reubicación dinámica, porque los procesos cambian de dirección física (basta con cambiar su registro base).
• Consume mucho tiempo: hay que copiar bloques enteros de memoria.

La otra solución es dejar de exigir que el proceso esté seguido: trocearlo. Eso es la memoria no contigua, con sus dos técnicas, segmentación y paginación.

Segmentación

Idea: descomponer el proceso en varios segmentos, que son sus trozos lógicos: código, datos, pila… Con el hardware adecuado, cada segmento puede ir a una zona distinta de la RAM.

En el dibujo, gcc tiene tres segmentos: código (3200 bytes), datos (1500) y pila (2000). En la RAM están separados y en otro orden, y la tabla de segmentos guarda dónde empieza cada uno (base) y cuánto mide (límite). El reparto del trabajo:

• La CPU trabaja con direcciones de dos piezas: ⟨segmento, desplazamiento⟩.
• El compilador identifica los segmentos del programa y genera direcciones segmentadas.
• El cargador del SO coloca cada segmento en una zona de memoria.
• La MMU traduce ⟨segmento, desplazamiento⟩ a direcciones lineales con la tabla de segmentos, que es una tabla de registros base y límite.

Traducir una dirección segmentada

La traducción es la de base y límite, pero con una pareja por segmento:

1. Con el número de segmento se busca su fila en la tabla.
2. Se comprueba que el desplazamiento es menor que el límite. Si no, excepción.
3. Física = base + desplazamiento.

⟨1, 600⟩ es el segmento de datos (base 4000, límite 1500): 600 < 1500, física 4000 + 600 = 4600. ⟨2, 2500⟩ es la pila (límite 2000): 2500 ≥ 2000, excepción.

Segmentación
Ventajas	Atenúa la fragmentación; permite compartir segmentos (una DLL puede ser un segmento en las tablas de varios procesos); permite proteger segmentos (solo lectura, solo ejecución en los de código)
Inconvenientes	El compilador y el enlazador trabajan con un espacio de dos dimensiones; necesita hardware; cada acceso es más lento (hay que mirar la tabla); no elimina del todo la fragmentación; su eficacia depende de cómo se trocee el proceso

Paginación

La paginación es la técnica que erradica definitivamente la fragmentación externa. La idea:

• El programa se trocea en páginas de tamaño fijo (por ejemplo, 4 KiB).
• La RAM se divide en marcos de página (page frames) del mismo tamaño.
• Cada página puede ir a cualquier marco libre, sin importar si están seguidos.
• La MMU asocia cada página lógica con su marco físico usando la tabla de páginas del proceso.

Las cuatro páginas de gcc están en los marcos 5, 9, 2 y 12: desordenados y separados por marcos de otros procesos. Da igual. Como páginas y marcos miden lo mismo, cualquier marco libre sirve para cualquier página: ya no puede haber un hueco libre demasiado pequeño.

Gestionar el espacio libre se vuelve muy sencillo: basta con saber qué marcos están libres. El SO lo apunta en una tabla de marcos de página, que se puede implementar con un mapa de bits (un bit por marco: libre u ocupado) o con una lista de marcos libres. Cuando llega un proceso de cuatro páginas, se cogen cuatro marcos de la lista y se apuntan en su tabla.

Partir la dirección en página y desplazamiento

Toda dirección lógica se descompone en número de página y desplazamiento dentro de la página. Si la página mide 2^n bytes, los n bits de abajo son el desplazamiento y el resto, la página. En el portátil usamos direcciones lógicas de 16 bits y páginas de 4 KiB = 2^12 bytes: 4 bits de página y 12 de desplazamiento.

Para traducir 0x1A2C:

1. En binario, 0001 1010 0010 1100. Los 4 bits de arriba, 0001, son la página 1. Los 12 de abajo, 1010 0010 1100 = 2604, el desplazamiento.
2. La tabla de páginas dice que la página 1 está en el marco 9 (1001).
3. Se cambian los 4 bits de la página por los del marco, y el desplazamiento se copia tal cual: 1001 1010 0010 1100 = 0x9A2C.

En decimal es la misma cuenta: 0x1A2C = 6700 = 1 · 4096 + 2604, y la física es 9 · 4096 + 2604 = 39468. Las fórmulas son:

• página = dirección lógica // tamaño de página
• desplazamiento = dirección lógica % tamaño de página
• física = marco · tamaño de página + desplazamiento

Fragmentación interna en la paginación

La paginación no es perfecta. Si gcc ocupa 13000 bytes, necesita 4 páginas de 4 KiB (16384 bytes), y la última está casi vacía:

4 · 4096 − 13000 = 3384 bytes asignados que nadie usa. Como el desperdicio está dentro de la página, es fragmentación interna. Con páginas de 1 KiB, gcc ocuparía 13 páginas y solo perdería 13 · 1024 − 13000 = 312 bytes, pero su tabla tendría 13 entradas en vez de 4.

Tamaño de página	Fragmentación interna	Tabla de páginas
Pequeño	Menor (se pierde menos en la última página)	Más grande (más páginas, más entradas)
Grande	Mayor	Más pequeña

La tabla de páginas en la RAM: dos accesos por cada uno

¿Dónde se guarda la tabla de páginas? En máquinas antiguas como el DEC PDP-11 (direcciones de 16 bits, páginas de 8 KiB = 2^13), la dirección tenía 3 bits de página y la tabla, 2^3 = 8 entradas, cabía en registros rápidos de la CPU. Hoy las tablas son enormes (un proceso de 20 MB con páginas de 1 KiB necesita 20K entradas), así que la tabla vive en la memoria principal, y la CPU tiene dos registros para encontrarla:

• RBTP (registro base de la tabla de páginas): dónde empieza la tabla en la RAM.
• RLTP (registro de longitud de la tabla de páginas): cuántas entradas tiene.

El problema salta a la vista: para leer un dato hacen falta dos accesos a la RAM, uno a la tabla de páginas y otro al dato. Todos los programas irían al doble de lento. La solución es la TLB.

La TLB: un atajo para la traducción

La TLB (Translation Lookaside Buffer, en español búfer de traducción adelantada) es una pequeña caché asociativa dentro del procesador que guarda unas pocas entradas de la tabla de páginas. Se consulta casi tan rápido como un registro de la CPU. Sirve para acelerar la traducción y evitar accesos a la tabla de páginas.

¿Cómo funciona?

• Guarda pares clave/valor ⟨página lógica, marco físico⟩.
• Para traducir la página P, se busca P en todas las entradas de la TLB a la vez (por eso es asociativa).
• Acierto de TLB: P está; se obtiene su marco y no hace falta mirar la tabla de páginas.
• Fallo de TLB: P no está; se lee la tabla de páginas en la RAM y se guarda el par ⟨P, marco⟩ en la TLB para la próxima vez.

Con una TLB de 5 ns y una RAM de 60 ns, un acierto cuesta 5 + 60 = 65 ns (la TLB y el dato) y un fallo, 5 + 60 + 60 = 125 ns (la TLB, la tabla y el dato).

La TLB acceso a acceso

El simulador de Compruébalo con Python traduce once accesos de gcc con una TLB de solo 2 entradas. Cuando está llena y hay un fallo, sale la entrada menos usada recientemente:

Sigue la columna «TLB después»:

Acceso	Qué pasa
0x0004	Fallo: la TLB está vacía. Entra (0→5)
0x0FF0	Acierto: también es la página 0
0x1A2C	Fallo: entra (1→9); ya hay dos entradas
0x0100	Acierto de la página 0, que pasa a ser la más reciente
0x3000	Fallo con la TLB llena: sale (1→9), la menos usada, y entra (3→12)
0x5008	La página 5 no está en la tabla: excepción, no se traduce

Al final, 7 aciertos de 10 accesos válidos: un 70 %. La página 0 se usa tanto que nunca sale de la TLB. Eso es la localidad: los programas usan una y otra vez las mismas pocas páginas, y por eso una TLB minúscula acierta tanto.

Tiempo efectivo de acceso

Con una tasa de aciertos h, el tiempo efectivo medio de acceso a memoria es:

t = h · (TLB + RAM) + (1 − h) · (TLB + RAM + RAM)

El ejemplo de clase: TLB de 5 ns, RAM de 60 ns y un 90 % de aciertos:

t = 0,9 · (5 + 60) + 0,1 · (5 + 60 + 60) = 58,5 + 12,5 = 71 ns

Solo 11 ns más que un acceso directo a la RAM, frente a los 120 ns que costaría sin TLB. En nuestro simulador, con un 70 %, sale 0,7 · 65 + 0,3 · 125 = 45,5 + 37,5 = 83 ns.

En procesadores reales se aciertan entre el 80 % y el 98 % de las veces, con TLB muy pequeñas: 22 entradas en el Motorola 68030, 32 en el Intel 80486 y entre 4 y 64 en los Intel Skylake (2015).

Situaciones especiales de la TLB

• Fallo con la TLB llena: hay que reemplazar una entrada. ¿Cuál? La más vieja, la menos usada, una al azar… En nuestro simulador, la menos usada recientemente.
• Cambio de contexto: las traducciones de gcc no valen para spotify (su página 0 está en otro marco). Hay que vaciar la TLB o cargarla con el contenido que tenía el proceso que entra en la CPU.

Protección en la paginación

La paginación también protege:

• Bits de protección en cada entrada de la tabla: lectura, escritura y ejecución. Así el código puede ser de solo lectura y ejecución, y los datos, de lectura y escritura.
• Protección contra accesos fuera del espacio lógico del proceso.

Para lo segundo hay tres medidas posibles:

• El RLTP: si el número de página no es menor que la longitud de la tabla, excepción.
• El bit de validez: las entradas que no corresponden a páginas del proceso se marcan como no válidas.
• La tabla de páginas invertida, en la que solo figuran las páginas válidas.

Eso es lo que pasó con 0x5008 en la traza: la página 5 no es de gcc y la traducción termina en excepción.

El tamaño de la tabla de páginas

Echemos cuentas con una arquitectura de 32 bits y páginas de 4 KiB:

12 bits de desplazamiento, así que quedan 20 bits de página: 2^20 = 1 048 576 entradas. Si cada entrada ocupa 4 bytes, la tabla de un solo proceso ocupa 4 MiB. Con direcciones de 48 o 64 bits es mucho peor.

La solución «fácil» es agrandar la página: con páginas de 4 MiB quedarían 10 bits de página y una tabla de 4 KiB… a cambio de disparar la fragmentación interna. Las soluciones serias son tres: paginación jerárquica, tabla de páginas invertida y tabla hash de páginas.

Paginación jerárquica

La propia tabla de páginas se pagina, y se forma una jerarquía de niveles. En el Intel x86 de 32 bits, la dirección se parte en 10 + 10 + 12 bits:

• p1 (10 bits) indexa la tabla exterior (primaria), que dice dónde está la tabla interior.
• p2 (10 bits) indexa esa tabla interior (secundaria), que da el marco.
• d (12 bits) es el desplazamiento dentro del marco.

¿Dónde está el ahorro? En que solo hace falta guardar las tablas interiores que el proceso usa de verdad. El precio: sin acierto de TLB, hacen falta tres accesos a la RAM (dos tablas y el dato), así que la TLB se vuelve todavía más necesaria. En general, con una jerarquía de n niveles son n + 1 accesos.

El x86 de 64 bits usa hasta cuatro niveles (page map level 4, page directory pointer table, page directory y page table, 9 bits cada uno, más 12 de desplazamiento; los bits 63 a 48 no se usan) y páginas de 4 KiB, 2 MiB o 1 GiB.

Tabla de páginas invertida

Le da la vuelta a la idea: en lugar de una tabla por proceso con una entrada por página, hay una sola tabla global con una entrada por cada marco real de la RAM. La entrada K dice qué página lógica hay en el marco K y a qué proceso (pid) pertenece.

La CPU emite ⟨pid, página, desplazamiento⟩. Se busca el par ⟨pid, página⟩ en la tabla, y la posición donde aparece es el marco. En el dibujo, ⟨412, 1⟩ (gcc, página 1) está en la posición 9: la física es ⟨9, 0xA2C⟩, la misma 0x9A2C de antes.

• Ventaja: grandísimo ahorro de memoria, porque el tamaño de la tabla depende de la RAM, no del número de procesos.
• Inconveniente: buscar en la tabla es lentísimo. Se confía en los aciertos de la TLB o se implementa como una tabla hash. La han usado PowerPC, UltraSPARC e IA-64.

Contigua, segmentación y paginación, frente a frente

	Contigua (MVT)	Segmentación	Paginación
Trozos	Uno	Segmentos lógicos, de tamaño variable	Páginas de tamaño fijo
Dirección lógica	Un número	⟨segmento, desplazamiento⟩	⟨página, desplazamiento⟩
Traducción	base + lógica (si < límite)	base[s] + d (si d < límite[s])	marco[p] · tamaño + d
Fragmentación externa	Sí	Menos, pero sí	No
Fragmentación interna	No	No	Sí, en la última página
¿La ve el programador?	No	Sí: son las partes de su programa	No

Errores típicos

Compruébalo con Python

Dos simuladores cortos con datos fijos, ejecutados una vez. Puedes copiarlos y ejecutarlos con python3.

Simulador 1: traducción con paginación y TLB

gcc tiene las cuatro páginas de la tabla del dibujo (0 → 5, 1 → 9, 2 → 2, 3 → 12), las páginas miden 4 KiB y la TLB tiene 2 entradas. El simulador traduce once direcciones, cuenta los aciertos y calcula el tiempo medio de dos formas: midiendo acceso a acceso y con la fórmula.

# Traducción de direcciones con paginación y una TLB de 2 entradas (datos fijos)
PAGINA = 4096                       # páginas de 4 KiB = 2**12 → 12 bits de desplazamiento
TABLA = {0: 5, 1: 9, 2: 2, 3: 12}   # tabla de páginas de gcc: página → marco
T_TLB, T_RAM = 5, 60                # ns: mirar la TLB y un acceso a la RAM
accesos = [0x0004, 0x0FF0, 0x1A2C, 0x1004, 0x0100, 0x3000, 0x3FFC, 0x0200, 0x5008, 0x3010, 0x0008]
tlb = []                            # pares (página, marco); el primero es el menos usado
aciertos = validos = total_ns = 0
print(f'{"lógica":<8}  {"pág":>4}  {"desp":>6}   {"TLB":<9}  {"marco":>5}  {"física":>8}  {"ns":>4}')
for dl in accesos:
    p, d = divmod(dl, PAGINA)       # p = 4 bits altos, d = 12 bits bajos
    marco = next((m for (q, m) in tlb if q == p), None)
    if marco is not None:           # acierto: la TLB ya sabía el marco
        tlb.remove((p, marco)); tlb.append((p, marco))
        estado, ns = 'acierto', T_TLB + T_RAM            # TLB + el dato
        aciertos += 1
    elif p in TABLA:                # fallo: hay que leer la tabla de páginas en la RAM
        marco = TABLA[p]
        estado, ns = 'fallo', T_TLB + T_RAM + T_RAM      # TLB + tabla + el dato
        if len(tlb) == 2:
            tlb.pop(0)              # TLB llena: sale la menos usada (LRU)
        tlb.append((p, marco))
    else:                           # la página no está en la tabla: acceso ilegal
        print(f'0x{dl:04X}    {p:>4}  {d:>6}   {"excepción":<9}  {"-":>5}  {"-":>8}  {"-":>4}')
        continue
    df = marco * PAGINA + d         # el desplazamiento se copia tal cual
    validos += 1; total_ns += ns
    print(f'0x{dl:04X}    {p:>4}  {d:>6}   {estado:<9}  {marco:>5}  {"0x%04X" % df:>8}  {ns:>4}')
h = aciertos / validos
print(f'aciertos de TLB: {aciertos}/{validos} = {h:.0%}')
print(f'tiempo medio medido: {total_ns / validos:.1f} ns')
print(f'fórmula: {h:.2f}·({T_TLB}+{T_RAM}) + {1 - h:.2f}·({T_TLB}+{T_RAM}+{T_RAM}) = {h * 65 + (1 - h) * 125:.1f} ns')

Esta es su salida real:

lógica     pág    desp   TLB        marco    física    ns
0x0004       0       4   fallo          5    0x5004   125
0x0FF0       0    4080   acierto        5    0x5FF0    65
0x1A2C       1    2604   fallo          9    0x9A2C   125
0x1004       1       4   acierto        9    0x9004    65
0x0100       0     256   acierto        5    0x5100    65
0x3000       3       0   fallo         12    0xC000   125
0x3FFC       3    4092   acierto       12    0xCFFC    65
0x0200       0     512   acierto        5    0x5200    65
0x5008       5       8   excepción      -         -     -
0x3010       3      16   acierto       12    0xC010    65
0x0008       0       8   acierto        5    0x5008    65
aciertos de TLB: 7/10 = 70%
tiempo medio medido: 83.0 ns
fórmula: 0.70·(5+60) + 0.30·(5+60+60) = 83.0 ns

Las piezas importantes:

• divmod(dl, PAGINA) hace la división entera y el resto a la vez: la página y el desplazamiento.
• La lista tlb guarda pares (página, marco) ordenados de menos a más usados. En un acierto, el par se quita y se vuelve a añadir al final (pasa a ser el más reciente); en un fallo con la TLB llena, tlb.pop(0) saca el primero, el menos usado. Es una TLB con reemplazo LRU.
• marco * PAGINA + d es la fórmula de la física: el desplazamiento no se toca.
• Las direcciones se imprimen en hexadecimal con 0x{dl:04X} para que se vea el truco de los tres últimos dígitos.

Qué observar:

1. En todas las filas, los tres últimos dígitos hexadecimales de la lógica y de la física son iguales: 0x1A2C → 0x9A2C, 0x3FFC → 0xCFFC. Solo cambia el primero (la página por el marco; el 12 es la C).
2. Los fallos cuestan 125 ns y los aciertos 65: un fallo es casi el doble.
3. En 0x3000 la TLB está llena con las páginas 1 y 0. Sale la 1 porque la 0 se acaba de usar en 0x0100. Si después se pidiera otra vez la página 1, fallaría.
4. 0x5008 no se traduce: la página 5 no está en TABLA, así que no hay marco ni tiempo, y no cuenta para la media.
5. La media medida (83 ns) y la de la fórmula coinciden, porque la fórmula es precisamente la media ponderada de 65 y 125 con la tasa de aciertos (0,70).

Simulador 2: primer, mejor y peor ajuste

Los cinco huecos y las cuatro peticiones del dibujo de las políticas. La función elige filtra los huecos que caben y escoge según la política.

# Asignación contigua (MVT): primer, mejor y peor ajuste con los mismos huecos (datos fijos)
HUECOS = [(100, 120), (300, 480), (900, 210), (1200, 300), (1600, 560)]   # (inicio, tamaño) en KiB
PETICIONES = [('gcc', 210), ('spotify', 430), ('campus', 110), ('onedrive', 470)]


def elige(huecos, tam, politica):
    validos = [h for h in huecos if h[1] >= tam]             # solo sirven los que caben
    if not validos:
        return None
    if politica == 'primer':
        return validos[0]                                    # el primero de la lista
    if politica == 'mejor':
        return min(validos, key=lambda h: h[1])              # el que deja menos resto
    return max(validos, key=lambda h: h[1])                  # peor: el más grande


for politica in ('primer', 'mejor', 'peor'):
    huecos = list(HUECOS)                                    # copia: cada política empieza igual
    print(f'== {politica} ajuste')
    for nombre, tam in PETICIONES:
        h = elige(huecos, tam, politica)
        if h is None:
            libre = sum(t for _, t in huecos)
            print(f'  {nombre:<8} {tam:>3} KiB → no cabe (libres {libre} KiB, mayor hueco {max(t for _, t in huecos)})')
            continue
        i = huecos.index(h)
        huecos[i] = (h[0] + tam, h[1] - tam)                 # el resto sigue siendo un hueco
        print(f'  {nombre:<8} {tam:>3} KiB → en {h[0]:>4} (hueco de {h[1]}, resto {h[1] - tam})')
    huecos = [h for h in huecos if h[1] > 0]
    print('  huecos:', ' '.join(str(t) for _, t in huecos))

Su salida real:

== primer ajuste
  gcc      210 KiB → en  300 (hueco de 480, resto 270)
  spotify  430 KiB → en 1600 (hueco de 560, resto 130)
  campus   110 KiB → en  100 (hueco de 120, resto 10)
  onedrive 470 KiB → no cabe (libres 920 KiB, mayor hueco 300)
  huecos: 10 270 210 300 130
== mejor ajuste
  gcc      210 KiB → en  900 (hueco de 210, resto 0)
  spotify  430 KiB → en  300 (hueco de 480, resto 50)
  campus   110 KiB → en  100 (hueco de 120, resto 10)
  onedrive 470 KiB → en 1600 (hueco de 560, resto 90)
  huecos: 10 50 300 90
== peor ajuste
  gcc      210 KiB → en 1600 (hueco de 560, resto 350)
  spotify  430 KiB → en  300 (hueco de 480, resto 50)
  campus   110 KiB → en 1810 (hueco de 350, resto 240)
  onedrive 470 KiB → no cabe (libres 920 KiB, mayor hueco 300)
  huecos: 120 50 210 300 240

Lo importante:

• validos deja solo los huecos con tamaño suficiente; si no queda ninguno, la petición fracasa.
• min(..., key=lambda h: h[1]) y max(...) eligen por tamaño, que es el segundo elemento de cada pareja (inicio, tamaño).
• huecos[i] = (h[0] + tam, h[1] - tam): el resto del hueco empieza donde acaba lo asignado. Si el resto es 0, el hueco desaparece al final.
• list(HUECOS) hace una copia para que las tres políticas empiecen con los mismos huecos.

Qué observar:

1. El primer ajuste mete a gcc en el hueco de 480 (el primero que le cabe) aunque el de 210 le iba justo.
2. El mejor ajuste mete a gcc en el de 210 con resto 0: aprovecha el hueco entero.
3. Cuando onedrive no cabe, hay 920 KiB libres y el mayor hueco es de 300: fragmentación externa de manual.
4. El peor ajuste entrega el hueco de 560 a gcc y lo deja en 350; luego campus se come parte de ese resto. Al final no queda ningún hueco grande.

Resumen

Concepto	En una frase
Dirección lógica / física	La que genera la CPU / la que llega a la RAM
MMU	Hardware que traduce lógicas a físicas en cada acceso
Reubicación estática / dinámica	La hace el cargador al cargar / el hardware al ejecutar
Base y límite	Física = base + lógica, solo si lógica < límite; si no, excepción
MFT / MVT	Particiones fijas al arrancar / variables con lista de huecos
Primer, mejor, peor ajuste	Primero que cabe / el que deja menos resto / el más grande
Fragmentación externa / interna	Huecos libres sueltos / espacio sin usar dentro de lo asignado
Segmentación	⟨s, d⟩ y tabla de segmentos con base y límite
Paginación	⟨p, d⟩, páginas y marcos del mismo tamaño, tabla de páginas
TLB	Caché de ⟨página, marco⟩; t = h·(T+M) + (1−h)·(T+2M)
Tamaño de la tabla	2^bits de página × tamaño de entrada
Jerárquica / invertida	La tabla se pagina (niveles + 1 accesos) / una entrada por marco para todo el sistema

Tres ideas para llevarte:

1. La MMU traduce cada acceso: con base y límite, con tabla de segmentos o con tabla de páginas, siempre se comprueba primero y se suma (o se sustituye) después.
2. Trocear el proceso ataca la fragmentación externa: la segmentación la atenúa y la paginación la elimina, a cambio de algo de fragmentación interna.
3. La paginación duplicaría el tiempo de acceso sin la TLB, y con direcciones grandes su tabla sería enorme sin niveles o tabla invertida.

Ahora toca demostrarlo. Primero, en la práctica guiada de gestión de memoria traducimos direcciones y calculamos el tiempo con TLB paso a paso; después, en los ejercicios tipo examen de gestión de memoria tienes un test con todos los formatos, cinco cálculos (traducir direcciones, tiempo efectivo, ajustes, tamaño de la tabla y segmentación) y preguntas de desarrollo. Y en el próximo tema daremos el paso que falta: la memoria virtual, que permite ejecutar procesos que no caben enteros en la RAM.

Siguiente paso: prácticaGestión de memoria — práctica con problemas guiados paso a paso: traducir con paginación, segmentación con límites, la TLB y un ejercicio con el formato del examen (y la dirección física que di para un segmento que no existía)

¿Te ha servido este artículo? Así puedes apoyar SergioLearns →