Towards feasible region calculus: An end-to-end schedulability analysis of real-time multistage execution

Efficient schedulability analysis of aperiodic distributed task systems has received much less attention in real-time computing literature than its periodic counterpart. As sys-tems become larger and more complex and as workloads become less regular, simple aperiodic task analysis tech-niques 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 un-der a category of fixed-priority scheduling. It is based on a simple primitive called the generalized stage delay theo-rem 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 dimen-sion is the utilization of one resource. This volume is a gen-eralization of the notion of utilization bounds for schedu-lability 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 num-ber of concurrent infinitesimal tasks. This paper generalizes the result to arbitrary sets of finite tasks, making it applica-ble to realistic workloads. We evaluate the performance of admission control based on feasible regions using simula-tion, showing that it is successful in eliminating deadline misses