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

Gilad Koren, Dennis Shasha

Research output: Contribution to journalArticlepeer-review


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
Issue number1-2
StatePublished - Jun 6 1994

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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