Memoria en UNIX, Solaris y Linux

💡 En simple

Hasta ahora vimos las ideas en abstracto (Clock, buddy, tablas multinivel). Aquí está cómo las usan dos sistemas reales:

• UNIX SVR4 / Solaris reemplaza páginas con un reloj de dos manecillas: una «marca» las páginas y otra, un rato después, se lleva las que nadie volvió a tocar.
• Linux mantiene dos listas: páginas activas (usadas a menudo) y inactivas (candidatas a salir). Una página tiene que demostrar dos veces que es útil para subir a «activa».
• Para el propio kernel, que pide trocitos pequeños todo el tiempo, ambos usan variantes del buddy y de cachés de objetos (slab).

🎯 Al terminar podrás

1. Relacionar cada idea abstracta (Clock, buddy, multinivel, LRU) con cómo la usa SVR4/Solaris o Linux.
2. Explicar el reloj de dos manecillas y qué controlan scanrate y handspread.
3. Aplicar la regla del lazy buddy (D_i = A_i − L_i) a un caso concreto.
4. Describir cómo una página sube a la lista activa en el split LRU, y para qué sirve slab.

Antes necesitas: Clock · Buddy system · Tablas multinivel

• Visual mira el diagrama o la tabla y explica qué cambia en cada paso
• Socrático responde la pregunta guía antes de seguir leyendo
• Feynman explícalo en voz alta sin mirar y compara con la lista

Mapa de la página: cada mecanismo real es una idea que ya conoces, ajustada para memorias grandes.

Idea abstracta	SVR4 / Solaris	Linux
Clock (bit de uso)	reloj de dos manecillas	antes: Clock con age (tipo LFU) · ahora: split LRU con listas activa e inactiva
Buddy	lazy buddy para el kernel	buddy para grupos de 1 a 32 frames
Tabla multinivel	tabla por proceso + descriptor de bloque	PGD → PUD → PMD → PTE
Objetos pequeños	lazy buddy	slab (SLAB, SLUB, SLOB)

UNIX SVR4 y Solaris (§8.3)

SVR4 tiene dos esquemas separados:

• el sistema de paginación, para la memoria virtual de los procesos y para la caché de bloques de disco;
• el asignador de memoria del kernel, para los objetos del kernel.

Estructuras del sistema de paginación (tabla 8.6)

Estructura	Una por…	Campos importantes
Tabla de páginas	proceso (una entrada por página virtual)	nº de frame · age (cuánto tiempo sin referenciar; depende del procesador) · copy on write · modify · reference · valid · protect
Descriptor de bloque de disco	página virtual	dispositivo de swap · nº de bloque · tipo de almacenamiento (área de swap o el ejecutable; si hay que poner el frame en ceros antes de cargarlo)
Tabla de datos de frames (pfdata)	frame físico (indexada por nº de frame)	estado de la página (en swap, en el ejecutable o con DMA en curso) · contador de referencias (procesos que la usan) · dispositivo y bloque de la copia · punteros a la lista libre y a la cola hash
Tabla de uso de swap	dispositivo de swap (una entrada por página del dispositivo)	contador de PTE que apuntan a esa página en disco · identificador

💡 En simple: fotocopiar solo cuando alguien escribe

Después de un fork, padre e hijo comparten el mismo cuaderno en lugar de fotocopiarlo entero. Solo cuando uno de los dos quiere escribir en una hoja, se fotocopia esa hoja para él. Si el hijo hace exec enseguida, casi no se fotocopió nada.

🔮 Predice antes de seguir

Un proceso de 200 páginas hace fork() y el hijo llama a exec() de inmediato. Con COW, ¿cuántas páginas se copian?

Ya tengo mi respuesta: comparar

Casi ninguna. El fork solo duplica la tabla de páginas y marca los frames como compartidos de solo lectura. Como el hijo hace exec antes de escribir, nadie dispara el fallo de protección y no se copia ninguna página de datos. A lo sumo se copian las pocas que el hijo alcance a escribir antes del exec, como la de la pila. Sin COW se habrían copiado las 200.

Copy on write (COW) es lo que hace barato a fork():

