¿En qué hueco cabe?

Operaciones sobre la memoria

La administración de memoria se reduce a tres operaciones: asignar un bloque de al menos el tamaño pedido, liberar un bloque que ya no se usa y compactar cuando los huecos quedan dispersos. Pueden hacerse a nivel del sistema operativo o de la aplicación: para pedidos pequeños, llamar al sistema provoca fragmentación interna, así que los compiladores suelen generar un heap que la biblioteca del programa administra por su cuenta.

Particiones fijas y variables

Antes se usaban particiones fijas: la memoria dividida en bloques iguales, o en grupos de tamaños predefinidos donde cada pedido iba a la partición más pequeña que lo contuviera. Eran simples, pero complicaban la programación (había que pensar en bloques, no en bytes, y usar superposiciones) y, sobre todo, causaban fragmentación interna.

Hoy se usan particiones variables: cada bloque se crea del tamaño que se pide y siempre es memoria contigua. Aprovechan mucho mejor la memoria, pero con el tiempo los huecos libres quedan repartidos: fragmentación externa. Para contenerla, al liberar un bloque se combina con sus vecinos libres; así, si se libera todo, vuelve a quedar un solo bloque del tamaño de la memoria.

Ajuste secuencial

Se mantiene una lista de bloques libres. Para un pedido de tamaño n se busca un bloque libre de tamaño k ≥ n, se marca como reservado y se saca de la lista. Si k es mayor que n, se decide si se divide (y el sobrante vuelve a la lista como bloque libre) o no (y queda como fragmentación interna). Al liberar, el bloque se marca libre y se une con sus vecinos libres. La política dice qué bloque elegir:

• Primer ajuste: el primero donde quepa. Simple y rápido, pero fragmenta mucho, porque divide bloques constantemente.
• Mejor ajuste: el más pequeño donde quepa. Guarda los bloques grandes para pedidos grandes, pero recorre toda la lista y deja astillas.
• Peor ajuste: el más grande. Lo que sobra queda útil, pero también recorre toda la lista.
• Óptimo ajuste: aplica el mejor ajuste sobre una muestra de la lista (por ejemplo N/e bloques) y luego toma el primero que supere al mejor de la muestra. Queda a medio camino entre primer y mejor ajuste, pero necesita saber cuántos bloques libres hay.

Dos optimizaciones: mantener la lista ordenada por tamaño (con el peor ajuste en orden descendente basta mirar el primer bloque, aunque liberar se vuelve más lento) y el apuntador vagabundo, que empieza cada búsqueda donde terminó la anterior para no acumular astillas en un solo punto.

Sistemas compañero

Los sistemas compañero no recorren listas: calculan. La memoria es un bloque de 2^U. Para un pedido de tamaño n, se divide el bloque por la mitad una y otra vez hasta tener el menor bloque de tamaño k con k ≥ n (y k/2 < n). Las dos mitades de una división son compañeras: tienen el mismo tamaño y salen del mismo bloque.

Al liberar un bloque, se une con su compañero si está libre, y así hacia arriba. La dirección del compañero se calcula con aritmética binaria: dirección del compañero = dirección del bloque XOR tamaño del bloque. Dos bloques libres vecinos no se unen si no son compañeros. Por eso aumenta la fragmentación interna (todo mide una potencia de 2) y aparece una variante de la externa.

El sistema Fibonacci divide según esa serie (… 8, 13, 21, 34, 55): un bloque de 55 se parte en 21 y 34, el de 21 en 8 y 13, y un pedido de 10 recibe el de 13. Desperdicia menos que las potencias de 2, pero calcular los compañeros es más complicado.

Compactación y recolección de basura

La compactación mueve todos los bloques ocupados a un extremo y deja un solo hueco libre. Exige que el sistema pueda relocalizar y bloquea a todos los procesos mientras dura, así que hay que equilibrar: compactar seguido da más memoria y peor rendimiento. Puede hacerse por demanda (cuando un pedido no cabe en ningún hueco pero sí en la suma de todos) o anticipada (un proceso de fondo mide un índice de fragmentación, como bloques libres entre bloques ocupados), y su alcance puede ser global o local.

La recolección de basura se usa en lenguajes donde no hay que liberar a mano. El algoritmo básico marca todos los bloques como libres, luego marca como ocupado cada bloque al que llega alguna variable, y enlaza en la lista de libres los que quedaron sin marcar. Otra estrategia lleva un contador por región: sube al asignarla a un apuntador y baja al soltarla; se eliminan las regiones con contador en cero.

Antes de leer la respuesta