Garbage Collection"/>
Garbage Collection
5 环形引用计数
续前篇，引用计数技术无法回收环形数据结构，这个由McBeth首先 注意到的问题可能是反对引用计数的最有力的论据[McBeth, 1963]。环形结构在应用层和系统层都是相当常见的。一般来说，当程序员们使用反向指针（back-pointer)、或是为了以自然的方式表达某些领域相关问题时，往往会创建一个环。此外，程序员有时也会在无意中创建环，例如在一个哈希表链（hash table chain)的链接中出现一个回边（back edge) [Boehm, 1994b]。函数式程序设计语言的实现也常常使用环来表示递归[Turner, 1979】。
在标准的引用计数机制下，为了处理环形结构，程序员不得不调整他们的程序设计风格 或是通过删除指针显式地打破环。不幸的是，应该去掉哪个指针并非总是那么明显。手工干涉不仅是一种负担，而且从本质上讲是不安全的。据我们所知，并不存在一种大规模、定义 良好的方法可以让我们避开环。有一种选择是采用混合型的内存管理器，其中大部分单元通过引用计数处理（因为绝大多数单元并不会被共享)，然后再周期性地调用一个标记一清扫收集器来收集环形垃圾。然而，人们还是投入了可观的努力，寻求各种无需借助全局垃圾收集就能回收环形数据的方法。这些算法中，部分是专为函数式程序设计语言所设计的[Friedman and Wise, 1979; Hughes, 1987】，部分只能适用于特定的程序设计手法（programming idioms) [Bobrow, 1980; Wise, 1985],也有一些具有通用性[Christopher, 1984; Lins, 1992a]。剩下的那些常常被人不加评论就直接引用的建议，要么存在错误[Brownbridge，1984],要么在某些病态 的情况下无法终止[Salkild, 1987]。据我们所知，在下面提出的所有解决方案里，没有一个方案被哪个重要的系统所采用。
5.1 函数式程序设计语言
Friedman和Wise观察到这样一个事实：纯函数式程序设计语言中指向环形数据结构的 引用是以一种定义良好的方式创建的，因此可以对其进行特殊处理[Friedman and Wise, 1979J。由于只有递归定义才会产生环，因此只要能够遵守下列限制，我们就能控制指向这类环形环境的引用：
1. 环形结构是作为一个整体同时创建的。
2. 对环的某一子集（不包括它的根）的使用，都是通过复制一个独立的复本而不是通过共享。
3. 指向环的头部、使环闭合的指针会被标记出来。
这些限制保证了整个环可以被当作一个实体来处理。特别地，对环的访问只能通过指向它的根的指针来进行。具体结果就是环中没有哪一部分在其他部分之前创建，也没有哪一部分的生命周期比其他部分更长。当指向环头部的最后一个指针被删除时，就可以回收整个环了。
5.2 Bobrow的技术
更通用的技术依赖于区分环内的指针和环外的指针。那些从环的一个成员指向另一个成 员的环内（internal)引用不需要计数。所有其他指向这个环的指针都是环外（external)引用， 所有的环外引用都被当作指向环的引用，并作为一个整体一起计数。
Bobrow采用这个思路来收集单元构成的组[Bobrow, 1980]。程序员将所有被分配的单元 指派到一个分组中。除此之外，如果程序员声明某个特定的指针为组内指针，那么单元也可能在不同的分组之间迁移。每个分组都有一个引用计数值，并且对于任意一个单元 都可以通过该单元的地址确定它属于哪个分组——单元可以保存它的分组号或是指向分组计数值（group reference count)的指针。每次改写一个指针，都必须检査这个 操作所涉及的3个单元所属的分组。如果创建或者删除了一个分组间的指针，那么相关分组 的引用计数值都必须进行调整。
//Bobrow算法
Update(R,S) =T = *Rgr = group_no(R)if gr != group_no(S)increment_groupRC(S)if gr != group_no(T)decrement_groupRC(T)if groupRC(T) == 0reclaim_group(T)*R = S这一方案只会将分组作为一个整体回收。即使某个存活分组中的一个成员或是一个子图 变得无法到达了，它们也必须等到释放整个分组时才能回收。请注意，系统并不为某一个节点单独进行引用计数。一旦某个分组的引用计数值变为0,那么整个分组就可以回收了。对于分组的布局，一种方案是在内存中专门为每个分组分配一块区域，释放分组时可以通过淸扫对应的区域来释放分组中的各个节点。另一种可选的方案是一个分组内的所有成员通过一个附加的指针域链接起来，这个指针域同时也用来链接自由链表。如果采用这种方案，我们可以仅用一个操作就将整个分组归还给自由链表。
Bobrow算法有一个根本的缺点：它只能处理分组内部的环，而无法处理分组之间的环。Hughes发现,Bobrow的方案在每个分组都包含一个图的强连通分量(SCC，strongly connected component)时工作的最好[Hughes, 1983; Hughes, 1987]。在这种情况下，每个单元可以在变得无法到达的同时立刻释放。对于一般情况，将图划分成SCC昂贵得让人无法接受，但是Hughes提出对于图规约器(graph reducer)来说这也许是可行的，因为图规约(graph reduction)不会随意的修改节点构成的图。图规约总是反复地创建新的图，然后将代表某个可约表达式 (redex)的节点替换成这个图。因为分配新的节点不会影响图的其他部分，所以新的子图可 以采用Taijan的算法独立地划分成SCC(除了那些可以到达图规约的根的节点）。类似的，替换可约表达式只影响它所在的分组。
5.3 弱指针算法
还有几个作者试图通过区分使环闭合的指针和其他指针来处理回收环形数据结构的问 题，他们将前者称为弱指针（weak pointer),后者称为强指针（strong pointer) [Brownbridge, 1985; Salkild, 1987;Pepelsdo/.，1988; Axford, 1990]。这类方法的基础如下所述。堆中每一个存活节点都可以从根出发并通过由强指针构成的指针链到达（强可到达性)。强指针绝对不允许构成环。以强指针为边所构成的图是一个无环图，因此，如果只计算强指针的数量，就可以采用标准引用计数算法来管理这个图。弱指针算法的正确性严重地依赖下面两个不变式：
1. 从根出发，通过强指针链可到达所有存活节点。（SW.1)
2. 强指针不构成环。 （SW.2)
得到最广泛的引用的弱指针算法应该归于Brownbridge。然而不那么广为人知的是，很 不幸，他的算法在某些情况下会过早地回收对象。Salkid修正了这个错误，但同时也引入了在某些病态情况下算法不能终止的问题。我们将尽可能简略地回顾一下Brownbridge-Salkild算法，同时看一看Pepels等人为修正这一算法所做的工作——虽然付出了可观的代价。
Brownbridge的通用算法在每个单元中保存两个引用计数器：一个为强指针计数，一个 为弱指针计数。因为分配新单元不可能产生环，因此指向新单元的指针总是强指针（参见下面算法,其中SRC(R)是单元R的强引用计数值，而strong(newceU)则使得返回的指针成为强指针)。
//Brownbridge的New过程
New() =if free_list == emptyabort "Memory exhausted"newcell = allocate()SRC(R) = 1return strong(newcell)另一方面，复制指针可能导致环的出现，在这种情况下，闭合的那个链接必须是弱的。Salkild修改了 Brownbridge的算法，让所有通过复制得到的指针都成为弱指针。这使得弱指 针不再只是简单地用于闭合环，而是可能在任何地方出现，尽管如此，那两个不变式依然得以保持。此外，这个方法适用于通用的指针操纵系统，而不仅仅是Brownbridge感兴趣的组合机（combinator machines)。下面算法中，WRC(S)是S的弱引用计数值，而weaken(*R)则使得R中的指针成为弱指针
//Salkild的Update过程
Update(R,S) =WRC(S) = WRC(S) + 1delete(*R)*R = Sweaken(*R)删除指针则要微妙得多。对于弱指针，可以直接删除并减小弱引用计数值，不需要额外的动作。根据不变式（SW.1),正在使用的对象可以通过一个强指针链到达，因此它的强引用计数值至少是1。所以，删除一个弱指针不会导致对象被释放；删除一个强指针，只要它不是最后一个，同样不会导致对象被释放。但如果被删除的强指针是指向这个单元的最后一个引用（既包括强引用也包括弱引用），那么就可以安全的把这个单元送回自由链表了。此时，所有从这个单元出发的指针也必须被删除。
//删除强指针和弱指针（未完待续）
delete(T) =if is_weak(t)WRC(T) = WRC(T) - 1elseSRC(T) = SRC(T) - 1if SRC(T) == 0 and WRC(T) == 0for U in Children(T)delete(*U)free(T)else if SRC(T) == 0 and WRC(T) > 0...但是，如果在删除最后一个强指针时，仍有其他弱指针指向这个单元,此时传统的引用计数机制就无能为力了。在这种情况下，已经没有强指针指向这 个单元了（它的强引用计数值为0)。它可能属于某个已经无法从根出发到达的环：但也有可能仍然存在强指针指向这个环中的某个单元，从而环中所有单元仍然是可到达的。在删除从一个单元指向另一个单元T的指针时，为了确定究竟是哪一种情况，系统会对T的后代进行 搜索，试着找到一个处在所有包含了单元T的环之外的指针——这意味着这个单元仍然能够从根出发到达。
首先，所有指向T的指针都被改为强指针。如果这个单元不是垃圾，那么它再一次成为 强可到达的了。然而，这一动作可能会建立强指针构成的环，因此为了识别和消除可能存在的强环，系统遍历从T出发可到达的数据结构（仅通过强指针)，就像査找外部指针时一样。对这一算法的上述描述引出了两个问题：
1. 我们如何确定一个指针是强是弱？
2. 我们如何高效地将所有指向T的弱指针变为强指针？
Brownbridge为这一难题给出了一个优雅的解法。每个指针、每个对象都关联一个强 位（strength-bit)。如果一个指针和它所指向的对象的强位的值相同，那么这个指针就是强指针；若值不同，那么这个指针就是弱指针。同时，强位还被用来确定两个引用计数器中哪个是SRC、哪个是WRC。要将所有指向T的弱指针变强，我们只需要简单地翻转T的强位的值就行了。
现在我们可以回到delete(T)了。如果欲删除的指针是指向单元T的最后一个强指针，但仍然存在其他弱指针指向T，那么delete过程将所有的弱指针变强并且修正T的子图中的指针以保持不变式（SW.1)和（SW.2)。如果SRC(T)仍然保持0,那么整个子图就可以递归地释放了。
//删除强指针和弱指针（续）
...if is_strong(T) and SRC(T) == 1 and WRC(T) > 0invert_strength(T)for U in Children(T)suicide(T,U)if SRC(T) == 0for U in Sons(T)delete(*U)free(T)搜索例程suicide,以T为出发点，沿着强指针遍历，在必要的时候将强指针变弱以保持不变式成立。这里存在一个问题。如果suicide对强指针的遍历将带回它的出发点，那么它就发现了一个由强指针构成的环，必须将环中某个强指针变弱以保持不变式 成立。对于这个角色，惟一可能的候选者就是S,也就是使环闭合的链接。如果存在其他强指针指向S所指向的单元，那么S同样也不必是强指针。在上述两种情况下， suicide将指针变弱，以打破任何之前可能建立起来的环。否则，suicide继续沿着强指针遍历下去。
//suicde过程搜索并打破强环
suicide(Start_node,S) =if is_strong(S)if S == Start_nodeweaken(S)else if SRC(S) > 1weaken(S)else for T in Children(S)Suicide(Start_node,*T)不幸地是，这个过程没有考虑到外部的弱指针。Salkild指出这个疏忽可能导致错误地将环形结构当作垃圾回收。
Salkild建议，如果suicide发现了这样一个单元，一方面存在着指向它的弱指针而另一方面仅有一个指向它的强指针，那么在这种情冼下，翻转这个单元的强位，并且从这个单元重新开始对外部引用和强环的搜索。尽管这个版本的suicide在保持不变式成立、只回收垃圾单元这一方面是正确的，但是现在这个算法在特定的情况下将无法终止。
使用标记机制是防止无限次搜索的一个手段。Pepels等人提供的解法使用了两种不同的 标记：一种防止无限次搜索，另一种确保每次搜索都能终止》他们提出的算法极端复杂。有兴趣的读者可以参阅[Pepels,etal,1988]获取算法的细节和对它正确性的证明。
感谢Peples等人的工作，现在这个算法是正确且可终止的。但是，这个算法是有效的 吗？如果图中并没有环，那么删除指向某个单元的最后一个强指针总是使得这个单元被回收。在这种情况下，由于存在suicide步骤，这个算法的开销是经典引用计数算法的两倍之多。在另外一个极端，我们完全可以想象某些病态的情况：在这些情况下，对于子图中每一个节点，suicide过程的每一个活动都会再一次调用suicide过程。在最坏的情况下，这个算法的复杂度至少是指数级别的。此外，空间开销也相当高：每个单元都需要两个引用计 数域、一个强位和标记位（尽管两种不同的标记可以使用同一位），空间开销超过标准引用计数算法的两倍。
5.4部分标记一清扫算法
最后一类算法采用一种非常不同的方式来解决引用计数回收环形数据结构的问题。它们共通的想法是对数据结构执行3次部分遍历。首先消除被遍历的子图内部的指针对各单元引用计数值的影响，第次遍历结束后，引用计数值就只反映了指向子图中节点的外部指针的数量。第二次遍历恢复那些可以从外部指针到达的节点的计数值，而第 三次通历则将垃圾淸扫回自由链表。
1.Christopher 的算法
这个方法最早是由Christopher发明的[Christopher, 1984],但后来又被几个研究者独立 地重新发现[Vestal, 1987; Martinez etal, 1990; Kennedy, 1991]。Christopher 设计他的算法是为了给像Fortran这样并不拥有垃圾收集机制的语言提供这一功能。在他的算法中，回收垃圾主要依靠引用计数，同时周期性地调用一个追踪式收集器来回收那些引用计数值不为0、但无法从外部到达的节点。因为这个收集器只访问堆中的节点，因此不要求它能够定位计算的 根集合(如果没有关于编译器的知识或是得到编译器的支持，精确地定位根集合是不可能的)。
2.Lins的算法
由Lins和他的同事们所开发的算法也是一种混合算法。绝大多数单元通过引用计数释 放，而环形垃圾则由标记一清扫收集器回收。对于那些只有一个引用的单元，一旦它们的计 数值降为0就通过引用计数机制回收。另一方面，如果指向某个共享节点的指针被删除，那么系统就调用收集器对被删除指针的传递闭包进行标记一淸扫[Martinez cm/.,1990]。但是，如果每次删除一个共享指针都要追踪遍历子图的话，那么处理环形结构的方法将会昂贵得让人无法接受——Martinez等人的算法显然是不切实际的。Lins的延迟环形引用计数算法将被删除的指针保存在一个控制集（controlset)中，以此来推迟这些遍历[Lins, 1992a]。在某些合适的时间点上，收集器可以搜索控制集的全部或部分内容来清扫垃圾。
Lins的算法拦截指针写操作，并将被改写的指针原来指向的目标记录下来，希望它们不会保持存活状态的希望^这一点突出了他的引用计数算法同延迟标记一清扫算法和标准的标记一清扫算法之间的区别。进行垃圾收集时，后者只要遍历存活数据结构，与之相反，Lins的收集器在最好的情况下只需要追踪环形垃圾（尽管它也可能不得不追踪存活数据)。
我们将首先详细考察Lins的延迟算法。Christopher的方案可以视作Lins方案的一个特例：每一个具有非0计数值的单元都在控制集中。除了引用计数域之外，Lins使用一个额外的域来保存单元的颜色。单元有四种颜色：黑色、灰色、白色和紫色2。与一般的直觉相符，存活单元涂成黑色，而垃圾和自由单元涂成白色。标记阶段中所访 问的单元涂成灰色——它们还需要再一次被访问。紫色的单元则可能是孤立的环的成员：它们需要被收集器遍历。
无论何时，如果删除了一个指向共享单元的指针，就把该单元涂成紫色并将其地址放进控制集。将被删除的单元涂成紫色避免了向控制集中加入重复的条目，同时也保证了收集器只会追踪那些被加入控制集并且在此之后并未确认依然存活的单元。控制集策略的启发作用在于，在不得不进行标记一清扫收集之前，将会有更多的迹象表明控制集中的单元究竟是不是垃圾。例如，对于某些单元，可能那时指向它们的最后一个引用已经被删除，在这种情况下它们会被送回自由链表（甚至可能己经被重用）；也可能某个指向它们的指针已经被复制,这样就能够确定它们仍然被使用。不论那种情况，这些单元都不会是紫色的。
Lins算法的Update过程和标准版本之间同样只有一个区别。由于Update过程的两个参数都必然是存活着的，因此应该将它们移出控制集以避免它们被标记一清扫；可以通过将它们涂成黑色（在逻辑上）完成这一工作。如果控制集是采用哈希表或是位图实 现的，那么也可以确实地删除它们在控制集中的条目；如果不是，那么删除它们的开销太大，也就不值得这么做了。如果控制集己经填满，那么必须首先扫描（或是扩展）它从而为新的 引用腾出空间。如果控制集是在堆中采用链接数据结构实现的，那么只有当整个堆耗尽时它才会填满，此时垃圾收集己经无法避免了。
//循环引用计数的Update过程
delete(T) =RC(T) = RC(T) - 1if RC(T) == 0colour(T) = blackfor U in Children(T)delete(*U)free(T)else if colour(T) != purpleif control_set is fullgc_control_set()colour(T) = purplepush(t，control_set)Update(R,S) =RC(S) = RC(S) + 1colour(R) = blackcolour(S) = blackdelete(*R)*R = S我们希望能够避免在控制集中有指向同一单元的多个引用，然而除非采用哈希表或位图实现，否则可能无法高效地做到这一点。假设我们采用一个队列保存控制集，那么并非队列中所有的单元都将是是紫色的。某些单元可能己经被Update过程或是前一次标记一清扫收集重新涂成了黑色：程序仍然在使用这些单元和它们的后代。还有一些单元，可能指向它们的 最后一个指针己经被删除。这样的单元要么在自由链表中（白色)，要么己经被重新分配利用了（黑色)。对指向这几类存活单元的指针执行删除操作将会使它们在控制集内的条目出现重 复。控制集是用来识别潜在的自由空间的。每当从中取出一个单元，都必须测试它的颜色。如果它仍是紫色的，那么也就仍然无法确定是否已经删除了指向一个环的最后一个指针，因此必须执行一次局部的标记一清扫了。
mark_grey过程从它被调用的单元出发，追踪与之相连的整个子图，并且消除由这个子图内部的指针对引用计数值的影响。为了确保算法终止，访问过的单元被标成灰色。
//Lins算法的三阶段标记-清扫
gc_control_set() =S = pop(control_set)if colour(S) == purplemark_grey(S)scan(S)collect_white(S)else if control_set != emptygc_control_set()//mark_grey过程消除内部指针对引用计数值的影响
mark_grey(S) =if colour(S) != greycolour(S) = greyfor T in Children(S)RC(*T) = RC(*T) - 1mark_grey(*T)在灰色的子图中，任何非0的引用计数值只可能来自外部引用。scan过程搜索这些外部引用，并调用scan_black过程将这些外部引用的传递引用闭包涂成黑色。没有直接指向它的外部引用的单元被涂成白色，表明它们可能是垃圾。在scan过程的下一阶段，白色的单元也可能被重新涂成黑色。
//Lins算法的第二阶段
scan(S) =if colour(S) == greyif RC(S) > 0scan_black(S)elsecolour(S) = whitefor T in Children(S)scan(*T)scan_black过程从它被调用的单元出发，将与之相连的子图涂成黑色，同时恢复所访问 的每个单元的引用计数值。恢复后的引用计数值再次包括被mark_grey过程所减去的、处于子图内部的活动指针的数量
//scan_black过程恢复成被sark_grey过程减少的引用计数值
scan_black(S) =colour(S) = blackfor T in Children(S)RC(*T) = RC(*T) + 1if colour(*T) != blackscan_black(*T)最后，colect_white过程回收子图中的白色单元，并将它们归还给自由链表。尽管下面给出的代码是通过沿着指针遍历来实现collect_white过程，但它同样可以通 过线性的扫描整个堆来实现。如果白色单元构成的子图足够大，那么采用线性扫描将比采用递归遍历更快。
//collect_white过程将白色单元清扫入自由列表
collect_white(S) =if colour(S) == whitecolour(S) = blackfor T in Children(S)collect_white(*T)free(S)3.控制集策略
Lins的算法仅在必要的时候才执行标记一淸扫收集，从这个意义上说，它是延迟的。我 们可以很容易地配合不同的策略来管理控制集。最简单的策略是仅仅在自由链表为空、或是存放控制集的结构己经填满的时候运行收集器。除此之外，我们也可以选择在自由链表的大小下降到一定程度的时候扫描队列。我们还可以选择在出现某种迹象表明堆内存已经过于破碎的时候进行收集。我们可以把控制集当作一个后进先出（LIFO)的栈来处理，也可以当作一个先进先出（FIFO)的队列。实现控制集的时候，可以采用堆分配的链表、位图或是固定大小的数组。每次收集我们可以处理整个控制集，也可以仅仅处理一部分。各种不同的管理策略的效果（对于一个普通的程序）可以参见[Lins and Vasques, 1991]。他们发现，对于足够大的控制集，scan_black过程始终不会运行。此时垃圾收集器仅仅处理环形垃圾，因此不 会出现对垃圾收集器不必要的调用。
像分代式垃圾收集一样，Lins的方法在副作用（side_effect)相对稀少的情况下（例如，采用函数式风格编写的程序）工作的最好。同时，它的成功还依赖于这样两个假设：第一，绝大多数节点都是独享的，可以在不借助垃圾收集的情况下回收；第二，收集器所遍历的子图足够小，从而使得垃圾收集时的停顿足够小。Lins算法的缺点在于它追踪垃圾，而标准的 标记一清扫算法只追踪存活单元。不幸的是，函数式程序设计语言的实现会产生大量的垃圾：堆中超过80%的空间被垃圾占据是常见的情况。另外，环形引用计数和其他方法之间并未进行过彻底的比较。
4.再谈Christopher算法
尽管可以将Christopher算法视作Lins算法的一个特例（将整个堆当作控制集)，它本身仍然有让人感兴趣的地方。首先，它被设计成能在没有任何编译器支持的情况下提供自动内存管理机制。其次，由于整个堆的状态无法确知，Christopher采取了对整个堆进行3次线性清扫的方式，而不是对每个被删除的指针的传递闭包进行3次追踪的方式。线性清扫的开销 要比对图进行追踪来得低。同时，它的行为更可预测，因此线性清扫的虚存性能也要比追踪强。与扫描相比，线性淸扫所减少的开销可能超过清扫整个堆4次的开销——这取决于所要处理的数据结构。此外，Christopher算法没有使用任何额外空间这一点也让人感兴趣：尽管恢复计数值的过程是递归的，但是恢复现场所用的栈是通过对象的引用计数域串连起来的。
和Lins算法一样，Chirstopher算法分3个阶段运行。在标记一淸扫之前，首先对整个堆 进行一次线性清扫,消除所有由堆内部的指针对引用计数值造成的影响。这一遍清扫类似于Lins算法中mark_grey进行的遍历。此时，只有那些被不在堆中的指针直接指向的对象才有非0的计数值。接着，这些单元和它们的后代在第二遍清扫中被标记：它们的引用计数域被写入一个特殊的值。这一遍淸扫类似于Lins算法中的scan 。 最后，收集器重新扫描堆，将所有引用计数值为0的对象放进自由链表，并恢复所有被标记的对象的引用计数值。
更多推荐
Garbage Collection
发布评论