對内存分配器透徹理解是編程高手的标志之一。

如果你不能理解malloc之類内存分配器實現原理的話，那你可能寫不出高性能程序，寫不出高性能程序就很難參與核心項目，參與不了核心項目那麼很難升職加薪，很難升級加薪就無法走向人生巅峰，沒想到内存分配竟如此關鍵，為了走上人生巅峰你也要勢必讀完本文。

現在我們知道了，對内存分配器透徹的理解是寫出高性能程序的關鍵所在，那麼我們該怎樣透徹理解内存分配器呢？

還有什麼能比你自己動手實現一個理解的更透徹嗎？

接下來，我們就自己實現一個malloc内存分配器。讀完本文後内存分配對你将不再是一個神秘的黑盒。在講解實現原理之前，我們需要回答一個基本問題，那就是我們為什麼要發明内存分配器這種東西。

程序員經常使用的内存申請方式被稱為動态内存分配，Dynamic Memory Allocation。我們為什麼需要動态的去進行内存分配與釋放呢？答案很簡單，因為我們不能提前知道程序到底需要使用多少内存。那我們什麼時候才能知道呢？答案是隻有當程序真的運行起來後我們才知道。

這就是為什麼程序員需要動态的去申請内存的原因，如果能提前知道我們的程序到底需要多少内存，那麼直接知道告訴編譯器就好了，這樣也不必發明malloc等内存分配器了。知道了為什麼要發明内存分配器的原因後，接下來我們着手實現一個。

實際上，現代程序員是很幸福的，程序員很少去關心内存分配的問題。作為程序員，可以簡單的認為我們的程序獨占内存，注意，是獨占哦。

寫程序時你從來沒有關心過如果我們的程序占用過多内存會不會影響到其它程序，我們可以簡單的認為每個程序(進程)獨占4G内存(32位操作系統)，即使我們的物理内存512M。不信你可以去試試，在即使隻有512M大小的内存上你依然可以申請到2G内存來使用，可這是為什麼呢？關于這個問題我們會在《深入理解操作系統》系列中詳細闡述。總之，程序員可以放心的認為我們的程序運行起來後在内存中是這樣的：

作為程序員我們應該知道，内存動态申請和釋放都發生在堆區，heap。我們使用的malloc或者C 中的new申請内存時，就是從堆區這個區域中申請的。接下來我們就要自己管理堆區這個内存區域。堆區這個區域實際上非常簡單，真的是非常簡單，你可以将其看做一大數組，就像這樣：

從内存分配器的角度看，内存分配器根本不關心你是整數、浮點數、鍊表、二叉樹等數據結構、還是對象、結構體等這些花哨的概念，在内存分配器眼裡不過就是一個内存塊，這些内存塊中可以裝入原生的字節序列，申請者拿到該内存塊後可以塑造成整數、浮點數、鍊表、二叉樹等數據結構以及對象、結構體等，這是使用者的事情，和内存分配器無關。我們要在這片内存上解決兩個問題：

• 實現一個malloc函數，也就是如果有人向我申請一塊内存，我該怎樣從堆區這片區域中找到一塊返回給申請者。
• 實現一個free函數，也就是當某一塊内存使用完畢後，我該怎樣還給堆區這片區域。

這是内存分配器要解決的兩個最核心的問題，接下來我們先去停車場看看能找到什麼啟示。

更多linux内核視頻教程文檔資料免費領取後台私信【内核】自行獲取.

Linux内核源碼/内存調優/文件系統/進程管理/設備驅動/網絡協議棧-學習視頻教程-騰訊課堂

實際上你可以把内存看做一條長長的停車場，我們申請内存就是要找到一塊停車位，釋放内存就是把車開走讓出停車位。

隻不過這個停車場比較特殊，我們不止可以停小汽車、也可以停占地面積很小的自行車以及占地面積很大的卡車，重點就是申請的内存是大小不一的，在這樣的條件下你該怎樣實現以下兩個目标呢？

• 快速找到停車位，在内存申請中，這涉及到以最大速度找到一塊滿足要求的空閑内存
• 盡最大程度利用停車場，我們的停車場應該能停盡可能多的車，在内存申請中，這涉及到在給定條件下盡可能多的滿足内存申請需求

現在，我們已經清楚的理解任務了，那麼該怎麼實現呢？

現在我們已經明确要實現什麼以及衡量其好壞的标準，接下來我們就要去設計實現細節了，讓我們把任務拆分一下，怎麼拆分呢？我們可以自己想一下從内存的申請到釋放需要哪些細節。申請内存時，我們需要在内存中找到一塊大小合适的空閑内存分配出去，那麼我們怎麼知道有哪些内存塊是空閑的呢？

