Hispanopedia Wiki
Articulo de referencia

Asignación de memoria de compañeros

La técnica de asignación de memoria Buddy es un algoritmo de asignación de memoria que divide la memoria en particiones para intentar satisfacer una solicitud de memoria de la m...

Hispanopedia WikiContenido en espanolLectura gratuita

La técnica de asignación de memoria Buddy 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 dar el mejor ajuste. Según Donald Knuth , el sistema Buddy fue inventado en 1963 por Harry Markowitz y fue descrito por primera vez por Kenneth C. Knowlton (publicado en 1965). [ 1 ] [ 2 ] La asignación de memoria Buddy es relativamente fácil de implementar. Admite una división y coalescencia limitada pero eficiente de bloques de memoria .

Algoritmo

Existen diversas formas del sistema de bloques asociados; la variedad más simple y común consiste en subdividir cada bloque en dos bloques más pequeños. Cada bloque de memoria en este sistema tiene un orden n , donde el orden es un número entero que va de 0 a un límite superior especificado. El tamaño de un bloque de orden n es proporcional a 2ⁿ , de modo que los bloques tienen exactamente el doble del tamaño de los bloques de un orden inferior. Los tamaños de bloque que son potencias de dos simplifican el cálculo de direcciones, ya que todos los bloques asociados se alinean en límites de direcciones de memoria que son potencias de dos. Cuando un bloque más grande se divide, se divide en dos bloques más pequeños, y cada bloque más pequeño se convierte en un bloque asociado único del otro. Un bloque dividido solo puede fusionarse con su bloque asociado ú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, si fueran posibles asignaciones de tamaño de bit), el sistema tendría que gestionar una gran cantidad de memoria y recursos computacionales para controlar qué partes de la memoria están asignadas y cuáles no. Sin embargo, puede ser conveniente un límite bajo para minimizar el desperdicio promedio de memoria por asignación (en lo que respecta a asignaciones cuyo tamaño no es múltiplo 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 como para evitar una sobrecarga excesiva. El tamaño del 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 debe entonces decidir, o escribir código para obtener, el orden más alto posible que quepa 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 dos del tamaño mínimo del bloque, el tamaño de bloque más grande puede no abarcar toda la memoria del sistema. Por ejemplo, si el sistema tuviera 2000 KB de memoria física y el tamaño del bloque de orden 0 fuera de 4 KB, el límite superior del orden sería 8, ya que un bloque de orden 8 (256 bloques de orden 0, 1024 KB) es el bloque más grande que cabe en la memoria. En consecuencia, es imposible asignar toda la memoria física en un solo bloque; los 976 KB restantes de memoria tendrían que asignarse en bloques más pequeños.

Ejemplo

A continuación se muestra un ejemplo de lo que sucede cuando un programa solicita 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 resulta en un bloque asignable máximo de 2⁴ × 64 K = 1024 K. A continuación se muestra un posible estado del sistema tras varias solicitudes de memoria.

Esta asignación podría haberse producido de la siguiente manera

  1. La situación inicial.
  2. El programa A solicita 34 K de memoria, orden 0.
    1. No hay bloques de orden 0 disponibles, por lo que un bloque de orden 4 se divide, creando dos bloques de orden 3.
    2. Todavía no hay bloques de orden 0 disponibles, por lo que el primer bloque de orden 3 se divide, creando dos bloques de orden 2.
    3. Todavía no hay bloques de orden 0 disponibles, por lo que el primer bloque de orden 2 se divide, creando dos bloques de orden 1.
    4. Todavía no hay bloques de orden 0 disponibles, por lo que el primer bloque de orden 1 se divide, creando dos bloques de orden 0.
    5. Ahora hay un bloque de orden 0 disponible, por lo que se asigna a A.
  3. El programa B solicita 66 KB de memoria, de orden 1. Hay un bloque de orden 1 disponible, por lo que se asigna a B.
  4. El programa C solicita 35 KB de memoria, orden 0. Hay un bloque de orden 0 disponible, por lo que se asigna a C.
  5. El programa D solicita 68 K de memoria, orden 1.
    1. No hay bloques de orden 1 disponibles, por lo que un bloque de orden 2 se divide, creando dos bloques de orden 1.
    2. Ahora hay un bloque de orden 1 disponible, por lo que se asigna a D.
  6. El programa B libera su memoria, liberando un bloque de orden 1.
  7. El programa D libera su memoria.
    1. Se libera un bloque de orden 1.
    2. Dado que el bloque compañero del bloque recién liberado también está libre, los dos se fusionan en un único bloque de orden 2.
  8. El programa A libera su memoria, liberando un bloque de orden 0.
  9. El programa C libera su memoria.
    1. Se libera un bloque de orden 0.
    2. Dado que el bloque compañero del bloque recién liberado también está libre, los dos se fusionan en un único bloque de orden 1.
    3. Dado que el bloque compañero del bloque de orden 1 recién formado también está libre, los dos se fusionan en un único bloque de orden 2.
    4. Dado que el bloque compañero del bloque de orden 2 recién formado también está libre, los dos se fusionan en un bloque de orden 3.
    5. Dado que el bloque compañero del bloque de orden 3 recién formado también está libre, los dos se fusionan en un único 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
  1. Búsqueda de coincidencia exacta: Busque una ranura de memoria libre con exactamente el tamaño de 2k deseado.
    1. Si se encuentra: asígnelo al programa inmediatamente.
    2. Si no se encuentra: El sistema busca en la cadena el siguiente bloque libre de potencia de dos más grande disponible (por ejemplo, 2k+1, 2k+2, etc.).
  2. Dividir el bloque más grande: Una vez que se encuentra un bloque libre más grande, el sistema ejecuta un bucle.
    1. Divide el bloque más grande por la mitad en dos "compañeros" iguales.
    2. Si las mitades resultantes siguen siendo más grandes que el tamaño objetivo de 2k, quédese con una mitad y divida la otra mitad nuevamente.
    3. Repita este proceso de división hasta que haya creado con éxito un bloque que coincida con el tamaño deseado de 2k.
  3. Asignar: Asigne uno de los bloques del tamaño objetivo recién creados al programa y deje su "compañero" en la lista de bloques libres.
  • Si se quiere liberar la memoria
  1. Un bloque asociado solo debe estar vinculado con el bloque original con el que se dividió. No puede estar vinculado con un bloque vecino (adyacente a un bloque asociado) que no estuviera asociado con él antes de la división.
  2. Espere hasta que el programa termine con el bloque que actualmente está asignado al programa.
  3. Si el compañero A está libre, comprueba si el compañero B también lo está; si lo está, combina los dos en un único bloque unificado.
  4. Comprueba si el bloque combinado de 64kb de Buddy A y Buddy B está libre y repite el proceso hacia arriba.

Implementación y eficiencia

En comparación con otras técnicas más sencillas, como la asignación dinámica , el sistema de memoria de tipo "buddy" presenta poca fragmentación externa y permite la compactación de la memoria con una sobrecarga mínima. El método "buddy" para liberar memoria es rápido, con un número máximo de compactaciones requeridas igual a O(orden más alto) = O(log 2 (tamaño total de la memoria)). Normalmente, el sistema de asignación de memoria "buddy" se implementa mediante un árbol binario para representar los bloques de memoria divididos utilizados o no utilizados. La dirección del "buddy" de un bloque es igual a la operación OR exclusiva (XOR) bit a bit de la dirección del bloque y su tamaño.

Sin embargo, persiste el problema de la fragmentación interna : se desperdicia memoria porque la cantidad solicitada es ligeramente mayor que la de un bloque pequeño, pero mucho menor que la de un bloque grande. Debido al funcionamiento de la técnica de asignación de memoria por bloques, un programa que solicita 66 KB de memoria recibiría 128 KB, lo que supone un desperdicio de 62 KB. Este problema se puede solucionar mediante la asignación por bloques , que se puede superponer al asignador por bloques, más general, para proporcionar una asignación más precisa.

Donald Knuth describió en detalle una versión del algoritmo de asignación de bloques en bloque en el volumen 1 de The Art of Computer Programming . [ 3 ] El kernel de Linux también utiliza el sistema de bloques en bloque, con modificaciones adicionales para minimizar la fragmentación externa, junto con otros asignadores para gestionar la memoria dentro de los bloques. [ 4 ]

jemalloces un asignador de memoria moderno que emplea, entre otras cosas, la técnica de compañeros. [ 5 ]

Véase también

Referencias

  1. ↑ Knowlton, Kenneth C. (1965). "Un asignador de almacenamiento rápido". Comm. ACM . 8 : 623. doi : 10.1145/365628.365655 .
  2. ↑ Knowlton, Kenneth C. (1966). "Descripción de L 6 por un programador ". Commun. ACM . 9 : 616. doi : 10.1145/365758.365792 .
  3. ↑ Knuth, Donald (1997). Algoritmos fundamentales . El arte de la programación informática . Vol. 1 (Segunda ed.). Reading, Massachusetts: Addison-Wesley. pp. 435–455 . ISBN    0-201-89683-4.
  4. ^ Mauerer, Wolfgang (octubre de 2008). Arquitectura profesional del kernel de Linux . Prensa Wrox . ISBN 978-0-470-34343-2.
  5. ↑ Evans, Jason (16 de abril de 2006), Una implementación concurrente escalable para FreeBSD (PDF) , págs . 4–5malloc(3) 
Lecturas relacionadas
6 articulos
Gestión de la memoriaGestión de la memoriaLa gestión de memoria (también gestión de memoria dinámica , asignación de almacenamiento dinámico o asignación de memoria dinámica ) es una forma ...Donald KnuthDonald KnuthDonald Ervin Knuth ( nacido el 10 de enero de 1938) es un informático y matemático estadounidense. Es profesor emérito de la Universidad de Stanfor...Harry MarkowitzHarry MarkowitzHarry Max Markowitz (24 de agosto de 1927 - 22 de junio de 2023) fue un economista estadounidense que recibió el Premio de Teoría John von Neumann ...Ken KnowltonKenneth Charles Knowlton (6 de junio de 1931 - 16 de junio de 2022) fue un pionero estadounidense de los gráficos por computadora, artista, mosaici...EnteroLos números enteros dispuestos en una línea numérica Un número entero es el número cero ( 0 ), un número natural positivo (1, 2, 3, . . .), o la ne...Dirección de memoriaDirección de memoriaEn informática , una dirección de memoria es una referencia a una ubicación de memoria específica utilizada en varios niveles por software y hardwa...