A dynamic scheduling algorithm for semi-hard real-time environments

In many real-time systems, it is crucial for the application tasks to meet their specified deadlines, otherwise the tasks cause catastrophic results. Every task is generally periodic, and the value of its period depends on the dynamics of the process it controls. In addition, some additional time-critical tasks said to be sporadic can occur and require to be processed at unpredictable times. The paper examines the fundamental problem of scheduling a given set of periodic tasks, together with sporadic tasks on a uniprocessor machine. More precisely, we are concerned with the dynamic problem arising when a sporadic task occurs, which starts to execute it as soon as possible while adhering to timing constraints of periodic tasks. First, we report on theoretical properties of the preemptive Earliest Deadline algorithm and describe an online scheduling strategy which is both optimal and easy to implement. Then, we show how this strategy could be integrated in a distributed scheduler: when a sporadic task arrives on a node, either this task is executed locally or migrates to another node which provides it with the best response time