Processor Utilization Bounds for Real-Time Systems With Precedence Constraints

This paper presents a novel approach to computing tight upper bounds on the processor utilization for general real-time systems where tasks are composed of subtasks and precedence constraints may exist among subtasks of the same task. By careful analysis of preemption effects among tasks, the problem is formulated as a set of linear programming (LP) problems. Observations are made to reduce the number of LP problem instances required to be solved, which greatly improves the computation time of the utilization bounds. Furthermore, additional constraints are allowed to be included under certain circumstances to improve the quality of the bounds.