TY - GEN

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

AU - Jayachandran, Praveen

AU - Abdelzaher, Tarek

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=52049109824&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52049109824&partnerID=8YFLogxK

U2 - 10.1109/ECRTS.2008.31

DO - 10.1109/ECRTS.2008.31

M3 - Conference contribution

AN - SCOPUS:52049109824

SN - 9780769532981

T3 - Proceedings - Euromicro Conference on Real-Time Systems

SP - 233

EP - 242

BT - Proceedings of the 20th Euromicro Conference on Real-Time Systems, ECRTS 2008

T2 - 20th Euromicro Conference on Real-Time Systems, ECRTS 2008

Y2 - 2 July 2008 through 4 July 2008

ER -