Asignación de memoria de amigos

La técnica de asignación de memoria de amigos es un algoritmo de asignación de memoria que divide la memoria en particiones para intentar satisfacer una solicitud de memoria de la manera más adecuada posible. Este sistema utiliza la división de la memoria en mitades para intentar lograr un mejor ajuste. Según Donald Knuth, el sistema de amigos fue inventado en 1963 por Harry Markowitz y descrito por primera vez por Kenneth C. Knowlton (publicado en 1965). La asignación de memoria de Buddy es relativamente fácil de implementar. Admite una división y fusión limitada pero eficiente de bloques de memoria.

Algoritmo

Hay varias formas del sistema de compañeros; aquellas en las que cada bloque se subdivide en dos bloques más pequeños son la variedad más sencilla y común. Cada bloque de memoria en este sistema tiene un orden, donde el orden es un número entero que va desde 0 hasta un límite superior específico. El tamaño de un bloque de orden n es proporcional a 2ⁿ, de modo que los bloques tienen exactamente el doble de tamaño que los bloques de un orden inferior. Los tamaños de bloques de potencia de dos simplifican el cálculo de direcciones, porque todos los compañeros están alineados en límites de direcciones de memoria que son potencias de dos. Cuando se divide un bloque más grande, se divide en dos bloques más pequeños, y cada bloque más pequeño se convierte en un compañero único para el otro. Un bloque dividido solo se puede fusionar con su bloque amigo único, que luego reforma el bloque más grande del que se separó.

Para empezar, se determina el tamaño del bloque más pequeño posible, es decir, el bloque de memoria más pequeño que se puede asignar. Si no existiera ningún límite inferior (por ejemplo, fueran posibles asignaciones de tamaño de bits), habría mucha memoria y sobrecarga computacional para que el sistema realizara un seguimiento de qué partes de la memoria están asignadas y no asignadas. Sin embargo, puede ser deseable un límite bastante bajo, de modo que se minimice el desperdicio promedio de memoria por asignación (con respecto a asignaciones que, en tamaño, no son múltiplos del bloque más pequeño). Normalmente, el límite inferior sería lo suficientemente pequeño como para minimizar el espacio promedio desperdiciado por asignación, pero lo suficientemente grande como para evitar una sobrecarga excesiva. El tamaño de bloque más pequeño se toma entonces como el tamaño de un bloque de orden 0, de modo que todos los órdenes superiores se expresan como potencias de dos múltiplos de este tamaño.

El programador luego tiene que decidir, o escribir código para obtener, el orden más alto posible que pueda caber en el espacio de memoria disponible restante. Dado que la memoria total disponible en un sistema informático determinado puede no ser un múltiplo de una potencia de dos del tamaño mínimo de bloque, es posible que el tamaño de bloque más grande no abarque toda la memoria del sistema. Por ejemplo, si el sistema tuviera 2000 K de memoria física y el tamaño del bloque de orden 0 fuera 4 K, el límite superior del orden sería 8, ya que un bloque de orden 8 (256 bloques de orden 0, 1024 K) es el bloque más grande que cabe en la memoria. En consecuencia, es imposible asignar toda la memoria física en un solo fragmento; los 976 K restantes de memoria tendrían que asignarse en bloques más pequeños.

Ejemplo

El siguiente es un ejemplo de lo que sucede cuando un programa realiza solicitudes de memoria. Supongamos que en este sistema, el bloque más pequeño posible tiene un tamaño de 64 kilobytes y el límite superior para el orden es 4, lo que da como resultado el bloque asignable más grande posible, 2⁴ multiplicado por 64 K = 1024 K. en tamaño. A continuación se muestra un posible estado del sistema después de varias solicitudes de memoria.

Esta asignación podría haber ocurrido de la siguiente manera

1. La situación inicial.
2. Programa A pide memoria 34 K, orden 0.
   1. No hay orden 0 bloques disponibles, por lo que un orden 4 bloque se divide, creando dos orden 3 bloques.
   2. Todavía no hay orden 0 bloques disponibles, por lo que el primer orden 3 bloques se divide, creando dos orden 2 bloques.
   3. Aún sin orden 0 bloques disponibles, por lo que el primer orden 2 bloques se divide, creando dos orden 1 bloques.
   4. Aún sin orden 0 bloques disponibles, por lo que el primer pedido 1 bloque se divide, creando dos orden 0 bloques.
   5. Ahora hay un orden 0 bloque disponible, por lo que se asigna a A.
