Gestión de memoria — ejercicios tipo examen con direcciones que traducir, una TLB que acierta y huecos que no alcanzan (y el medio nanosegundo que perdí por no sumar la TLB)

Respuesta: Una dirección lógica (o virtual)

Dirección lógica o virtual: la que genera la CPU. Dirección física: la que recibe el chip de memoria. Entre las dos está la MMU.

Respuesta: Traduce las direcciones lógicas que genera la CPU a direcciones físicas

La MMU (unidad de manejo de memoria) es un dispositivo hardware: si la traducción la hiciera el SO por software en cada acceso, el ordenador sería lentísimo.

Respuesta: Que la RAM no tenga sitio para todos los procesos que quieren ejecutarse · Que un proceso lea o escriba en la zona de otro proceso o del SO · Que los procesos solo accedan a las zonas que el SO les ha permitido

Los dos grandes problemas son la falta de capacidad (no cabe todo) y la protección (cada proceso, en su zona). La tercera opción es la misma idea vista desde el SO.

Respuesta: Aprovechar al máximo la memoria principal · Tener varios procesos cargados sin que el sistema se venga abajo · Que un programa pueda ejecutarse sin estar entero en la memoria principal

Rendimiento = sacar partido a la RAM. Proteger al SO y a cada proceso, y permitir compartir zonas, es el otro bloque de objetivos: protección y compartición.

• Reubicación → Que un programa pueda vivir en cualquier zona de la memoria física
• Fragmentación → Huecos libres que quedan entre zonas asignadas y que acaban sin servir
• Tiempo de acceso → La gestión de memoria no debe hacer mucho más lento cada acceso

Son los tres conceptos clave del tema. La opción sobrante es falsa: el núcleo está una sola vez en la RAM.

Orden correcto:

1. Programa fuente
2. Compilación
3. Módulo objeto
4. Enlazado
5. Programa ejecutable
6. Carga en memoria
7. Ejecución

El compilador produce el objeto, el enlazador lo junta con otros objetos y bibliotecas en un ejecutable, y el cargador lo pone en memoria para que se ejecute.

Para que un programa pueda colocarse en cualquier parte de la RAM, el compilador genera direcciones reubicables, que no son definitivas. Si el cargador las convierte al cargar el programa, la reubicación es estática; si las traduce el hardware mientras se ejecuta, es dinámica.

Con direcciones absolutas el programa solo podría ir a una zona fija: no sería reubicable. La reubicación dinámica es la que hace la MMU en cada acceso.

• V — Delimitan la zona de memoria en la que el proceso puede trabajar.
• F — Si la dirección está fuera de la zona, la petición sale al bus y la memoria la rechaza.
• V — Un acceso ilegal provoca una excepción.
• V — La comprobación solo se hace en modo usuario: el núcleo puede tocar toda la memoria.

El acceso indebido no llega al bus: lo corta el circuito de comprobación antes y salta una excepción. En modo núcleo no hay comprobación.

Respuesta: 52730

Física = base + lógica = 52000 + 730 = 52730 (suponiendo que 730 es menor que el límite).

Una biblioteca compartida se carga la primera vez que algún proceso llama a una de sus funciones; por eso se habla de enlace dinámico. En Windows se llaman DLL. Las llamadas pasan por una tabla indirecta que gestiona el SO, y aunque la usen diez procesos solo hay una copia en memoria.

En Unix y GNU/Linux se llaman shared libraries (.so). Si la memoria está muy llena, el SO puede sacar las que nadie referencia.

Respuesta: La imagen de onedrive, porque lleva mucho tiempo bloqueado

Swap out = volcar a disco la imagen de un proceso bloqueado; swap in = traerla de vuelta cuando vuelve a hacer falta. Su coste es el tiempo de esas copias.

Respuesta: MFT

MFT: particiones fijas, rígida pero muy eficiente. Su evolución, MVT, crea particiones de tamaño variable con una lista dinámica de huecos.

• Primer ajuste → El primero que encuentra al recorrer la lista
• Mejor ajuste → El que deja el resto libre más pequeño
• Peor ajuste → El más grande de todos

En inglés: first-fit, best-fit y worst-fit. El mejor ajuste tiene un riesgo: va dejando restos diminutos que no sirven.

