[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空闲链表,回收完成