Scheduling real-time systems with end-to-end timing constraints using the distributed pinwheel model

Chih Wen Hsueh, Kwei Jay Lin

Research output: Contribution to journalJournal Article peer-review

27 Scopus citations

Abstract

Real-time distributed applications have timing constraints on tasks running on several processors. To design real-time systems with end-to-end performance requirements, we need to have algorithms to schedule and to coordinate tasks on different processor nodes. In this paper, an end-to-end scheduling approach based on the pinwheel scheduling model is presented for distributed real-time systems. We show how tasks on different nodes may be transformed to have periods consisting of only harmonic numbers. With harmonic periods, we can use a polynomial-time algorithm to find the start and finish times of each task on each node. Phase alignment algorithms are then applied to adjust the phases between schedules of neighboring nodes so that the overall end-to-end delay is minimized. Using the distributed pinwheel model, schedules on different nodes are synchronized to lessen the delays. For many real-time systems, this approach provides a predictable performance and a short end-to-end delay.

Original languageEnglish
Pages (from-to)51-66
Number of pages16
JournalIEEE Transactions on Computers
Volume50
Issue number1
DOIs
StatePublished - 01 2001
Externally publishedYes

Fingerprint

Dive into the research topics of 'Scheduling real-time systems with end-to-end timing constraints using the distributed pinwheel model'. Together they form a unique fingerprint.

Cite this