17 · Gestión del espacio libre

Apuntes propios sobre el capítulo 17 de OSTEP (Free-Space Management). Fuente: https://ostep.org

17.1 El problema

Gestionar memoria libre es trivial con unidades fijas (una lista de páginas iguales: coge una cualquiera). Se vuelve difícil con unidades de tamaño variable: es el caso de malloc/free dentro del heap de un proceso, y del SO gestionando segmentos (cap. 16). El enemigo: la fragmentación externa — espacio libre total suficiente, pero picado en trozos donde no cabe la petición.

Condiciones del juego para un asignador tipo malloc: free(ptr) no recibe el tamaño (hay que apañárselas), no se puede compactar (los punteros entregados son sagrados: no puedes mover memoria en uso), y la región gestionada es una (creciente con sbrk/mmap).

17.2 Mecanismos de base

Free list. Estructura que enumera los huecos libres: lista enlazada (construida dentro de la propia memoria libre: cada hueco guarda su tamaño y el puntero al siguiente).

División (splitting). Petición de 1 byte y hueco de 10 → se parte: 1 se entrega, 9 quedan en la lista.

Fusión (coalescing). Al liberar, si el bloque es adyacente a huecos libres, se fusionan en uno mayor. Sin fusión, tras muchas liberaciones la lista degenera en confeti aunque todo esté libre.

Cabeceras. Cómo sabe free() cuánto liberar: malloc reserva unos bytes extra antes del puntero devuelto — una cabecera con el tamaño (y típicamente un número mágico de integridad). free(ptr) mira en ptr - sizeof(header). Por eso pedir N bytes consume N + cabecera.

Crecer el heap. Lista vacía → pedir más al SO (sbrk/mmap) y añadirlo como hueco.

17.3 Políticas clásicas

¿Qué hueco elegir para una petición?

Política Idea Pros/contras
Best fit El hueco más pequeño que quepa Desperdicia poco por decisión… pero genera astillas diminutas inútiles; y buscar cuesta (recorrido completo)
Worst fit El hueco más grande Intención: dejar restos grandes y útiles. En la práctica, de lo peor: fragmenta y busca mucho
First fit El primero que quepa Rápido; tiende a acumular astillas al principio de la lista
Next fit Como first, pero desde donde quedó la última búsqueda Reparte las astillas por toda la lista; rendimiento ~first fit

Ninguna gana siempre: depende de la carga (tamaños y patrón de peticiones). Lección del capítulo: sin conocer la carga, solo hay compromisos.

17.4 Enfoques más elaborados

  • Listas segregadas: listas separadas por tamaños populares. Caso extremo y célebre: el slab allocator (Bonwick, Solaris 1994) para el kernel — cachés de objetos del mismo tipo (inodos, locks) preinicializados: asignar = sacar de la caché, liberar = devolver sin destruir. Linux lo usa (SLUB) para todos los objetos del kernel.
  • Buddy allocator: la memoria se parte recursivamente en mitades (potencias de 2). Asignar = bajar dividiendo hasta el tamaño justo; liberar = si tu “buddy” (la otra mitad) está libre, fusionar y subir recursivamente. Fusión elegantísima (el buddy se encuentra con un XOR de la dirección); fragmentación interna por el redondeo a potencia de 2. Es el asignador de páginas físicas de Linux (/proc/buddyinfo).
  • Escalabilidad: los asignadores modernos atacan además la velocidad y el multihilo — búsquedas O(1) con árboles/índices y arenas por hilo para no serializar en un lock global.

Ampliación (no está en OSTEP)

  • El malloc real de glibc (ptmalloc2): bins segregados por tamaño + arenas por hilo + umbral mmap para peticiones grandes. Los de alto rendimiento (jemalloc, tcmalloc, mimalloc) refinan lo mismo: clases de tamaño, caches por hilo sin locks, devolución de memoria al SO por rangos (madvise(MADV_DONTNEED)).
  • Robson (1971) probó cotas teóricas: cualquier asignador sin mover memoria puede necesitar ~log(ratio de tamaños) veces más memoria que la óptima — la fragmentación externa es matemáticamente inevitable, no un fallo de ingenio.
  • Los GC compactadores (Java, .NET) esquivan el teorema moviendo objetos (pueden, porque controlan todos los punteros): la respuesta del otro lado del espejo.

Referencias

  • OSTEP cap. 17.
  • Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review, IWMM 1995 — el survey definitivo.
  • Bonwick, The Slab Allocator, USENIX 1994.
  • Knuth, TAOCP vol. 1 §2.5 (buddy system).
  • Robson, An estimate of the store size necessary for dynamic storage allocation, JACM 1971.