MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling

Gilad Koren, Dennis Shasha

Research output: Contribution to journalArticlepeer-review

Abstract

We study competitive on-line scheduling in multiprocessor real-time environments. In our model, every task has a deadline and a value that it obtains only if it completes by its deadline. A task can be assigned to any processor, all of which are equally powerful. The problem is to design an on-line scheduling algorithm (i.e. one in which the scheduler has no knowledge of a task unit it is released) with worst-case guarantees as to the total value obtained by the system. We study systems with two or more processors. We present an inherent limit on the best competitive guarantee that any on-line parallel real-time scheduler can give. Then we present a competitive algorithm that achieves a worst-case guarantee which is within a small factor from the best possible guarantee in many cases. These are the most general results yet known for competitive scheduling of multiprocessor real-time systems.

Original languageEnglish (US)
Pages (from-to)75-97
Number of pages23
JournalTheoretical Computer Science
Volume128
Issue number1-2
DOIs
StatePublished - Jun 6 1994

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling'. Together they form a unique fingerprint.

Cite this