基本介紹
- 中文名：夥伴算法
- 外文名：buddy算法
夥伴關係,夥伴算法的實現原理,記憶體分配,記憶體回收,
夥伴關係
夥伴關係的定義為：由一個母實體分成的兩個各方面屬性一致的兩個子實體，這兩個子實體就處於夥伴關係。在作業系統分配記憶體的過程中，一個記憶體塊經常被分成兩個大小相等的記憶體塊，這兩個大小相等的記憶體塊就處於夥伴關係。它滿足3個條件：兩個塊具有相同大小；物理地址是連續的；從同一個大塊中拆分出來。
夥伴算法的實現原理
為了便於頁面的維護，將多個頁面組成記憶體塊，每個記憶體塊都有2的方冪個頁，方冪的指數被稱為階。在操作記憶體時，經常將這些記憶體塊分成大小相等的兩個塊，分成的兩個記憶體塊被稱為夥伴塊，採用一位二進制數來表示它們的夥伴關係。當這個位為1，表示其中一塊在使用；當這個位為0，表示兩個頁面塊都空閒或者都在使用。系統根據該位為0或位為1來決定是否使用或者分配該頁面塊。系統每次分配和回收夥伴塊時都要對它們的夥伴位跟1進行異或運算。所謂異或是指剛開始時，兩個夥伴塊都空閒，它們的夥伴位為0，如果其中一塊被使用，異或後得1；如果另一塊也被使用，異或後得0；如果前面一塊回收了異或後得1；如果另一塊也回收了異或後得0。
記憶體分配
Linux核心為了儘量減少空間的浪費，減少申請釋放記憶體的消耗時間，採用基於夥伴算法的存儲分配機制。夥伴系統算法把記憶體中的所有頁框按照大小分成10組不同大小的頁塊，每塊分別包含1，2，4，8，……，512個頁框。每種不同的頁塊都通過一個free-area-struct結構體來管理。系統將10個free-area-struct結構體組成一個free-area[]數組。在free-area-struct包含指向空閒頁塊鍊表的指針。此外在每個free-area-struct中還包含一個系統空閒頁塊點陣圖（bitmap），點陣圖中的每一位都用來表示系統按照當前頁塊大小劃分時每個頁塊的使用情況，同mem-map一樣，系統在初始化時調用free-area-struct()函式來初始化每個free-area-struct中的點陣圖結構。
記憶體回收
當向記憶體請求分配一定數目的頁框時，若所請求的頁框數目不是2的冪次方，則按稍大於此數目的2的冪次方在頁塊鍊表中查找空閒頁塊，如果對應的頁塊鍊表中沒有空閒頁塊，則在更大的頁塊鍊表中查找。當分配的頁塊中有多餘的頁框時，夥伴系統將根據多餘的頁框大小插入到對應的空閒頁塊鍊表中。向夥伴系統釋放頁框時，夥伴系統會將頁框插入到對應的頁框鍊表中，並且檢查新插入的頁框能否和原有的頁塊組合構成一個更大的頁塊，如果兩個塊的大小相同且這兩個塊的物理地址連續，則合併成一個新頁塊加入到對應的頁塊鍊表中，并迭代此過程直到不能合併為止，這樣可以極大限度地減少記憶體的外碎片。
夥伴系統提供了分配和釋放頁框的函式。get-zeroed-page()用於分配用0填充好的頁框。和get-zeroed-page()相似，-get-free-page()用來分配一個新的頁框，但是沒有被0填充，-get-free-page()用來分配指定數目的頁框。通過調用-free-page()和-free-pages()可以向夥伴系統釋放已申請的頁框。alloc-pages-node()是夥伴系統分配頁框的核心函式，它有兩個變體：alloc-page()和alloc-pages()。alloc-pages-node()函式在指定的節點中分配一定數目的頁框。alloc-page()和alloc-pages()分別在當前節點中分配一個或指定數目的頁框。
