published on
tags: tech

垃圾回收机制简介

什么是垃圾回收?

如果你是一个传统的C/C++语言或Pascal语言的用户,可能会对垃圾回收这个名词感到模式。而对于函数式语言来说,垃圾回收一直是一个不可缺少的组成部分。到目前来看,凡是比较新的语言,不管是不是函数式的,基本都吸取了这个特性,提供了垃圾回收机制作为内存管理的方案。

那么什么是垃圾回收呢,对于C语言来说,你如果需要申请一段内存保存你的数据,那么在用完了之后,必须显式的告诉系统,这段内存不用了,而可以复用。这个要求对程序员的负担其实挺重的,必须清楚的确定每个对象的生存周期。而且在有的场景下,很难决定何时来释放这个对象(比如多线程环境下不知道别人在不在用)。

于是就会有自动的内存管理方案,垃圾回收机制产生了。其作用是在一个内存不用了之后,系统可以自动再利用这段内存,而不用产生泄漏。其要点在于及时。即不能太早也不能太晚,太早的话可能别人还要用这个对象,太晚的话就可能会浪费太多内存。当然这两个条件,不能早是绝对要满足的,而是否可以晚一点是一个相对宽松的条件,可能会为了各种因素来取舍(比如性能)

那么如何进行垃圾回收呢,其主要分成两个部分

  1. 如何判断一个对象是否可以释放了
  2. 如何管理内存的申请和释放的操作

基本方法

实际使用中,垃圾回收可能是很多方法组合而成的,而其基本的思路基本有3种:

  • 引用计数
  • 标记-清扫
  • 节点复制

引用计数

引用计数的原理比较简单,只要我在每个对象的开头附加一个域,统计有多少个指针指向这个对象。当指针赋值的时候,被指向的对象的计数+1,没被指向的对象的计数器-1。当一个对象的计数器变成0的时候,说明没有指针指向它了。那么就可以释放掉它。

比如C++中的std::shared_ptr就是使用引用计数的原理来实现的。

引用计数的优点:

能很快的进行释放,如果没人用了,马上就能知道。这属于渐进式的收集,和那些一开始垃圾回收就要停住别的地方的程序相比,是个很大的优点。

能马上知道何时可以回收的好处还有别的一些,这里就不多展开了。

引用计数的缺点:

  • 最主要的缺点是对付不了环形的结构,如果A对象有B对象的引用,而B对象又有A对象的引用,这样他们的引用计数永远都不会变成0,即使没有从全局变量区或堆栈来的指针能都访问到他们了。
  • 第二点比较复杂的是如果是多线程的环境下,维护引用计数的成本很高。需要使用锁,或者复杂的硬件机 制来保证原子性。
  • 第三点是它需要附加一些空间来保存引用计数的值。在小对象多的情况下空间浪费很高。

尽管有缺点,但都会有人研究怎么补偿这些问题,但是这里只是做个简介,就不再展开。

标记清扫

另一个被广泛使用的计数就是标记清扫。比如在lua就是用了一种渐进式的标记清扫算法进行的垃圾回收工作。boehm给C做了一个保守的收集器,也是基于这个算法,而且这个收集器被guile拿去用在收集scheme里面的对象了。

其基本原理如下,假设分配程序叫alloc_mem:

alloc_mem(size) {
    if (!pool_can_alloc(size)) {
        mark_sweap()
    }
    return alloc_from_pool()
}

mark_sweap() {
    // mark 阶段
    mark(root)
    mark(stack)
    // 清扫阶段
    for (object : all_objects) {
        if (not_marked(object)) {
            free(object)
        }
    }
}

mark(object) {
    // 标记当前的对象
    set_marked(object)
    // 递归的去标记改对象引用了的那些对象
    for (ref_obj : get_ref_obj(object)) {
        mark(ref_obj)
    }
}

简单来说,就是把引用关系看成一个有向图,做一次dfs,把能到达的对象都标出来,剩下的统统干掉。

这里面可能要考虑的一些问题:

  • 这里是stop the world的收集,也就是说一旦进入了这里面,程序遇到内存分配的时候都得等在这。所以基本上就干不了什么事了。在一些实时性要求比较高一点的地方就不好使用了,简单的话可以在比较要紧的时候禁止执行gc,过后再说,当然更好的是用渐进式、分代等优化策略。
  • 这里mark的过程是递归的,实际实现的时候要考虑堆栈溢出的风险。尤其是想想如果遇到一个很大的链表的时候。这里面也有一些相应的技巧可以降低gc过程中对内存的消耗。

节点复制

节点复制算法比较有意思,就是我现在的堆我只用一半,当这一半满了的时候,我们按照标记-清扫的办法来寻找存活节点,在寻找的时候我们并不用进行标记,而是将其复制到堆的另一半里面。这样标记的过程一完成,我们就把所有存活节点弄到新的半区去了,然后记得把引用改成到新的半区里的对象的位置,旧的半区直接抛弃就行了,接下来就可以在新的半区继续分配内存了。

这样做的优缺点和前面的方法就截然不同了:

优点:

  • 分配内存简单:每次只要在上次分配的地方再继续往后分配即可
  • 对象都连续存放在一块,对缓存友好
  • 只要访问存活的对象就行了,而不像标记清扫算法那样在清扫阶段会访问所有对象

缺点:

  • 复制起来需要花费时间(特别如果都是大对象)
  • 需要留出一半的空间

这个方法带来的移动对象可以提供命中和简化分配是一个很好的思路,所以为了不用两个堆,就产生了标记-缩并的思路:在同一个堆里先标记,再把存活对象纷纷往前移动到开头的位置。在javascript引擎v8中的垃圾回收就是用缩并的方式进行的。

进一步的内容

垃圾收集相关的研究相当之多。有一本非常好的书对各个方面进行了详尽的讨论:《Garbage Collection: Algorithms for Automatic Dynamic Memory Management》,而且居然还有中译本,虽然翻译的已经绝版了。

里面还进一步涉及了下面一些更高级的主题

  • 分代,很多对象生命周期很短,而长的一般保持很久,所以收集的时候可以将它们区别开。
  • 渐进式,平滑的收集需要的一些技术。
  • 并发式,在并发环境下怎么进行垃圾回收。
  • 硬件相关 / 缓存利用

(完) 本来想配点图的,终究又不知道怎么画比较好,于是放弃了。