Resource augmentation bounds for approximate demand bound functions

Jian Jia Chen, Samarjit Chakraborty

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

30 Scopus citations


In recent work, approximation of the demand bound function for a sporadic task uses a linear approximation when the interval length of interest is larger than the relative deadline of the task. Such an approximation leads to a factor 2 for resource augmentation under a naïve analysis, i.e., if the schedulability test using this approximate demand bound function fails, the task set is not schedulable by slowing down the system to 50% of the original speed. In this paper we provide a tighter analysis of such an approach on uniprocessor systems and on identical multiprocessor systems with partitioned scheduling under the earliestdeadline-first strategy. For uniprocessor systems, we prove that the resource augmentation factor is at most 2e-1/e ≈ 1.6322, where e is the Euler number. For identical multiprocessor systems with M processors, with respect to resource augmentation, we show that deadline-monotonic partitioning with approximate demand bound functions leads to a factor 3e-1/e - 1/M ≈ 2.6322 - 1/M for constrained-deadline task sets and a factor 3 - 1/M for arbitrarydeadline task sets, in which the best results known so far are 3 - 1/M for constrained-deadline ones and 4 - 2/M for arbitrarydeadline ones. Moreover, we also provide concrete input instances to show that the lower bound of resource augmentation factors for uniprocessor systems (identical multiprocessor systems under an arbitrary order of fitting and a large number of processors, respectively) under such approaches is 1.5 (2.5, respectively).

Original languageEnglish
Title of host publicationProceedings - 2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011
Number of pages10
StatePublished - 2011
Event2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011 - Vienna, Austria
Duration: 29 Nov 20112 Dec 2011

Publication series

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


Conference2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011


  • Approximate demand bound function
  • Approximation
  • DBF
  • Resource augmentation
  • Schedulability analysis


Dive into the research topics of 'Resource augmentation bounds for approximate demand bound functions'. Together they form a unique fingerprint.

Cite this