Respuesta: Primer y mejor ajuste rinden parecido, y mejor que peor ajuste

Los sistemas reales usan algoritmos más elaborados; Linux, por ejemplo, el sistema buddy (de parejas).

• V — Puede haber más memoria libre en total de la que pide un proceso y aun así no poder dárselo.
• F — La compactación funciona igual con reubicación estática que con dinámica.
• V — Compactar consume tiempo, porque hay que copiar bloques de memoria.
• V — Trocear el proceso (segmentación o paginación) es otra forma de atacar la fragmentación.

Compactar mueve los procesos de sitio, así que solo es posible si sus direcciones se traducen al ejecutarse: reubicación dinámica.

Respuesta: Reduce la fragmentación frente a la memoria contigua · Permite compartir un segmento entre procesos, como el código de una DLL · Permite proteger segmentos, por ejemplo marcarlos de solo lectura o de código

Inconvenientes: el compilador trabaja con direcciones de dos dimensiones, hace falta hardware, cada acceso es más lento y su eficacia depende de cómo se trocee el programa.

Respuesta: Un par ⟨segmento, desplazamiento⟩

El compilador identifica los segmentos, el cargador coloca cada uno en una zona y la MMU traduce con la tabla de segmentos (una pareja base y límite por segmento).

Respuesta: Marcos

Página = trozo de la memoria lógica; marco = trozo de la memoria física. Al tener el mismo tamaño, cualquier marco libre sirve para cualquier página.

Traducir en paginación es averiguar qué marco guarda cada página del proceso. Lo hace la MMU consultando la tabla de páginas del proceso, que está en la memoria principal. Por eso, sin ayuda, cada acceso a memoria cuesta dos accesos a la RAM.

Un acceso para leer la entrada de la tabla y otro para el dato. La TLB existe precisamente para ahorrarse el primero.

Respuesta: Desaparece la externa, pero hay interna en la última página de cada proceso

Un proceso de 13000 bytes con páginas de 4 KiB ocupa 4 páginas (16384 bytes): 3384 bytes asignados que no usa nadie. Eso es fragmentación interna.

Respuesta: Registro base de la tabla de páginas

El RBTP apunta a la tabla de páginas en la RAM. Su compañero, el RLTP (registro de longitud), dice cuántas entradas tiene y sirve para detectar páginas fuera de rango.

Respuesta: Bits de lectura, escritura y ejecución en cada entrada · El bit de validez · El registro de longitud de la tabla de páginas (RLTP) · La tabla de páginas invertida, en la que solo están las páginas válidas

Con bits de protección se puede tener, por ejemplo, el código de solo lectura y ejecución, y los datos de lectura y escritura.

Respuesta: Disminuye la fragmentación interna · La tabla de páginas tiene más entradas

Página pequeña: menos desperdicio en la última página, pero tabla más grande. Página grande: lo contrario.

La TLB es una pequeña caché asociativa dentro del procesador que guarda algunas entradas de la tabla de páginas. Se consulta casi tan rápido como los registros de la CPU y sirve para traducir direcciones lógicas a físicas sin leer la tabla de páginas.

Asociativa = busca la página en todas sus entradas a la vez. Por eso es tan rápida y por eso es pequeña (de 4 a 64 entradas en procesadores reales).

Respuesta: Clave: número de página lógica. Valor: número de marco

Acierto de TLB: la página lógica está entre las claves y sale su marco. Fallo de TLB: no está; se lee la tabla de páginas y se guarda el par en la TLB.

• V — En un cambio de contexto hay que vaciarla o cargarla con las entradas del proceso que entra.
• V — En sistemas reales es normal acertar entre el 80 % y el 98 % de las veces.
• F — Si la TLB está llena, un fallo obliga a vaciarla entera.
• F — Con un acierto de TLB no hace falta acceder a la RAM.

Si está llena se reemplaza una entrada (la más vieja, la menos usada, una al azar…). Y con acierto se ahorra el acceso a la tabla, pero el dato sigue estando en la RAM: un acceso.

Respuesta: 64

Acierto: 4 + 50 = 54 ns. Fallo: 4 + 50 + 50 = 104 ns. Efectivo: 0,8·54 + 0,2·104 = 43,2 + 20,8 = 64 ns.

