Transforming distributed acyclic systems into equivalent uniprocessors under preemptive and non-preemptive scheduling

Praveen Jayachandran, Tarek Abdelzaher

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

Abstract

Many scientific disciplines provide composition primitives whereby overall properties of systems are composed from those of their components. Examples include rules for block diagram reduction in control theory and laws for computing equivalent circuit impedance in circuit theory. No general composition rules exist for real-time systems whereby a distributed system is transformed to an equivalent single stage analyzable using traditional uniprocessor schedulabil-ity analysis techniques. Towards such a theory, in this paper, we extend our previous result on pipeline delay composition for preemptive and non-preemptive scheduling to the general case of distributed acyclic systems. Acyclic systems are defined as those where the superposition of all task flows gives rise to a Directed Acyclic Graph (DAG). The new extended analysis provides a worst-case bound on the end-to-end delay of a job under both preemptive as well as non-preemptive scheduling, in the distributed system. A simple transformation is then shown of the distributed task system into an equivalent uniprocessor task-set analyzable using traditional uniprocessor schedulability analysis. Hence, using the transformation described in this paper, the wealth of theory available for uniprocessor schedulability analysis can be easily applied to a larger class of distributed systems.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Euromicro Conference on Real-Time Systems, ECRTS 2008
Pages233-242
Number of pages10
DOIs
StatePublished - 2008
Event20th Euromicro Conference on Real-Time Systems, ECRTS 2008 - Prague, Czech Republic
Duration: Jul 2 2008Jul 4 2008

Publication series

NameProceedings - Euromicro Conference on Real-Time Systems
ISSN (Print)1068-3070

Other

Other20th Euromicro Conference on Real-Time Systems, ECRTS 2008
Country/TerritoryCzech Republic
CityPrague
Period7/2/087/4/08

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Transforming distributed acyclic systems into equivalent uniprocessors under preemptive and non-preemptive scheduling'. Together they form a unique fingerprint.

Cite this