Recycler算法——环状引用计数算法的一种实现

该文章是《垃圾回收算法手册》一书的阅读笔记。详情请参阅原书。

背景

垃圾回收算法中的引用计数算法无法回收环状引用数据结构，包括自引用结构。这会造成一个问题，即如果这个整体在程序中是不可达的时候，但是回收器依然无法回收这部分内存——它们的引用计数将永远不会为0.
为了解决这种问题，一种有效的解决方案就是试验删除(trial deletion)算法。该算法的思想是：
1.1 在环状垃圾指针结构内部，所有对象的引用计数均由其内部对象之间的指针产生；
1.2 只有在删除某一对象的某个引用后该对象的引用计数仍大于0的时候，才有可能出现环状垃圾；
其中1.2是一条很弱的筛选条件。后面将进一步讨论这个问题。
有了这两条，可以使用部分追踪(partial tracing)从一个可能是垃圾的对象开始进行子图追踪。对于每一个候选垃圾对象，算法将对其进行试验删除，从而移除由内部指针产生的引用计数。追踪完成后，如果某个对象的引用计数仍然不为0，那么肯定存在一个外部对象引用了该对象，进而可以该对象及其传递闭包都不是垃圾。

Recycler算法

首先要明确几个状态，这几个状态分别用不同的颜色表示：

• 黑色：确定存活的对象（或者free）；
• 紫色：可能存在环状引用的对象；
• 灰色：在回收器扫描到这个对象和完成这个对象扫描，找到所有子节点之前，这一段时间内会被染成灰色；
• 绿色：不可能存在环状引用对象的对象；

在明确了这几个概念之后，算法的流程为：

• 首先，回收器从某个可能是环状垃圾成员的对象出发进行子图追踪，同时减少由内部指针产生的引用计数。该过程遍历的对象会被标记成为灰色；
• 其次，对子图中的所有对象进行检测，如果某一个对象的引用计数不是0，则该对象必然被外面对象引用。此时需要对第一阶段的试验删除操作进行修正，这种修正会将存活的灰色对象重新着色为黑色，同时将其余的灰色对象染成白色；
• 最后，将子图中的白色对象回收；

这里面的过程可以简化为：

• 首先找到可能是环状引用中的一个对象，而后，试着“打破”环。
• 在打破环之后，沿着该对象出发进行遍历，对每一个对象的引用计数都减少1，这个过程实际上消除了内部引用。对于这个步骤的理解容易陷入一个误区，即只减少该对象直接引用对象的引用计数，而不是在整个遍历过程遍历到的对象都需要减少1.对此，我的理解是，引用的消除是一种链式反应。只需要考虑一种情况，就很容易理解。A->B->C->D->A，假定说我们认为A是可能的环状引用对象，那么我们仅仅消除了A与B之间的引用，那么剩下的引用关系还会被保留。但是实际上，它们就只有环状引用的内部引用而已。这也可以归纳为，B因为A而存活下来，而得以存在的引用其他对象的关系也应当被消除。如此递归下去，就很容易看出来，要消除内部引用，仅仅减少直接引用对象的引用计数是不行的。
• 如果在减少了1之后的对象引用计数还不为0，那么说明有环以外的对象引用该对象，那么就需要修正从该对象出发的所有可达对象的引用。这里，是“所有可达对象”而不是直接可达对象的原因和上述一致。
• 最后就是将引用计数为0 的对象删除。

伪代码

这个部分的伪代码如下：

New():
  ref<- allocate()
  if ref=null
    collect() //垃圾回收
    ref <-allocate
    if ref=null
        error "out of memory"
  return ref

addReference(ref):
  if ref!=null
    rc(ref)<-rc(ref)+1 //不可能在环状垃圾中
    color(ref)<-black

deleteReference(ref):
  if ref!=null
    rc(ref)--
    if rc(ref)=0
        release(ref) //垃圾
    else
        candidate(ref) //可能环状引用，这里要注意，目前的判断条件是，减1之后的引用计数不为0，就会被认为可能是环状垃圾

release(ref):
  for each fld in Pointers(ref)
    deleteReference(fld)
  color(ref)<-black
  if not ref in candidate
    free(ref)

candidate(ref):  //将ref标记为备选垃圾，并将其添加到集合中
  if color(ref)!=purple
    color(ref)<-purple
    candidate<- candidate U {ref}

atomic collect():
  markCandidate()
  for each ref in candidate
    scan(ref)
  collectCandidate()

markCandidate():
  for ref in candidate
    if color=purple
      markGrey(ref) //将ref的递归闭包都标记为grey
    else
      remove(candidate, ref)
      if color(ref)=black && rc(ref)=0 //rc为0代表没用被引用，注意前面黑色的定义
        free(ref)

markGrey():
  if color(ref)=grey
    color(ref)<-grey
    for each fld in Pointers(ref)
        child<-*fld
        if child !=null
            rc(child)-- //引用计数减1，消除内部引用，也就是试验删除
            markGrey(child) //递归

scan(ref):
  if color(ref)=grey
      if rc(ref)>0 //说明还有外部引用
        scanBlack(ref) //补偿前面的试验删除
      else
        color(ref)<-white //垃圾
        for each fld in Pointers(ref)
            child<-*fld
            if child!=null
                scan(child) //递归

scanBlack(ref):
  color(ref)<-black
  for each fld in Pointers(ref)
    child<-*fld
    if child!=null
        rc(child)++ //补偿试验删除
        if color(child)!=black
            scanBlack(child)

collectCandidate():
  while not isEmpty(candidate)
    ref<-remove(candidate)
    collectWhite(ref)

collectWhite(ref):
  if color(ref)= white && not ref in candidate
    color(ref)<-black
    for each fld in Pointers(ref)
        child<-*fld
        if child!=null
            collectWhite(child)
    free(ref)

例子

thumb_IMG_0069_1024.jpg

（哈哈，字和图都很丑，不要介意）
这张图里面可以看到一个事情，就是如果一个对象多个内部对象引用，那么最终从这些内部对象出发造成的引用计数减1会最终将该对象的所有内部引用计数都消除，而外部引用计数会被保存下来。

现在还剩下一个问题，就是确定可能的环状引用。在前面的描述中，备选的垃圾对象都是根据引用计数减1之后大于0来判定的。这是一个非常弱的条件。因为，这个条件反过来也可以理解为，引用计数为0的不可能是备选的垃圾——它就是垃圾了。这种判断之下，所有的存活对象都会被判定为备选的垃圾。
但是仔细考虑就会发现这里面有很多对象是不可能是备选垃圾。比如不包含指针的对象，不可能是环状数据结构成员的对象等。这些对象会被染成绿色。经过这种筛选，理论上是可以减少备选对象一个数量级。