Dynamic Storage Allocation

Asignación de almacenamiento dinámico.

¿Por qué no es la asignación estática suficiente para todo? Impredecible: no se puede
predecir de antemano la cantidad de memoria, o en qué forma, será necesario:

• Los procedimientos recursivos. Incluso los procedimientos regulares son difíciles de predecir (datos dependencias).
• Estructuras de datos complejas, por ejemplo, tabla de símbolos de enlace. Si todo el almacenamiento debe ser reservado con anticipación (estáticamente), entonces se utiliza en forma ineficiente (lo suficiente será reservados para manejar o emplearse en el peor de los casos).
• OS no sabe cuánto trabajo habrá o cual de los programas será ejecutado.

Necesitara la asignación dinámica de memoria tanto para la memoria principal como para espacio de archivos en disco.

Dos operaciones básicas en el manejo de almacenamiento dinámico:
• Asignar
• Libre/liberar.

La asignación dinámica puede ser manejada en una de las dos formas generales:
• La asignación de pila (jerárquico): limitado, pero simple y eficiente.
• Asignación del montón: más general, pero menos eficiente, más difícil de implementar.

Organización de apilamiento: la asignación de memoria y la liberación son parcialmente predecibles (como siempre,  lo que hacemos mejor cuando podemos predecir el futuro).

Asignación  jerárquica: la memoria se libera en el orden inverso de la asignación. Si alloc (A) y alloc (B), entonces alloc (C), entonces debe ser libre (C), entonces sin (B) y libre (A).
• Ejemplo: procedimiento de llamada. X llamada Y llama Y llama una vez más. Espacio para las variables locales y las direcciones de retorno se asigna en una pila.
• Las pilas también son útiles para muchas otras cosas: recorrido de árbol, la expresión
evaluación, de arriba hacia abajo analizadores descenso recursivo, etc

Systema Operativo

Una organización basada en la pila mantiene todo el espacio libre en un solo lugar.
Ventaja de la jerarquía: bueno tanto para la simplificación de la estructura y eficiente
implementaciones.
Organización montón: asignación y liberación son impredecibles (esto no es lo mismo
significado del montón como en la estructura de datos utilizada para la clasificación). Pilas se utilizan para
estructuras arbitrarias lista, las organizaciones de datos complejos. Ejemplo: sistema de nómina.
No se sabe cuándo los empleados entran y salen de la empresa, debe ser capaz de
seguimiento de todas ellas utilizando la menor cantidad posible de almacenamiento.
• La memoria se compone de las zonas asignadas y zonas de libre (o huecos). Inevitablemente final
con un montón de agujeros. Objetivo: utilizar el espacio de los agujeros para mantener el número de
pequeños agujeros, su gran tamaño.
• Fragmentación: el uso ineficiente de la memoria debido a que los agujeros son demasiado pequeños para
ser de utilidad. En la asignación de pila, todos los agujeros están juntos en un gran paquete.
• Consulte a un volumen de Knuth para el tratamiento detallado de lo que sigue.
• Por lo general, los esquemas de asignación de montón de utilizar una lista de la libertad de no perder de vista el almacenamiento
que no está en uso.
Algoritmos difieren en cómo gestionar la lista libre.
• Mejor ajuste: mantener una lista enlazada de bloques, búsqueda de toda la lista en cada
asignación, elija bloque que más se acerca a igualar las necesidades de los
asignación, salvo el exceso para más adelante. Durante las operaciones de liberación, se fusionan
bloques adyacentes libres.
• Ajuste Primero: sólo lista de exploración para el primer hoyo que sea suficientemente grande. El exceso de forma gratuita.
También fusionar en las emisiones. Implementaciones de adaptarse a la mayoría primero giran ajuste de primera.
• Mejor ajuste no es necesariamente mejor que el primer ajuste. Supongamos que la memoria contiene 2
tres bloques de tamaño 20 y 15.
- Supongamos que hay 10 operaciones de asignación de 20: el enfoque que gana?
- Supongamos que operaciones son 8, 12, entonces 12: ¿cuál prevalece?

Primer ajuste tiende a dejar "promedio" agujeros de tamaño, mientras que el mejor ajuste tiende a dejar algunas muy
los grandes, algunos muy pequeños. Los muy pequeños no se pueden utilizar muy fácilmente.
Knuth afirma que si el almacenamiento está cerca de quedarse, se quedará sin importar de
qué sistema se utiliza, así que escoja esquema más fácil o más eficiente (primer ajuste).
• Mapa de bits: se utiliza para la asignación de almacenamiento que viene en trozos de tamaño fijo (por ejemplo,
bloques de disco, o trozos de 32 bytes). Mantenga una gran variedad de bits, uno por cada
fragmento. Si el bit es 0 significa que buena parte está en uso, si el bit es 1 significa que buena parte es libre.
Será discutido más cuando se habla de sistemas de archivos.
• Las piscinas: una piscina de mantener la asignación para cada tamaño popular. La asignación es
rápido, sin fragmentación. Sin embargo, puede obtener alguna ineficiencia, si algunos grupos se quede sin
mientras que otras piscinas tienen un montón de bloques libres: conseguir aleatoria entre grupos.
Los métodos de recuperación: ¿cómo sabemos cuando asignados de forma dinámica la memoria puede
ser liberados?
• Es fácil cuando una parte se utiliza únicamente en un solo lugar.
• Recuperación es difícil cuando se comparte la información: no se puede reciclar hasta
todos los partícipes terminado. Compartir es indicado por la presencia de
punteros a los datos. Sin un puntero, no pueden acceder (no lo encuentra).

Dos problemas en la recuperación:
• punteros colgantes: mejor no reciclar de almacenamiento mientras que todavía está en uso.
• Las pérdidas de memoria: no mejor "perder" almacenamiento por olvidarse de libre incluso cuando
no puede nunca ser utilizado de nuevo.
Cuentas de Referencia: realizar un seguimiento del número de punteros en circulación de cada
trozo de memoria. Cuando esta llega a cero, sin la memoria. Ejemplo: Smalltalk,
descriptores de archivo en Unix. Funciona bien para las estructuras jerárquicas. La referencia
cuenta deben manejarse con cuidado (por el sistema) por lo que no se cometen errores en
incremento y decremento ellos.