TY - JOUR

T1 - Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks

AU - Chen, Jian Jia

AU - Chakraborty, Samarjit

N1 - Funding Information:
Acknowledgements This work was partially supported by Baden Württemberg MWK Juniorprofessoren-Programms. We also thank the anonymous reviewers for their valuable feedback in helping improve this paper.

PY - 2013/7

Y1 - 2013/7

N2 - Although the earliest-deadline-first (EDF) policy is known to be optimal for preemptive real-time task scheduling in uniprocessor systems, the schedulability analysis problem has recently been shown to be coNP-hard. Therefore, approximation algorithms, and in particular, approximations based on resource augmentation have attracted a lot of attention for both uniprocessor and multiprocessor systems. Resource augmentation based approximations assume a certain speedup of the processor(s). Using the notion of approximate demand bound function (dbf), in this paper we show that for uniprocessor systems the resource augmentation factor is at most 2e-1/e ≈ 1.6322, where e is the Euler number. We approximate the dbf using a linear approximation when the analysis interval length of interest is larger than the relative deadline of the task. For identical multiprocessor systems with M processors and constrained-deadline task sets, we show that the deadline-monotonic partitioning (that has been proposed by Baruah and Fisher) with the approximate dbf leads to an approximation factor of 3e-1/e-1/M ≈ 2.6322-1/M with respect to resource augmentation. We also show that the corresponding factor is 3-1/M for arbitrary-deadline task sets. The best known results so far were 3-1/M for constrained-deadline tasks and 4-2/M for arbitrary-deadline ones. Our tighter analysis exploits the structure of the approximate dbf directly and uses the processor utilization violations (which were ignored in all previous analysis) for analyzing resource augmentation factors. We also provide concrete input instances to show that the lower bound on the resource augmentation factor for uniprocessor systems - using the above approximate dbf - is 1.5, and the corresponding bound is 2.5 for identical multiprocessor systems with an arbitrary order of fitting and a large number of processors. Further, we also provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions under the assumption that the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant, which is a more relaxed assumption compared to the assumptions required for deriving such a PTAS in the past.

AB - Although the earliest-deadline-first (EDF) policy is known to be optimal for preemptive real-time task scheduling in uniprocessor systems, the schedulability analysis problem has recently been shown to be coNP-hard. Therefore, approximation algorithms, and in particular, approximations based on resource augmentation have attracted a lot of attention for both uniprocessor and multiprocessor systems. Resource augmentation based approximations assume a certain speedup of the processor(s). Using the notion of approximate demand bound function (dbf), in this paper we show that for uniprocessor systems the resource augmentation factor is at most 2e-1/e ≈ 1.6322, where e is the Euler number. We approximate the dbf using a linear approximation when the analysis interval length of interest is larger than the relative deadline of the task. For identical multiprocessor systems with M processors and constrained-deadline task sets, we show that the deadline-monotonic partitioning (that has been proposed by Baruah and Fisher) with the approximate dbf leads to an approximation factor of 3e-1/e-1/M ≈ 2.6322-1/M with respect to resource augmentation. We also show that the corresponding factor is 3-1/M for arbitrary-deadline task sets. The best known results so far were 3-1/M for constrained-deadline tasks and 4-2/M for arbitrary-deadline ones. Our tighter analysis exploits the structure of the approximate dbf directly and uses the processor utilization violations (which were ignored in all previous analysis) for analyzing resource augmentation factors. We also provide concrete input instances to show that the lower bound on the resource augmentation factor for uniprocessor systems - using the above approximate dbf - is 1.5, and the corresponding bound is 2.5 for identical multiprocessor systems with an arbitrary order of fitting and a large number of processors. Further, we also provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions under the assumption that the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant, which is a more relaxed assumption compared to the assumptions required for deriving such a PTAS in the past.

KW - Approximate demand bound function

KW - Approximation

KW - DBF

KW - PTAS

KW - Resource augmentation

KW - Schedulability analysis

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

U2 - 10.1007/s11241-013-9181-5

DO - 10.1007/s11241-013-9181-5

M3 - Article

AN - SCOPUS:84878785279

SN - 0922-6443

VL - 49

SP - 475

EP - 516

JO - Real-Time Systems

JF - Real-Time Systems

IS - 4

ER -