TY - GEN

T1 - Resource augmentation bounds for approximate demand bound functions

AU - Chen, Jian Jia

AU - Chakraborty, Samarjit

PY - 2011

Y1 - 2011

N2 - 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).

AB - 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).

KW - Approximate demand bound function

KW - Approximation

KW - DBF

KW - Resource augmentation

KW - Schedulability analysis

UR - http://www.scopus.com/inward/record.url?scp=84863048553&partnerID=8YFLogxK

U2 - 10.1109/RTSS.2011.32

DO - 10.1109/RTSS.2011.32

M3 - Conference contribution

AN - SCOPUS:84863048553

SN - 9780769545912

T3 - Proceedings - Real-Time Systems Symposium

SP - 272

EP - 281

BT - Proceedings - 2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011

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

Y2 - 29 November 2011 through 2 December 2011

ER -