动态内存分配
此条目需要精通或熟悉相关主题的编者参与及协助编辑。 (2011年8月21日) |
在计算机科学中, 动态内存分配(Dynamic memory allocation)又称为堆内存分配,是指计算机程序在运行期中分配使用内存。它可以当成是一种分配有限内存资源所有权的方法。
动态分配的内存在被程序员明确释放或被垃圾回收之前一直有效。与静态内存分配的区别在于没有一个固定的生存期。这样被分配的对象称之为有一个“动态生存期”。
细节
编辑分配过程包括寻找一块足够大未被使用的内存。
通常,内存是从一个被称为堆(heap)的内存池中分配出来的。高级语言封装了内存地址的概念,内存通常是通过指针来间接访问的。分配算法经常将组织分配释放组块等操作封装成抽象的接口供上层函数调用。
效率
编辑堆分配的效率与分配算法的优劣关系很大。
实现
编辑定长分配
编辑定长分配通常被称为内存池分配,使用一个链表来保存空闲内存块信息(通常每块内存大小相同)。这种方法在简单的嵌入式系统中效果很好。
伙伴系统
编辑在伙伴存储器分配方式下,内存从一个2的N次幂大的内存块中分配。当内存块比要分配的长度大两倍以上,内存块平均分裂成两块。选中其中一半,重复这个过程(检查长度,满足条件则分裂)直到内存块刚好等于需要的长度。
所有的块信息保存在一个排序过的链表或者二叉树中。当一个块被释放的时候与他的相邻块进行比较。如果他们都被释放,就合并成一个大块放进更大的一个块列表 中。每当分配结束,分配器会从尽量小的块重新开始分配,以避免产生不必要的碎片。
参见
编辑外部链接
编辑补充阅读
编辑- "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.