今天去面試，一位面試官提到了記憶體管理的夥伴系統，當時就懵了，因為根本就沒有聽說過。晚上回來在實驗室查了一些資料，現總結如下：
1.夥伴系統概念
夥伴系統是一種經典的記憶體管理方法。Linux夥伴系統的引入為核心提供了一種用于配置設定一組連續的頁而建立的一種高效的配置設定政策，并有效的解決了外碎片問題。
2.夥伴系統的組織結構
Linux中的記憶體管理的“頁”大小為4KB。把所有的空閑頁分組為11個塊連結清單，每個塊連結清單分别包含大小為1，2，4，8，16，32，64，128，256，512和1024個連續頁框的頁塊。最大可以申請1024個連續頁，對應4MB大小的連續記憶體。每個頁塊的第一個頁的實體位址是該塊大小的整數倍。
結構如圖所示：第i個塊連結清單中，num表示大小為(2^i)頁塊的數目，address表示大小為(2^i)頁塊的首位址。
3.夥伴系統的記憶體配置設定及釋放
當向核心請求配置設定(2^(i-1)，2^i]數目的頁塊時，按照2^i頁塊請求處理。如果對應的塊連結清單中沒有空閑頁塊，則在更大的頁塊連結清單中找。當配置設定的頁塊中有多餘的頁時，夥伴系統根據多餘的頁框大小插入到對應的空閑頁塊連結清單中。
當釋放單頁的記憶體時，核心将其置于CPU高速緩存中，對很可能出現在cache的頁，則放到“快表”的清單中。在此過程中，核心先判斷CPU高速緩存中的頁數是否超過一定“門檻值”，如果是，則将一批記憶體頁還給夥伴系統，然後将該頁添加到CPU高速緩存中。
當釋放多頁的塊時，核心首先計算出該記憶體塊的夥伴的位址。核心将滿足以下條件的三個塊稱為夥伴：(1)兩個塊具有相同的大小，記作b。(2)它們的實體位址是連續的。(3)第一塊的第一個頁的實體位址是2*(2^b)的倍數。如果找到了該記憶體塊的夥伴，確定該夥伴的所有頁都是空閑的，以便進行合并。記憶體繼續檢查合并後頁塊的“夥伴”并檢查是否可以合并，依次類推。
4.夥伴系統的反碎片機制
核心将已配置設定頁分為以下三種不同的類型：
(1)不可移動頁：這些頁在記憶體中有固定的位置，不能夠移動。
(2)可回收頁：這些頁不能移動，但可以删除。核心在回收頁占據了太多的記憶體時或者記憶體短缺時進行頁面回收。
(3)可移動頁：這些頁可以任意移動，使用者空間應用程式使用的頁都屬于該類别。它們是通過頁表映射的。當它們移動到新的位置，頁表項也會相應的更新。
在記憶體子系統初始化期間，所有的頁都被标記為可移動的。在啟動期間，核心核心配置設定的記憶體是不可移動的。此時核心的政策是配置設定一個盡可能大的連續記憶體塊，将其從可移動清單轉換到不可移動清單。配置設定一個盡可能大的連續記憶體塊而不是選擇更小的滿足要求的記憶體塊的原因如下：
例如：現有一塊可移動的具有16頁的連續空閑記憶體塊。當核心需要配置設定1頁不可移動記憶體頁時。配置設定器選擇後8頁(而不是一頁)轉移到不可移動清單，然後從不可移動清單中選擇1頁用于配置設定。如果核心又需要配置設定1頁不可移動記憶體頁則從不可移動清單中選擇一頁用于配置設定，下圖顯示了進行4次配置設定後記憶體的分布。
但如果核心隻選擇1頁用于配置設定将其加入到不可移動清單，當下次需要配置設定時又選擇一頁加入到不可移動清單，下圖顯示了按照這種方式進行4次配置設定後記憶體的分布。
是以，當沒有滿足可用于配置設定的不可移動空閑塊時，配置設定器會在可移動清單中遷移一個盡可能大的連續記憶體塊給不可移動清單。這樣避免了啟動期間核心配置設定的記憶體散列到實體記憶體各處，進而使其他類型的記憶體配置設定免受碎片的幹擾。