WOOP - Project Description

The most significant difference between real-time systems and other computer systems is that the system behavior must not only be correct but the result of a computation must be available within a predefined deadline. It has turned out that a major progress in order to guarantee the timeliness of real-time systems can only be achieved if the scheduling problem is solved accordingly. Most scheduling algorithms assume that the runtime of a task is known a priori. Thus the worst case performance of a task plays a crucial role.

We recognize two difficult tasks in estimating the timing behavior of a program:

Most researchers try to ease the task of estimating the number of general loop iterations by forbidding general loops, i.e., by forcing the user to supply constant upper bounds for the number of iterations. Another approach is to let the user specify a time bound within the loop has to complete. Recursive procedures are forbidden in all well-known real-time programming languages, too.

Project WOOP follows a different approach: The gap between general loops and for-loops is narrowed by defining discrete loops. These loops are known to complete and are easy to analyze (especially their number of iterations) and capture a large part of applications which otherwise would have been implemented by the use of general loops. These include Heapsort, a bottom-up version of Mergesort, and Euclid's algorithm to compute the greatest common divisor of two positive numbers. Furthermore all divide and conquer algorithms can be handled by discrete loops, e.g. binary search and tree traversing algorithms such as weight-balanced trees or AVL-trees.

We have determined under which conditions recursive procedures and functions can be used within real-time applications. The conditions are not too restrictive such that not only simple mathematical recursions, like the Factorial Numbers and the Fibonacci Numbers, but also more complicated recursive procedures, like a recursive version of Mergesort and recursive tree traversal algorithms, can be handled.

Each method of a real-time object/class has to be equipped by a WCP-formula which describes the Worst Case Performance behavior of the method. In general this formula does not only depend on the execution speed of the processor, but it also depends on generic parameters of the real-time object. Such formulas are called gWCP-formulas. One of the major advantages of gWCP-formulas is that they greatly improve reusability of software.

In case of a tree-like object, such a generic parameter may be N, the upper bound of the number of nodes present in the tree. If the tree is balanced, the operations defined on the tree structure certainly depend on this generic parameter and can be performed in O(log N) time. Thus the gWCP-formulas assigned to the methods of this tree structure are supposed to contain a log N-term. The constant terms contained in the formulas depend on more primitive timing properties of the implementation and of the underlying hardware.

Generalizing the formulas introduced above, state parameters may also be part of a timing formula. In many cases this gives sharper estimates. The corresponding formulas are called aWCP-formulas. For example the performance of the operations defined on a tree structure depends on the number of nodes actually present in the tree, although it is bounded above by the value given by a gWCP-formula without state parameters.

Thus WCP-estimates form a hierarchy of estimates of timing properties of generic objects/classes. In detail we have

actual performance <= aWCP <= gWCP <= WCP,

where the last WCP denotes a constant upper bound of the performance if such an upper bound exists.

Summing up, Project WOOP is divided into several tasks:

If you are interested, please contact Johann Blieberger