GC算法-标记清除算法

概述

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

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

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

实现

介绍写的很清楚了, 实现也是两个阶段呗, 先打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法 ,延迟清除算法等等个人感觉很鸡肋(好吧, 或许是我未得其精髓).

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