Go up. Go to department page.

Scheduling Real-Time Garbage Collection


R. Henriksson

Licentiate thesis, Lund Institute of Technology, Lund University, Lund, Sweden, 1996.


Since computer software represents an increasing share of the complexity of systems for automatic control and other types of critical equipment, the issue of software quality becomes more and more important. One factor that influences the complexity, especially with the introduction of object-oriented implementation techniques, is how memory management is handled. Systems for automatic memory management, or garbage collection, can decrease the risk of software errors and shorten development time.

There exist garbage collection techniques suitable for interactive and soft real-time systems, but few algorithms are suitable for systems with hard real-time requirements, such as control systems (embedded systems). This thesis is focused on the scheduling problem, i.e. how the work of a garbage collector should be scheduled in order to disturb the application program as little as possible. It concentrates especially on control systems, i.e. embedded systems controlling some external physical process. In such systems, the hard real-time requirements are often isolated to a few high-priority software processes which execute periodically. A scheduling strategy is presented that employs this property to ensure that no garbage collection work is performed during the execution of the critical processes, thus not causing any disturbance.

The thesis shows how to adapt a standard incremental garbage collection algorithm to schedule its work according to the presented strategy. It is also discussed how to implement such a system by integrating the garbage collector with the process scheduler of the real-time kernel. Traditionally, garbage collection and process scheduling have been viewed as two separate issues.

The scheduling algorithm has been implemented in an actual real-time environment in order to show that the strategy is feasible in practice.