目錄

malloc()和free()的分配算法

內(nèi)存池

池化技術(shù)

---

相對于棧而言，堆這片內(nèi)存面臨著一個稍微復(fù)雜的行為模式：在任意時刻，程序可能發(fā)出請求，要么申請一段內(nèi)存，要么釋放一段已經(jīng)申請過的內(nèi)存，而且申請的大小從幾個字節(jié)到幾個GB都有可能，我們不能假設(shè)程序一次申請多少堆空間，因此，堆的管理顯得較為復(fù)雜。

那么，使用 malloc() 在堆上分配內(nèi)存到底是如何實現(xiàn)的呢？

一種做法是把 malloc() 的內(nèi)存管理交給系統(tǒng)內(nèi)核去做，既然內(nèi)核管理著進(jìn)程的地址空間，那么如果它提供一個系統(tǒng)調(diào)用，可以讓 malloc() 使用這個系統(tǒng)調(diào)用去申請內(nèi)存，不就可以了嗎？當(dāng)然這是一種理論上的做法，但實際上這樣做的性能比較差，因為每次程序申請或者釋放堆空間都要進(jìn)行系統(tǒng)調(diào)用。我們知道系統(tǒng)調(diào)用的性能開銷是比較大的，當(dāng)程序?qū)Χ训牟僮鞅容^頻繁時，這樣做的結(jié)果會嚴(yán)重影響程序的性能。

比較好的做法就是 malloc() 向操作系統(tǒng)申請一塊適當(dāng)大小的堆空間，然后由 malloc() 自己管理這塊空間。

malloc() 相當(dāng)于向操作系統(tǒng)“批發(fā)”了一塊較大的內(nèi)存空間，然后“零售”給程序用。當(dāng)全部“售完”或程序有大量的內(nèi)存需求時，再根據(jù)實際需求向操作系統(tǒng)“進(jìn)貨”。當(dāng)然 malloc() 在向程序零售堆空間時，必須管理它批發(fā)來的堆空間，不能把同一塊地址出售兩次，導(dǎo)致地址的沖突。于是 malloc() 需要一個算法來管理堆空間，這個算法就是堆的分配算法。

malloc()和free()的分配算法

在程序運行過程中，堆內(nèi)存從低地址向高地址連續(xù)分配，隨著內(nèi)存的釋放，會出現(xiàn)不連續(xù)的空閑區(qū)域，如下圖所示：

圖1：已分配內(nèi)存和空閑內(nèi)存相間出現(xiàn)

帶陰影的方框是已被分配的內(nèi)存，白色方框是空閑內(nèi)存或已被釋放的內(nèi)存。程序需要內(nèi)存時，malloc() 首先遍歷空閑區(qū)域，看是否有大小合適的內(nèi)存塊，如果有，就分配，如果沒有，就向操作系統(tǒng)申請（發(fā)生系統(tǒng)調(diào)用）。為了保證分配給程序的內(nèi)存的連續(xù)性，malloc() 只會在一個空閑區(qū)域中分配，而不能將多個空閑區(qū)域聯(lián)合起來。

內(nèi)存塊（包括已分配和空閑的）的結(jié)構(gòu)類似于鏈表，它們之間通過指針連接在一起。在實際應(yīng)用中，一個內(nèi)存塊的結(jié)構(gòu)如下圖所示：

圖2：內(nèi)存塊的結(jié)構(gòu)

next 是指針，指向下一個內(nèi)存塊，used 用來表示當(dāng)前內(nèi)存塊是否已被使用。這樣，整個堆區(qū)就會形成如下圖所示的鏈表：

圖3：類似鏈表的內(nèi)存管理方式

現(xiàn)在假設(shè)需要為程序分配100個字節(jié)的內(nèi)存，當(dāng)搜索到圖中第一個空閑區(qū)域（大小為200個字節(jié)）時，發(fā)現(xiàn)滿足條件，那么就在這里分配。這時候 malloc() 會把第一個空閑區(qū)域拆分成兩部分，一部分交給程序使用，剩下的部分任然空閑，如下圖所示：

圖4：為程序分配100個字節(jié)的內(nèi)存

仍然以圖3為例，當(dāng)程序釋放掉第三個內(nèi)存塊時，就會形成新的空閑區(qū)域，free() 會將第二、三、四個連續(xù)的空閑區(qū)域合并為一個，如下圖所示：

圖5：釋放第三個內(nèi)存塊

