Skip-over: algorithms and complexity for overloaded systems that allow skips

Gilad Koren, Dennis Shasha

Research output: Contribution to conferencePaperpeer-review

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.

Original languageEnglish (US)
Pages110-117
Number of pages8
StatePublished - 1995
EventProceedings of the 1995 16th IEEE Real-Time Systems Symposium - Pisa, Italy
Duration: Dec 5 1995Dec 7 1995

Other

OtherProceedings of the 1995 16th IEEE Real-Time Systems Symposium
CityPisa, Italy
Period12/5/9512/7/95

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Skip-over: algorithms and complexity for overloaded systems that allow skips'. Together they form a unique fingerprint.

Cite this