通常情況下，一個(gè)高級(jí)操作系統(tǒng)必須要給進(jìn)程提供基本的、能夠在任意時(shí)刻申請(qǐng)和釋放任意大小內(nèi)存的功能，就像 malloc 函數(shù)那樣，然而，實(shí)現(xiàn) malloc 函數(shù)并不簡(jiǎn)單，由于進(jìn)程申請(qǐng)內(nèi)存的大小是任意的，如果操作系統(tǒng)對(duì) malloc 函數(shù)的實(shí)現(xiàn)方法不對(duì)，將直接導(dǎo)致一個(gè)不可避免的問題，那就是內(nèi)存碎片。

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

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

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

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

下面通過一個(gè)簡(jiǎn)單的例子來說明該算法的工作原理：

假設(shè)要請(qǐng)求一個(gè) 256（129 ~ 256）個(gè)頁(yè)框的塊。算法先在 256 個(gè)頁(yè)框的鏈表中檢查是否有一個(gè)空閑塊。如果沒有這樣的塊，算法會(huì)查找下一個(gè)更大的頁(yè)塊，也就是，在 512 個(gè)頁(yè)框的鏈表中找一個(gè)空閑塊。如果存在這樣的塊，內(nèi)核就把 512 的頁(yè)框分成兩等分，一般用作滿足需求，另一半則插入到 256 個(gè)頁(yè)框的鏈表中。如果在 512 個(gè)頁(yè)框的塊鏈表中也沒找到空閑塊，就繼續(xù)找更大的塊 —— 1024 個(gè)頁(yè)框的塊。如果這樣的塊存在，內(nèi)核就把 1024 個(gè)頁(yè)框塊的 256 個(gè)頁(yè)框用作請(qǐng)求，然后剩余的 768 個(gè)頁(yè)框中拿 512 個(gè)插入到 512 個(gè)頁(yè)框的鏈表中，再把最后的 256 個(gè)插入到 256 個(gè)頁(yè)框的鏈表中。如果 1024 個(gè)頁(yè)框的鏈表還是空的，算法就放棄并發(fā)出錯(cuò)誤信號(hào)。

簡(jiǎn)而言之，就是在分配內(nèi)存時(shí)，首先從空閑的內(nèi)存中搜索比申請(qǐng)的內(nèi)存大的最小的內(nèi)存塊。如果這樣的內(nèi)存塊存在，則將這塊內(nèi)存標(biāo)記為“已用”，同時(shí)將該內(nèi)存分配給應(yīng)用程序。如果這樣的內(nèi)存不存在，則操作系統(tǒng)將尋找更大塊的空閑內(nèi)存，然后將這塊內(nèi)存平分成兩部分，一部分返回給程序使用，另一部分作為空閑的內(nèi)存塊等待下一次被分配。

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

• 兩個(gè)塊具有相同的大小，記作 b 。
• 它們的物理地址是連續(xù)的。
• 第一塊的第一個(gè)頁(yè)框的物理地址是 2 * b * 2^12 的倍數(shù)。

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

假設(shè)要釋放一個(gè) 256 個(gè)頁(yè)框的塊，算法就把其插入到 256 個(gè)頁(yè)框的鏈表中，然后檢查與該內(nèi)存相鄰的內(nèi)存，如果存在同樣大小為 256 個(gè)頁(yè)框的并且空閑的內(nèi)存，就將這兩塊內(nèi)存合并成 512 個(gè)頁(yè)框，然后插入到 512 個(gè)頁(yè)框的鏈表中，如果不存在，就沒有后面的合并操作。然后再進(jìn)一步檢查，如果合并后的 512 個(gè)頁(yè)框的內(nèi)存存在大小為 512 個(gè)頁(yè)框的相鄰且空閑的內(nèi)存，則將兩者合并，然后插入到 1024 個(gè)頁(yè)框的鏈表中。

簡(jiǎn)而言之，就是當(dāng)程序釋放內(nèi)存時(shí)，操作系統(tǒng)首先將該內(nèi)存回收，然后檢查與該內(nèi)存相鄰的內(nèi)存是否是同樣大小并且同樣處于空閑的狀態(tài)，如果是，則將這兩塊內(nèi)存合并，然后程序遞歸進(jìn)行同樣的檢查。

下面通過一個(gè)例子，來深入地理解一下伙伴算法的真正內(nèi)涵（下面這個(gè)例子并不嚴(yán)格表示Linux 內(nèi)核中的實(shí)現(xiàn)，是闡述伙伴算法的實(shí)現(xiàn)思想）：

