TY - GEN

T1 - On non-utilization bounds for arbitrary fixed priority policies

AU - Liu, Xue

AU - Abdelzaher, Tarek

PY - 2006/10/17

Y1 - 2006/10/17

N2 - Prior research on schedulability bounds focused primarily on bounding utilization as a means to meet deadline constraints. Non-trivial bounds were found for a handful of scheduling policies in which utilization is directly related to the ability of the policy to meet deadlines. Examples include Rate Monotonic, Deadline Monotonic and EDF scheduling. For most other scheduling policies, however, utilization is not correlated with schedulability. For example, shortest job first can miss deadlines at an arbitrarily low utilization. This raises the question of whether or not some other non-utilization-based metric might be more indicative of schedulability in those cases. This paper answers the above question positively by extending the notion of schedulability bounds, in a uniform manner, to arbitrary priorities and non-utilization metrics. We present a simple function that generates the schedulability metric to be bounded from the definition of a (fixed-priority) scheduling policy, and derive a non-trivial schedulability bound on that metric. It is shown that the generated metrics and bounds are valid in that no deadline misses occur when these bounds are not violated. This result allows efficient real-time admission control to be performed in systems with arbitrary fixed-priority scheduling policies. As an example, we illustrate applying schedulability bounds for admission control to shortest-job-first and velocity monotonic scheduling.

AB - Prior research on schedulability bounds focused primarily on bounding utilization as a means to meet deadline constraints. Non-trivial bounds were found for a handful of scheduling policies in which utilization is directly related to the ability of the policy to meet deadlines. Examples include Rate Monotonic, Deadline Monotonic and EDF scheduling. For most other scheduling policies, however, utilization is not correlated with schedulability. For example, shortest job first can miss deadlines at an arbitrarily low utilization. This raises the question of whether or not some other non-utilization-based metric might be more indicative of schedulability in those cases. This paper answers the above question positively by extending the notion of schedulability bounds, in a uniform manner, to arbitrary priorities and non-utilization metrics. We present a simple function that generates the schedulability metric to be bounded from the definition of a (fixed-priority) scheduling policy, and derive a non-trivial schedulability bound on that metric. It is shown that the generated metrics and bounds are valid in that no deadline misses occur when these bounds are not violated. This result allows efficient real-time admission control to be performed in systems with arbitrary fixed-priority scheduling policies. As an example, we illustrate applying schedulability bounds for admission control to shortest-job-first and velocity monotonic scheduling.

KW - Aperiodic tasks

KW - Real-time scheduling

KW - Schedulability analysis

KW - Utilization bounds

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

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

U2 - 10.1109/RTAS.2006.32

DO - 10.1109/RTAS.2006.32

M3 - Conference contribution

AN - SCOPUS:33749601273

SN - 0769525164

SN - 9780769525167

T3 - Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS

SP - 167

EP - 176

BT - Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium

T2 - 12th IEEE Real-Time and Embedded Technology and Applications Symposium

Y2 - 4 April 2006 through 7 April 2006

ER -