Faculté informatique et communications IC, Programme doctoral Informatique, Communications et Information, Institut d'informatique fondamentale IIF (Laboratoire de programmation distribuée LPD)
Reflexes: programming abstractions for highly responsive computing in Java
Thèse Ecole polytechnique fédérale de Lausanne EPFL : 2008 ; no 4228.Ajouter à la liste personnelle
- Achieving sub-millisecond response times in a managed language environment such as Java introduces significant implementation challenges. The Achilles' heel of Java is its reliance on automatic memory management for reclaiming dead objects. Typically, the garbage collectors used in commercial Java virtual machines are designed to maximize the performance of applications at the expense of predictability. Moreover, it is non-deterministic as to when and for how long the garbage collector will run. As a consequence garbage collection introduces execution interference that can easily reach hundreds of milliseconds, preventing the timeliness requirements of the real-time systems from being satisfied. Another source of interference relates to the integration of real-time tasks with a time-oblivious application. Typical programming practices for sharing data between threads involve synchronized access to some shared data structure through mutual exclusion. In a real-time system this might lead to unbounded blocking of the real-time thread, so-called priority inversion, causing serious deadlines infringements. Faced with these challenges a system designer typically has two options: to deploy a realtime garbage collector (RTGC), or to restrict the programming model. RTGCs achieve much improved predictability over traditional stop-the-world garbage collectors by interleaving the application execution with the garbage collection. Recent advances in real-time garbage collection algorithms have reduced latency to approximately 1 millisecond. Nevertheless, some applications, e.g., safety critical applications certified according to DO-178B, have temporal requirements beyond what is possible with state-of-the-art RTGCs. Moreover, real-time garbage collectors still face the problem of priority inversion. This thesis presents Reflexes, a simple, statically type-safe restricted programming model facilitating the construction of highly-responsive applications in Java. Reflexes are designed to make it easy to write and integrate simple periodic tasks or complex stream processors, both observing real-time timing constraints in the sub-millisecond range, into larger time-oblivious Java applications. Reflex tasks run in a part of memory free from garbage collection interference, and maintain a class-based separation between object lifetimes, enabling reclamation of periodic garbage in constant time. Tasks are organized in a graph and communicate through uni-directional, non-blocking channels. Furthermore, Reflexes enable non-blocking interaction between real-time tasks and time-oblivious code using methods with transactional semantics, circumventing typical problems of priority inversion when using common programming practices for synchronizing access to shared data. Reflexes specify a set of static safety checks preventing dangling pointers and preventing a Reflex from observing heap-allocated objects in an inconsistent state as they are, e.g., when being copied by a garbage collector. These checks are enforced statically by an extension of the standard Java compiler to guarantee correctness. We describe two implementations of Reflexes: a stand-alone prototype implementation built on top of a research Java real-time virtual machine, and an implementation based on an integration of Reflexes with two existing restricted programming models into a single unified framework, Flexotask, running on top of an industrial-strength Java real-time virtual machine. Whereas the prototype implementation of Reflexes is limited to a virtual machine with uni-processor support and exploits non-standard features of the virtual machine, the latter implementation leverages the multi-processor support of an industrial-strength virtual machine with minimal extensions. For both implementations we report separately on a number of encouraging results from empirical experiments using benchmark and real-world applications. Specifically, our experiments show that Reflexes in both cases are capable of achieving sub-millisecond response time with a high degree of predictability.