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.
Cited By
- Combaz J, Fernandez J, Sifakis J and Strus L (2018). Symbolic quality control for multimedia applications, Real-Time Systems, 40:1, (1-43), Online publication date: 1-Oct-2008.
- Combaz J, Fernandez J, Lepley T and Sifakis J QoS control for optimality and safety Proceedings of the 5th ACM international conference on Embedded software, (90-99)
- Combaz J, Fernandez J, Lepley T and Sifakis J Fine Grain QoS Control for Multimedia Application Software Proceedings of the conference on Design, Automation and Test in Europe - Volume 2, (1038-1043)
Recommendations
Preemptive scheduling in overloaded systems
The following scheduling problem is studied: We are given a set of tasks with release times, deadlines, and profit rates. The objective is to determine a 1-processor preemptive schedule of the given tasks that maximizes the overall profit. In the ...
Skip-Over: algorithms and complexity for overloaded systems that allow skips
RTSS '95: Proceedings of the 16th IEEE Real-Time Systems SymposiumIn 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 ...