Linköping University: Students Alumni Trade and Industry/Society Internal Search
SONDA04

Combining Static and Dynamic Scheduling for Real-Time Systems

Luis Alejandro Cortes
 
Petru Eles Author homepage
Zebo Peng Author homepage

Workshop on Software Analysis and Development for Pervasive Systems (SONDA 2004), Invited Paper, Verona, Italy, August 24, 2004, pp. 32-40.

ABSTRACT
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.


Related files:
SONDA04.pdfAdobe Acrobat portable document
SONDA04.ps.gzpostscript document, compressed (with gzip)


[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.
( ! ) perl script by Giovanni Squillero with modifications from Gert Jervan   (v3.1, p5.2, September-2002-)