A new algorithm for scheduling periodic, real-time tasks

Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is more effective than the known Deadline Algorithm. We also give an (exponential-time) algorithm to decide if a task system is schedulable by the Slack-Time or the Deadline Algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed-priority scheduling algorithm. This resolves an open question posed by Leung and Whitehead. Finally, it is shown that the problem of deciding if a task system is schedulable by the Slack-Time, the Deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixed m≥.

Original languageEnglish (US)
Pages (from-to)209-219
Number of pages11
JournalAlgorithmica
Volume4
Issue number1
DOIs
StatePublished - Dec 1 1989

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Multiprocessor system
  • Periodic
  • Real-time tasks
  • Schedulability
  • co-NP-hard

Fingerprint

Dive into the research topics of 'A new algorithm for scheduling periodic, real-time tasks'. Together they form a unique fingerprint.

Cite this