Erik Altman photo

Exotasks - overview

Many real-time systems decompose naturally into a set of tasks that communicate solely by message passing. Such a decomposition provides a very high level of determinism and reliability because each task is purely functional in its inputs and the task abstraction matches the sensor-to-actuator control flow of many systems.

Exotasks provide such a task model within Java, adapted from that of Giotto, but extending it to allow individually garbage collected tasks and the communication of arbitrarily complex values over ports.

Exotasks receive new objects from external sources (via ports). If those sources include types not previously seen by the Exotask, they could cause previously un-validated code to be executed in overridden methods. As a result, the Exotask validator must check not only its given task, but also ensure that any changes to the call graphs of preexisting tasks are benign.

Exotasks and their ports also implement the logical execution time abstraction of Giotto, which provides platform-independent programming of the timing behavior of the task. The result is an extension of Java's principle of "write once, run anywhere" from the functional domain to the timing domain.

The logical execution time (LET) of a task determines how long the task executes in real time to produce its result, independently of any platform characteristics such as system utilization and CPU speed. Then, we check statically and dynamically if the task does indeed execute within its LET for a given platform, e.g., characterized by a scheduling strategy and WCETs. If the task needs less time, its output is buffered and only made available exactly when its LET has elapsed. As a result, the behavior of the system is both platform independent (assuming sufficient resources to complete on time) and composable (since two LET-based sets of tasks can be composed without changing their external behavior).

The difference between a task's WCET and its deadline is called its slack. By analogy, we call the difference between a tasks base memory and its allocated memory its slop. Depending on the amount of slack and slop, garbage collections can be introduced to trade space for time. Garbage collection is triggered by setting the limit of the private heap to some value between its maximum live memory and its total allocated memory; this is called its space-out.

One of the major problems with the message-based model of Exotasks is that it appears to require that data structures sent on ports be immutable; otherwise a data structure read from the same port by two tasks, or sent on a port and (perhaps partially) retained by reference in the task, would be subject to mutation that could cause side effects.

Such a restriction is undesirable because it would significantly limit the flexibility of the data structures and the ability to use pre-existing libraries to create and process them. However, it is not the mutability of the data structure that is the fundamental problem, but rather the potential for sharing.

We solve this problem with send-by-collection: at the end of the task execution, a specialized garbage collector copies the objects in ports from the sender to the receiver. In the event that it knows, either statically or dynamically, that there is no sharing, it may be possible to optimize that operation. However, if there is sharing, then multiple receivers will each receive their own copy of the mutable data, and there will be no side effects.

In addition to allowing the use of mutable data structures, send-by-collection means that Exotasks can even make use of libraries that invoke synchronized methods because all data is guaranteed to be task-local and the synchronizations are therefore guaranteed to be redundant. The specialized collection simply removes any synchronization state from the copied objects that are sent to other tasks.