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

William Hawkins, Tarek Abdelzaher

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005
DOIs
StatePublished - Dec 1 2005
Event26th IEEE International Real-Time Systems Symposium, RTSS 2005 - Miami, FL, United States
Duration: Dec 5 2005Dec 8 2005

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725

Other

Other26th IEEE International Real-Time Systems Symposium, RTSS 2005
CountryUnited States
CityMiami, FL
Period12/5/0512/8/05

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Towards feasible region calculus: An end-to-end schedulability analysis of real-time multistage execution'. Together they form a unique fingerprint.

  • Cite this

    Hawkins, W., & Abdelzaher, T. (2005). Towards feasible region calculus: An end-to-end schedulability analysis of real-time multistage execution. In Proceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005 [1563097] (Proceedings - Real-Time Systems Symposium). https://doi.org/10.1109/RTSS.2005.42