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

点击翻译按钮获取中文摘要

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.