夥伴系統

Linux內核中採用了一種同時適用於32位和64位系統的內存分頁模型，對於32位系統來說，兩級頁表足夠用了，而在x86_64系統中，用到了四級頁表，如圖2-1所示。四級頁表分別為：

頁全局目錄(Page Global Directory)

頁上級目錄(Page Upper Directory)

頁中間目錄(Page Middle Directory)

頁表(Page Table)

頁全局目錄包含若干頁上級目錄的地址，頁上級目錄又依次包含若干頁中間目錄的地址，而頁中間目錄又包含若干頁表的地址，每一個頁表項指向一個頁框。Linux中採用4KB大小的頁框作為標準的內存分配單元。

在實際應用中，經常需要分配一組連續的頁框，而頻繁地申請和釋放不同大小的連續頁框，必然導致在已分配頁框的內存塊中分散了許多小塊的空閑頁框。這樣，即使這些頁框是空閑的，其他需要分配連續頁框的應用也很難得到滿足。

為了避免出現這種情況，Linux內核中引入了夥伴系統演演算法(buddy system)。把所有的空閑頁框分組為11個塊鏈表，每個塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個連續頁框的頁框塊。最大可以申請1024個連續頁框，對應4MB大小的連續內存。每個頁框塊的第一個頁框的物理地址是該塊大小的整數倍。

假設要申請一個256個頁框的塊，先從256個頁框的鏈表中查找空閑塊，如果沒有，就去512個頁框的鏈表中找，找到了則將頁框塊分為2個256個頁框的塊，一個分配給應用，另外一個移到256個頁框的鏈表中。如果512個頁框的鏈表中仍沒有空閑塊，繼續向1024個頁框的鏈表查找，如果仍然沒有，則返回錯誤。

頁框塊在釋放時，會主動將兩個連續的頁框塊合併為一個較大的頁框塊。