A faster exact schedulability analysis for fixed-priority scheduling

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.03.023 Byline: Wan-Chen Lu (a), Jen-Wei Hsieh (b), Wei-Kuan Shih (a), Tei-Wei Kuo (b) Keywords: Real-time systems; Schedulability analysis; Periodic tasks; Fixed-priority preemptive scheduling Abstract: Real-time scheduling for task sets has been studied, and the corresponding schedulability analysis has been developed. Due to the considerable overheads required to precisely analyze the schedulability of a task set (referred to as exact schedulability analysis), the trade-off between precision and efficiency is widely studied. Many efficient but imprecise (i.e., sufficient but not necessary) analyses are discussed in the literature. However, how to precisely and efficiently analyze the schedulability of task sets remains an important issue. The Audsley's Algorithm was shown to be effective in exact schedulability analysis for task sets under rate-monotonic scheduling (one of the optimal fixed-priority scheduling algorithms). This paper focuses on reducing the runtime overhead of the Audsley's Algorithm. By properly partitioning a task set into two subsets and differently treating these two subsets during each iteration, the number of iterations required for analyzing the schedulability of the task set can be significantly reduced. The capability of the proposed algorithm was evaluated and compared to related works, which revealed up to a 55.5% saving in the runtime overhead for the Audsley's Algorithm when the system was under a heavy load. Author Affiliation: (a) Department of Computer Science, National Tsing Hua University, 101, Kuang Fu Road, Hsinchu 300, Taiwan, ROC (b) Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan, ROC Article History: Received 11 July 2005; Revised 16 March 2006; Accepted 18 March 2006