动态内存分配

在计算机科学中, 动态内存分配（Dynamic memory allocation）又称为堆内存分配，是指计算机程序在运行期中分配使用主存储器。它可以当成是一种分配有限内存资源所有权的方法。

动态分配的内存在被程序员明确释放或被垃圾回收之前一直有效。与静态内存分配的区别在于没有一个固定的生存期。这样被分配的对象称之为有一个「动态生存期」。

 细节 
分配过程包括寻找一块足够大未被使用的内存。

 分配过程当中的问题
 内部和外部碎片。
 减少碎片需要特别处理，从而导致更复杂的实现(参考 算法效率)。
 分配器的元数据需要占用额外的空间。
 尝试组块来减轻这个效应。

通常，内存是从一个被称为堆（heap）的内存池中分配出来的。高级语言封装了内存地址的概念，内存通常是通过指针来间接访问的。分配算法经常将组织分配释放组块等操作封装成抽象的接口供上层函数调用。

 效率 
堆分配的效率与分配算法的优劣关系很大。

 实现 
 定长分配 

定长分配通常被称为内存池分配，使用一个链表来保存空闲内存块信息(通常每块内存大小相同)。这种方法在简单的嵌入式系统中效果很好。

 伙伴系统 
在方式下，内存从一个2的N次幂大的内存块中分配。当内存块比要分配的长度大两倍以上，内存块平均分裂成两块。选中其中一半，重复这个过程（检查长度，满足条件则分裂）直到内存块刚好等于需要的长度。

所有的块信息保存在一个排序过的链表或者二叉树中。当一个块被释放的时候与他的相邻块进行比较。如果他们都被释放，就合并成一个大块放进更大的一个块列表
中。每当分配结束，分配器会从尽量小的块重新开始分配，以避免产生不必要的碎片。

参见
 自动内存分配

 垃圾回收
 冒险指针


 Java虚拟机 heap
 malloc
 内存池

 new (C++)


 SLOB
 基于堆栈的内存分配

外部链接
 Sample bit-mapped arena memory allocator in C 
 TLSF: a constant time allocator for real-time systems
 Slides for knowing about Dynamic memory allocation
 Inside A Storage Allocator 

 补充阅读 
 "Dynamic Storage Allocation: A Survey and Critical Review", Department of Computer Sciences University of Texas at Austin

 参考文献 

 Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.5: Dynamic Storage Allocation, pp. 435–456.
 Simple Memory Allocation Algorithms on OSDEV Community




Category:記憶體管理

'''

en:Memory management#Dynamic memory allocation