Fork-Join实时任务图模型的NP-hardness与可调度算法研究

本文档深入探讨了Fork-Join（FJ）实时任务图模型在实际应用中的可行性，特别是在调度复杂性方面。首先，作者关注于实时系统分析中的两个关键主题：分支代码建模和任务内部并行结构建模。FJ模型结合了这两个特性，将传统的有向图任务模型扩展到支持并发的fork（分支）和join（合并）操作。 核心研究内容聚焦于FJ实时任务模型在预抢占单处理器环境下的可调度性问题。作者证明了一个重要的理论结果，即对于FJ模型的 earliest deadline first (EDF) 调度策略，即使任务系统的利用率被严格限制在一个常数小于1的范围内，该问题依然属于强NP-hard问题。这表明，在一般情况下，解决这个问题的困难程度极高，不容易找到有效的全局最优解。 然而，文章并未止步于负面结论，而是进一步探讨了通过施加特定的结构限制来提升问题的可处理性。作者提出，当任务中的并行部分受到某些约束时，调度问题变得可计算，即可以通过一种具有伪多项式时间复杂度的精确调度测试来解决。这意味着，尽管整体上问题很硬，但在某些特定条件下，我们能够找到相对高效的方法。 因此，这项研究为FJ实时任务图模型的可行性和算法设计提供了一条边界线，即在保持模型表达力的同时，如何通过适当的结构调整和优化策略来降低调度问题的复杂性。这对于理解和设计实时系统的调度算法具有重要的理论价值，也为工程实践中如何选择合适的模型和方法提供了指导。