Orden correcto:

1. La CPU genera la dirección lógica (p, d)
2. Se busca p en la TLB y no está
3. Se lee la entrada p de la tabla de páginas en la RAM
4. Se guarda el par (p, marco) en la TLB
5. Se forma la dirección física (marco, d)
6. Se accede al dato en la RAM

Dos accesos a la RAM: el de la tabla y el del dato. La próxima vez que se use esa página, si sigue en la TLB, será un acierto.

• Paginación jerárquica → La propia tabla de páginas se divide en páginas, en varios niveles
• Tabla invertida → Una sola tabla global con una entrada por cada marco de la RAM
• Tabla hash de páginas → La entrada se localiza con una función hash del número de página

La solución «fácil» sería agrandar la página, pero aumenta la fragmentación interna.

Respuesta: 5

Uno por cada nivel de tabla más el del dato: 4 + 1 = 5. Con dos niveles (x86 de 32 bits) son 3; con tres niveles, 4.

Respuesta: Qué proceso (pid) y qué página lógica están en el marco 9

Hay una entrada por cada marco real. Ahorra mucha memoria, pero buscar el par (pid, página) es lento: se usa una función hash y se confía en la TLB. La han usado PowerPC, UltraSPARC e IA-64.

Con 4 KiB = 2^12, los 12 bits bajos son el desplazamiento y los 4 altos la página; en hexadecimal, el primer dígito es la página. Por ejemplo, 0x2B10 = 11024 = 2·4096 + 2832: página 2, desplazamiento 2832. La tabla dice marco 11, así que la física es 11·4096 + 2832 = 47888 (0xBB10).

El desplazamiento nunca cambia al traducir: solo se cambia la página por el marco. 0x1FFF es el último byte de la página 1 (desplazamiento 4095).

Acierto = TLB + RAM (el dato). Fallo = TLB + un acceso por cada nivel de tabla + el dato. Efectivo = h·acierto + (1 − h)·fallo.

A: 0,8·110 + 0,2·210 = 88 + 42 = 130. B: 0,95·52 + 0,05·102 = 49,4 + 5,1 = 54,5. C: 0,75·84 + 0,25·164 = 63 + 41 = 104.

D: con dos niveles, un fallo cuesta 5 + 60 + 60 + 60 = 185 ns, así que 0,9·65 + 0,1·185 = 58,5 + 18,5 = 77 ns: 6 ns más que con un nivel (71).

Primer ajuste: A entra en el primero que cabe (600 → quedan 360), B en 520, C en 150 y D (370) ya no cabe, porque el mayor hueco es de 360: los huecos son 0, 360, 250, 350 y 20.

Mejor ajuste: A elige el más justo, 250 (resto 10); B, 520; C, 150; D, 600 (quedan 230): todos caben, porque el hueco grande seguía entero.

Peor ajuste: A coge el mayor, 600 (quedan 360); B, 520; C, el mayor que queda, 360 (quedan 220); D no cabe: los huecos son 150, 220, 250, 350 y 20.

Fíjate en que el peor ajuste rompe el hueco grande primero y luego no le queda ninguno para D.

Bits de desplazamiento = log2 del tamaño de página (4 KiB → 12, 16 KiB → 14, 1 KiB → 10, 512 B → 9). Bits de página = bits de la dirección − bits de desplazamiento. Entradas = 2^bits de página. Tamaño = entradas × bytes por entrada.

Fila 1: 32 − 12 = 20 bits, 2^20 = 1 048 576 entradas × 4 B = 4 MiB = 4096 KiB. Fila 2: cuadruplicar la página (de 4 a 16 KiB) quita 2 bits y divide la tabla entre 4: 1024 KiB. Fila 3: 2^14 × 2 B = 32 KiB. Fila 4: 2^11 × 4 B = 8 KiB.

Primero se compara el desplazamiento con el límite de su segmento; solo si es menor se suma la base.