​

因此，第一個實現細節出現了，我們需要把内存塊用某種方式組織起來，這樣我們才能追蹤到每一塊内存的分配狀态。現在空閑内存塊組織好了，那麼一次内存申請可能有很多空閑内存塊滿足要求，那麼我們該選擇哪一個空閑内存塊分配給用戶呢？

因此，第二個實現細節出現了，我們該選擇什麼樣的空閑内存塊給到用戶。接下來我們找到了一塊大小合适的内存塊，假設用戶需要16個字節，而我們找到的這塊空閑内存塊大小為32字節，那麼将16字節分配給用戶後還剩下16字節，這剩下的内存該怎麼處理呢？因此，第三個實現細節出現了，分配出去内存後，空閑内存塊剩餘的空間該怎麼處理？

​

最後，分配給用戶的内存使用完畢，這是第四個細節出現了，我們該怎麼處理用戶還給我們的内存呢？以上四個問題是任何一個内存分配器必須要回答的，接下來我們就一一解決這些問題，解決完這些問題後一個嶄新的内存分配器就誕生啦。

空閑内存塊的本質是需要某種辦法來來區分哪些是空閑内存哪些是已經分配出去的内存。有的同學可能會說，這還不簡單嗎，用一個鍊表之類的結構記錄下每個空閑内存塊的開始和結尾不就可以了，這句話也對也不對。

​

說不對，是因為如果要申請内存來創建這個鍊表那麼這就是不對的，原因很簡單，因為創建鍊表不可避免的要申請内存，申請内存就需要通過内存分配器，可是你要實現的就是一個内存分配器，你沒有辦法向一個還沒有實現的内存分配器申請内存。

說對也對，我們确實需要一個類似鍊表這樣的結構來維護空閑内存塊，但這個鍊表并不是我們常見的那種。因為我們無法将空閑内存塊的信息保存在其它地方，那麼沒有辦法，我們隻能将維護内存塊的分配信息保存在内存塊本身中，這也是大多數内存分配器的實現方法。那麼，為了維護内存塊分配狀态，我們需要知道哪些信息呢？很簡單：

• 一個标記，用來标識該内存塊是否空閑
• 一個數字，用來記錄該内存塊的大小

為了簡單起見，我們的内存分配器不對内存對齊有要求，同時一次内存申請允許的最大内存塊為2G，注意，這些假設是為了方便講解内存分配器的實現而屏蔽一些細節，我們常用的malloc等不會有這樣的限制。因為我們的内存塊大小上限為2G，因此我們可以使用31個比特位來記錄塊大小，剩下的一個比特位用來标識該内存塊是空閑的還是已經被分配出去了，下圖中的f/a是free/allocate，也就是标記是已經分配出去還是空閑的。這32個比特位就是header，用來存儲塊信息。

剩下的灰色部分才是真正可以分配給用戶的内存，這一部分也被稱為負載，payload，我們調用malloc返回的内存起始地址正是這塊内存的起始地址。現在你應該知道了吧，不是說堆上有10G内存，這裡面就可以全部用來存儲數據的，這裡面必然有一部分要拿出來維護内存塊的一些信息，就像這裡的header一樣。

有了上圖，我們就可以将堆這塊内存區域組織起來并進行内存分配與釋放了，如圖所示：

​

在這裡我們的堆區還很小，每一方框代表4字節，其中紅色區域表示已經分配出去的，灰色區域表示空閑内存，每一塊内存都有一個header，用帶斜線的方框表示，比如16/1，就表示該内存塊大小是16字節，1表示已經分配出去了；而32/0表示該内存塊大小是32字節，0表示該内存塊當前空閑。細心的同學可能會問，那最後一個方框0/1表示什麼呢？原來，我們需要某種特殊标記來告訴我們的内存分配器是不是已經到末尾了，這就是最後4字節的作用。通過引入header我們就能知道每一個内存塊的大小，從而可以很方便的遍曆整個堆區。遍曆方法很簡單，因為我們知道每一塊的大小，那麼從當前的位置加上當前塊的大小就是下一個内存塊的起始位置，如圖所示：

​

通過每一個header的最後一個bit位就能知道每一塊内存是空閑的還是已經分配出去了，這樣我們就能追蹤到每一個内存塊的分配信息，因此上文提到的第一個問題解決了。接下來我們看第二個問題。

