REAL-TIME DISPATCHING: SCHEDULING STABILITY AND PRECEDENCE

This paper introduces a new graph theoretical concept called strong precedence which is used to address the problem of scheduling instability is non-preemptive static list scheduling. Scheduling instability occurs when a reduction in task duration of one or more tasks causes other tasks to miss their deadline. This problem has been addressed in the past by introducing additional precedence constraints into the precedence graph representing the workload, or by limiting the depth the dispatchers scan at run-time. We present an alternative stabilization approach based on the concept of strong and weak precedence. By defining a strong precedence relation on selected subgraphs, the workload becomes inherently stable without requiring the introduction of new edges into the graph.