Generalized Utilization Bounds for Fixed Priority Scheduling

The essence of real-time computing is to bring the semantics of real time ( time in the real world ) to digital computing, so that the software actions can confrom to their (real) timing requirements. It is cost prohibitive to associate every computer instruction with a time stamp and therefore real time management of software is usually done at process level, controlled by the scheduler of the operating system. A critical requirement of real time scheduling scheme is the need for extremely low scheduling overhead at run time. And therefore, an admission control strategy based on schedulability analysis is commonly used to determine whether or not the system can serve a new real time task. Because of its extremely low computing cost at run time, processor utilization is the most commonly used admission criterion, but one must first prove mathematically the schedulability (utilization) bound is guaranteed. Many schedulability bounds have been derived for different schedulers since the seminal work on the utilization bound of the periodic tasks by Liu and Layland. These results are derived based on different techniques and there is no easy way to determine their relationship.

In a recent work, we took the network calculus workload representation model to derive a general expression for a broad range of fixed priority schedulers.

The k and η represent normalized deadline and workload heterogeneity of the workload, and n is the number of tasks. This parameterized expression defines a solution space. By simple assignment of proper parameter values of this expression, one can arrive at several well known utilization bounds obtained in the past two decades. Their relationship is depicted in the following figure. Our bound expression is depicted by the grid curves stretching in a waterfall shape, and all existing solutions fall on different points of the sheet.