嵌入式系统设计中的存储碎片收集策略

关联存储碎片收集

关联存储碎片收集(generational garbage collection)的工作方式如下：许多存储器区域被指定为存放新产生对象的特殊场所。当这些对象存在的时间变长(存活的时间变长，在存储碎片收集期间依然存活)，就会将它们从这一特殊区域转移出去并且放到主存储区域。某些关联存储碎片收集算法甚至还区分几个"较早的"代。.NET平台以及C＃语言的存储碎片收集器可以区分三代，所以可以将第一代与存放新产生对象的区域分别开来。为了简单起见，介绍仅有两代的情况，多代的算法与此相似，只是管理操作方面的运算更多。


关联存储碎片收集仅仅考虑新产生对象存储区域，从本质上来说，它假定所有驻留在非新产生对象存储区域的对象仍然在被引用(也就是说它们仍然是有效的)。要做到这一点，就需要有一种方法来计算所有索引了新产生对象的集合。为了加速这一过程，需要维护一个独立的"老对象到新产生对象的索引"表，这一索引表列出了所有非新产生对象对于新产生对象的索引。这一表格极大地加速了新产生对象存储区域对象的检查，与此同时非新产生对象则根本不需要检查。


也许有人会关心：开始的时候如何追踪非新产生对象对新产生对象的索引？答案在于一种称为"写屏蔽"技术。写屏蔽监视所有的存储操作，并且不断查询"正在存储的对象索引了非新产生的对象吗"？如果是这样，接下来就会询问是否将正在被写的旧值以及/或正在被存储的新值进行了索引，并产生了新的对象。此外，还要对这一组老对象到新产生对象的索引进行相关的刷新。请注意：通过比较索引的地址与新产生对象存储区域的边界地址，存储碎片收集器可以迅速地判定一个索引是否指向了一个新产生的对象。


典型应用的实际测试表明：老对象到新产生对象的索引集合通常都比较小。测试也证实关联存储碎片收集可以线性地分配空间收集工作。也就是说，关联存储碎片收集在大约八分之一全部存储碎片收集的时间里可以收集到最新的第八个存储器空间。这将释放比八分之一存储碎片要多得多的空间。

图3显示了存储碎片收集之前的一种情况。新产生对象存储空间包含三个对象：C、D和E。对象C包含到对象E的索引。主要存储器区域包含两个对象：A和B。对象A包含到对象C的索引。这一个索引被记录在"老对象到新产生对象"的集合中。根索引集合包含到A和E的索引。


这个实例显示了对新产生对象存储区域同时进行存储碎片收集和去碎片的情况。同时也显示了对新产生对象存储区域进行存储碎片收集并且直接收集到主存储空间中的情况。这样可以提升新产生对象存储区域中的所有对象。也就是说，这些对象下一轮的关联存储碎片收集过程中将不再被检查。如果算法支持几代关联存储碎片收集过程，那么就需要通过存储器去碎片技术整合到一个区域并且进行更高一代关联存储碎片收集。


在关联存储碎片收集过程中，根到A的索引将被忽略，但是根到E的索引将把E标示为有效，所以在目标区域中会创建E的一个副本，并且刷新C到E的索引。


E不包括任何索引，因而对E不作任何处理。老对象到新产生对象的集合也需要检查，在检查中会发现A到C的索引。C会被标示为有效，所以在目标区域中就会创建C的一个副本，并且刷新从A到C的索引。对象C包含一个到E的索引。由于E已经被复制，C中的索引被刷新，但是无需再复制E。而无法访问的对象D则不会被复制，因此该区域重新整理时D就会被删除。这样就会产生图4中显示出的结果。

增量式存储碎片收集

增量式存储碎片收集(incremental garbage collection)比关联存储碎片收集更加复杂。尽管现在有几种不同的实现方式都声称是增量式存储碎片收集，但事实上这是多年来悬而未决的问题。下面描述增量式存储碎片收集的一种特定的实现方式。

考虑在"来源"和"目的"区域上运行的一个去碎片存储碎片收集器(关联型或者非关联型)。随着存储碎片收集的进行，"来源"区域中的全部有效对象都会移到"目的"区域。复制过程由索引遍历来驱动。每一个索引都采取以下的处理方式：如果目标对象还没有被复制，那么就复制该目标对象，并且将其索引添加到要处理的索引列表中。最初的索引都要重新改写以反映对象的新位置，并且指向目标对象新位置的一个前向地址会保留在那个对象最初的"来源位置"处。当所有索引的对象都已经被复制，并且所有的索引都已经重新改写，那么存储碎片收集(那一个区域的)就结束，并且"来源"区域可以重新使用。


增量式存储碎片收集通常采取突发、短时运行方式。在这些突发的运行之间，允许用户线程运行，这样就可以减少等待时间。当然，在用户线程执行之前，存储碎片收集器并不能够保证对一个对象的所有索引都进行合适的重新改写。那么当索引仅仅修正了一半的时候，程序怎样才能准确无误地继续运行？答案同样也在于写屏蔽。


当程序试图对存储器进行写操作时，系统会进行检查，以确保被写入的对象是否正在被存储碎片收集器移走。如果是这样，那么写操作就会在旧的位置和新的位置同时进行。这样的技术避免了"读屏蔽"的必要性，同时也保证借助于没有被修正的索引，所作的修改不会被丢失。


聪明的读者会注意到：对象索引的集合在突发的存储碎片收集之间可能会改变。去掉索引应该没有什么坏处。存储碎片收集器已经标示出：一个对象是有效对象移去之后这个对象最后的索引，那么该对象肯定可以在下一次的存储碎片收集过程中收集起来。


然而必须小心处理索引的增加。存储碎片收集进程"正在处理"的过程中，每一次存储一个新的索引时，当存储碎片收集继续执行时，必须将该索引添加到需要处理的索引列表中。同样写屏蔽也要确保这一过程将工作正常。


在增量式存储碎片收集过程中，关于新对象的创建也有其它巧妙的细节。这些对象必须小心地分配在一个独立的区域中，存储碎片收集结束后，该区域将成为新产生对象的存储区域。如果能让这些新对象立即参与当前的存储碎片收集过程，那么它们就可以迅速升级。而采用其它方法，它们则会错过最开始的机会，并且没有机会存储在新产生对象的存储空间中，并通过关联存储碎片收集器来进行快速收集。