可以看到，malloc() 和 free() 所做的工作主要是對已有內(nèi)存塊的分拆和合并，并沒有頻繁地向操作系統(tǒng)申請內(nèi)存，這大大提高了內(nèi)存分配的效率。

另外，由于單向鏈表只能向一個方向搜索，在合并或拆分內(nèi)存塊時不方便，所以大部分 malloc() 實現(xiàn)都會在內(nèi)存塊中增加一個 pre 指針指向上一個內(nèi)存塊，構(gòu)成雙向鏈表，如下圖所示：

鏈表是一種經(jīng)典的堆內(nèi)存管理方式，經(jīng)常被用在教學(xué)中，很多C語言教程都會提到“棧內(nèi)存的分配類似于數(shù)據(jù)結(jié)構(gòu)中的棧，而堆內(nèi)存的分配卻類似于數(shù)據(jù)結(jié)構(gòu)中的鏈表”就是源于此。

鏈表式內(nèi)存管理雖然思路簡單，容易理解，但存在很多問題，例如：

• 一旦鏈表中的 pre 或 next 指針被破壞，整個堆就無法工作，而這些數(shù)據(jù)恰恰很容易被越界讀寫所接觸到。
• 小的空閑區(qū)域往往不容易再次分配，形成很多內(nèi)存碎片。
• 經(jīng)常分配和釋放內(nèi)存會造成鏈表過長，增加遍歷的時間。

針對鏈表的缺點，后來人們提出了位圖和對象池的管理方式，而現(xiàn)在的 malloc() 往往采用多種方式復(fù)合而成，不同大小的內(nèi)存塊往往采用不同的措施，以保證內(nèi)存分配的安全和效率。

內(nèi)存池

不管具體的分配算法是怎樣的，為了減少系統(tǒng)調(diào)用，減少物理內(nèi)存碎片，malloc() 的整體思想是先向操作系統(tǒng)申請一塊大小適當(dāng)?shù)膬?nèi)存，然后自己管理，這就是內(nèi)存池（Memory Pool）。

內(nèi)存池的研究重點不是向操作系統(tǒng)申請內(nèi)存，而是對已申請到的內(nèi)存的管理，這涉及到非常復(fù)雜的算法，是一個永遠(yuǎn)也研究不完的課題，除了C標(biāo)準(zhǔn)庫自帶的 malloc()，還有一些第三方的實現(xiàn)，比如 Goolge 的 tcmalloc 和 jemalloc。

我們知道，C/C++是編譯型語言，沒有內(nèi)存回收機制，程序員需要自己釋放不需要的內(nèi)存，這在給程序帶來了很大靈活性的同時，也帶來了不少風(fēng)險，例如C/C++程序經(jīng)常會發(fā)生內(nèi)存泄露，程序剛開始運行時占用內(nèi)存很少，隨著時間的推移，內(nèi)存使用不斷增加，導(dǎo)致整個計算機運行緩慢。

內(nèi)存泄露的問題往往難于調(diào)試和發(fā)現(xiàn)，或者只有在特定條件下才會復(fù)現(xiàn)，這給代碼修改帶來了不少障礙。為了提高程序的穩(wěn)定性和健壯性，后來的 Java、Python、C#、JavaScript、PHP 等使用了虛擬機機制的非編譯型語言都加入了垃圾內(nèi)存自動回收機制，這樣程序員就不需要管理內(nèi)存了，系統(tǒng)會自動識別不再使用的內(nèi)存并把它們釋放掉，避免內(nèi)存泄露。可以說，這些高級語言在底層都實現(xiàn)了自己的內(nèi)存池，也即有自己的內(nèi)存管理機制。

池化技術(shù)

在計算機中，有很多使用“池”這種技術(shù)的地方，除了內(nèi)存池，還有連接池、線程池、對象池等。以服務(wù)器上的線程池為例，它的主要思想是：先啟動若干數(shù)量的線程，讓它們處于睡眠狀態(tài)，當(dāng)接收到客戶端的請求時，喚醒池中某個睡眠的線程，讓它來處理客戶端的請求，當(dāng)處理完這個請求，線程又進(jìn)入睡眠狀態(tài)。

所謂“池化技術(shù)”，就是程序先向系統(tǒng)申請過量的資源，然后自己管理，以備不時之需。之所以要申請過量的資源，是因為每次申請該資源都有較大的開銷，不如提前申請好了，這樣使用時就會變得非常快捷，大大提高程序運行效率。

總結(jié)

以上是生活随笔為你收集整理的malloc()背后的实现原理——内存池的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。