带时间约束实时任务图模型上可调度性分析算法研究

The digraph real-time task with timing constraints (TCDRT) is one of the most expressiveness models in real-time community, but its corresponding schedulability analysis (SA) is strongly NP-hard problem. Present researchers focus on a tractable TCDRT model where the number of constraints is bounded by a constant K, and the only known method for the TCDRT model uses a transformation into an equivalent DRT model, which leads to a high complexity that is exponential in the width of the constraints. This work analyzes the schedulability of the TCDRT model directly in order to achieve a much lower complexity. First, we propose a dynamic program to deal with the demand bound computation problem for the K-bounded TCDRT case and refine the complexity result to a better bound that has no relation with the width of constraints. Second, we prove that the schedulability of bound T can be computed within a pseudo-polynomial time, and the corresponding computation complexity is drastically linear in K instead of being exponential. Furthermore, our approach also indicates another tractable TCDRT model that is not necessary to postulate the K-bounded constraints.