Timing properties of software (relating to its ability to meet timing constraints) have traditionally been analyzed using real-time scheduling theory. This theory is perhaps one of the most studied and well understood aspects of real-time computing. However, the current state of the art is far from complete.
One of the big gaps in the theoretical underpinnings lie in our inability to relate aggregate metrics (such as utilization) to per-task temporal performance metrics (such as response time of individual tasks) except in some restricted special cases (such as that of scheduling periodic tasks). Of particular interest is the derivation of regions, defined in the state space of aggregate metrics, that imply satisfaction of all individual temporal performance constraints. Utilization bounds for schedulability of periodic tasks are the only counter-example where such regions are well-defined. However, the periodicity requirement limits applicability. Moreover, no framework exists for composing such relations (i.e., feasible regions) of individual components to compute those of aggregate systems.
In this research effort, we are concerned with bridging the gap between per-task performance and aggregate performance in complex software systems. We are also interested in developing a calculus for composing feasible regions of arbitrary topology software systems. The computation of such regions allows computation of overall capacity of large systems (their ability to meet deadlines) as well as performance optimization of large software components subject to timeliness constraints.
Observe that most scheduling problems are NP-complete, which typically calls for heuristic solutions. We demonstrate that computationally tractable sufficient solutions to the general problem of temporal analysis of distributed resource constrained communicating tasks are also possible if the feasible region is appropriately defined. The following references constitute a brief tutorial on feasible region calculus.
The first basic result: a utilization bound for aperiodic tasks under fixed-priority scheduling. This results drops the periodicity requirement that prevented prior work from being applicable to a large category of systems with no regularity in task arrival patterns.
Extensions of the basic results to multiprocessors (these are derived mainly for the sake of completeness and intellectual curiousity).
Extensions to accounting for mutual exclusion (blocking). These allow modeling systems of non-independent tasks, in which semaphores or other synchronization constraints are used to regulate access to passive resources.
Extensions to resource pipelines. These basic results allow composing feasible regions of individual components to compute those of distributed systems.
An application of feasible region calculus; computing the real-time capacity of a sensor network.