On non-utilization bounds for arbitrary fixed priority policies

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

Abstract

Prior research on schedulability bounds focused primarily on bounding utilization as a means to meet deadline constraints. Non-trivial bounds were found for a handful of scheduling policies in which utilization is directly related to the ability of the policy to meet deadlines. Examples include Rate Monotonic, Deadline Monotonic and EDF scheduling. For most other scheduling policies, however, utilization is not correlated with schedulability. For example, shortest job first can miss deadlines at an arbitrarily low utilization. This raises the question of whether or not some other non-utilization-based metric might be more indicative of schedulability in those cases. This paper answers the above question positively by extending the notion of schedulability bounds, in a uniform manner, to arbitrary priorities and non-utilization metrics. We present a simple function that generates the schedulability metric to be bounded from the definition of a (fixed-priority) scheduling policy, and derive a non-trivial schedulability bound on that metric. It is shown that the generated metrics and bounds are valid in that no deadline misses occur when these bounds are not violated. This result allows efficient real-time admission control to be performed in systems with arbitrary fixed-priority scheduling policies. As an example, we illustrate applying schedulability bounds for admission control to shortest-job-first and velocity monotonic scheduling.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium
Pages167-176
Number of pages10
DOIs
StatePublished - Oct 17 2006
Event12th IEEE Real-Time and Embedded Technology and Applications Symposium - San Jose, CA, United States
Duration: Apr 4 2006Apr 7 2006

Publication series

NameProceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
Volume2006
ISSN (Print)1545-3421

Other

Other12th IEEE Real-Time and Embedded Technology and Applications Symposium
CountryUnited States
CitySan Jose, CA
Period4/4/064/7/06

Keywords

  • Aperiodic tasks
  • Real-time scheduling
  • Schedulability analysis
  • Utilization bounds

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'On non-utilization bounds for arbitrary fixed priority policies'. Together they form a unique fingerprint.

  • Cite this

    Liu, X., & Abdelzaher, T. (2006). On non-utilization bounds for arbitrary fixed priority policies. In Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (pp. 167-176). [1613333] (Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS; Vol. 2006). https://doi.org/10.1109/RTAS.2006.32