malloc lab隐式空闲链表
时间: 2025-01-14 19:31:47 浏览: 37
### 隐式空闲链表的实现与细节
在 `malloc` 实验室中,隐式空闲链表是一种用于管理堆内存的技术。这种技术通过维护一个未被使用的内存块列表来优化内存分配和释放操作。
#### 内存布局
当程序启动时,会初始化一个小的堆区(例如16个字大小),每个字为4字节[^1]。这个初始堆可以看作是一整块连续的可用内存区域。随着程序运行过程中调用 `malloc()` 和 `free()`, 这些大块会被分割成更小的部分以满足不同的请求尺寸需求。
对于每一个已分配或已被释放但仍处于自由状态下的区块,在其头部通常存储有元数据信息,比如前驱/后继节点地址以及当前块的状态标志位等。这些额外的数据结构使得能够有效地链接起所有的闲置片段形成所谓的“隐式”链条——即不显式的保存整个列表头指针而是依靠各部分之间的相对位置关系来进行遍历查找工作。
#### 分配算法
为了从这样的空闲链表中找到合适的内存块供新申请使用:
- **首次适配(First Fit)**: 顺序扫描直到发现第一个足够大的空洞为止;
- **最佳适配(Best Fit)**: 寻找最接近所需大小的那个间隙;虽然理论上看起来不错但实际上可能导致过多碎片化问题。
- **下次适配(Next Fit)**: 类似于首次匹配但是记住上一次停止的地方继续向下搜索而不是每次都重新回到起点处开始寻找。
每种策略都有各自的优劣之处,具体选择取决于应用场景的要求平衡效率同资源利用率之间矛盾点所在。
#### 合并机制
当某个曾经占用过的区间再次变为可利用状态时(也就是执行了一次成功的 `free()` 调用之后),应当考虑将其前后相邻且同样为空置状况的小片断连接起来构成更大的整体以便后续更大规模的需求能更容易得到满足。这一过程被称为“合并”。
```c
void coalesce(void *ptr) {
// 获取该块的前后邻居的信息
size_t prev_alloc = GET_ALLOC(FTRP(ptr));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
void *prev = PREV_BLKP(ptr);
void *next = NEXT_BLKP(ptr);
if (!prev_alloc && !next_alloc){
// 如果前后都是空闲,则三者合并
ptr = prev;
PUT(HDRP(ptr), PACK(get_size(prev)+get_size(next)+sizeof(size_t)*2,0));
PUT(FTRP(ptr), PACK(get_size(prev)+get_size(next)+sizeof(size_t)*2,0));
}else if(!prev_alloc && next_alloc){
// 只前面是空闲则两者合并
ptr = prev;
PUT(HDRP(ptr), PACK(get_size(ptr)+get_size(NEXT_BLKP(ptr)),GET_ALLOC(HDRP(NEXT_BLKP(ptr)))));
PUT(FTRP(ptr), PACK(get_size(ptr)+get_size(NEXT_BLKP(ptr)),GET_ALLOC(HDRP(NEXT_BLKP(ptr)))));
}else if(prev_alloc && !next_alloc){
// 只后面是空闲则两者合并
PUT(HDRP(ptr), PACK(get_size(ptr)+get_size(NEXT_BLKP(ptr)),GET_ALLOC(HDRP(ptr))));
PUT(FTRP(ptr), PACK(get_size(ptr)+get_size(NEXT_BLKP(ptr)),GET_ALLOC(HDRP(ptr))));
}
}
```
此函数展示了如何处理不同情况下两个或多个相连的空闲块之间的组合逻辑。它检查给定指针对应的位置及其周围的几个单元格是否标记为非活动状态,并相应调整它们共同组成的较大实体边界上的属性值。
阅读全文
相关推荐









