動態主記憶體分配

在電腦科學中, 動態主記憶體分配（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.