Feasibility of Fork-Join Real-Time Task Graph Models

• DOI: 10.1145/2809780
• Publication Date: 2016-02-22T13:07:16Z
• Authors: Jinghao Sun; Nan Guan; Yang Wang; Qingxu Deng; Peng Zeng; Wang Yi
• Keywords: Uniprocessor system; Fork (system call); Digraph; Worst-case execution time

In the formal analysis of real-time systems, modeling branching codes and intratask parallelism structures are two most important research topics. These properties combined, resulting in fork-join task (FJRT) model, which extends digraph-based model with forking joining semantics. We prove that EDF schedulability problem on a preemptive uniprocessor for FJRT is coNP-hard strong sense, even if utilization system bounded by constant strictly less than 1. Then, we show becomes tractable some slight structural restrictions parallel sections, propose an exact test pseudo-polynomial time complexity. Our results thus establish borderline between intractable models.