Exploiting hierarchy for planning and scheduling

In real-time systems, tasks must satisfy strict timing constraints in order to avoid timing failures. In situations in which task running times are not known a priori, i.e., at design time, dynamic scheduling approaches attempt to guarantee, at run time, that tasks will meet their deadlines. Clearly, such guar-antees may not always be possible, and so schedulability failures are likely. One option to minimize the effect of such failures is to instead schedule alternative tasks. In this paper, we present and evaluate an approach that exploits hierarchically structured program representations that naturally occur in many application scenarios. Hierarchy allows us to (a) simplify the specification of real-time requirements and (b) specify the alternative tasks to schedule in the event of an impending timing failure. We extend an existing dynamic scheduling algorithm to deal with hierarchical task structures and present the results of our experimentation aimed at determining the efficacy of our approach.