Skip-Over: algorithms and complexity for overloaded systems that allow skips
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 110-117
- https://doi.org/10.1109/real.1995.495201
Abstract
In applications ranging from video reception to telecommunications and packet communication to aircraft control, tasks enter periodically and have fixed response time constraints, but missing a deadline is acceptable, provided most deadlines are met. We call such tasks "occasionally skippable". We look at the problem of uniprocessor scheduling of occasionally skippable periodic tasks in an environment having periodic tasks. We show that making optimal use of skips is NP-hard. We then look at two algorithms called Skip-Over Algorithms (one a variant of earliest deadline first and one of rate monotonic scheduling) that exploit skips. We give schedulability bounds for both.Keywords
This publication has 13 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
- Accounting for interrupt handling costs in dynamic priority task systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling slack time in fixed priority pre-emptive systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Dual priority schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Aperiodic task scheduling for Hard-Real-Time systemsReal-Time Systems, 1989
- A new algorithm for scheduling periodic, real-time tasksAlgorithmica, 1989
- Performance of real-time bus scheduling algorithmsACM SIGMETRICS Performance Evaluation Review, 1986
- A note on preemptive scheduling of periodic, real-time tasksInformation Processing Letters, 1980
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973