云风的 BLOG: 基于并行处理的垃圾回收方法

最近在做的一个虚拟机是基于垃圾回收(garbage collection)的，采用的是标记整理算法。这种算法的好处在于不需要太多额外的内存，而且可以将内存中的 garbage 完全压缩掉。至于长期占用的内存空间，会被压到内存块的底部，整理时无须移动。

对于需要长期稳定运行的服务器程序，在 32bit 操作系统下，受限于有限的地址空间， gc 技术是根本解决内存碎片问题的最佳通用方案。

我计划在服务器程序中，全部程序逻辑都放在虚拟机内运行。由于和 client 程序不同，不用太考虑物理内存的占用，所以计划在服务启动的时候就预设 1~2G 的内存块供虚拟机使用。在这个内存块耗尽之前，所以涉及内存分配的操作都会相当的快了。但是一旦发生 gc ，光是扫描一遍内存，都是非常耗时的。所以我不得不考虑解决方案。

很自然的，我想到了并行技术。如果可以在 gc 的过程，不太影响逻辑线程的运行，那么即时 gc 的过程慢一点，我们也是可以接受的。而且如今硬件多核技术的发展，如何充分利用多个 CPU 并行处理，将是未来软件设计的重点方向。

我暂时想到的方案是这样的：

假设对一个 2G 的内存块做 gc 的时间是 10s 。(只是一个估算，没有实测。我想按今天的内存总线的吞吐量，10秒内做完应该不是难事）那么 10s 内，软件产生的新的内存分配的需求应该不是特别的大，比如 8M ，就可以满足其要求。那么我们就预留这么一小块内存做备用。

另外，程序运行堆栈是永远不需要做内存整理的，所以我们也可以把它刨开。剩下的就是一个超过 1G 容量的巨大的内存堆。实际上，在 gc 过程中，能对这个堆做的数据修改也是极少的操作。假如我们可以在 gc 发生的时候，将内存堆以 copy-on-write 的方式共享给另一个进程。unix 下可以直接 fork 子进程，windows 下可以 share memory。在共享的那一刻，我们保证这是一个原子操作。然后， gc 进程对堆的整理操作不再影响逻辑进程。而逻辑进程所以产生的内存分配请求，都在备用的小内存堆中完成。而对正在 gc 的堆的任何写操作，都 log 在备用堆上。

一旦 gc 进程工作完毕，可以把整理过的内存堆切换回逻辑进程。逻辑进程则停止手头的工作，将 log 过的操作逐一提交。(这里，gc进程应该给出做内存整理时产生的新旧地址对照表，需要对 log 的操作信息做一个先期处理) 然后，逻辑进程将备用堆中的信息移动进主内存堆。这些操作虽然繁琐，但是数据量远远小于主内存堆，所以可以在极快的时间内完成。

maillist 上的相关讨论：
<a href="http://codingnow.com/pipermail/cpp/2005-December/000910.html">http://codingnow.com/pipermail/cpp/2005-December/000910.html</a>

Comments

我这个方法的作用是, 在 gc 过程中，逻辑进程可以正常的工作，直 gc 结束, 所以即使慢很多也没关系。这个是为了减少 gc 的停滞。 1 G 内存，即使copy一遍都不只 1000 ms（当然我用的整理算法，不需要整个的copy) 。所以 gc 发生时的停顿感是很可怕的，除非分代 gc, 否则我认为我这个方案是很有效的。

Posted by: Cloud | (6) January 21, 2006 07:24 PM

