The granularity metric for fine-grain real-time scheduling

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


This paper investigates the task scheduling problem for real-time systems that provide rate of progress guarantees on task execution. A parameterized task system model, called the (r, g) task system, is introduced that allows rate of progress requirements to be specified in terms of two simple parameters: an execution rater r and a granularity g. The granularity parameter is a new metric that allows the specification of "line-grain" timing constraints on the task's execution and is a generalization of the stretch metric used in recent research on task scheduling. It is shown that the product rlg(1/g) is an important determiner of the existence of good online scheduling algorithms. Specifically, there is an upper bound on this product above which there are no good online algorithms, but below which an online algorithm with logarithmic competitive ratio exists. This paper also demonstrates a fundamental difference between two contrasting strategies for admission control: greedy versus nongreedy. It is shown that "greed does not pay": there is a scheduling algorithm with a nongreedy admission policy that provably outperforms the well-known Greedy EDF scheduling algorithm.

Original languageEnglish (US)
Pages (from-to)1572-1583
Number of pages12
JournalIEEE Transactions on Computers
Issue number12
StatePublished - Dec 2005

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Online algorithms
  • Quality of service provisioning
  • Real-time systems
  • Scheduling


Dive into the research topics of 'The granularity metric for fine-grain real-time scheduling'. Together they form a unique fingerprint.

Cite this