文章插图
具体这部分书中提到了四种方法：
隐式列表 Implicit List：在首部记录长度 ， 链接所有块
显式列表 Explicit List：用指针的空闲块的显式列表
分离的空闲列表 Segregated Free List：不同大小的不同链表
按大小对块排序 Blocks Sorted by Size：使用平衡树（如红黑树） ， 每个空闲块都有指针 ， 长度作为键
8 跟踪自由块8.1 隐式空闲列表每个块都记录大小和分配状态 ， 只需一个字节 ， 当块对齐时 ， 一些低阶地址位总是0 ， 与其存储始终为0的位 ， 不如将其作为已分配/空闲标志 。 当读取Size字节时 ， 必须屏蔽该位
文章插图
文章插图
8.1.1 数据结构
文章插图
8.1.2 头访问
文章插图
8.1.3 遍历链表
文章插图
8.1.4 找到一个空闲块如何确定哪部分空间合适 ， 有三种方法：
First Fit: 每次都从头进行搜索 ， 找到第一个合适的块 ， 线性查找
Next Fit: 每次从上次搜索结束的位置继续搜索 ， 避免重复搜索没有帮助的块 ， 速度较快 ， 但可能会有更多碎片 ， 一些研究表明碎片化教糟糕
Best Fit: 每次遍历列表 ， 找到剩余字节最少最合适的块 ， 碎片较少 ， 通常可提高内存利用率 ， 但是速度最慢 ， 仍是贪婪算法 ， 没最优保证
文章插图
8.1.5 分配空闲块由于已分配空间可能小于空闲空间 ， 可以分割块
文章插图
8.1.6 释放块最简单的实现方式是清除“已分配”的标记 ， 但可能导致错误的碎片化
文章插图
8.1.7 合并若下一个/前一个块是空闲的 ， 则连接合并
文章插图
8.1.8 双向合并在前面的基础上 ， 在空闲块的“底部”记录块的大小 ， 允许反向遍历列表 ， 但需额外空间 ， 边界标签（Knuth73）
文章插图
8.1.9 通过footers实现
文章插图
文章插图
文章插图
8.1.10 常数时间合并总共四种情况 ， 这里以第一种为例：
文章插图
文章插图
注意：对于头和尾需要加上”dummy footer” ， 标记为已分配 ， 防止在释放第一块和最后一块时意外合并
8.1.11 高层malloc/free代码malloc/free不常用 ， 因为线性时间分配 ， 多用于特殊目的应用
const size_t dsize = 2*sizeof(word_t);void *mm_malloc(size_t size){ size_t asize = round_up(size + dsize, dsize); block_t *block = find_fit(asize); if (block == NULL) return NULL; size_t block_size = get_size(block); write_header(block, block_size, true); write_footer(block, block_size, true); split_block(block, asize); return header_to_payload(block);}void mm_free(void *bp){ block_t *block = payload_to_header(bp); size_t size = get_size(block); write_header(block, size, false); write_footer(block, size, false); coalesce_block(block);}
- 什么是显卡 显卡有什么用
- 陀螺仪的作用是什么 陀螺仪有什么用
- 耳返的作用 耳返是干什么用的
- 电压互感器vv接线形式的特点
- 谐波保护器的应用领域及参数
- 数字解调器作用
- 调制解调器的用途与特点
- 调制器和解调器的作用
- 如何安装解调器
- 浅谈磨粉设备、输送设备与振动筛的配套问题