觉得即便有较大的内存和多核，这个算法可能也会存在问题。其实你的算法更像一个节点复制的算法，只是使用了操作系统的机制进行了复制操作，但无法做缩并，所以分配内存的效率应该不及节点复制的算法（这是节点复制算法最有价值的优点），二者理论上内存使用量是一样的，都是最大工作集的两倍，那么你得算好似乎是浪费了空间，确没得到该得到的好处。另外，因为要对一个很大的堆中（1g？）中的存活集进行复制，势必会触及很多内存页，会使cache命中率下降到非常低的水平，如果一旦触及虚存，性能下降会更明显，最大GC时间可能会很长。所谓并行垃圾收集是为了使最差情况下的GC时间尽量的小，而不是平均GC时间，而你的算法在追求什么效果？我猜测你的算法性能不如分代是垃圾收集，甚至最差情况可能不如简单的Mark-Sweap，更没有必要和最差响应时间是6ms以内的基于并行的实时垃圾收集器进行比较，不过你的算法实现起来应该比它们都简单多了。因为要实现一个ECMAScript的运行环境，我看过一些垃圾收集的书和paper，算是了解一些，以上都是根据这些在理论上的推测，还是以实际性能统计的数据为准吧，理论代替不了实际，甚至背道而驰。如果你有什么性能测试的数据，请贴出来共享。。。

Posted by: mouse | (5) January 21, 2006 10:22 AM

这不是一个C++的解决方案, 需要统一的对象模型，还需要有一个虚拟机。即，所有进程中的对象都符合同一对象模型，我的解决方案是实现了类似 .net 或者 javavm 这样的虚拟机。这样就没有 mark 位的问题。也可以在 gc 发生和没发生时期有不同的操作对象的行为。 mark 位放跟对象放在一起即可。标记所有对象的过程会发生大量内存复制，但这还是空间换时间的方法，过大的内存堆上垃圾收集的问题主要集中在 gc 发生时停顿时间太长。这个方案可以最大限度减少这个延迟，而代码是需要配备更多的内存。增加物理内存是件很廉价的事情，这又并不浪费逻辑进程的内存地址空间。在多核的机器上，gc 进程可以跟逻辑进程并行，所以 gc 进程即使慢一些也没有关系。至于逻辑进程无须知道对象是否垃圾，因为 gc 发生后，它就不准在原有堆上分配任何内存了，所以不会在原有堆产生新的垃圾。会发生停顿的时候在于 gc 进程整理完主堆后，把整理过程中逻辑进程发生的操作合并的阶段。需要合并的数据量取决于整理过程的时间，这个时间不会太长，就算长达一分钟，一分钟内产生的新的内存分配操作也不会太多。

Posted by: Cloud | (4) January 20, 2006 02:11 PM

对这个设计的空间和世间效率很怀疑。不知你的Mark位放在哪？如果放在对象头里，那么所有存活对象都会被复制，且似乎也无法在逻辑进程中知道哪些是垃圾那些不是。如果使用bitmap mark位，那么bitmap又放在哪呢？并行垃圾收集十个复杂的问题，比较流行的是由三色抽象而来的几个算法，集体就不多说了，建议你看看人民邮电出版社出的《垃圾收集》（ISBN 7-115-12070-6）中的第8章，作者Richard Jones应该是在垃圾收集算法领域涉猎很广的学者。事情往往没有想象得那么简单，垃圾收集要考虑的问题很多。

Posted by: mouse | (3) January 20, 2006 10:23 AM

呵呵. gc 在内存使用问题上，更多的是解决地址空间有限的问题，而非物理内存不足的问题。

Posted by: Cloud | (2) December 11, 2005 05:15 PM

我认为使用C++来实现garbage collection并不是一件好事情，最主要是语言特性上，Ｃ＋＋一直在强调其大力使用exception handle来控制程序运行的好处．我记得在2000年时，国内有名的在线棋牌游戏运营商就遇过这个问题．在使用ＨＰ服务器时，硬件内存非常贵，只能想法在内存上想办法．从我了解的信息看，最后很好的解决了问题之一，使用Ｃ＋＋实现了消息对队，除了ＩＯ读写，好像其它技术都没有用上．并且可能并没有使用模板技术．时至今日，我使用Ｃ＋＋也有3年的时间，我想云风可以考虑多接触多方的技术公司进行交流．也许会有一些更新的资讯．

Posted by: xds2000 | (1) December 11, 2005 10:42 AM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

基于并行处理的垃圾回收方法

Comments

Post a comment