A faster exact schedulability analysis for fixed-priority scheduling

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

7 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)1744-1753
Journal / PublicationJournal of Systems and Software
Volume79
Issue number12
Online published4 May 2006
Publication statusPublished - Dec 2006
Externally publishedYes

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.

Research Area(s)

  • Fixed-priority preemptive scheduling, Periodic tasks, Real-time systems, Schedulability analysis

Citation Format(s)

A faster exact schedulability analysis for fixed-priority scheduling. / Lu, Wan-Chen; Hsieh, Jen-Wei; Shih, Wei-Kuan et al.

In: Journal of Systems and Software, Vol. 79, No. 12, 12.2006, p. 1744-1753.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review