On Non-Utilization Bounds for Arbitrary Fixed Priority Policies

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-jobfirst and velocity monotonic scheduling.