1. Padre e hijo comparten los frames, marcados como de solo lectura y con el bit COW.
2. Cuando uno de los dos escribe, se produce un fallo de protección y el kernel recién entonces copia esa página.

Cómo leerlo: a la izquierda, después del fork: las dos tablas apuntan a los mismos frames, marcados de solo lectura. A la derecha, el hijo escribió en su página 1: el fallo de protección hace que el kernel copie solo esa página a un frame nuevo (verde) y cambie la flecha del hijo. La página 0 sigue compartida.

Si el hijo hace exec enseguida, casi no se copia nada (ver fork).

El reloj de dos manecillas (fig. 8.21)

💡 En simple: el que pega stickers y el que pasa después

Dos empleados recorren las estanterías, uno detrás del otro:

1. El primero pega un sticker de «¿alguien usa esto?» en cada producto (pone el bit de referencia en 0).
2. El segundo, un rato después, revisa: si alguien quitó el sticker (el producto se usó), lo deja; si el sticker sigue ahí, nadie lo usó y lo retira.

Mientras menos espacio libre queda, más rápido caminan los dos.

El reemplazo usa la tabla de frames. Los frames libres están en una lista; cuando bajan de un umbral, el kernel «roba» frames. El algoritmo es un Clock refinado con dos manecillas que recorren la lista de páginas elegibles (no bloqueadas):

1. La manecilla delantera (fronthand) pone el bit de referencia en 0 en cada página que pasa.
2. Un rato después pasa la manecilla trasera (backhand) por la misma página:
   • si el bit está en 1, la página se usó en ese intervalo: se deja;
   • si sigue en 0, nadie la tocó: va a la lista para expulsar.

Cómo leerlo: cada círculo es una página y el número es su bit R. La delantera va adelante apagando bits; la trasera la sigue a una distancia fija (el handspread, arco punteado). Las páginas entre las dos tienen un tiempo para volver a usarse: la que tiene un 1 se usó en ese intervalo y se salvará. La de arriba sigue en 0 cuando llega la trasera, así que se expulsa. Ejemplo propio.

Parámetro	Qué controla
scanrate	páginas por segundo que recorren las manecillas. Varía linealmente entre slowscan y fastscan a medida que la memoria libre baja de lotsfree a minfree: con menos memoria libre, las manecillas giran más rápido
handspread	distancia entre las dos manecillas

Juntos determinan la ventana de oportunidad: cuánto tiempo tiene una página para ser usada antes de que la expulsen.

¿Por qué dos manecillas y no una (el Clock normal)?

Con un puntero, el tiempo entre apagar el bit y volver a revisarlo es una vuelta completa. Con memorias enormes, eso puede tardar muchísimo, y casi todas las páginas tendrían el bit en 1 (todo parece «usado»). Con dos manecillas, el intervalo de observación queda fijado por el handspread y el scanrate, y no por el tamaño de la memoria. Además se puede ajustar en caliente según la presión de memoria.

Asignador del kernel: lazy buddy

💡 En simple: no volver a pegar el chocolate

En el buddy normal, cuando dos mitades quedan libres se pegan enseguida. Pero si al segundo alguien pide otra vez una mitad, hay que volver a partir. El lazy buddy («buddy perezoso») deja algunas mitades sin pegar, porque probablemente las vuelvan a pedir pronto. Solo las une cuando sobran demasiadas.

El kernel crea y destruye objetos pequeños todo el tiempo: buffers de rutas, buffers de STREAMS, estructuras proc, vnodes, zombies. Paginar para eso sería ineficiente.

SVR4 usa un buddy (ver buddy system), pero el buddy pierde tiempo en partir y fusionar: si liberas un bloque de $2^i$ y se fusiona enseguida, quizá la próxima petición sea otra vez de $2^i$ y haya que partirlo de nuevo.

El lazy buddy (Barkley y Lee) demora la fusión hasta que parece necesaria. Para cada tamaño $2^i$ lleva estas cuentas:

• $N_i = A_i + G_i + L_i$:
  • $A_i$: bloques asignados;
  • $G_i$: bloques libres globalmente, que sí se pueden fusionar;
  • $L_i$: bloques libres localmente, que se guardan sin fusionar porque se espera volver a pedirlos.
