39/2009 : Nonblocking Real-Time Garbage Collection

RR Number

39/2009

Conference

ACM Transactions on Embedded Computing Systems

Author(s)

Martin Schoeberl, Wolfgang Puffitsch

Abstract

A real-time garbage collector has to fulfill two basic properties: ensure that programs with bounded allocation rates do not run out of memory and provide short blocking times. Even for incremental garbage collectors, two major sources of blocking exist, namely root scanning and heap compaction. Finding root nodes of an object graph is an integral part of tracing garbage collectors and cannot be circumvented. Heap compaction is necessary to avoid probably unbounded heap fragmentation, which in turn would lead to unacceptably high memory consumption. In this paper, we propose solutions to both issues. Thread stacks are local to a thread, and root scanning therefore only needs to be atomic with respect to the thread whose stack is scanned. This fact can be utilized by either blocking only the thread whose stack is scanned, or by delegating the responsibility for root scanning to the application threads. The latter solution eliminates blocking due to root scanning completely. The impact of this solution on the execution time of a garbage collector is shown for two different variants of such a root scanning algorithm. During heap compaction, objects are copied. Copying is usually performed atomically to avoid interference with application threads, which could render the state of an object inconsistent. Copying of large objects and especially large arrays introduces long blocking times that are unacceptable for real-time systems. In this paper an interruptible copy unit is presented that implements non-blocking object copy. The unit can be interrupted after a single word move. We evaluate a real-time garbage collector that uses the proposed techniques on a Java processor. With this garbage collector, it is possible to run high priority hard real-time tasks at 10~kHz parallel to the garbage collection task on a 100~MHz system.

Bibtex

@ARTICLE{jop:tecs:nbgc,
  author = {Martin Schoeberl and Wolfgang Puffitsch},
  title = {Nonblocking Real-Time Garbage Collection},
  journal = {ACM Transactions on Embedded Computing Systems},
  year = {2010},
  volume = {10},
  number = {1},
  pages = {6:1--6:28},
  address = {New York, NY, USA},
  issn = {1539-9087},
  publisher = {ACM}
}

Download

Get nbgc.pdf - Adobe PDF-format, (292.78 KB; posted at April 27 2009; )