JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]


Journal of Information Science and Engineering, Vol. 34 No. 2, pp. 319-335


Efficient Optimal Priority Assignment for Fixed Priority Preemption Threshold Scheduling


SAEHWA KIM
Department of Information Communications Engineering
Hankuk University of Foreign Studies
Gyeonggi-do, 449-791 Korea
E-mail:
ksaehwa@hufs.ac.kr


    This paper proposes an efficient priority assignment algorithm for fixed priority preemption threshold scheduling (PTS), which we named FAST-TRAVERSE. It is optimal in the sense that it always finds a feasible priority assignment if one exists. While there are existing optimal algorithms, they are inefficient to be used in practice. The key ideas of FAST-TRAVERSE are to prune sibling traverses and preemption threshold assignments if possible based on the notion of the effective blocking task. The empirical evaluation results clearly show that FAST-TRAVERSE achieves the largest feasibility and can be employed as an on-line priority assignment algorithm for PTS.


Keywords: real-time systems and embedded systems, system integration and implementation, real-time feasibility, scalability, fixed-priority scheduling

  Retrieve PDF document (JISE_201802_01.pdf)