GC算法-标记清除算法---烟草的香味

概述

标记清除算法, 描述起来很简单, 从名字上就能看出, 分为两个阶段:

标记阶段: 遍历所有对象, 将活动对象都打上标记清除阶段: 遍历堆, 将没有标记的对象释放掉.

介绍完毕, 本文结束. 开玩笑, 确实看上去很简单啦. 那就具体思考一下实现吧.

实现

介绍写的很清楚了, 实现也是两个阶段呗, 先打tag, 后清除.

标记

寻找所有的活动对象, 要从一个起点开始, 根集合(包括栈、常量池等等), 然后一层一层找下去. 简单来说就像这样:

add_mark(obj){ // 防止重复标记 if(obj.mark == true) return; obj.mark = true // 遍历所有子对象 for(o in objs){ add_mark(o) } }

将根集合的所有对象都调用一遍, 标记完成.

清除

标记时遍历的是活动对象, 清除阶段呢? 遍历堆. 将堆上所有非活动对象清除. 就比如:

// 这里一直堆的开始位置 HEAP_START 和结束位置 HEAP_END p = HEAP_START while(p < HEAP_END){ size = p.size // 对象的大小, 用于找到下一个对象 // 判断当前对象是否是活动对象 if(p.mark == true){ p.mark = false // 为下一次标记做准备 }else{ // 回收 free(p) } p += size }

当然, 其中的free函数也不是简单的将地址回收, 而是将其记录到一个链表中, 以方便下次申请内存. 实现大概如下:

free(p){ // 这里有一个全局变量, 保存链表头: FREE_HEAD // 若当前对象和上一次回收的对象是连续内存, 直接合并 if(FREE_HEAD + FREE_HEAD.size == p){ FREE_HEAD.size += p.size }else{ p.next = FREE_HEAD FREE_HEAD = p } }

这样, 申请内存时遍历FREE_HEAD, 找到大小合适的分块. 若没有找到, 就动态扩容咯. 这里其实还有一个优化的小方向, 开始的时候忘记了. 为了提高查找内存时速度, 可以将空闲链表按照大小进行区分, 这样, 需要多大的内存, 直接到对应的链表中找就行了.

虽然实现写的很粗糙, 但大致意思有了.

问题

1.内存的碎片化

从上面可以看到, 只对内存进行了清除, 但是没有整理. 而内存的申请又是动态的, 就会导致出现很多离散的小片空闲内存. 极端情况甚至可能内存中还有200mb的空闲内存, 但是申请个10kb的空间却找不到.

2.暂停时间长

其暂停时间与堆的大小成正比, 堆越大, 遍历清除耗费的时间就越久.

为了解决标记清除算法的问题, 衍生出了位图标记法, BiBOP法 ,延迟清除算法等等个人感觉很鸡肋(好吧, 或许是我未得其精髓).

为了解决标记清除的问题, 有衍生出了 标记复制 , 标记整理 算法, 之后再议.

---来自腾讯云社区的---烟草的香味