[TOC] ## Budy內存管理算法 - Budy算法是經典的內存管理算法 - 算法基于計算機處理二進制的優勢具有極高的效率 - 算法主要是為了解決**內存外碎片**的問題(轉移為了內存內碎片的問題) - 努力讓內存分配與相鄰內存合并能快速進行 ### 內存分配原則 1. 向上取整為2的冪大 ``` 70k→128k 申請70k,則分配128k的內存 129k→256k 666k→1024k ``` ### 伙伴系統 - “伙伴”指的是內存的“伙伴” - 片連續內存的“伙伴”是相鄰的另一片大小一樣的連續內存 創建一系列空閑塊鏈表,每一種都是2的冪  ### 算法流程 #### 分配流程 假設:現在只有1MB 的內存塊, 都是null,而需要分配100 KB 的內存 1. 100k向上取2的冪=128k 2. 查詢是否有128k空閑內存塊? 3. 沒有!查詢是否有256k空閑內存塊? 4. 沒有!查詢是否有512k空閑內存塊? 5. 沒有!查詢是否有1M空閑內存塊? 6. 有,摘下1M空閑內存塊,分配出去 7. 拆下512k放在512k的空閑鏈表,其余的分配出去 8. 拆下256k放在256k的空閑鏈表,其余的分配出去 9. 拆下128k放在128k的空閑鏈表,其余的分配出去 10. 分配完畢 > 最終分配了128k的內存,把內幕才能外碎片的問題轉為內存內碎片問題 #### 回收流程 1. 判斷剛才分配的內存伙伴在空閑鏈表上嗎? 2. 在,移除伙伴,合并為256k空閑內存,判斷 3. 在,移除伙伴,合并為512k空閑內存,判斷 4. 在,移除伙伴,合并為1M空閑內存 5. 插入1M空閑鏈表,回收完成