跳至內容

動態內存分配

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

計算機科學中, 動態內存分配(Dynamic memory allocation)又稱為堆內存分配,是指計算機程序運行期中分配使用內存。它可以當成是一種分配有限內存資源所有權的方法。

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

細節

分配過程包括尋找一塊足夠大未被使用的內存。

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

通常,內存是從一個被稱為(heap)的內存池中分配出來的。高級語言封裝了內存地址的概念,內存通常是通過指針來間接訪問的。分配算法經常將組織分配釋放組塊等操作封裝成抽象的接口供上層函數調用。

效率

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

實現

定長分配

定長分配通常被稱為內存池分配,使用一個鍊表來保存空閒內存塊信息(通常每塊內存大小相同)。這種方法在簡單的嵌入式系統中效果很好。

夥伴系統

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

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

參見

外部連結

補充閱讀

參考文獻