该文章是《垃圾回收算法手册》一书的阅读笔记。详情请参阅原书。
背景
垃圾回收算法中的引用计数算法无法回收环状引用数据结构，包括自引用结构。这会造成一个问题，即如果这个整体在程序中是不可达的时候，但是回收器依然无法回收这部分内存——它们的引用计数将永远不会为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)
例子
（哈哈，字和图都很丑，不要介意）
这张图里面可以看到一个事情，就是如果一个对象多个内部对象引用，那么最终从这些内部对象出发造成的引用计数减1会最终将该对象的所有内部引用计数都消除，而外部引用计数会被保存下来。
现在还剩下一个问题，就是确定可能的环状引用。在前面的描述中，备选的垃圾对象都是根据引用计数减1之后大于0来判定的。这是一个非常弱的条件。因为，这个条件反过来也可以理解为，引用计数为0的不可能是备选的垃圾——它就是垃圾了。这种判断之下，所有的存活对象都会被判定为备选的垃圾。
但是仔细考虑就会发现这里面有很多对象是不可能是备选垃圾。比如不包含指针的对象，不可能是环状数据结构成员的对象等。这些对象会被染成绿色。经过这种筛选，理论上是可以减少备选对象一个数量级。
