Research On Real-Time Algorithms Of Garbage Collection For Embedded Real-Time System

With complexity of embedded real-time systems grows rapidly, memorymanagement is more and more important. Automatic storage management, or garbagecollection(i.e. GC) can avoid producing memory leaks and dangling pointers andmemory fragment compared with manual memory management. However, traditionalgarbage collector known as 'stop-the-world' GC needs all mutators stop running when itworks. Obviously it is not compatible with real-time programming. Thus, research ofreal-time garbage collection and applying it into development of software of large-scaleembedded system can enhance the efficiency. It is important to shorten developmentcycle and enhance the safety and reliability of embedded real-time systems.This dissertation introduces function of garbage collection and history of real-timegarbage collection. Some typical algorithms and strategies of real-time garbagecollection are introduced. Since in embedded systems resources such as CPU andmemory are limited, the dissertation emphasizes on reducing memory requirement ofsystem on the condition that real-time tasks meet their deadlines. The maincontributions of this dissertation are as follows:1. Development of real-time garbage collection and distributed garbage collection aresummarized. Since in embedded real-time systems resources are limited, a dynamicgarbage collection is proposed. The proposed GC can process memory space of eachtask dynamically based on the variance of amount of live objects, thus reducememory requirement under the condition that mutators meets their deadlines.Furthermore, if GC defers processing active tasks until the states of tasks becomeinactive, more time slice of aperiodic server can be saved for aperiodic tasks andflexibility of system is enhanced.2. Scheduling strategy is proposed that mutators and GC are scheduled under EDF. It isproved by memory analysis and simulation that if tasks are limited, EDF scheduledsystems can be more portable and system memory requirement can be furtherreduced compared with other scheduling strategies based on RM algorithm underthe condition that mutators meet their deadlines. 3. Hybrid garbage collections are researched systematically and an algorithm ofincremental collecting cyclic garbage is proposed. Garbage collection can collectpartial cyclic garbage during the GC cycle for reuse and therefore reduce memoryrequirement. A hybrid garbage collection based on timestamp is also proposed. Thisalgorithm also can partly collect cyclic garbage when deadlines of real-time tasksare guaranteed. Furthermore, the proposed GC fits for large-scale system comparedwith hybrid GC based on mark-sweep algorithm since execution time of GC isunconcerned with objects of system.4. Some typical distributed garbage collections are researched and a real-timedistributed garbage collection based on verification of critical reference is proposed.The algorithm can detect and reclaim cyclic distributed garbage at the shortest timeto avoid storage spaces are exhausted, thus it is soft real-time. Though the algorithmrequires more memory space, it is fault-tolerance and easy to be implemented withlow overhead. A hybrid distributed garbage collection of active objects is alsoproposed and it is fault-tolerance and fits for large-scale system compared withprevious work.At present, the researches on real-time garbage collection are in the stage ofdevelopment, and there are many problems to be resolved. Scheduling strategy ofreal-time garbage collection, hybrid garbage collection and distributed garbagecollection are researched in depth and new algorithms are proposed, which maycontribute to enhancement of performance of real-time garbage collection.