buddy算法

buddy算法，計算機算法的一種，是用來做記憶體管理的經典算法，目的是為了解決記憶體的外碎片。

基本介紹

• 中文名：buddy算法
• 用來：做記憶體管理的經典算法
• 目的：為了解決記憶體的外碎片
• 塊鍊表：10個

避免外碎片的方法有兩種

1，利用分頁單元把一組非連續的空閒頁框映射到非連續的線性地址區間。

2，開發適當的技術來記錄現存的空閒連續頁框塊的情況，以儘量避免為滿足對小塊的請求而把大塊的空閒塊進行分割。

核心選擇第二種避免方法

基於下面三種原因，核心選擇第二種避免方法：

1，在某些情況下，連續的頁框確實必要。

2，即使連續頁框的分配不是很必要，它在保持核心頁表不變方面所起的作用也是不容忽視的。假如修改頁表，則導致平均訪存次數增加，從而頻繁刷新TLB。

3，通過4M的頁可以訪問大塊連續的物理記憶體，相對於4K頁的使用，TLB未命中率降低，加快平均訪存速度。

例子

buddy算法將所有空閒頁框分組為10個塊鍊表，每個塊鍊表的每個塊元素分別包含1,2,4,8,16,32,64,128,256,512個連續的頁框，每個塊的第一個頁框的物理地址是該塊大小的整數倍。如，大小為16個頁框的塊，其起始地址是16*2^12(一個頁框的大小為4k,16個頁框的大小為16*4K,1k=1024=2的10次方，4k=2的12次方)的倍數。

例，假設要請求一個128個頁框的塊，算法先檢查128個頁框的鍊表是否有空閒塊，如果沒有則查256個頁框的鍊表，有則將256個頁框的塊分裂兩份，一份使用，一份插入128個頁框的鍊表。如果還沒有，就查512個頁框的鍊表，有的話就分裂為128，128，256，一個128使用，剩餘兩個插入對應鍊表。如果在512還沒查到，則返回出錯信號。

優缺點

Buddy算法的優缺點：

1）儘管夥伴記憶體算法在記憶體碎片問題上已經做的相當出色，但是該算法中，一個很小的塊往往會阻礙一個大塊的合併，一個系統中，對記憶體塊的分配，大小是隨機的，一片記憶體中僅一個小的記憶體塊沒有釋放，旁邊兩個大的就不能合併。
2）算法中有一定的浪費現象，夥伴算法是按2的冪次方大小進行分配記憶體塊，當然這樣做是有原因的，即為了避免把大的記憶體塊拆的太碎，更重要的是使分配和釋放過程迅速。但是他也帶來了不利的一面，如果所需記憶體大小不是2的冪次方，就會有部分頁面浪費。有時還很嚴重。比如原來是1024個塊，申請了16個塊，再申請600個塊就申請不到了，因為已經被分割了。

3）另外拆分和合併涉及到 較多的鍊表和點陣圖操作，開銷還是比較大的。

夥伴關係

回收過程相反，核心試圖把大小為b的空閒夥伴合併為一個大小為2b的單獨塊，滿足以下條件的兩個塊稱為夥伴：1，兩個塊具有相同的大小，記做b；2，它們的物理地址是連續的，3，第一個塊的第一個頁框的物理地址是2*b*2^12的倍數，該算法疊代，如果成功合併所釋放的塊，會試圖合併2b的塊來形成更大的塊。