當應用程序調用我們實現的malloc時，内存分配器需要遍曆整個空閑内存塊找到一塊能滿足應用程序要求的内存塊返回，就像下圖這樣：

​

假設應用程序需要申請4字節内存，從圖中我們可以看到有兩個空閑内存塊滿足要求，第一個大小為8字節的内存塊和第三個大小為32字節的内存塊，那麼我們到底該選擇哪一個返回呢？這就涉及到了分配策略的問題，實際上這裡有很多的策略可供選擇。

First Fit最簡單的就是每次從頭開始找起，找到第一個滿足要求的就返回，這就是所謂的First fit方法，教科書中一般稱為首次适應方法，當然我們不需要記住這樣拗口的名字，隻需要記住這是什麼意思就可以了。

​

這種方法的優勢在于簡單，但該策略總是從前面的空閑塊找起，因此很容易在堆區前半部分因分配出内存留下很多小的内存塊，因此下一次内存申請搜索的空閑塊數量将會越來越多。

Next Fit該方法是大名鼎鼎的Donald Knuth首次提出來的，如果你不知道誰是Donald Knuth，那麼數據結構課上折磨的你痛不欲生的字符串匹配KMP算法你一定不會錯過，KMP其中的K就是指Donald Knuth，該算法全稱Knuth–Morris–Pratt string-searching algorithm，如果你也沒聽過KMP算法那麼你一定聽過下面這本書：

這就是更加大名鼎鼎的《計算機程序設計藝術》，這本書就是Donald Knuth寫的，如果你沒有聽過這本書請面壁思過一分鐘，比爾蓋茨曾經說過，如果你看懂了這本書就去給微軟投簡曆吧，這本書也是很多程序員買回來後從來不會翻一眼隻是拿來當做鎮宅之寶用的。不止比爾蓋茨，有一次喬布斯見到Knuth老爺子後。。算了，扯遠了，有機會再和大家講這個故事，拉回來。Next Fit說的是什麼呢？這個策略和First Fit很相似，是說我們别總是從頭開始找了，而是從上一次找到合适的空閑内存塊的位置找起，老爺子觀察到上一次找到某個合适的内存塊的地方很有可能剩下的内存塊能滿足接下來的内存分配請求，由于不需要從頭開始搜索，因此Next Fit将遠快于First Fit。

​

然而也有研究表明Next Fit方法内存使用率不及First Fit，也就是同樣的停車場面積，First Fit方法能停更多的車。

Best FitFirst Fit和Next Fit都是找到第一個滿足要求的内存塊就返回，但Best Fit不是這樣。Best Fit算法會找到所有的空閑内存塊，然後将所有滿足要求的并且大小為最小的那個空閑内存塊返回，這樣的空閑内存塊才是最Best的，因此被稱為Best Fit。就像下圖雖然有三個空閑内存塊滿足要求，但是Best Fit會選擇大小為8字節的空閑内存塊。

顯然，從直覺上我們就能得出Best Fit會比前兩種方法能更合理利用内存的結論，各項研究也證實了這一點。然而Best Fit最大的缺點就是分配内存時需要遍曆堆上所有的空閑内存塊，在速度上顯然不及前面兩種方法。以上介紹的這三種策略在各種内存分配器中非常常見，當然分配策略遠不止這幾種，但這些算法不是該主題下關注的重點，因此就不在這裡詳細闡述了，假設在這裡我們選擇First Fit算法。

重要的是，從上面的介紹中我們能夠看到，沒有一種完美的策略，每一種策略都有其優點和缺點，我們能做到的隻有取舍和權衡。因此，要實現一個内存分配器，設計空間其實是非常大的，要想設計出一個通用的内存分配器，就像我們常用的malloc是很不容易的。

​

其實不止内存分配器，在設計其它軟件系統時我們也沒有銀彈。

現在我們找到合适的空閑内存塊了，接下來我們又将面臨一個新的問題。如果用戶需要12字節，而我們的空閑内存塊也恰好是12字節，那麼很好，直接返回就可以了。但是，如果用戶申請12字節内存，而我們找到的空閑内存塊大小為32字節，那麼我們是要将這32字節的整個空閑内存塊标記為已分配嗎？就像這樣：

​

這樣雖然速度最快，但顯然會浪費内存，形成内部碎片，也就是說該内存塊剩下的空間将無法被利用到。

​

一種顯而易見的方法就是将空閑内存塊進行劃分，前一部分設置為已分配，返回給内存申請者使用，後一部分變為一個新的空閑内存塊，隻不過大小會更小而已，就像這樣：

