動態內存分配

在計算機科學中, 動態內存分配（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.