• Criterio: que los libres locales no superen a los asignados, $L_i \le A_i$. Se usa la variable de demora $D_i = A_i - L_i$:
  • si $D_i \ge 2$, el bloque liberado queda libre local (sin fusionar);
  • si $D_i = 1$, se libera globalmente y se fusiona si se puede;
  • si $D_i = 0$, se libera globalmente y además se libera globalmente un bloque libre local.

Cómo leerlo: D mide cuánta demanda hay: muchos bloques asignados frente a pocos guardados. Con D alto conviene guardar el bloque sin fusionar, porque lo van a volver a pedir. Con D bajo ya sobran guardados, así que se fusiona.

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

Complétalo: lazy buddy para bloques de 2ⁱ

Para cierto tamaño hay A_i = 5 bloques asignados y L_i = 3 libres locales. Se libera un bloque. Calcula D_i = A_i − L_i y decide qué pasa con él. Después repite con A_i = 4 y L_i = 3.

Comparar

• A = 5, L = 3 → D = 2 ≥ 2: el bloque queda libre local, sin fusionar.
• A = 4, L = 3 → D = 1: se libera globalmente y se fusiona con su buddy si este está libre.
• La idea: mientras haya muchos asignados en comparación con los guardados, conviene guardar el bloque para la próxima petición del mismo tamaño.

Linux (§8.4)

La unidad básica es la página física (struct page), normalmente de 4 KB. Linux también soporta HugePages (por ejemplo, 2 MB), que reducen los fallos de TLB. DPDK las usa para los buffers de red.

Direccionamiento virtual: tablas de varios niveles

En el modelo que describe Stallings, la dirección virtual tiene cuatro campos:

┌──────────────────┬──────────────────────┬────────────────┬────────┐
│ page directory   │ page middle directory│  page table    │ offset │
└──────────────────┴──────────────────────┴────────────────┴────────┘

• Page directory: uno por proceso activo, del tamaño de una página y siempre en RAM.
• Page middle directory: puede ocupar varias páginas.
• Page table: cada entrada apunta a una página virtual.

Se diseñó para el Alpha de 64 bits (tres niveles en hardware). En x86 de 32 bits, que tiene dos niveles, el middle directory se define de tamaño 1 y el compilador elimina ese nivel: no hay costo en tiempo de ejecución. El x86-64 actual usa 4 niveles (PGD → PUD → PMD → PTE), y 5 con LA57. La idea es la misma: tabla multinivel.

Cómo leerlo: es el diagrama de dos niveles de paginación, pero con cuatro tablas encadenadas. Cada campo de 9 bits elige una de las 512 entradas de su tabla, y esa entrada dice dónde está la tabla siguiente. CR3 apunta a la primera y el offset baja directo a la página.

Asignación de páginas: buddy

Para leer y escribir bloques contiguos eficientemente, Linux mantiene grupos de 1, 2, 4, 8, 16 o 32 frames contiguos y los parte o fusiona con el algoritmo buddy.

Reemplazo: de «age» al split LRU

Versión	Algoritmo
Antes de 2.6.28	Clock con una variable age de 8 bits en lugar del bit de uso. Cada acceso la incrementa y un barrido periódico la decrementa. Una página con age = 0 es la mejor víctima. Es una forma de LFU (menos frecuentemente usada). Problema: los barridos cuestan cada vez más CPU con memorias grandes
Desde 2.6.28: split LRU	dos listas por zona de memoria, activa e inactiva, y dos flags por página, PG_active y PG_referenced. El demonio kswapd recorre periódicamente las PTE y limpia los bits de acceso

Ciclo de vida de una página (fig. 8.24):

1. Primer acceso a una página inactiva: se pone PG_referenced.
2. Segundo acceso (en otro barrido): la página pasa a la lista activa. Hacen falta dos accesos en barridos distintos para ser activa.
3. Si el segundo acceso no llega a tiempo, PG_referenced se borra.
4. Igual al revés: hacen falta dos «timeouts» para bajar de activa a inactiva.
5. Las víctimas salen de la lista inactiva, con un criterio tipo LRU.

