Efficient feasibility analysis of DAG scheduling with real-time constraints in the presence of faults
Xiaotong Cui, Jun Zhang, Kaijie Wu, Edwin H.‐M. Sha · 2014
Tasks in hard real-time systems are required to meet deadlines in the presence of faults. We conclude that a sufficient condition of a task set experiencing its worst-case finish time (WCFT) is that its critical task (CT) incurs all faults. An algorithm is presented to identify the CT and the WCFT in O(N2) with N being the task number. A common practice that bet the WCFT using the task with the longest re-execution time could under estimate by up-to 35%!