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

 收藏

最近在做的一个虚拟机是基于垃圾回收(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>

回复