Uniprocessor scheduling under precedence constraints for embedded systems design
Leonardo Mangeruca, Massimo Baleani, Alberto Ferrari, Alberto Luigi Sangiovanni-Vincentelli · ACM Transactions on Embedded Computing Systems · 2007
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.