动态内存分配

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

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

细节

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

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

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

效率

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

实现

定长分配

主条目：内存池

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

伙伴系统

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

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

参见

• 自动内存分配
• 动态数组
• 垃圾回收
• 冒险指针
• Heap溢出
• Hoard记亿体配置器
• Java虚拟机 heap
• malloc
• 内存池
• mmap
• new (C++)
• obstack
• Slab分配
• 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
• Wilson, P.R.; Johnstone, M.S.; Neely, M.; Boles, D. Dynamic Storage Allocation: A Survey and Critical Review. Memory Management: International Workshop, Iwmm'95, Kinross, Uk, September 27-29, 1995: Proceedings (Springer). 1995 [2008-01-06]. ISBN 9783540603689. 
• Berger, E.D.; Zorn, B.G.; McKinley, K.S. Composing high-performance memory allocators. ACM SIGPLAN Notices. 2001, 36 (5): 114–124. doi:10.1145/381694. 
• Berger, E.D.; Zorn, B.G.; McKinley, K.S. Reconsidering custom memory allocation. Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications. ACM Press New York, NY, USA: 1–12. 2002.