Maintaining data structure semantics of concurrent queues such as first-in first-out (FIFO) ordering requires expensive synchronization mechanisms which limit scalability. However, deviating from the original semantics of a given data structure may allow for a higher degree of scalability and yet be tolerated by many concurrent applications. We introduce the notion of a k-FIFO queue which may be out of FIFO order up to a constant k (called semantical deviation). Implementations of k-FIFO queues may be distributed and therefore be accessed unsynchronized while still being starvation-free. We show that k-FIFO queues whose implementations are based on state-of-the-art FIFO queues, which typically do not scale under high contention, provide scalability. Moreover, probabilistic versions of k-FIFO queues improve scalability further but only bound semantical deviation with high probability.

Exotasks are a novel Java programming construct that achieve three important goals. They achieve low latency while allowing the fullest use of Java language features, compared to previous attempts to restrict the Java language for use in the submillisecond domain. They support pluggable schedulers, allowing easy implementation of new scheduling paradigms in a real-time Java system. They can achieve deterministic timing, even in the presence of other Java threads, and across changes of hardware and software platform. To achieve these goals, the program is divided into tasks with private heaps. Tasks may be strongly isolated, communicating only with each other and guaranteeing determinism, or weakly isolated, allowing some communication with the rest of the Java application. Scheduling of the tasks' execution, garbage collection, and value passing is accomplished by the pluggable scheduler. Schedulers that we have written employ logical execution time (LET) in association with strong isolation to achieve time portability. We have also built a quad-rotor model helicopter, the JAviator, which we use to evaluate our implementation of Exotasks in an experimental embedded version of IBM's J9 real-time virtual machine. Our experiments show that we are able to maintain very low scheduling jitter and deterministic behavior in the face of variations in both software load and hardware platform. We also show that Exotasks perform nearly as well as Eventrons on a benchmark audio application.

Existing programming methodologies for real-time systems suffer from a low level of abstraction and non-determinism in both the timing and the functional domains. As a result, real-time systems are difficult to test and must be re-certified every time changes are made to either the software or hardware environment. Exotasks are a novel Java programming construct that achievedeterministic timing, even in the presence of other Java threads, and across changes of hardware and software platform. They are deterministic functional data-flow tasks written in Java, combined with an orthogonal scheduling policy based on the logical execution time (LET) model. We have built a quad-rotor model helicopter, the JAviator, which we use as a testbed for this work. We evaluate our implementation of exotasks in IBM's J9 real-time virtual machine using actual flights of the helicopter. Our experiments show that we are able to maintain deterministic behavior in the face of variations in both software load and hardware platform.