A HYBRID TEST FOR FASTER FEASIBILITY ANALYSIS OF PERIODIC TASKS

作者：Min Allah Nasro^*; Khan Samee Ullah

来源：International Journal of Innovative Computing Information and Control, 2011, 7(10): 5689-5698.

• Real-time systems
• Fixed-priority scheduling
• Feasibility analysis
• Online schedulability test

In this paper, the issue of impracticality of testing the feasibility of periodic tasks at run time is studied. We provide an exact test, which is a hybrid solution obtained through both inexact (sufficient but not necessary) and exact (necessary and sufficient) schedulability tests. The task set is divided into two subsets such that (a) all tasks in the first group can be scheduled and the feasibility of this part is tested by the inexact test, while (b) the feasibility of the second group that consists of both schedulable and un-schedulable tasks is determined by the exact test. The proposed test outperforms existing alternatives from the perspective of execution time, and becomes an ideal candidate for determining feasibility of online systems. In addition, two well-known bounds, namely LL-bound and H-bound, are compared and it is proved that the H-bound is always true when the LL-bound holds.

• 出版日期2011-10