Combined task and message scheduling in distributed real-time systems

Tarek F. Abdelzaher, Kang G. Shin

Research output: Contribution to journalArticlepeer-review


This paper presents an algorithm for off-line scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real-time systems. Tasks are assumed to communicate via message passing based on a time-bounded communication paradigm, such as the real-time channel [1]. The algorithm uses a branch-and-bound (B&B) technique to search for a task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It generates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an extensive simulation study to evaluate the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain.

Original languageEnglish (US)
Pages (from-to)1179-1191
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
StatePublished - 1999
Externally publishedYes


  • Combined task and message scheduling
  • Deadlock
  • Distributed hard real-time systems
  • Real-time scheduling
  • Resource constraints

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Combined task and message scheduling in distributed real-time systems'. Together they form a unique fingerprint.

Cite this