Utilization bound revisited

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

29 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)351-361
Journal / PublicationIEEE Transactions on Computers
Volume52
Issue number3
Online published10 Mar 2003
Publication statusPublished - Mar 2003
Externally publishedYes

Abstract

Utilization bound is a well-known concept introduced in the seminal paper of Liu and Layland, which provides a simple and practical way to test the schedulability of a real-time task set. The original utilization bound for the fixed-priority scheduler was given as a function of the number of tasks In the periodic task set. In this paper, we define the utilization bound as a function of the information about the task set. By making use of more than just the number of tasks, better utilization bound over the Liu and Layland bound can be achieved. We investigate in particular the bound given a set of periods for which it is still unknown if there is a polynomial algorithm for the exact bound. By investigating the relationships among the periods, we derive algorithms that yield better bounds than the Liu and Layland bound and the harmonic chain bound. Randomly generated task sets are tested against different bound algorithms. We also give a more intuitive proof of the harmonic chain bound and derive a computationally simpler algorithm.

Research Area(s)

  • Preemptive fixed-priority scheduling, Rate-monotonic priority assignment, Utilization bound

Citation Format(s)

Utilization bound revisited. / Chen, Deji; Mok, Aloysius K.; Kuo, Tei-Wei.

In: IEEE Transactions on Computers, Vol. 52, No. 3, 03.2003, p. 351-361.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review