Table of Contents
Libraries are vital to the software development process. By providing reusable code, they save developers time that would otherwise be spent creating sorting algorithms and other general-purpose functions. However, most libraries are designed to have good average-case performance, and little thought is given to their worst-case performance. As a result, the execution time of their operations may be difficult to predict, making them unsuitable for real-time systems.
For hard real-time systems, where guaranteed predictability is not just important but crucial, a new approach to software libraries is necessary. Such libraries should conform to safety-critical specifications that demand complete WCET analyzability and other forms of static verification. Achieving this goal demands certain restrictions: 1) The maximum bound of every loop in the library must be known; 2) exceptions are prohibited; and 3) dynamic memory allocations (after initialization) are prohibited.
As a demonstration of how to create an analyzable library, Volta includes Canteen, a set of predictable collection classes. It provides hard real-time versions of an array, linked list, set, and map, each of which conforms to its equivalent standard Java interface, including support for generics.
Canteen conforms to the same interfaces as the java.util package, so their usage is largely self-explanatory. There are, however, some special restrictions required by Canteen for hard real-time predictability.
First, creating elements the usual way (i.e., by calling Java's new operator) will not work. Instead, each collection must be initialized with a set of pre-allocated elements. When a new element is to be added to the collection, the user must pull one of these elements from the collection by calling newElement or newEntry, then pass it to the collection's add or put method.
Second, some methods are unimplemented. The unimplemented methods are documented as such in the Canteen source code.
For an example of how to use the classes in keeping these restrictions, refer to Canteen's QuickTest.java file.