轉(zhuǎn)載，詳見原文：http://azhao.net/index.php/archives/81/
<article class="post" style="box-sizing: border-box; display: block; padding-top: 20px;">

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

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

一種做法是把 malloc() 的內(nèi)存管理交給系統(tǒng)內(nèi)核去做谱邪，既然內(nèi)核管理著進(jìn)程的地址空間炮捧，那么如果它提供一個(gè)系統(tǒng)調(diào)用，可以讓 malloc() 使用這個(gè)系統(tǒng)調(diào)用去申請(qǐng)內(nèi)存惦银，不就可以了嗎咆课？當(dāng)然這是一種理論上的做法，但實(shí)際上這樣做的性能比較差扯俱，因?yàn)槊看纬绦蛏暾?qǐng)或者釋放堆空間都要進(jìn)行系統(tǒng)調(diào)用书蚪。我們知道系統(tǒng)調(diào)用的性能開銷是比較大的，當(dāng)程序?qū)Χ训牟僮鞅容^頻繁時(shí)蘸吓，這樣做的結(jié)果會(huì)嚴(yán)重影響程序的性能善炫。

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

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

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

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

image

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

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

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

image

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

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

image

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

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

image

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

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

image

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

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

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

image

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

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

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

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

內(nèi)存池

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

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

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

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

池化技術(shù)

在計(jì)算機(jī)中，有很多使用“池”這種技術(shù)的地方撕予，除了內(nèi)存池鲫惶，還有連接池、線程池实抡、對(duì)象池等欠母。以服務(wù)器上的線程池為例欢策，它的主要思想是：先啟動(dòng)若干數(shù)量的線程，讓它們處于睡眠狀態(tài)赏淌，當(dāng)接收到客戶端的請(qǐng)求時(shí)踩寇，喚醒池中某個(gè)睡眠的線程，讓它來處理客戶端的請(qǐng)求六水，當(dāng)處理完這個(gè)請(qǐng)求俺孙，線程又進(jìn)入睡眠狀態(tài)。

所謂“池化技術(shù)”掷贾，就是程序先向系統(tǒng)申請(qǐng)過量的資源睛榄，然后自己管理，以備不時(shí)之需想帅。之所以要申請(qǐng)過量的資源场靴，是因?yàn)槊看紊暾?qǐng)?jiān)撡Y源都有較大的開銷，不如提前申請(qǐng)好了港准，這樣使用時(shí)就會(huì)變得非持及快捷，大大提高程序運(yùn)行效率浅缸。

</article>

<center style="box-sizing: border-box; color: rgb(52, 73, 94); font-family: Lato, Helvetica, Arial, sans-serif; font-size: 18px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">

• [](javascript:void(0))
• C語言的調(diào)試
• 常用的初等數(shù)學(xué)公式

</center>