Improved competitive algorithms for two-processor real-time systems

Joseph Leung

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The problem of competitive on-line scheduling in two-processor real-time environments is studied. The model of Koren and Shasha is followed: Every task has a deadline and a value that it obtains only if it completes by its deadline - the value being its computation time. The goal is to design on-line schedulers with worst-case guarantees compared with a clairvoyant scheduler. Koren and Shasha gave algorithms for the migration and no-migration models, with competitive multipliers of 2 and 3, respectively. In this article, we give an algorithm for the no-migration model with an improved competitive multiplier of 2(1+16). We also show that the competitive multiplier for the migration model can be lowered by using a fast processor and a slow processor, compared with using several parallel and identical processors with the same aggregate computing power.

Original languageEnglish (US)
Pages (from-to)733-751
Number of pages19
JournalInternational Journal of Foundations of Computer Science
Volume15
Issue number5
DOIs
StatePublished - Dec 1 2004

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Keywords

  • Competitive on-line scheduling
  • Migration
  • Parallel and identical processors
  • Preemptive scheduling
  • Real-time systems
  • Uniform processors

Fingerprint Dive into the research topics of 'Improved competitive algorithms for two-processor real-time systems'. Together they form a unique fingerprint.

Cite this