⟨0, 1200⟩: 1200 < 2500 → 6000 + 1200 = 7200. ⟨1, 900⟩: 900 ≥ 800 → excepción. ⟨2, 3999⟩: el último byte válido, 15000 + 3999 = 18999. ⟨3, 1000⟩: 1000 no es menor que 1000 → excepción (el límite es el tamaño: los desplazamientos válidos van de 0 a 999). ⟨1, 50⟩: 1200 + 50 = 1250.

Respuesta modelo:

El compilador genera direcciones reubicables, que no son definitivas. La reubicación consiste en convertirlas en direcciones físicas, y la diferencia está en cuándo se hace.

En la reubicación estática la conversión la hace el cargador, una sola vez, al cargar el programa en memoria. A partir de ahí las direcciones del proceso son físicas y fijas: si el proceso se moviera, apuntarían a la zona antigua.

En la reubicación dinámica el proceso conserva sus direcciones lógicas y es el hardware (la MMU) quien las traduce en cada acceso, por ejemplo sumando un registro base: física = base + lógica.

Compactar significa mover procesos para juntar los huecos libres. Con reubicación dinámica basta con copiar el proceso y cambiar su registro base; con reubicación estática habría que corregir todas sus direcciones, cosa que no se puede hacer.

Respuesta modelo:

Las dos son técnicas de memoria no contigua: el proceso se trocea y cada trozo puede ir a una zona distinta de la RAM.

En la segmentación los trozos son lógicos y de tamaño variable (código, datos, pila…). La dirección es ⟨segmento, desplazamiento⟩ y la MMU usa una tabla de segmentos con una base y un límite por segmento: si el desplazamiento es menor que el límite, física = base + desplazamiento; si no, excepción. Reduce la fragmentación externa, pero no la elimina, y facilita compartir y proteger segmentos enteros.

En la paginación los trozos son de tamaño fijo (páginas) y la RAM se divide en marcos del mismo tamaño. La dirección es ⟨página, desplazamiento⟩ y la MMU usa una tabla de páginas que da el marco de cada página: física = marco · tamaño + desplazamiento. No hay fragmentación externa (cualquier marco libre vale), pero sí interna en la última página.

La segmentación respeta cómo ve el programador su programa; la paginación es invisible para él y mucho más fácil de gestionar.

Respuesta modelo:

En los sistemas actuales la tabla de páginas está en la memoria principal, así que cada acceso de un programa costaría dos accesos a la RAM: uno para leer la entrada de la tabla y otro para el dato.

La TLB es una pequeña caché asociativa dentro del procesador que guarda pares ⟨página lógica, marco⟩. Al traducir, se busca la página en todas sus entradas a la vez. Si está (acierto), se obtiene el marco sin leer la tabla y solo se accede a la RAM para el dato. Si no está (fallo), se lee la tabla de páginas, se forma la dirección y se guarda la traducción en la TLB, reemplazando una entrada si está llena.

Acierto: 5 + 60 = 65 ns. Fallo: 5 + 60 + 60 = 125 ns. Tiempo efectivo: 0,9 · 65 + 0,1 · 125 = 58,5 + 12,5 = 71 ns, muy cerca de los 60 ns de un acceso directo.

En un cambio de contexto la TLB se vacía o se carga con las entradas del proceso que entra, porque las traducciones de un proceso no valen para otro.

Respuesta modelo:

4 KiB = 2^12, así que hay 12 bits de desplazamiento y 32 − 12 = 20 bits de página: 2^20 = 1 048 576 entradas. A 4 bytes por entrada, la tabla ocupa 4 MiB por proceso, y con direcciones de 48 o 64 bits sería mucho peor.

Paginación jerárquica: la propia tabla se pagina. En x86 de 32 bits la dirección se parte en 10 + 10 + 12 bits: una tabla exterior apunta a tablas interiores, y solo existen las interiores que el proceso usa. Inconveniente: sin acierto de TLB hacen falta tres accesos a la RAM (niveles + 1), así que la TLB se vuelve aún más necesaria.

Tabla de páginas invertida: una sola tabla para todo el sistema, con una entrada por marco que dice qué proceso (pid) y qué página hay en él. Ahorra muchísima memoria, pero buscar el par ⟨pid, página⟩ es lento; se resuelve con una tabla hash y confiando en la TLB.

La solución fácil, agrandar la página, encoge la tabla pero aumenta la fragmentación interna.