【12.3】高级数据结构--存储管理

一、 分配与回收

• 内存管理最基本的问题

• 分配存储空间

• 回收被“释放”的存储空间

• 碎片问题

• 存储的压缩

• 无用单元收集

• 无用单元:可以回收而没有回收的空间

• 内存泄漏 (memory leak)。 程序员忘记 delete 已经不再使用的指针

二、 可利用空间表

• 把存储器看成一组定长块组成的数组

• 一些块是已分配的

• 链接空闲块，形成可利用空间表 (freelist)

• 存储分配和回收

• new p 从可利用空间分配

• delete p 把 p 指向的数据块返回可利用空间表

可利用空间表的函数重载

可利用空间表:单链表栈

• new 即栈的删除操作
• delete 即栈的插入操作
• 直接引用系统的 new 和 delete 操作符， 需要强制用“::new p” 和“::delete p”
• 例如，程序运行完毕时，把 avail 所占用的空 间都交还给系统 (真正释放空间)

三、 存储的动态分配和回收

3.1 变长可利用块

• 分配

• 找到其长度大于等于申请长度的结点

• 从中截取合适的长度

• 回收

• 考虑刚刚被删除的结点空间能否与邻接合并

• 以便能满足后来的较大长度结点的分配请求

3.2 空闲块的数据结构

3.3 碎片问题

• 内部碎片:多于请求字节数的空间
• 外部碎片:小空闲块

3.4 空闲块的顺序适配 (sequential fit)

• 首先适配 (first fit)
• 最佳适配 (best fit)
• 最差适配 (worst fit)

四、 失败处理策略和无用单元回收

回收:考虑合并相邻块

如果遇到因内存不足而无法满足一个存储请求， 存储管理器可以有两种行为

• 一是什么都不做，直接返回一个系统错误信息
• 二是使用失败处理策略 (failure policy) 来满足请求

存储压缩 (compact)

在可利用空间不够分配或在进行无用单元的收 集时进行“存储压缩”

无用单元收集

无用单元收集:最彻底的失败处理策略

• 普查内存，标记把那些不属于任何链的结点
• 将它们收集到可利用空间表中
• 回收过程通常还可与存储压缩一起进行

五、思考

• 比较首先适配、最佳适配和最差适配的特点

• 哪种适配方案更容易产生外部碎片?

• 哪种方案总体最优?

• 怎样有效地组织空闲块，使得分配时查找到合 适块的效率更高?

• 所有空闲块都组织在一个线性表中

• 不同规模的空闲块组织在不同的链表中

• 以空闲块的大小为 key 组织在平衡的 BST 中

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