夥伴系統（buddy system）

想像一條由 16 小格組成的巧克力，而你只能從正中對折掰開。要給某人一小格，你把整條掰成兩個 8、把一個 8 掰成兩個 4、一個 4 掰成兩個 2、一個 2 掰成兩個 1，然後遞出一格。當小塊回來時，你可以把兩半黏回它們原本的整塊——但只能黏回曾經在一起的那兩個特定半邊，也就是它們的夥伴（buddy）。夥伴系統管理記憶體就是這麼做：每個區塊都是 2 的次方大小，切割總是把區塊對半分，而合併永遠只把一個區塊與它唯一的原始夥伴重新接合。

精確地說：配置器為每個 2 的次方區塊大小（16 KiB、32 KiB、64 KiB……）各保有一條自由串列。要滿足一個請求，它向上湊到下一個 2 的次方，再找出至少那麼大的最小空閒區塊；若該區塊比所需大，它把它對半切割，把其中一半（夥伴）放到較小尺寸的自由串列上，並重複直到得到正確大小的區塊。釋放則相反：當一個區塊被釋放，配置器檢查它的夥伴——它被切出來的另一半，只要把區塊位址的某一位元翻轉就能找到——是否也空閒；若是，兩者合併回上一個尺寸，並沿鏈往上重複這個檢查。因為一個區塊的夥伴是把其位址做單一位元翻轉算出的（位址 A、大小 S 的區塊，其夥伴是 A XOR S），所以切割與合併檢查都極快。

夥伴系統是 Linux 核心以及許多其他系統內部以頁為單位的配置器：它以 2 的次方的連續頁來管理實體記憶體，也是 slab 配置器向它索取 slab 的對象。它的長處是快速、簡單的合併，能有效對抗外部碎片。它誠實的弱點是 2 的次方湊整造成的內部碎片：一個 17 KiB 的請求必須用 32 KiB 的區塊服務，浪費近一半。這就是刻意的取捨——粗糙、湊整的尺寸，換取便宜且可預測的切割與合併。