The system considered in this thesis integrates two subsystems that traditionally handle memory allocation and reclamation differently. On the one hand, the Scheme interpreter typically uses a garbage collector for the reclamation of unused memory space. On the other hand, real-time systems avoid dynamic memory management since it makes the behavior of the system hard to predict. We face three options for the memory management: an implicit management (garbage collection), an explicit management (hand-coded), or a hybrid management (partly explicit, partly implicit.)

Choosing implicit memory management places a garbage collector face to face to a real-time task. It will be difficult, a priori, to predict the system behavior and guarantee hard real-time conditions. However, if we choose to use explicit management we will run into problems to realize the Scheme interpreter. In such a dynamic, interpreted environment the relationships between the objects are complex and deciding when storage space can be released is tricky and error-prone. It may also necessitate a complete rewrite of existing interpreters to adjust to this solution. Furthermore, as shown by Nilsen [NG95] traditional allocation algorithms have bad worst case delay times, which does not make them a suitable option for hard real-time. If we choose a hybrid system the interpreter would rely on a garbage collector to clean the heap; the real-time task would manage its heap explicitly. It might be an intermediate solution but does introduce new problems. Both heaps must cooperate to resolve references across the boundaries of the two heaps. This coordination might be more unpredictable and take more time than an optimized garbage collector. Furthermore, the system looses flexibility if the objects in the environment cannot be fully shared between the two tasks.

 

Figure 7.3: Garbage collection during the synthesis will block the synthesis thread.

Since we have chosen to develop in the Java language we will rely on its implicit memory management. We will examine the influence of the garbage collector by studying the possible cases of interaction between the two subsystems. Consider figure 7.3, for a start. The synthesis process calls an object; the object in its turn allocates storage space in the heap. The heap, however, does not have enough space available to satisfy the request and is forced to scan the heap for unused memory and collect the garbage. This collection will most probably take a fair amount time and the synthesis process will not be able to calculate its output value in time. The synthesis thread will not be able to deliver the output in time to the audio device and will no longer be synchronized. This situation must absolutely be avoided. Therefore, we impose the constraint that the synthesis processes and all the objects they call do not allocate new storage space during the synthesis. All the methods called during the synthesis should only perform calculations or assign new values. They should not allocate storage space. This is not necessarily a big constraint: it is the design any developer of a signal processing technique would choose to optimize the algorithm. Obviously, the objects can allocate storage space, but only when they are called in the event or user thread. If this constraint is taken into consideration, the synthesis thread will never directly rely on the services offered by the garbage collector.

 

Figure 7.4: Garbage collection during the event handling does not necessarily block the synthesis, if the collector is concurrent.

A seemingly disastrous situation might occur as shown in figure 7.4. A program, called from within the event thread, requires storage space from the heap. The heap does not have enough space available and performs a garbage collection. Again, this collection might take a lot of time. Sure enough, the synthesis thread will need to acquire the CPU before the collector finishes. This situation does not raise any problems, if the garbage collector can work concurrently to the other threads. In that case the thread allocating storage space is suspended; all other threads that do not allocate memory are not suspended. When the synthesis thread needs to come into play it simply suspends the garbage collector since the latter has a lower priority. This means that the garbage collection need not interrupt the synthesis in this case neither.

 

Figure 7.5: Garbage collection in a critical region may provoke a priority inversion; the synthesis thread will be delayed.

Problems can arise, however, if an object allocates storage space from within a critical zone (Figure 7.5). In this case a priority inversion might occur, and when the synthesis thread tries to access the object it will find itself waiting till the end of the garbage collection. To avoid this problem, the objects on which synthesis processes rely should not allocate storage space inside a critical region.

So far we looked at the interaction between the components of the system. However, the synthesizer itself must be able to keep its worst case delay bounded. We will consider this in the next section.