A utilization bound for aperiodic tasks and priority driven scheduling

Tarek F. Abdelzaher, Vivek Sharma, Chenyang Lu

Research output: Contribution to journalArticlepeer-review

Abstract

Real-time scheduling theory offers constant-time schedulability tests for periodic and sporadic tasks based on utilization bounds. Unfortunately, the periodicity or the minimal interarrival-time assumptions underlying these bounds make them inapplicable to a vast range of aperiodic workloads such as those seen by network routers, Web servers, and event-driven systems. This paper makes several important contributions toward real-time scheduling theory and schedulability analysis. We derive the first known bound for schedulability of a periodic tasks. The bound is based on a utilizatio-like metric we call synthetic utilization, which allows implementing constant-time schedulability tests at admission control time. We prove that the synthetic utilization bound for deadline-monotonic scheduling of aperiodic tasks is 1/1+√1/2. We also show that no other time-independent scheduling policy can have a higher schedulability bound. Similarly, we show that EDF has a bound of 1 and that no dynamic-priority policy has higher bound. We assess the performance of the derived bound and conclude that it is very efficient in hit-ratio maximization.

Original languageEnglish (US)
Pages (from-to)334-350
Number of pages17
JournalIEEE Transactions on Computers
Volume53
Issue number3
DOIs
StatePublished - Mar 2004
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'A utilization bound for aperiodic tasks and priority driven scheduling'. Together they form a unique fingerprint.

Cite this