Real time library
From JopWiki
Libraries are vital to the software development process. By providing reusable code, libraries can save developers time that would otherwise be spent creating containers, iterators, sorting algorithms, and other general-purpose functions. Libraries also improve code quality: Because they are shared among many developers, bugs in libraries are more likely to be detected and fixed. (This is an instance of Linus's Law.)
In addition, libraries are more likely to offer higher performance and more features because they are usually crafted by experts in the library's domain. For example, libraries for image processing are normally produced by those with experience in signal processing, Euclidian transformations, and so on. An ordinary developer creating the same code for individual use may not have the required expertise and, furthermore, may not be able to spend the time optimizing and fine-tuning the code.
To put it simply, libraries save developers from having to "reinvent the wheel."
Contents |
[edit] The Problem with Libraries in Real-time Systems
Given their importance, many general-purpose software libraries have been developed over the years. Popular implementations include the Standard Template Library for C++, the Base Class Library for .NET, and the Class Library for Java.
In a typical environment, such as a desktop computer or enterprise system, these libraries provide a variety of helpful features with a high degree of flexibility. They simplify many common tasks, such as maintaining lists of items or performing complex string parsing, allowing the developer to focus on the specific goals of the application itself.
This flexibility comes at a price, however. Standard libraries for general-purpose tasks are designed to have good average-case performance, and little thought is given to worst-case performance. As a result, the execution time for common operations may be very difficult to predict. For example, Java's ArrayList class provides an operation to append an item to the end of a list. The operation normally executes quickly and in constant time, but if the additional item would exceed the current size of the array, a larger array is created, and the old array's contents are copied into it. Allocating and copying memory are expensive linear-time operations, and as a result, the add operation suffers from a broad variation between its best- and worst-case times.
The following figure illustrates this concept in more detail. The data points show the amount of time the add operation takes as the size of the list increases. The green data set represents the typical case of an ArrayList that grows automatically as new elements are added. Note that almost every operation completes in virtually no time, and yet a few operations (approximately at list sizes of 500, 2500, and 8000) take far longer. These points indicate where the ArrayList was forced to create a larger copy of its internal data store.
The graph reveals a common behavior among standard library operations: Usually they execute very quickly but occasionally very slowly. In most computing environments, such a variation is not a serious issue. Many applications can tolerate the occasional slowdown as long as the average performance is still good. In real-time systems, however, this unpredictability can cause disaster. If, for example, the software controlling a robotic arm assumes that an operation always executes quickly, any unexpected delay of the operation would break this assumption, disrupting the delicate timing of the system and potentially damaging the arm or the objects it manipulates.
There are many possible solutions to this problem. An obvious one is to take the conservative approach. The software could assume that every library operation exhibits its worst-case behavior. While this tactic prevents scheduling errors by taking into account any unexpected delays, it is also tremendously inefficient. The system would lay idle most of the time, waiting for a potential slowdown even when it does not occur. (A faster processor could reduce the idle time, but this too would be a waste of resources.)
Another solution is to statically allocate data structures. For instance, an ArrayList object can be initialized with a user-specified size for its internal data store. If this size is at least as large as the number of elements that will ever be added to list, then the slowdown caused by reallocating and copying the array will never occur. The result is that the add operation behaves predictably, without any major spikes in its timing, as shown by the red data set of the graph. The downside, of course, is that allocating data structures statically is inflexible and inefficient. It often requires intimate knowledge of the library's internal data structures, and it can needlessly increase the memory requirements of the system. For example, a string for buffering an error log could be allocated statically during the system's initialization phase, but unless an error occurs, the memory goes to waste.
[edit] Design Goals for Real-time Libraries
None of these solutions is satisfactory. Combining general-purpose libraries with real-time systems requires the programmer to put substantially more thought and effort into code design, and even then the system may be too inefficient. The problem is that the critical tasks in real-time systems must execute on tight deadlines in a predictable fashion, but existing libraries ignore all deadline requirements, favoring flexibility and average-case performance over predictability.
Therefore, an entirely different approach is necessary. We postulate that a custom-made library, designed specifically for timeliness and predictability, would be the optimal solution to meet the special requirements and unique complications of real-time systems. Such a library would aim for the following goals:
- All operations in the library will be statically analyzable for worst-case execution time (WCET). Knowing the WCET is needed to guarantee the timeliness of the system.
- As a corollary to the previous requirement, the maximum bound of any loop must be known in order to calculate the WCET. Thus, information about all loop bounds will be incorporated into the real-time library. (Because fully automatic loop bound detection is currently impractical, a manual annotation mechanism will be considered sufficient to meet this requirement.)
- The library will not include any support for exceptions. Exception handling makes the control flow of a program so complex that validating all program paths becomes an intractable problem. Safety-critical certification standards such as the DO-178B, which mandate MC/DC, LCSAJ, or other forms of code coverage, specifically forbid reliance on exception-based software due to the lack of pathway predictability. Likewise, high-integrity software implementations, such as SPARK (see High-Integrity Ada by John Barnes), leave out exceptions because they make formal reasoning and verification much more difficult. They simply create too many possible exit points for a function. (See Inquiry Board Traces Ariane 5 Failure to Overflow Error for an example of how exceptions can cause catastrophic failure.)
[edit] Libraries for Real-time Java
As a secondary requirement in the design of the library, it will be implemented entirely in Java. In addition to maximizing portability and ease of use, Java is a much easier target for static analysis of WCET (when combined with a native processor such as JOP), thus helping to meet a key design requirement. The library will also implement as many standard Java interfaces as possible, such as those found in Java's collection classes (List, Map, Set, etc.), in order to retain a degree of compatibility with existing Java source code.
Naturally, this approach will not be the first to address the problem of libraries in real-time Java. Two other specific techniques have commonly been adopted:
- Careful application of Java's standard library
- Javolution, a third-party designed for real-time systems
[edit] Accommodating Java's Standard Class Library
Java's standard class library is very tempting for real-time developers. As the official API for over a decade, it has been widely tested and debugged. It is now feature-rich, offering virtually every bit of functionality one would expect from a general-purpose library. Taking advantage of this richness would speed real-time application development by freeing developers from having to re-implement the same functionality.
Accommodating Java's class library in a real-time environment is far from straightforward, however. The issue of worst-case performance, as in the ArrayList example, is only part of the problem. When using the Real-Time Specification for Java (RTSJ), the biggest hurdle is that many of the best practices from standard Java, including most of the design patterns, cannot be used because they will cause memory leaks. The trouble arises in the RTSJ's scoped memory model when objects are used in mixed contexts: either shared by heap and non-heap objects or accessed from different memory areas. For mutable data structures, this invariably leads to illegal assignment errors and other such problems.
Instead of simply doing without these essential classes and struggling with reduced productivity, some RTSJ developers choose to work around them. For example, the scoped memory and real-time thread features of the RTSJ are intended for time-sensitive tasks, such as reading sensor data into a buffer. These critical tasks may be relatively simple and small, and thus they may not need to use the general-purpose libraries at all. Instead, the critical threads can transfer data to non-real-time threads, which can then safely use the standard libraries as needed.
While this tactic can work, it limits the ability of real-time threads to do useful work. The increasing sophistication of real-time systems means that these threads are being called upon to perform increasingly complex tasks that necessitate the use of a class library. Incorporating such libraries into an RTSJ application demands special compromises and strict programming discipline in order to avoid memory leaks and scoped memory exceptions. Work-arounds include:
- Avoiding sharing across scoped memory contexts
- Ensuring collections are big enough so that they do not grow dynamically
- Performing initial accesses in the proper memory area to prevent timing delays caused by lazy initialization
- Explicitly switching memory areas to perform certain library operations
These extra steps can adversely impact developer productivity. Having to take a number of special precautions whenever a library is used can offset whatever productivity gains were made by integrating with the library in the first place. For these reasons, the standard Java class library is inadequate for real-time applications.
[edit] Javolution
To mitigate the limitations of Java's built-in library, an alternative solution has emerged. It consists of a specially designed library called Javolution. Created by a Raytheon engineer and released as open-source, Javolution is the first and only class library targeted specifically for real-time systems. It is intended to replace Java's standard collection classes (List, Map, Set, etc.) with time-predictable versions to eliminate problems such as:
- Large arrays allocated and copied for internal resizing, resulting in large worst-case times
- Long garbage collection pauses due to memory fragmentation when large collections are allocated
- Sudden bursts of computation (e.g., internal rehashing of hash maps or hash sets)
The figure below elucidates the latter problem: a delay caused by rehashing. Note that the performance of the FastMap's put operation remains relatively constant, while the standard HashMap class suffers from occasional delays that are orders of magnitude longer than its expected time.
Javolution also includes special support for the scoped memory model of the RTSJ. Unlike the standard Java library, which is susceptible to memory leaks and illegal access errors under the RTSJ, Javolution is scope-safe. It allocates additional memory for a collection from the same memory area as the collection itself. Consider, for example, a map allocated in immortal memory:
static Map<Foo, Bar> map = new HashMap<Foo, Bar>();
In an RTSJ environment, this code will cause memory leaks when entries are removed. It will also cause illegal assignment errors if new entries are added from a scoped memory area. With Javolution, these problems can be eliminated simply by instantiating a different kind of map:
static Map<Foo, Bar> map = new FastMap<Foo, Bar>();
With this change, the map's entries are internally recycled, and new entries are placed in immortal memory, thereby eliminating the run-time errors caused by the RTSJ's memory model.
Javolution achieves these goals largely by judicious memory management, always favoring time predictability over space efficiency. For instance, it ensures that any capacity increase of a collection occurs smoothly, allocating in small increments instead of a single large chunk. In particular, the FastTable class relies on multi-dimensional arrays to avoid resizing and copying its internal data store. Another example of Javolution's approach is its FastMap class, whose entries each have their own entry table. When the map's size increases beyond capacity, it allocates new, larger tables for the new entries. Because the old entries are not moved, the map does not suffer from delays incurred by rehashing.
Despite these advantages, Javolution can only claim to be predictable. It does not provide any guaranteed bound on WCET, for example. Its liberal use of exception handling also prohibits most forms of static analysis, making Javolution inappropriate for safety-critical real-time systems.
[edit] Collection Classes for Safety-Critical Real-time Java
To overcome these limitations, we have begun development on a custom library called Canteen. Designed specifically for safety-critical systems, it includes implementations of the three most common types of collection classes:
- List A simple sequence that allows precise control over element ordering. It allows multiple entries of the same element, including null. Canteen provides both an array-based and a linked-list-based representation of the list.
- Set A collection that ensures it contains no duplicate elements. As the name implies, it models the mathematical abstraction known as a set. The set in Canteen is a sorted set that uses a red-black tree to keep track of entries.
- Map A dictionary-type collection that maps keys to values. Each key can map to at most one value. The map in Canteen is a sorted set that uses a red-black tree to keep track of entries.
Each of these classes supports the following features:
- All operations statically analyzable for WCET
- Because safety-critical systems require validation of WCET, the classes in Canteen were designed to facilitate static timing analysis tools. For example, recursion is non-existent, and all loops have been annotated to provide a finite bound on their iteration count.
- No exceptions thrown during the mission phase
- As discussed in the section "Design Goals," exception support makes safety-critical validation much more difficult. Therefore, the Canteen classes never deliberately throw unchecked exceptions, and none of their methods declare checked exceptions.
- No memory allocation during the mission phase
- Memory allocation is problematic in safety-critical systems. Validation and timing analysis of memory allocation, as well as garbage collection mechanisms, is still an ongoing area of research. Most safety-critical systems, including the latest specifications such as JSR-302, simply prohibit dynamic memory allocation altogether. The Canteen library continues with this convention and avoids Java's
newoperator, relying instead on custom memory pools that recycle objects in constant time. (Before the mission phase begins, however, the classes may allocate memory from Java's heap for the pools and other necessary structures.) - Support for Generics
- In early versions of Java, collection classes were simply buckets of objects. Nothing prevented a buggy program from putting, e.g., integer objects into a set meant to contain only strings. Such mistakes resulted in runtime errors that were difficult to isolate. With the advent of Java 5, collection classes can now take parameters that indicate the kind of objects a collection may contain. These parameters, known in Java as generics, allow the compiler to enforce type checking rules on collection class operations. The Canteen library fully supports this feature and thus provides greater validation of its correctness, as required by safety-critical systems.
- Compatibility with standard Java interfaces
- The collection classes in Canteen implement the same set, list, and map interfaces declared in Java's standard library. The classes can therefore act as drop-in replacements for the standard collection classes, thereby maximizing compatibility with and reusability of existing code.
[edit] Results
The collection classes in Canteen were implemented in 100% pure Java. They consist of approximately 500 lines of non-commenting source code statements (or approximately 3000 lines including comments). Each method is fully documented; the API reference is available online. The source code is also available online; it is distributed as open source under the GPL license.
A suite of 72 test cases was also created to show correct behavior of the library. An interesting benefit of these test cases is that they can run in "standard" mode, such that new objects are obtained from the heap instead of Canteen's memory pools, and the standard Java collection classes are used instead of Canteen's time-predictable versions. All 72 test cases pass in this mode, demonstrating that Canteen can provide drop-in replacements for the standard Java interfaces.
[edit] Implemented Methods
Due to the restrictions of a safety-critical environment, not all of the methods in these interfaces could be implemented. The following tables provide a summary of which interfaces were implemented, which were not, and why.
| add(E) | yes |
| add(int, E) | yes |
| addAll(Collection) | no1 |
| addAll(int, Collection) | no1 |
| clear() | yes |
| contains(Object) | yes |
| containsAll(Collection) | no2 |
| equals(Object) | yes |
| get(int) | yes |
| hashCode() | yes |
| indexOf(Object) | yes |
| isEmpty() | yes |
| iterator() | yes |
| lastIndexOf(Object) | yes |
| listIterator() | yes |
| listIterator(int) | yes |
| newElement() | yes |
| remove(int) | yes |
| remove(Object) | yes |
| removeAll(Collection) | yes |
| retainAll(Collection) | yes |
| set(int, E) | yes |
| size() | yes |
| subList(int, int) | no3 |
| toArray() | no3 |
| toArray(T[]) | no3 |
| add(E) | yes |
| addAll(Collection) | no1 |
| clear() | yes |
| contains(Object) | yes |
| containsAll(Collection) | no2 |
| equals(Object) | yes |
| hashCode() | yes |
| isEmpty() | yes |
| iterator() | yes |
| newElement() | yes |
| remove(Object) | yes |
| removeAll(Collection) | yes |
| retainAll(Collection) | yes |
| size() | yes |
| toArray() | no3 |
| toArray(T[]) | no3 |
| clear() | yes |
| containsKey(Object) | yes |
| entrySet() | yes |
| equals(Object) | yes |
| get(Object) | yes |
| hashCode() | yes |
| isEmpty() | yes |
| keySet() | yes |
| put(K, V) | yes |
| putAll(Map) | no1 |
| remove(Object) | yes |
| size() | yes |
| values() | yes |
1. Two reasons: 1) Adding elements from some other collection, instead of this collection's memory pool, could cause memory leaks. 2) The maximum size of the given collection must be known for WCET analysis, but current analysis tools cannot detect loop bounds for arbitrary polymorphic objects.
2. Two reasons: 1) Implementing this method would require accessing the given collection's iterator. This could be dangerous, given that iterators cannot be allocated in a safety-critical environment, and (given current analysis tools) a single iterator must be shared across all users. Attempting to use a shared iterator could corrupt it. 2) The maximum size of the given collection must be known for WCET analysis, but current analysis tools cannot detect loop bounds for arbitrary polymorphic objects.
3. Without some sort of sophisticated analysis, implementation of this method would require allocating memory or using a single shared return object (dangerous).
[edit] Time Complexity
As with any implementation of collection classes, time complexity is an important attribute. Users must know the expected running time of the collections in order to predict the performance of programs that use them. The following tables summarize the time complexity of the basic operations in each class.
| insert | O(n) |
| delete | O(n) |
| search | O(n) |
| indexed search | O(1) |
| insert | O(1) |
| delete | O(1) |
| search | O(n) |
| indexed search | O(n) |
| insert | O(lg(n)) |
| delete | O(lg(n)) |
| search | O(lg(n)) |
| insert | O(lg(n)) |
| delete | O(lg(n)) |
| search | O(lg(n)) |
[edit] Loop Bound Annotations
Because time predictability is a key requirement in safety-critical systems, collection classes must be analyzed using a WCET tool to provide an upper bound on execution time. For programs containing loops, however, the WCET is essentially unbounded. A pure control-flow analyzer has no way of knowing how many times a loop will execute in the worst case.
To solve this problem in Canteen, we rely on the traditional source code annotation approach. Each loop construct in the Canteen source code includes an annotation that declares the loop's maximum iteration count. Although these annotations must be inserted manually and thus require more implementation effort and can be error-prone, they make WCET analysis much faster and simpler.
To implement the loop annotations in Canteen, we have built upon our prior work in annotations. We adapted Java's built-in annotation mechanism and extended it to allow annotations directly on loop constructs. This provides "for free" syntax checking, type safety, and support from existing tools. The following code snippet shows an example of the annotation syntax:
@LoopBound(max=10) for (int i = 0; i < 10; i++) ...
For collection classes, however, this annotation is insufficient. The problem is that the bound of nearly all loops in a collection class depends on the maximum size of the collection object. For instance, if two list objects have a maximum sizes of 10 and 100, then the loop bound of a search operation for the second list will be 10 times more than the first. In other words, the loop bound annotation of a collection class method cannot be specified using a simple constant.
To address this issue, loop bound annotations in Canteen are expressed symbolically:
public int indexOf(Object o) {
@LoopBound(max=COLLECTION_BOUND)
for (int i = 0; i < array.length; i++)
...
}
When the WCET analyzer encounters this annotation, it searches for the collection object field that invoked the loop's method. It then extracts the collection bound from an annotation on this field. For example:
class MyClass {
@CollectionBound(max=1024)
private PredictableList<Int> list;
...
private void foo(Object bar) {
int index = list.indexOf(bar);
...
}
}
In this example, the analyzer would determine that the value of 1024 should be mapped onto the COLLECTION_BOUND symbol for this particular invocation of indexOf.
Although this technique works for the typical usage of collection classes, it has limitations. If, for example, the field is aliased to some other variable, the WCET analyzer will retrieve the wrong CollectionBound annotation:
@CollectionBound(max=2048) private PredictableList<Int> other; ... list = other;
In this case, the WCET analyzer will incorrectly use 1024 as the collection bound. (It should be 2048.)
Likewise, the analyzer will be unable to determine the collection bound if the object is declared as a local variable or passed as a method parameter instead of simply accessed as a class field. Fixing these problems would require a sophisticated data flow analysis (DFA) tool that does not yet exist.
[edit] Memory Management
As required by most safety-critical software specifications, Canteen never allocates memory from the heap during the mission phase. This greatly simplifies analysis and validation. Instead, it pre-allocates all elements in a memory pool during the initialization phase, up to a user-defined maximum size. When the user needs to add a new element to a collection, it can be retrieved from the pool in constant time. When the element is removed, it is recycled back into the pool, again in constant time. (Note that array-based collections may require an additional linear time algorithm in order to perform the insertion or deletion of the element within the array. However, this time can easily be bounded through static WCET analysis.)
[edit] Iterators
In addition to collection elements, collection Iterators must also be pre-allocated. This presents a problem, given that the iterator design pattern assumes on-demand allocation of new iterator objects, and yet safety-critical systems prevent dynamic allocation. Canteen works around this problem by pre-allocating one iterator per collection object and returning this object whenever an iterator is requested. The shared iterator is reset to its initial state on each request.
Although this approach solves the problem in the majority of cases (assuming single-threaded execution), there may be corner cases where an iterator is requested while it is already in use. When this happens, the state of the iterator will be unexpectedly reset, causing dangerous run-time errors that are difficult to detect and prevent.
[edit] Object Mutation and Recycling
Another complication of memory pools is that all elements stored in a collection must be mutable. If the elements are immutable, their state will never change, having been allocated and initialized to a default state during the library's initialization phase. As a consequence, none of Java's standard data type wrappers, such as Integer, Float, etc., can be used in Canteen. Users must instead write their own data type wrappers whose state can be changed. Users must also be careful to reset this state when retrieving an element from a memory pool. Unlike objects allocated with the new operator, an object in Canteen may have been recycled from a previous use and its fields might not be zero (or null).
Furthermore, objects obtained from a memory pool must always be added back to the collection from which they came. If the client mistakenly adds an element to some other collection, memory leaks will occur.
In addition, users must be careful not to access an object once it has been removed from a collection. It will be recycled back into the memory pool and could therefore be in use by some other part of code, leading to data corruption through concurrent access.
[edit] Element Replacement
Yet another issue in memory pool management is element replacement. The List and Map interfaces allow the user to replace an existing element with some other element. The methods for performing this replacement---get for lists and put for maps---are dangerous in safety-critical Java. The root of the problem is that replacement elements cannot be created at run-time due to memory allocation restrictions in safety-critical environments. Instead, the replacement element must come from a memory pool, and pools contain only enough objects for the maximum declared capacity of their corresponding container.
Replacing elements under these circumstances may cause memory leaks and null pointer dereferencing. For example, consider a list containing a single element and a maximum size of two. A user might request an object from the memory pool in order to replace the existing element. If this happens, there will be no more free objects in the memory pool, even though the user may assume that another object remains, given that the list has not yet reached its maximum size.
There are various potential solutions to this problem, although none is satisfactory. One possibility is to perform a static analysis on the code to determine how many times a replacement method is called, then pre-allocate an object in the memory pool for each call. This approach could be very wasteful of memory, however. Another solution is to disallow element replacement altogether, but there may be legitimate reasons to do so, such as swapping two elements in a list. Also, the Map.put method is used not only for replacement; it is also the primary mechanism for adding new elements.
Canteen relies on none of these solutions. Instead, we observe that element replacement is usually necessary only because the Java objects placed in a container are typically immutable (e.g., Integer, Float, etc.). Since the safety-critical requirements of our library permit only mutable objects, the need for element replacement is substantially reduced. Therefore, we simply add a documentation warning that an object passed to the set method must have been obtained from the list itself and not its memory pool. Likewise, the put method must only be used for swapping elements or adding new ones. We relegate additional support for element replacement to future work.
[edit] Exception Handling
As previously mentioned, the Canteen library explicitly avoids exception handling in order to facilitate program verification and timing analysis. During the initialization phase, however, which does not require timing analysis, the container classes are free to throw exceptions. Also, the classes may inadvertently throw unchecked exceptions, such as a null-pointer exception an or array index out-of-bounds exception, if they are initialized or invoked incorrectly.
In certain situations, the lack of exception handling in Canteen means that error codes must be used (e.g., null object values or negative integer values). Substituting error codes for structured exception handling is error-prone, since the user could forget to check a return value for an error. Even worse, errors may sometimes have to be suppressed entirely in order to maintain compatibility with existing collection interfaces. For example, the add(int,E) method in the List interface returns void, relying on thrown exceptions to report errors in standard implementations. Therefore, users of Canteen have no way to check for an error when invoking this method.
[edit] Static Timing Analysis
To verify that the collection classes in Canteen are amenable to static WCET analysis, we tested them under the Clepsydra analyzer. It was able to compute an upper bound on execution time for a variety of test programs. The code below is one example:
public class Sort
{
@CollectionBound(max=10)
private PredictableList<Int> list;
...
public void bubbleSort() {
int i, j;
Int v1, v2;
@LoopBound(max=10)
for (i = list.size() - 1; i > 0; i--) {
@LoopBound(max=10)
for (j = 1; j <= i; j++) {
v1 = list.get(j - 1);
v2 = list.get(j);
if (v1.compareTo(v2) == 1) {
list.set(j, v1);
list.set(j - 1, v2);
}
}
}
}
...
}
Running Clepsydra on the bubbleSort method results in a WCET cycle count of 2,145,244 (based on the 100 MHz JOP).
[edit] External Resources
Java For Critical Jobs provides a nice table from Aonix that compares safety-critical Java to standard, soft-, and hard-real-time.
In Pursuit of Safety-Critical Java provides an overview of the state of the art (for 2005) of safety-critical Java
JSR-302: Safety Critical Java Technology is the official spec for safety-critical Java
Analysis of Static Properties in a Draft Standard for Safety-Critical Java provides a list of limitations in safety-critical Java
Java Becoming Solution for Safety-Critical Applications discusses Aonix and JSR-302
Memory safety without garbage collection for embedded applications perhaps interesting
Safety critical applications and hard real-time profile for Java: a case study in avionics
Safety Critical Java Specification Initiative various documents on Aonix's work in safety-critical Java
Safety Critical Java Technology a two-page overview of JSR-302
Safety-Critical Mailing List A forum for discussion of the engineering and assessment of safety-critical systems, with special reference to computing. Hosted by the High Integrity Systems Engineering Group at the University of York.
