Asignación dinámica de memoria

De Wikipedia, la enciclopedia libre

En ciencia de la computación, asignación dinámica de la memoria es la asignación de almacenamiento de memoria para utilización por parte de un programa de computador durante el tiempo de ejecución de ese programa. Es una manera de distribuir la propiedad de recursos de memoria limitada entre muchas piezas de código y datos. Un objeto asignado dinámicamente permanece asignado hasta que es desasignado explícitamente, o por el programador o por un recolector de basura; esto es notablemente diferentede la asignación automática de memoria y de la asignación estática de memoria. Se dice que tal objeto tiene tiempo de vida dinámico.

La tarea de satisfaces una petición de asignación, la cual conlleva encontrar un bloque de memoria sin usar de cierto tamaño en el heap, es un problema complicado. Se han propuesto una amplia variedad de soluciones , incluyendo listas de bloques libres, Paginación, y Asignación buddy de memoria.

El problema principal para la mayoría de algoritmos de asignación de memoria dinámica es evitar la fragmentación interna y externa mientras se mantiene la eficiencia del algoritmo. También, la mayoría de algoritmos en uso tienen el problema de que un número grande de pequeñas asignaciones pueden causar el desaprovechamiento del espaco debido a la recolección de metadatos; así la mayoría de los programadores intentan evitar esto, a veces usando una estrategia llamada chunking.

Tabla de contenidos

1 Soluciones para los problemas de asignación
2 Referencias
3 Véase también

[editar] Soluciones para los problemas de asignación

[editar] Asignación de bloques de tamaño fijo

Una solución es tener una lista enlazada LIFO de bloques de memoria de tamaño fijo. Esto funciona bien para sistemas empotrados simples.

[editar] Algoritmo Buddy

Otra solución es tener un asignador buddy de bloques binarios. En este sistema, la memoria se asigna desde un gran bloque de memoria que es tamaño potencia de dos. Si el bloque es más del doble de grande de lo necesario, se parte en dos. Se selecciona una de las dos mitades, y el proceso se repite (comprobando el tamaño otra vez y partiendo si se necesita) hasta que el bloque sea justamente el necesitado.

Todos los segmentos de memoria de un tamaño particular son guardados en una lista enlazada ordenada o una estructura de datos en árbol. Cuando se libera un bloque, se compara con su buddy(vecino). Si los dos están libres, son combinados y colocados en la lista de bloques buddy de siguiente mayor tamaño. (Cuando un bloque es asignado, el asignador empezará con el bloque grande suficientemente pequeño para evitar romper bloques innecesariamente)

Date cuenta de que los asignadores buddy de bloques no son únicamente para los Sistemas Operativos de Tiempo-Real (RTOS); ellos también son usados en sistemas operativos de propósito general (tales como Microsoft Windows y Linux).

[editar] Asignación de memoria basada en Heap

En la asignación de memoria basada en heap, la memoria es asignada desde un gran pool de área de memoria sin usar llamada heap (también llamada almacén de libres). "El heap" no tiene nada que ver con la estructura de datos Heap. El tamaño de la asignación de memoria puede ser determinado en run-time, y el tiempo de vida de la asignación no es dependiente del procedimiento actual o del marco de pila. La región de memoria asignada es accedida indirectamente, normalmente por medio de una referencia. El algoritmo preciso usado para organizar la área de memoria y asignar y desasignar los trozos está oculto detrás de una interfaz abstracta y puede usar cualquiera de los métodos descritos antes.

En contraste, la memoria de la pila de llamadas es normalmente de tamaño limitado y el tiempo de vida de la asignación depende de la duración de las funciones correspondientes.

[editar] Referencias

Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sección 2.4: Asignación de Almacenamiento Dinámico, pp.435–456.
Simple Memory Allocation Algorithms en la Comunidad OSDEV
La memoria de la computadora Visión del heap, y de la pila(stack)