Uniprocessor Scheduling Under Precedence Constraints for Embedded Systems Design

摘要

In this paper, we present a novel approach to the constrained scheduling problem, while addressing a more general class of constraints that arise from the timing requirements on real-time embedded controllers. We provide general necessary and sufficient conditions for scheduling under precedence constraints and derive sufficient conditions for two well-known scheduling policies. We define mathematical problems that provide optimum priority and deadline assignments, while ensuring both precedence constraints and system's schedulability. We show how these problems can be relaxed to corresponding integer linear programming (ILP) formulations leveraging on available solvers. The results are demonstrated on a real design case.