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

Gilad Koren, Dennis Shasha, Shih Chen Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 until 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. The models are a distributed system having a centralized scheduler as well as a shared memory multiprocessor.

Original languageEnglish (US)
Title of host publicationProceedings - Real-Time Systems Symposium
Editors Anon
PublisherPubl by IEEE
Pages172-181
Number of pages10
ISBN (Print)081864480X
StatePublished - 1993
EventProceedings of the Real- Time Systems Symposium - Durham, NC, USA
Duration: Dec 1 1993Dec 3 1993

Publication series

NameProceedings - Real-Time Systems Symposium

Other

OtherProceedings of the Real- Time Systems Symposium
CityDurham, NC, USA
Period12/1/9312/3/93

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

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