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 tratar de satisfacer una solicitud de memoria de la manera más adecuada posible. Este sistema utiliza la división de la memoria en mitades para tratar de dar el mejor ajuste. Según Donald Knuth , el sistema de compañeros fue inventado en 1963 por Harry Markowitz y fue descrito por primera vez por Kenneth C. Knowlton (publicado en 1965). [1] La asignación de memoria Buddy es relativamente fácil de implementar. Admite la división y fusión limitadas pero eficientes de bloques de memoria .
Algoritmo
Hay varias formas del sistema de compañeros; aquellos en los que cada bloque se subdivide en dos bloques más pequeños son la variedad más simple 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 especificado. El tamaño de un bloque de orden n es proporcional a 2 n , de modo que los bloques tienen exactamente el doble del tamaño de los bloques que son un orden más bajo. Los tamaños de bloque de potencias de dos simplifican el cálculo de direcciones, porque todos los amigos 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 del otro. Un bloque dividido solo se puede fusionar con su bloque de amigos único, que luego reforma el bloque más grande del que se dividió.
Partiendo, 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, las asignaciones de tamaño de bits fueran posibles), 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 de memoria promedio 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 desperdiciado promedio por asignación, pero lo suficientemente grande para evitar gastos generales excesivos. 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 múltiplos de potencia de dos de este tamaño.
El programador entonces 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 dado puede no ser una potencia de dos múltiplos del tamaño de bloque mínimo, el tamaño de bloque más grande puede no abarcar 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 de la 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 solicita memoria. Digamos 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 pedido es 4, lo que da como resultado un bloque asignable más grande posible, 2 4 veces 64 K = 1024 K. A continuación se muestra un posible estado del sistema después de varias solicitudes de memoria.
Paso | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K | 64 K |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 2 4 | |||||||||||||||
2.1 | 2 3 | 2 3 | ||||||||||||||
2.2 | 2 2 | 2 2 | 2 3 | |||||||||||||
2.3 | 2 1 | 2 1 | 2 2 | 2 3 | ||||||||||||
2.4 | 2 0 | 2 0 | 2 1 | 2 2 | 2 3 | |||||||||||
2.5 | A: 2 0 | 2 0 | 2 1 | 2 2 | 2 3 | |||||||||||
3 | A: 2 0 | 2 0 | B: 2 1 | 2 2 | 2 3 | |||||||||||
4 | A: 2 0 | C: 2 0 | B: 2 1 | 2 2 | 2 3 | |||||||||||
5.1 | A: 2 0 | C: 2 0 | B: 2 1 | 2 1 | 2 1 | 2 3 | ||||||||||
5.2 | A: 2 0 | C: 2 0 | B: 2 1 | D: 2 1 | 2 1 | 2 3 | ||||||||||
6 | A: 2 0 | C: 2 0 | 2 1 | D: 2 1 | 2 1 | 2 3 | ||||||||||
7.1 | A: 2 0 | C: 2 0 | 2 1 | 2 1 | 2 1 | 2 3 | ||||||||||
7.2 | A: 2 0 | C: 2 0 | 2 1 | 2 2 | 2 3 | |||||||||||
8 | 2 0 | C: 2 0 | 2 1 | 2 2 | 2 3 | |||||||||||
9.1 | 2 0 | 2 0 | 2 1 | 2 2 | 2 3 | |||||||||||
9.2 | 2 1 | 2 1 | 2 2 | 2 3 | ||||||||||||
9.3 | 2 2 | 2 2 | 2 3 | |||||||||||||
9.4 | 2 3 | 2 3 | ||||||||||||||
9.5 | 2 4 |
Esta asignación podría haber ocurrido de la siguiente manera
- La situación inicial.
- El programa A solicita memoria 34 K, orden 0.
- No hay bloques de orden 0 disponibles, por lo que un bloque de orden 4 se divide, creando dos bloques de orden 3.
- Aún no hay bloques de orden 0 disponibles, por lo que el primer bloque de orden 3 se divide, creando dos bloques de orden 2.
- Aún no hay bloques de orden 0 disponibles, por lo que el primer bloque de orden 2 se divide, creando dos bloques de orden 1.
- Aún no hay bloques de orden 0 disponibles, por lo que el primer bloque de orden 1 se divide, creando dos bloques de orden 0.
- Ahora hay disponible un bloque de orden 0, por lo que se asigna a A.
- El programa B solicita la memoria 66 K, orden 1. Hay un bloque de orden 1 disponible, por lo que se asigna a B.
- El programa C solicita memoria 35 K, orden 0. Hay un bloque de orden 0 disponible, por lo que se asigna a C.
- El programa D solicita la memoria 67 K, orden 1.
- No hay bloques de orden 1 disponibles, por lo que un bloque de orden 2 se divide, creando dos bloques de orden 1.
- Ahora hay disponible un bloque de orden 1, por lo que se asigna a D.
- El programa B libera su memoria, liberando un bloque de orden 1.
- El programa D libera su memoria.
- Se libera un bloque de orden 1.
- Dado que el bloque de amigos del bloque recién liberado también es libre, los dos se fusionan en un bloque de orden 2.
- El programa A libera su memoria, liberando un bloque de orden 0.
- El programa C libera su memoria.
- Se libera un bloque de orden 0.
- Dado que el bloque de amigos del bloque recién liberado también es libre, los dos se fusionan en un bloque de orden 1.
- Dado que el bloque de amigos del bloque de orden 1 recién formado también es libre, los dos se fusionan en un bloque de orden 2.
- Dado que el bloque de amigos del bloque de orden 2 recién formado también es libre, los dos se fusionan en un bloque de orden 3.
- Dado que el bloque de amigos del bloque de orden 3 recién formado también es libre, los dos se fusionan en un bloque de orden 4.
Como puede ver, lo que sucede cuando se realiza una solicitud de memoria es lo siguiente:
- Si se va a asignar memoria
- Busque una ranura de memoria de un tamaño adecuado (el bloque mínimo de 2 k que sea mayor o igual al de la memoria solicitada)
- Si se encuentra, se asigna al programa.
- Si no es así, intenta hacer una ranura de memoria adecuada. El sistema lo hace probando lo siguiente:
- Divida una ranura de memoria libre más grande que el tamaño de memoria solicitado a la mitad
- Si se alcanza el límite inferior, asigne esa cantidad de memoria
- Vuelva al paso 1 (busque una ranura de memoria de un tamaño adecuado)
- Repita este proceso hasta que encuentre una ranura de memoria adecuada
- Si la memoria se va a liberar
- Libera el bloque de memoria
- Mire el bloque vecino, ¿también es gratis?
- Si es así, combine los dos y vuelva al paso 2 y repita este proceso hasta que se alcance el límite superior (se libere toda la memoria) 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 del compañero para liberar memoria es rápido, con el número máximo de compactaciones requeridas igual a log 2 (orden más alto). 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 usados. El "amigo" de cada bloque se puede encontrar con un OR exclusivo 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 da como resultado un desperdicio de 62 K de memoria. Este problema puede resolverse mediante la asignación de bloques, que puede colocarse en capas sobre el asignador de compañeros más grueso 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 The Art of Computer Programming . [2] El kernel de Linux también usa el sistema buddy, con más modificaciones para minimizar la fragmentación externa, junto con varios otros asignadores para administrar la memoria dentro de los bloques. [3]
jemalloc
[4] es un asignador de memoria moderno que emplea, entre otras, la técnica del compañero.
Ver también
Referencias
- ^ Kenneth C. Knowlton. Un asignador de almacenamiento rápido. Communications of the ACM 8 (10): 623–625, octubre de 1965. también Kenneth C Knowlton. Descripción de un programador de L6. Communications of the ACM , 9 (8): 616–625, agosto de 1966 [ver también: Google books [1] página 85]
- ^ Knuth, Donald (1997). Algoritmos fundamentales . El arte de la programación informática . 1 (Segunda ed.). Reading, Massachusetts: Addison-Wesley. págs. 435–455. ISBN 0-201-89683-4.
- ^ Mauerer, Wolfgang (octubre de 2008). Arquitectura profesional del kernel de Linux . Prensa Wrox . ISBN 978-0-470-34343-2.
- ^ Evans, Jason (16 de abril de 2006), A Scalable Concurrent
malloc(3)
Implementation for FreeBSD (PDF) , págs. 4-5