動態主記憶體分配

電腦科學中, 動態主記憶體分配(Dynamic memory allocation)又稱為堆主記憶體分配,是指電腦程式執行期中分配使用主記憶體。它可以當成是一種分配有限主記憶體資源所有權的方法。

動態分配的主記憶體在被程式設計師明確釋放或被垃圾回收之前一直有效。與靜態主記憶體分配的區別在於沒有一個固定的生存期。這樣被分配的對象稱之為有一個「動態生存期」。

細節

分配過程包括尋找一塊足夠大未被使用的主記憶體。

  • 分配過程當中的問題
    • 內部和外部碎片
      • 減少碎片需要特別處理,從而導致更複雜的實現(參考 演算法效率)。
    • 分配器的元資料需要占用額外的空間。
      • 嘗試組塊來減輕這個效應。

通常,主記憶體是從一個被稱為(heap)的主記憶體池中分配出來的。高階語言封裝了主記憶體位址的概念,主記憶體通常是通過指標來間接訪問的。分配演算法經常將組織分配釋放組塊等操作封裝成抽象的介面供上層函式呼叫。

效率

堆分配的效率與分配演算法的優劣關係很大。

實現

定長分配

定長分配通常被稱為主記憶體池分配,使用一個鏈結串列來儲存空閒主記憶體塊資訊(通常每塊主記憶體大小相同)。這種方法在簡單的嵌入式系統中效果很好。

夥伴系統

夥伴記憶體分配英語Buddy memory allocation方式下,主記憶體從一個2的N次冪大的主記憶體塊中分配。當主記憶體塊比要分配的長度大兩倍以上,主記憶體塊平均分裂成兩塊。選中其中一半,重複這個過程(檢查長度,滿足條件則分裂)直到主記憶體塊剛好等於需要的長度。

所有的塊資訊儲存在一個排序過的鏈結串列或者二元樹中。當一個塊被釋放的時候與他的相鄰塊進行比較。如果他們都被釋放,就合併成一個大塊放進更大的一個塊列表 中。每當分配結束,分配器會從儘量小的塊重新開始分配,以避免產生不必要的碎片。

參見

外部連結

補充閱讀

參考文獻