通常情況下，一個高級操作系統必須要給進程提供基本的、能夠在任意時刻申請和釋放任意大小內存的功能，就像malloc 函數那樣，然而，實現malloc 函數并不簡單，由于進程申請內存的大小是任意的，如果操作系統對malloc 函數的實現方法不對，將直接導致一個不可避免的問題，那就是內存碎片。

內存碎片就是內存被分割成很小很小的一些塊，這些塊雖然是空閑的，但是卻小到無法使用。隨著申請和釋放次數的增加，內存將變得越來越不連續。最后，整個內存將只剩下碎片，即使有足夠的空閑頁框可以滿足請求，但要分配一個大塊的連續頁框就可能無法滿足，所以減少內存浪費的核心就是盡量避免產生內存碎片。

針對這樣的問題，有很多行之有效的解決方法，其中伙伴算法被證明是非常行之有效的一套內存管理方法，因此也被相當多的操作系統所采用。

伙伴算法，簡而言之，就是將內存分成若干塊，然后盡可能以最適合的方式滿足程序內存需求的一種內存管理算法，伙伴算法的一大優勢是它能夠完全避免外部碎片的產生。什么是外部碎片以及內部碎片，前面博文slab分配器后面已有介紹。申請時，伙伴算法會給程序分配一個較大的內存空間，即保證所有大塊內存都能得到滿足。很明顯分配比需求還大的內存空間，會產生內部碎片。所以伙伴算法雖然能夠完全避免外部碎片的產生，但這恰恰是以產生內部碎片為代價的。

Linux 便是采用這著名的伙伴系統算法來解決外部碎片的問題。把所有的空閑頁框分組為 11 塊鏈表，每一塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512 和 1024 個連續的頁框。對1024 個頁框的最大請求對應著 4MB 大小的連續RAM 塊。每一塊的第一個頁框的物理地址是該塊大小的整數倍。例如，大小為 16個頁框的塊，其起始地址是 16 * 2^12 （2^12 = 4096，這是一個常規頁的大小）的倍數。

下面通過一個簡單的例子來說明該算法的工作原理：

假設要請求一個256（129~256）個頁框的塊。算法先在256個頁框的鏈表中檢查是否有一個空閑塊。如果沒有這樣的塊，算法會查找下一個更大的頁塊，也就是，在512個頁框的鏈表中找一個空閑塊。如果存在這樣的塊，內核就把512的頁框分成兩等分，一般用作滿足需求，另一半則插入到256個頁框的鏈表中。如果在512個頁框的塊鏈表中也沒找到空閑塊，就繼續找更大的塊——1024個頁框的塊。如果這樣的塊存在，內核就把1024個頁框塊的256個頁框用作請求，然后剩余的768個頁框中拿512個插入到512個頁框的鏈表中，再把最后的256個插入到256個頁框的鏈表中。如果1024個頁框的鏈表還是空的，算法就放棄并發出錯誤信號。

簡而言之，就是在分配內存時，首先從空閑的內存中搜索比申請的內存大的最小的內存塊。如果這樣的內存塊存在，則將這塊內存標記為“已用”，同時將該內存分配給應用程序。如果這樣的內存不存在，則操作系統將尋找更大塊的空閑內存，然后將這塊內存平分成兩部分，一部分返回給程序使用，另一部分作為空閑的內存塊等待下一次被分配。

以上過程的逆過程就是頁框塊的釋放過程，也是該算法名字的由來。內核試圖把大小為 b 的一對空閑伙伴塊合并為一個大小為 2b 的單獨塊。滿足以下條件的兩個塊稱為伙伴：

• 兩個塊具有相同的大小，記作 b
• 它們的物理地址是連續的
• 第一塊的第一個頁框的物理地址是 2 * b * 2^12 的倍數

該算法是迭代的，如果它成功合并所釋放的塊，它會試圖合并 2b 的塊，以再次試圖形成更大的塊。

下面通過一個例子，來深入地理解一下伙伴算法的真正內涵（下面這個例子并不嚴格表示Linux 內核中的實現，是闡述伙伴算法的實現思想）：

假設系統中有 1MB 大小的內存需要動態管理，按照伙伴算法的要求：需要將這1M大小的內存進行劃分。這里，我們將這1M的內存分為 64K、64K、128K、256K、和512K 共五個部分，如下圖 a 所示

1.此時，如果有一個程序A想要申請一塊45K大小的內存，則系統會將第一塊64K的內存塊分配給該程序（產生內部碎片為代價），如圖b所示；

2.然后程序B向系統申請一塊68K大小的內存，系統會將128K內存分配給該程序，如圖c所示；

3.接下來，程序C要申請一塊大小為35K的內存。系統將空閑的64K內存分配給該程序，如圖d所示；

4.之后程序D需要一塊大小為90K的內存。當程序提出申請時，系統本該分配給程序D一塊128K大小的內存，但此時內存中已經沒有空閑的128K內存塊了，于是根據伙伴算法的原理，系統會將256K大小的內存塊平分，將其中一塊分配給程序D，另一塊作為空閑內存塊保留，等待以后使用，如圖e所示；

5.緊接著，程序C釋放了它申請的64K內存。在內存釋放的同時，系統還負責檢查與之相鄰并且同樣大小的內存是否也空閑，由于此時程序A并沒有釋放它的內存，所以系統只會將程序C的64K內存回收，如圖f所示；

6.然后程序A也釋放掉由它申請的64K內存，系統隨機發現與之相鄰且大小相同的一段內存塊恰好也處于空閑狀態。于是，將兩者合并成128K內存，如圖g所示；

7.之后程序B釋放掉它的128k，系統也將這塊內存與相鄰的128K內存合并成256K的空閑內存，如圖h所示；

8.最后程序D也釋放掉它的內存，經過三次合并后，系統得到了一塊1024K的完整內存，如圖i所示。

https://blog.csdn.net/wenqian1991/article/details/27968779