Files in this item



application/pdfTransforming Di ... -Preemptive Scheduling.pdf (211kB)
(no description provided)PDF


Title:Transforming Distributed Acyclic Systems into Equivalent Uniprocessors Under Preemptive and Non-Preemptive Scheduling
Author(s):Jayachandran, Praveen; Abdelzaher, Tarek F.
Subject(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.
Issue Date:2007-10
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2007-2906
Rights 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).
Date Available in IDEALS:2009-04-22

This item appears in the following Collection(s)

Item Statistics