​

我們需要将空閑内存塊大小從32修改為16，其中消息頭header占據4字節，剩下的12字節分配出去，并将标記為置為1，表示該内存塊已分配。分配出16字節後，還剩下16字節，我們需要拿出4字節作為新的header并将其标記為空閑内存塊。

到目前為止，我們的malloc已經能夠處理内存分配請求了，還差最後的内存釋放。内存釋放和我們想象的不太一樣，該過程并不比前幾個環節簡單。我們要考慮到的關鍵一點就在于，與被釋放的内存塊相鄰的内存塊可能也是空閑的。如果釋放一塊内存後我們僅僅簡單的将其标志位置為空閑，那麼可能會出現下面的場景：

從圖中我們可以看到，被釋放内存的下一個内存塊也是空閑的，如果我們僅僅将這16個字節的内存塊标記為空閑的話，那麼當下一次申請20字節時圖中的這兩個内存塊都不能滿足要求，盡管這兩個空閑内存塊的總數要超過20字節。因此一種更好的方法是當應用程序向我們的malloc釋放内存時，我們查看一下相鄰的内存塊是否是空閑的，如果是空閑的話我們需要合并空閑内存塊，就像這樣：

​

在這裡我們又面臨一個新的決策，那就是釋放内存時我們要立即去檢查能否夠合并相鄰空閑内存塊嗎？還是說我們可以推遲一段時間，推遲到下一次分配内存找不到滿足要的空閑内存塊時再合并相鄰空閑内存塊。釋放内存時立即合并空閑内存塊相對簡單，但每次釋放内存時将引入合并内存塊的開銷，如果應用程序總是釋放12字節然後申請12字節，然後在釋放12字節等等這樣重複的模式：

free(ptr); obj* ptr = malloc(12); free(ptr); obj* ptr = malloc(12); ...

​

那麼這種内存使用模式對立即合并空閑内存塊這種策略非常不友好，我們的内存分配器會有很多的無用功。但這種策略最為簡單，在這裡我們依然選擇使用這種簡單的策略。實際上我們需要意識到，實際使用的内存分配器都會有某種推遲合并空閑内存塊的策略。

合并空閑内存塊的故事到這裡就完了嗎？問題沒有那麼簡單。讓我們來看這樣一個場景：

​

使用的内存塊其前和其後都是空閑的，在當前的設計中我們可以很容易的知道後一個内存塊是空閑的，因為我們隻需要從當前位置向下移動16字節就是下一個内存塊，但我們怎麼能知道上一個内存塊是不是空閑的呢？

​

我們之所以能向後跳是因為當前内存塊的大小是知道的，那麼我們該怎麼向前跳找到上一個内存塊呢？還是我們上文提到的Donald Knuth，老爺子提出了一個很聰明的設計，我們之所以不能往前跳是因為不知道前一個内存塊的信息，那麼我們該怎麼快速知道前一個内存塊的信息呢？

​

Knuth老爺子的設計是這樣的，我們不是有一個信息頭header嗎，那麼我們就在該内存塊的末尾再加一個信息尾，footer，footer一詞用的很形象，header和footer的内容是一樣的。因為上一内存塊的footer和下一個内存塊的header是相鄰的，因此我們隻需要在當前内存塊的位置向上移動4直接就可以等到上一個内存塊的信息，這樣當我們釋放内存時就可以快速的進行相鄰空閑内存塊的合并了。

至此，我們的内存分配器就已經設計完畢了。我們的簡單内存分配器采用了First Fit分配算法；找到一個滿足要求的内存塊後會進行切分，剩下的作為新的内存塊；同時當釋放内存時會立即合并相鄰的空閑内存塊，同時為加快合并速度，我們引入了Donald Knuth的設計方法，為每個内存塊增加footer信息。這樣，我們自己實現的内存分配就可以運行起來了，可以真正的申請和釋放内存。

本文從0到1實現了一個簡單的内存分配器，但不希望這裡的闡述給大家留下内存分配器實現很簡單的印象，實際上本文實現的内存分配器還有大量的優化空間，同時我們也沒有考慮線程安全問題，但這些都不是本文的目的。本文的目的在于把内存分配器的本質告訴大家，對于想理解内存分配器實現原理的同學來說這些已經足夠了，而對于要編寫高性能程序的同學來說實現自己的内存池是必不可少的，内存池實現也離不開這裡的讨論。希望本文對大家理解内存分配器有幫助。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!