假設(shè)系統(tǒng)中有 1MB 大小的內(nèi)存需要?jiǎng)討B(tài)管理，按照伙伴算法的要求：需要將這 1 M 大小的內(nèi)存進(jìn)行劃分。這里，我們將這 1 M 的內(nèi)存分為 64K、64K、128K、256K、和 512K 共五個(gè)部分，如下圖 a 所示

1、此時(shí)，如果有一個(gè)程序 A 想要申請(qǐng)一塊 45 K 大小的內(nèi)存，則系統(tǒng)會(huì)將第一塊 64 K 的內(nèi)存塊分配給該程序（產(chǎn)生內(nèi)部碎片為代價(jià)），如圖 b 所示；

2、然后程序 B 向系統(tǒng)申請(qǐng)一塊 68 K 大小的內(nèi)存，系統(tǒng)會(huì)將 128 K 內(nèi)存分配給該程序，如圖 c 所示；

3、接下來，程序 C 要申請(qǐng)一塊大小為 35 K 的內(nèi)存。系統(tǒng)將空閑的 64 K 內(nèi)存分配給該程序，如圖 d 所示；

4、之后程序 D 需要一塊大小為 90 K 的內(nèi)存。當(dāng)程序提出申請(qǐng)時(shí)，系統(tǒng)本該分配給程序 D 一塊 128 K 大小的內(nèi)存，但此時(shí)內(nèi)存中已經(jīng)沒有空閑的 128 K 內(nèi)存塊了，于是根據(jù)伙伴算法的原理，系統(tǒng)會(huì)將 256 K 大小的內(nèi)存塊平分，將其中一塊分配給程序 D，另一塊作為空閑內(nèi)存塊保留，等待以后使用，如圖 e 所示；

5、緊接著，程序 C 釋放了它申請(qǐng)的 64 K 內(nèi)存。在內(nèi)存釋放的同時(shí)，系統(tǒng)還負(fù)責(zé)檢查與之相鄰并且同樣大小的內(nèi)存是否也空閑，由于此時(shí)程序A并沒有釋放它的內(nèi)存，所以系統(tǒng)只會(huì)將程序 C 的 64 K 內(nèi)存回收，如圖 f 所示；

6、然后程序 A 也釋放掉由它申請(qǐng)的 64 K 內(nèi)存，系統(tǒng)隨機(jī)發(fā)現(xiàn)與之相鄰且大小相同的一段內(nèi)存塊恰好也處于空閑狀態(tài)。于是，將兩者合并成 128 K 內(nèi)存，如圖 g 所示；

7、之后程序 B 釋放掉它的 128 k，系統(tǒng)也將這塊內(nèi)存與相鄰的 128 K 內(nèi)存合并成 256 K 的空閑內(nèi)存，如圖 h 所示；

8、最后程序 D 也釋放掉它的內(nèi)存，經(jīng)過三次合并后，系統(tǒng)得到了一塊 1024 K 的完整內(nèi)存，如圖 i 所示。

?

有了前面的了解，我們通過Linux 內(nèi)核源碼（mmzone.h）來看看伙伴算法是如何實(shí)現(xiàn)的：

伙伴算法管理結(jié)構(gòu)

#define MAX_ORDER 11struct zone {……struct free_area free_area[MAX_ORDER];……}struct free_area {struct list_head free_list[MIGRATE_TYPES];unsigned long nr_free; //該組類別塊空閑的個(gè)數(shù)};

前面說到伙伴算法把所有的空閑頁(yè)框分組為 11 塊鏈表，內(nèi)存分配的最大長(zhǎng)度便是 2^10 頁(yè)面。

上面兩個(gè)結(jié)構(gòu)體向我們揭示了伙伴算法管理結(jié)構(gòu)。zone 結(jié)構(gòu)中的 free_area 數(shù)組，大小為 11，分別存放著這 11 個(gè)組，free_area 結(jié)構(gòu)體里面又標(biāo)注了該組別空閑內(nèi)存塊的情況。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

將所有空閑頁(yè)框分為 11 個(gè)組，然后同等大小的串成一個(gè)鏈表對(duì)應(yīng)到 free_area 數(shù)組中。這樣能很好的管理這些不同大小頁(yè)面的塊。

(啊哦，有時(shí)間再補(bǔ)充吧...)

?

?

（SAW：Game Over！）

總結(jié)

以上是生活随笔為你收集整理的OS / Linux / 伙伴（buddy）算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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