Reducing preemptions and migrations in EKG

EKG is a multiprocessor scheduling algorithm which is optimal for the scheduling of real-time periodic tasks with implicit deadlines. It consists in a semi-partitioned algorithm which adheres to the deadline partitioning fair (DP-Fair) theory. It was shown in recent studies that the division of the time in slices bounded by two successive deadlines and the systematic execution of migratory tasks in each time slice inherent in DP-Fair algorithms, significantly reduce the practicality of EKG. Nevertheless, its semi-partitioned approach allows to bound the number of migrating tasks and increases the locality of the tasks in memories, thereby lowering the time overheads imposed by task preemptions and migrations. Hence, we propose two techniques with the aim of reducing the amount of preemptions and migrations incurred by the system when scheduled with EKG, while maintaining the advantages of its semi-partitioned approach. The first improvement consists in a swapping algorithm which exchanges execution time between tasks and time slices. The second one aims at decreasing the number of time slices needed to ensure that all job deadlines are respected. Both have a strong impact on the number of preemptions and migrations while keeping the optimality of EKG.