Utilization bound re-visited

Utilization bound is a well-known concept first introduced in the seminal paper of Liu and Layland (1973) which provides a simple and practical way to test the schedulability of a real-time task set. The original utilization bound for the fixed-priority scheduler was given as a function of the number of tasks in the periodic task set. We define the utilization bound as a function of the information about the task set. By making use of more than just the number of tasks, we obtain various improvements over the Liu and Layland bound. In particular, we give a more intuitive derivation of the bound as a function of the number of harmonic chains in the task periods which allows us to derive a simpler algorithm to calculate such bounds. We derive algorithms that yield better bounds as a function of the period parameters of the task set. We also give a generalization of the bound for tasks whose deadlines are smaller than their periods.