Probabilistic performance guarantee for real-time tasks with varying computation times
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10801812) , 164-173
- https://doi.org/10.1109/rttas.1995.516213
Abstract
Describes how the scheduling algorithms and schedulability analysis methods developed for periodic tasks can be extended to provide performance guarantees to semi-periodic tasks. Like periodic tasks, the requests in a semi-periodic task are released regularly. However, their computation times vary widely. We focus on systems where the total maximum utilization of the tasks on each processor is larger than one. Hence, according to the existing schedulability conditions for periodic tasks, we cannot guarantee that the semi-periodic tasks are schedulable, even though their total average utilization is very small. We describe two methods of providing probabilistic schedulability guarantees to the semi-periodic tasks. The first method, called probabilistic time-demand analysis, is a modification of the exact schedulability test for periodic tasks. The second method, called the transform-task method, transforms each task into a periodic task followed by a sporadic task. The transform-task method can provide an absolute guarantee to requests with shorter computation times and a probabilistic guarantee to the longer requests.Keywords
This publication has 10 references indexed in Scilit:
- The rate monotonic scheduling algorithm: exact characterization and average case behaviorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On-line scheduling of hard deadline aperiodic tasks in fixed-priority systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- PERTS: A prototyping environment for real-time systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systemsReal-Time Systems, 1996
- Fixed Priority Scheduling Theory for Hard Real-Time SystemsPublished by Springer Nature ,1991
- Some Results of the Earliest Deadline Scheduling AlgorithmIEEE Transactions on Software Engineering, 1989
- Aperiodic task scheduling for Hard-Real-Time systemsReal-Time Systems, 1989
- On the complexity of fixed-priority scheduling of periodic, real-time tasksPerformance Evaluation, 1982
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973