Hyperbolic utilization bounds for rate monotonic scheduling on homogeneous multiprocessors

Hongya Wang, Lih Chyun Shu, Wei Yin, Yingyuan Xiao, Jiao Cao

研究成果: Article同行評審

8 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)1510-1521
期刊IEEE Transactions on Parallel and Distributed Systems
出版狀態Published - 2014 6月

All Science Journal Classification (ASJC) codes

  • 訊號處理
  • 硬體和架構
  • 計算機理論與數學


深入研究「Hyperbolic utilization bounds for rate monotonic scheduling on homogeneous multiprocessors」主題。共同形成了獨特的指紋。