loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
26th IEEE International Real-Time Systems Symposium (RTSS'05)
Towards Feasible Region Calculus: An End-to-End Schedulability Analysis of Real-Time Multistage Execution
Miami, Florida
December 05-December 08
ISBN: 0-7695-2490-7
William Hawkins, University of Illinois at Urbana-Champaign
Tarek Abdelzaher, University of Illinois at Urbana-Champaign
Efficient schedulability analysis of aperiodic distributed task systems has received much less attention in real-time computing literature than its periodic counterpart. As systems become larger and more complex and as workloads become less regular, simple aperiodic task analysis techniques are needed to accommodate unpredictability and scale, while erring on the safe side. This paper presents a simple analytic framework for computing the end-to-end feasibility regions of distributed aperiodic task systems under a category of fixed-priority scheduling. It is based on a simple primitive called the generalized stage delay theorem that expresses the maximum fraction of the end-to-end deadline that a task can spend at a resource as a function of the (instantaneous or synthetic) utilization of that resource. For the task to meet its end-to-end deadline, the sum of such fractions must be less than 1. This constraint identifies a volume in a multidimensional space in which each dimension is the utilization of one resource. This volume is a generalization of the notion of utilization bounds for schedulability in single-resource systems. It extends the bound (a uni-dimensional schedulable region) to a multi-dimensional representation for distributed-resource systems. Prior work identified this volume for the special case of an infinite number of concurrent infinitesimal tasks. This paper generalizes the result to arbitrary sets of finite tasks, making it applicable to realistic workloads. We evaluate the performance of admission control based on feasible regions using simulation, showing that it is successful in eliminating deadline misses.
Citation:
William Hawkins, Tarek Abdelzaher, "Towards Feasible Region Calculus: An End-to-End Schedulability Analysis of Real-Time Multistage Execution," rtss, pp.75-86, 26th IEEE International Real-Time Systems Symposium (RTSS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.