Schedulability analysis of applications with stochastic task execution times
Authors:
Open Access
- 1 November 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 3 (4) , 706-735
Abstract
In the past decade, the limitations of models considering fixed (worst-case) task execution times have been acknowledged for large application classes within soft real-time systems. A more realistic model considers the tasks having varying execution times with given probability distributions. Considering such a model with specified task execution time probability distribution functions, an important performance indicator of the system is the expected deadline miss ratio of the tasks and of the task graphs. This article presents an approach for obtaining this indicator in an analytic way. Our goal is to keep the analysis cost low, in terms of required analysis time and memory, while considering as general classes of target application models as possible. The following main assumptions have been made on the applications that are modeled as sets of task graphs: the tasks are periodic, the task execution times have given generalized probability distribution functions, the task execution deadlines are given and arbitrary, the scheduling policy can belong to practically any class of non-preemptive scheduling policies, and a designer supplied maximum number of concurrent instantiations of the same task graph is tolerated in the system. Experiments show the efficiency of the proposed technique for monoprocessor systems.Keywords
This publication has 30 references indexed in Scilit:
- Symbolic performance modeling of parallel systemsIEEE Transactions on Parallel and Distributed Systems, 2003
- Algorithm selection: a quantitative optimization-intensive approachIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999
- Codesign of embedded systems: status and trendsIEEE Design & Test of Computers, 1998
- Automatic configuration of embedded multicomputer systemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- Scheduling for embedded real-time systemsIEEE Design & Test of Computers, 1998
- Execution time analysis of communicating tasks in distributed systemsIEEE Transactions on Computers, 1996
- Fixed priority pre-emptive scheduling: An historical perspectiveReal-Time Systems, 1995
- Hardware-software co-design of embedded systemsProceedings of the IEEE, 1994
- Nonexistence of Brownian models for certain multiclass queueing networksQueueing Systems, 1993
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973