Hyperbolic utilization bounds for rate monotonic scheduling on homogeneous multiprocessors

The utilization bounds for partitioned multiprocessor scheduling are a function of task allocation algorithms and the schedulability conditions selected for uniprocessor scheduling algorithms. In this paper, we use rate-monotonic scheduling on each processor and present the lower and upper limits of the utilization bounds for all reasonable task allocation heuristics. Unlike previous work, the hyperbolic bound due to Bini, instead of the Liu & Layland bound, is adopted to do the schedulability test on uniprocessors. We also derive the utilization bounds with respect to the worst fit allocation algorithm and reasonable allocation decreasing heuristics, and the two bounds are found to coincide with the worst and best achievable multiprocessor utilization bounds, respectively. Analytical and experimental results show that the proposed utilization bound performs better than the existing bound under quite a lot of parameter settings, and combining these two bounds together can significantly (up to 3 times) increase the number of schedulable task sets with little extra overhead.