动态内存分配

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

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

细节

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

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

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

效率

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

实现

定长分配

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

伙伴系统

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

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

参见

外部链接

补充阅读

参考文献