【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 中

参考资料

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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学