核心內部與作業系統建構

夥伴系統(buddy system)

核心持續需要以整頁為單位的實體記憶體區塊——有時一頁、有時連續好幾頁——而且它必須能快速發出與收回,又不把記憶體切成無法使用的碎屑。夥伴系統(buddy system)就是它用來做這件事的經典演算法。想像一條由等大方格組成的巧克力:若你要一小塊,就把一大塊折成一半、也許再折一半,只取你需要的大小;用完後又能把相配的兩半折回去、拼成更大的一條。夥伴系統就是用這種對半折的方式來分割與重組記憶體。

具體來說,空閒記憶體被保存在依大小分組的清單裡,每種大小都是 2 的次方頁數:1 頁、2 頁、4、8……一路到某個上限(在 Linux 中是第 0 到第 10 階)。要滿足一個請求,配置器會找出大到足夠的最小可用區塊;若唯一的空閒區塊太大,它就把它反覆對半切開,而一次切割出來的兩半互稱為夥伴。當一個區塊被釋放時,配置器會檢查它的夥伴(當初一起切出來、相配的那一半)是否也空閒;若是,就把兩者合併回上一級更大的區塊,並持續向上合併。由於夥伴位在固定且可計算的位址(一個區塊與它的夥伴恰好相差一個區塊的大小),尋找夥伴與合併都很快。

它之所以重要,是因為快速合併能讓實體記憶體不致碎裂成一堆無用的微小空閒碎屑——核心得以持續產出大型的連續區塊,而某些操作與裝置正需要這個。誠實的取捨是 2 的次方取整所帶來的內部碎裂:要求 5 頁卻拿到一個 8 頁的區塊,浪費了 3 頁。這正是為什麼核心對許多小型物件會在夥伴系統之上再疊一層 slab 配置器,而不是把每個微小的配置都向上取整成一整頁。

假設核心要 1 頁,但最小的空閒區塊是 8 頁。配置器把 8 切成兩個 4 頁的夥伴、把其中一個 4 切成兩個 2 頁的夥伴、把其中一個 2 切成兩個 1 頁的夥伴,然後交出其中一個 1 頁的區塊——其餘各半留在空閒清單上。日後當這些夥伴全被釋放時,它們又會向上合併回一個 8 頁的區塊,準備好應付下一個大型請求。

按需以對半方式分割區塊;釋放時把夥伴合併回去,以對抗碎裂。

夥伴系統能減少外部碎裂,卻無法消除內部碎裂,因為每個請求都被向上取整成 2 的次方頁數。當記憶體分散時,它也難以滿足大型的連續請求——這正是為什麼核心還會為高階配置提供退而求其次的方案。

又称
buddy allocatorpage allocator夥伴配置器