Efficient memory-reference checks for real-time Java

The scoped-memory feature is central to the Real-Time Specification for Java. It allows greater control over memory management, in particular the deallocation of objects without the use of a garbage collector. To preserve the safety of storage references associated with Java™ since its inception, the use of scoped memory is constrained by a set of rules in the specification. While a program's adherence to the rules can be partially checked at compile-time, undecidability issues imply that some - perhaps, many - checks may be required at run-time. Poor implementations of those run-time checks could adversely affect overall performance and predictability, the latter being a founding principle of the specification. In this paper we present efficient algorithms for managing scoped memories and the checks they impose on programs. Implementations and results published to date require time linear in the depth of scope nesting; our algorithms operate in constant time. We describe our approach and present experiments quantifying the gains in efficiency.