A Study on Real-Time Garbage Collection under Multi-threaded Environment

在开发适用于多线程、强实时环境的GC算法时，我们尝试了两种不同的方法。第一种方法是使增量标记-清扫算法具有实时性。我们改进了Java语言实现jexc的垃圾回收器，使得分配的空闲列表的搜索时间在有限的时间内执行，但代价是可能增加碎片。但碎片化在实际应用中不会是问题。我们选择了初始快照算法作为带返回屏障的增量式垃圾收集器，使得即使在堆栈级别增加的情况下，暂停时间也是有界的，达到了单线程应用的实时性要求。第二种方法是将分代垃圾收集器和增量式垃圾收集器相结合。该算法每次调用次收集时都会增量地执行主收集，有效地消除了大收集带来的长时间停顿。使用这种方法，我们实现并评估了粗粒度增量垃圾收集器，它是基于复制的世代收集器和基于跑步机的增量收集器的组合。实验结果在IPSJ第45届SIGPRO会议上公布。实验表明，垃圾回收器虽然不是硬实时的，但具有很高的CPU效率，暂停时间对许多应用来说都是可以接受的。

On developing GC algorithm applicable to multi-threaded, hard real-time environment, we tried two different approaches. The first approach is to make incremental mark-sweep algorithm real-time. We improved the garbage collector of jexc, a Java language implementation, so that search time of free-list for allocation be performed in bounded time, with price of possible increase of fragmentation. But fragmentation will not be a problem in practical application. We chose Snapshot-at-the-Beginning algorithm as incremental garbage collector with Return Barrier, As a result, pause time is bounded even when stack level gets increased, and achieved real-time requirement in single-threaded applications. The second approach is to combine generational garbage collector and incremental garbage collector. This novel algorithm performs major collection incrementally every time minor collection is invoked, effectively removing long pause time caused by major collection. Using this approach, we implemented and evaluated coarse-grained incremental garbage collector which is a combination of copy-based generational collector and Treadmill-based incremental collector. The result was presented in IPSJ 45th SIGPRO.Experiments show that the garbage collector achieves high CPU efficiency, with pause time acceptable for many applications, although the algorithm is not hard real-time.