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)