Combining Static and Dynamic Scheduling for Real-Time Systems
Workshop on Software Analysis and Development for Pervasive Systems (SONDA 2004), Invited Paper, Verona, Italy, August 24, 2004, pp. 32-40.
We address in this paper the combination of static and dynamic scheduling into an approach called quasi-static scheduling, in the context of real-time systems composed of hard and soft tasks. For the particular problem discussed in this paper, a single static schedule is too pessimistic while a purely dynamic scheduling approach causes a very high on-line overhead. In the proposed quasi-static solution we compute at design-time a set of schedules, and leave for run-time only the selection of a particular schedule based on the ime-triggered and event-triggered clusters, interconnected via gateways. We have proposed a schedulability analysis for such systems, including a worst-case queuing delay analysis for the gateways, responsible for routing inter-cluster traffic. Based on this analysis, we address design problems which are characteristic to multi-clusters: partitioning of the system functionality into time-triggered and event-triggered domains, and process mapping. We present a branch and bound algorithm for solving these problems. Our heuristic is able to find schedulable implementations under limited resources, achieving an efficient utilization of the system. The developed algorithms are evaluated using extensive experiments and a real-life example.
[AEP04] Luis Alejandro Cortes, Petru Eles, Zebo Peng, "Combining Static and Dynamic Scheduling for Real-Time Systems", Workshop on Software Analysis and Development for Pervasive Systems (SONDA 2004), Invited Paper, Verona, Italy, August 24, 2004, pp. 32-40.