Reduction-based schedulability analysis of distributed systems with cycles in the task graph

作     者：Jayachandran, Praveen Abdelzaher, Tarek 

作者机构：Univ Illinois Dept Comp Sci Urbana IL 61801 USA 

出 版 物：《REAL-TIME SYSTEMS》 (实时系统)

年 卷 期：2010年第46卷第1期

页      面：121-151页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CNS 05-53420, CNS 06-13665, CNS 07-20513] ONR [N00014-10-1-0172] 

主　　题：Schedulability analysis End-to-end delay Real-time distributed system Non-acyclic systems Problem reduction 

摘      要：A significant problem with no simple solutions in current real-time literature is analyzing the end-to-end schedulability of tasks in distributed systems with cycles in the task graph. Prior approaches including network calculus and holistic schedulability analysis work best for acyclic task flows. They involve iterative solutions or offer no solutions at all when flows are non-acyclic. This paper demonstrates the construction of the first generalized closed-form expression for schedulability analysis in distributed task systems with non-acyclic flows. The approach is a significant extension to our previous work on schedulability in Directed Acyclic Graphs. Our main result is a bound on end-to-end delay for a task in a distributed system with non-acyclic task flows. The delay bound allows one of several schedulability tests to be performed. Using the end-to-end delay bound, we extend the delay composition algebra developed for acyclic distributed systems in prior work, to handle loops in the task graph as well. Evaluation shows that the schedulability tests thus constructed are less pessimistic than prior approaches for large distributed systems.