The hyperbolic schedulability bound for multiprocessor RM scheduling

Hongya Wang, Lih-Chyun Shu, Wei Yin, Jie Jin, Jiao Cao

Research output: Contribution to conferencePaper

1 Citation (Scopus)

Abstract

To verify the feasibility of real-time task sets on homogeneous multiprocessor systems, Lopez et al. derived the utilization bound based on Best Fit Decreasing allocation algorithm and Rate-Monotonic scheduling, which coincides with the maximum achievable multiprocessor utilization bound, using Liu & Lyland bound as the uniprocessor schedulability condition. In this paper, a novel feasibility test for the same target problem is developed based on the hyperbolic bound due to Bini et al., instead of the Liu & Layland bound. 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 increase the number of schedulable task sets with little extra overhead.

Original languageEnglish
Pages124-133
Number of pages10
DOIs
Publication statusPublished - 2012 Dec 1
Event18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012 - Seoul, Korea, Republic of
Duration: 2012 Aug 192012 Aug 22

Other

Other18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012
CountryKorea, Republic of
CitySeoul
Period12-08-1912-08-22

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition

Cite this

Wang, H., Shu, L-C., Yin, W., Jin, J., & Cao, J. (2012). The hyperbolic schedulability bound for multiprocessor RM scheduling. 124-133. Paper presented at 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012, Seoul, Korea, Republic of. https://doi.org/10.1109/RTCSA.2012.29