Models of Real-Time Workload: Expressiveness and Complexity
Prof. Wang YI
Recorded 09 September 2013 in Lausanne, Vaud, Switzerland
This lecture will provide a survey on task models to characterize real-time workloads at different levels of abstraction for the design and analysis of real-time systems. It covers the classic periodic and sporadic models by Liu and Layland et al., their extensions to describe recurring and branching structures as well as general graph- and automata-based models to allow modeling of complex structures such as mode switches, local loops and also global timing constraints. The focus is on the precise semantics of the various models and on the solutions and complexity results of the respective feasibilty and schedulability analysis problems.
We will also present our recent results which demonstrate known intractable problems in real-time scheduling can be solved effectively by successive refinement and approximation. We show the analysis problem related to the real-time calculus due to Thiele et al can be solved in pseudo-polynomial time.
1. Martin Stigge and Wang Yi. Models of Real-Time Workload: A Survey. In the volume of Real-Time Systems: the past, the present, and the future, Proceedings of a conference organized in celebration of Professor Alan Burns 60th birthday, 2013.
2. Martin Stigge and Wang Yi. Iterative Abstraction Refinement for Feasibility Analysis. In the proc. of RTSS 2013, December 3-6, Vancouver, Canada.
3. Nan Guan and Wang Yi. Finitary Real-Time Calculus: Efficient Performance Analysis of Distributed Embedded Systems. In the proc. of RTSS 2013, December 3-6, Vancouver, Canada.
Watched 589 times.Watch