Skip-Over: Algorithms and Complexity for Overloaded Systems that Allow Skips

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 masking 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 10, 1996
Accession Number
AD1020232

Entities

People

  • Dennis Shasha
  • Gilad Koren

Organizations

  • Courant Institute of Mathematical Sciences, NYU

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Aircrafts
  • Algorithms
  • Biological Phenomena
  • Communication Systems
  • Ecological And Environmental Phenomena
  • Engineering
  • Environment
  • Mathematics
  • Scheduling (Production)

Fields of Study

  • Computer science

Readers

  • Artificial Intelligence
  • Mathematical Modeling and Probability Theory.
  • Parallel and Distributed Computing.