Budy内存管理算法
最后更新于：2022-04-02 04:05:41
[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空闲链表,回收完成
';