Transforming Distributed Acyclic Systems into Equivalent Uniprocessors Under Preemptive and Non-Preemptive Scheduling

Jayachandran, Praveen; Abdelzaher, Tarek F.

Permalink

https://hdl.handle.net/2142/11400 Copy

Description

Title

Transforming Distributed Acyclic Systems into Equivalent Uniprocessors Under Preemptive and Non-Preemptive Scheduling

Author(s)

• Jayachandran, Praveen
• Abdelzaher, Tarek F.

Issue Date

2007-10

Keyword(s)

distributed systems

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 schedulability analysis techniques. Towards such a theory, in this paper, we extend our previous result on pipeline delay composition to the general case of distributed acyclic systems as well as to non-preemptive scheduling. 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 a distributed system described by a Directed Acyclic Graph (DAG). The bound is computed as a function of graph topology and resource sharing policies on different resources. Our composition rule permits a simple transformation 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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11400

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections