TY - GEN

T1 - Towards feasible region calculus

T2 - 26th IEEE International Real-Time Systems Symposium, RTSS 2005

AU - Hawkins, William

AU - Abdelzaher, Tarek

PY - 2005/12/1

Y1 - 2005/12/1

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

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

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

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

U2 - 10.1109/RTSS.2005.42

DO - 10.1109/RTSS.2005.42

M3 - Conference contribution

AN - SCOPUS:84879352950

SN - 0769524907

SN - 9780769524900

T3 - Proceedings - Real-Time Systems Symposium

BT - Proceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005

Y2 - 5 December 2005 through 8 December 2005

ER -