3. Programa B pide memoria 66 K, orden 1. Un pedido 1 bloque está disponible, por lo que se asigna a B.
4. Programa C pide memoria 35 K, orden 0. Un orden 0 bloque está disponible, por lo que se asigna a C.
5. Programa D pide memoria 67 K, orden 1.
   1. No hay orden 1 bloques disponibles, por lo que un orden 2 bloques se divide, creando dos orden 1 bloques.
   2. Ahora hay un pedido 1 bloque disponible, por lo que se asigna a D.
6. Programa B libera su memoria, liberando un pedido 1 bloque.
7. El programa D libera su memoria.
   1. Una orden 1 bloque es liberado.
   2. Dado que el bloque amigo del nuevo bloque liberado también es libre, los dos se fusionan en un solo orden de 2 bloques.
8. Programa Una libera su memoria, liberando un pedido 0 bloque.
9. Programa C libera su memoria.
   1. Una orden 0 bloque es liberado.
   2. Dado que el bloque amigo del nuevo bloque liberado también es libre, los dos se fusionan en un solo orden 1 bloque.
   3. Dado que el bloque amigo del nuevo pedido formado 1 bloque también es libre, los dos se fusionan en un solo orden 2 bloque.
   4. Dado que el bloque amigo del nuevo pedido 2 bloque es también libre, los dos se fusionan en un solo orden 3 bloque.
   5. Dado que el bloque amigo del nuevo pedido 3 bloque es también libre, los dos se fusionan en un solo orden 4 bloque.

Como puedes ver, lo que sucede cuando se realiza una solicitud de memoria es lo siguiente:

• Si se desea asignar la memoria

1. Busque una ranura de memoria de un tamaño adecuado (el mínimo 2^k bloque que es mayor o igual al de la memoria solicitada)
   1. Si se encuentra, se asigna al programa
   2. Si no, intenta hacer una ranura de memoria adecuada. El sistema lo hace al intentar lo siguiente:
      1. Dividir una ranura de memoria libre más grande que el tamaño de memoria solicitado en la mitad
      2. Si se alcanza el límite inferior, entonces asigne esa cantidad de memoria
      3. Volver al paso 1 (mirar una ranura de memoria de un tamaño adecuado)
      4. Repita este proceso hasta que se encuentre una ranura de memoria adecuada

• Si la memoria es ser liberada

1. Libre el bloque de memoria
2. Mira el bloque vecino - ¿Es gratis también?
3. Si lo es, combinar los dos, y volver al paso 2 y repetir este proceso hasta que se alcance el límite superior (toda la memoria se libera), o hasta que se encuentre un bloque vecino no libre

Implementación y eficiencia

En comparación con otras técnicas más simples, como la asignación dinámica, el sistema de memoria de amigos tiene poca fragmentación externa y permite la compactación de la memoria con poca sobrecarga. El método de compañero para liberar memoria es rápido, con el número máximo de compactaciones requeridas igual a O(orden más alto) = O(log₂(tamaño total de la memoria)). Normalmente, el sistema de asignación de memoria de amigos se implementa con el uso de un árbol binario para representar bloques de memoria dividida usados o no utilizados. La dirección del "amigo" de un bloque; es igual al OR exclusivo bit a bit (XOR) de la dirección del bloque y el tamaño del bloque.

Sin embargo, todavía existe el problema de la fragmentación interna: la memoria se desperdicia porque la memoria solicitada es un poco más grande que un bloque pequeño, pero mucho más pequeña que un bloque grande. Debido a la forma en que funciona la técnica de asignación de memoria de amigos, a un programa que solicita 66 K de memoria se le asignarían 128 K, lo que resulta en un desperdicio de 62 K de memoria. Este problema se puede resolver mediante la asignación de bloques, que se puede colocar en capas encima del asignador de compañeros más aproximado para proporcionar una asignación más detallada.

Donald Knuth describió en detalle una versión del algoritmo de asignación de amigos en el volumen 1 de El arte de la programación informática. El kernel de Linux también utiliza el sistema de amigos, con modificaciones adicionales para minimizar la fragmentación externa, junto con varios otros asignadores para administrar la memoria dentro de los bloques.

jemalloc es un asignador de memoria moderno que emplea, entre otras, la técnica del amigo.