Cómo leerlo: cada acceso mueve la página una casilla a la derecha (verde) y cada timeout del barrido, una a la izquierda. Desde la izquierda del todo hasta la lista activa hacen falta dos accesos; para volver, dos timeouts. Así una página usada una sola vez no desplaza a las que se usan seguido.

Memoria del kernel: slab

💡 En simple: un organizador de tornillos

El buddy entrega páginas enteras (4 KB), pero el kernel pide todo el tiempo objetos chiquitos (64 bytes, 128 bytes…). Darle una página entera a cada uno sería como usar una caja de mudanza para guardar un tornillo.

Slab es un organizador con cajoncitos de tamaño fijo: toma una página y la divide en muchos huecos del mismo tamaño para un tipo de objeto. Pedir y devolver un objeto es tomar o dejar un cajoncito.

La base es el asignador de páginas (buddy), pero su unidad mínima es una página. Para trozos pequeños y de tamaños raros, Linux usa slab dentro de páginas ya asignadas. En x86 los trozos son de 32, 64, 128, 252, 508, 2040 o 4080 bytes, con una lista por tamaño.

Cómo leerlo: el buddy solo sabe dar páginas enteras. Slab toma una y la corta en huecos iguales para un tamaño de objeto: pedir memoria es tomar un hueco libre y liberar es devolverlo. Lo que sobra dentro del hueco (28 B en el ejemplo) es fragmentación interna. El dibujo usa como ejemplo una caché de 128 B.

Asignador	Objetivo
SLAB	lo más amigable posible con la caché (menos fallos de caché); el más usado
SLUB (unqueued slab)	simple, con menos instrucciones (el predeterminado en los kernels actuales)
SLOB (simple list of blocks)	lo más compacto posible, para sistemas con poca memoria

⚠️ Errores que cuestan puntos

• Creer que la manecilla delantera expulsa páginas.La delantera solo pone el bit en 0. La trasera expulsa las que siguen en 0 cuando pasa ella.
• Decir que el split LRU sube una página a activa con un solo acceso.Hacen falta dos accesos en barridos distintos (PG_referenced y luego PG_active).
• Pensar que slab reemplaza al buddy.Slab trabaja dentro de páginas que el buddy ya entregó. El buddy sigue siendo la base.

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. En el reloj de dos manecillas de SVR4, la manecilla trasera expulsa las páginas con…

a) bit de referencia en 1b) bit de referencia en 0: nadie las usó desde que pasó la delanterac) bit modify en 1d) age máximo

2. Si la memoria libre baja, el scanrate…

a) bajab) sube: las manecillas giran más rápidoc) no cambiad) se pone en 0

3. Copy on write sirve para…

a) bloquear framesb) que fork no copie páginas hasta que alguien escribac) el swapd) la TLB

4. El lazy buddy…

a) fusiona siempre de inmediatob) demora la fusión manteniendo bloques libres localesc) no usa potencias de 2d) es para memoria de usuario

5. En el split LRU de Linux, una página pasa a la lista activa…

a) al primer accesob) tras dos accesos en barridos distintosc) cuando age = 0d) nunca

6. slab sirve para…

a) páginas de usuariob) objetos pequeños del kernel dentro de páginas ya asignadasc) el TLBd) el swap

7. ¿Qué asignador de Linux busca ser lo más compacto posible?

a) SLABb) SLUBc) SLOBd) buddy

🗣️ Explícalo tú (Feynman)

¿Por qué Solaris usa dos manecillas en vez del Clock normal de un solo puntero? Explícalo con una memoria de 64 GB como ejemplo.

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…

• Con un solo puntero, el tiempo entre apagar un bit y revisarlo es una vuelta completa, y con 64 GB eso tarda muchísimo.
• En ese tiempo casi todas las páginas se vuelven a usar, así que todas parecen «útiles» y el algoritmo no distingue nada.
• Con dos manecillas, la ventana de observación la fija el handspread (y el scanrate), no el tamaño de la RAM.
• Con poca memoria libre, el scanrate sube y la ventana se acorta.

📈 ¿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.3 (UNIX and Solaris Memory Management: tabla 8.6, fig. 8.21, lazy buddy fig. 8.22) · Stallings 9e §8.4 (Linux Memory Management: fig. 8.23, 8.24, slab)