What deterministic garbage collection algorithms are out there?

Question

What deterministic garbage collection algorithms are out there?

By deterministic I vaguely mean that can be used in critical real-time software like aerospace flight software. Garbage collectors (and dynamic memory allocation for that matter) are big no-no's in flight software because they are considered non-deterministic. However, I know there's ongoing research on this, so I wonder is this problem has been solved by now.

I'm also including in the question any garbage collection algorithms that put restrictions on how they're used.

Answer 1

I know azul systems has a jvm whose GC is hardware assisted. It can also run concurrently and collect massive amounts of data pretty fast.

Not sure how deterministic it is though.

Answer 2

Metronome GC and BEA JRockit are two deterministic GC implementations that I'm aware of (both for Java).

Answer 3

To me, 100% real-time Java is still very much a hit-and-miss technology, but I don't claim to be an expert.

I'd recommend reading up on these articles - Cliff Click blog. He's the architect of Azul, has pretty much coded all of the standard 1.5 Java concurrent classes etc... FYI, Azul is designed for systems which require very large heap sizes, rather than just standard RT requirements.

Answer 4

You may have some luck with the following PhD thesis CMU-CS-01-174 - Scalable Real-time Parallel Garbage Collection for Symmetric Multiprocessors.

Answer 5

I know I might get a lot of down-votes for this reply, but if you are already trying to avoid dynamic memory in the first place, because you said it's a no-no, why do you use GC at all? I'd never use GC in a real-time system where predictable runtime speed is the major concern. I'd avoid dynamic memory wherever possible, thus there are very, very little dynamic objects to start with and then I'd handle the very few dynamic allocations I have manually, so I have 100% control when something is released and where it is released. After all not just GC is not deterministic, free() is as little deterministic as malloc() is. Nobody says that a free() call just has to mark the memory as free. It might as well try to combine smaller free memory blocks surrounding the free'd one to a big one and this behavior is not deterministic, nor is the runtime for it (sometimes free won't do that and malloc will do that instead on next allocation, but nowhere is written that free mustn't do that).

In a critical realtime system, you might even replace the system standard malloc()/free() with a different implementation, maybe even writing your own one (it's not as hard as it sounds! I've done that before just for the fun of it) that works most deterministic. For me GC is a plain convenience thingy, it is to get programmers away from focusing on sophisticated malloc()/free() planing and instead having the system deal with this automatically. It helps doing rapid software development and saves hours of debugging working finding and fixing memory leaks. But just like I'd never use GC within an operating system kernel, I'd never use it within a critical realtime application either.

If I need a more sophisticated memory handling, I'd maybe write my own malloc()/free() that works as desired (and most deterministic) and write my own reference counting model on top of it. Reference counting is still manual memory management, but much more comfortable than just using malloc()/free(). It is not ultra fast, but deterministic (at least increasing/decreasing the ref counter is deterministic in speed) and unless you may have circular references, it will catch all dead memory if you follow a retain/release strategy throughout your application. The only non deterministic part about is that you won't know if calling release will just decrease the ref counter or really free the object (depending if the ref count goes to zero or not), but you could delay the actual free by offering a function to say "releaseWithoutFreeing", which decreases the ref counter by one, but even if it reaches zero, it won't free() the object yet. Your malloc()/free() implementation can have a function "findDeadObjects" that searches for all objects with a retain counter of zero, that have not yet been released and free them (at a later point, when you are in a less critical part of your code that has more time for such kind of tasks). Since this is also not deterministic, you could limit the amount of time it may use for this like "findDeadObjectsForUpTo(ms)", and ms is the amount of milliseconds it may use for finding and freeing them, coming back as soon as this time quantum has been used, so you won't spent too much time in this task.

Answer 6

It's not GC, but there are simple O(1) fixed sized block allocation/free schemes you can use for simple usage. For example, you can use a free list of fixed sized blocks.

struct Block {
   Block *next;
}

Block *free_list = NULL; /* you will need to populate this at start, an 
                          * easy way is to just call free on each block you 
                          * want to add */

void release(void *p) {
    if(p != NULL) {
        struct Block *b_ptr = (struct Block *)p;
        b_ptr->next = free_list;
        free_list = b_ptr;
    }
}

void *acquire() {
    void *ret = (void *)free_list;
    if(free_list != NULL) {
        free_list = free_list->next;
    }
    return ret;
}

/* call this before you use acquire/free */
void init() {
    /* example of an allocator supporting 100 blocks each 32-bytes big */
    static const int blocks = 100;
    static const int size = 32;
    static unsigned char mem[blocks * size];
    int i;
    for(i = 0; i < blocks; ++i) {
        free(&mem[i * size]);
    }
}

If you plan accordingly, you could limit your design to only a few specific sizes for dynamic allocation and have a free_list for each potential size. If you are using c++, you can implement something simple like scoped_ptr (for each size, i'd use a template param) to get simpler yet still O(1) memory management.

The only real caveat, is that you will have no protection from double frees or even accidentally passing a ptr to release which didn't come from acquire.

Answer 7

Real-time means a guaranteed upper bound on response time. This means an upper bound on the instructions that you can execute until you deliver the result. This also puts an upper limit on the amount of data you can touch. If you don't know how much memory you're going to need, it is extremely likely that you'll have a computation for which you cannot give an upper limit of its execution time. Otoh, if you know the upper bound of your computation, you also know how much memory gets touched by it (unless you don't really know what your software does). So, the amount of knowledge you have about your code obviates the need for a GC.

There are features, like regions in RT-Java, that allow for expressiveness beyond local and global (static) variables. But they will not relieve you from your obligation to manage the memory you allocate, because otherwise you cannot guarantee that the next upcoming allocation will not fail because of insufficient memory resources.

Admittedly: I've gotten somewhat suspicious about things that call themselves "realtime garbage collectors". Of course, any GC is real time if you assume that every allocation runs a full collection (which still doesn't guarantee that it will succeed afterwards, because all memory blocks might found to be reachable). But for any GC that promises a lower time bound on allocation, consider its performance on the following example code:

// assume that on `Link` object needs k bytes:
class Link {
    Link next = null;
    /* further fields */
    static Link head = null;
}

public static void main (String args) {
    // assume we have N bytes free now
    // set n := floor (N/k), assume that n > 1

    for (int i = 0; i < n; i ++) {
        Link tmp = new Link ();
        tmp.next = Link.head;
        Link.head = tmp;
    } 
    // (1)
    Link.head = Link.head.next; // (2)
    Link tmp = new Link ();  // (3)
}

• At point (1), we have less than k bytes free (allocation of another Link object would fail), and all Link objects allocated so far are reachable starting from the Link.static Link head field.

• At point (2),

  • (a) what used to be the first entry in the list is now not reachable, but
  • (b) it is still allocated, as far as the memory management part is concerned.

• At point (3), the allocation should succeed because of (2a) - we can use what used to be the first link - but, because of (2b), we must start the GC, which will end up traversing n-1 objects, hence have a running time of O(N).

So, yes, it's a contrived example. But a GC that claims to have a bound on allocation should be able to master this example as well.

Answer 8

Sun has extensively documented their real-time garbage collector, and provided benchmarks you can run for yourself here. Others mentioned Metronome, which is the other major production-grade RTGC algorithm. Many other vendors of RT JVMs have their own implementations -- see my list of vendors over here and most of them provide extensive documentation.

If your interest is particularly in avionics/flight software, I suggest you take a look at aicas, an RTSJ vendor who specifically markets to the avionics industry. Dr. Siebert's (aicas CEO) home page lists some academic publications that go into great detail about PERC's GC implementation.