Track: Operations Research

Abstract

This paper presents a method of scheduling tasks of a closed loop control system on multi-core systems using historical statistics - mean run-time and standard-deviation in run-times - of the tasks. The run-time statistics is used to first predictively and then to reactively schedule the tasks in order to minimize the makespan. The predicted schedule is a list of tasks ordered by a function of mean and standard deviation, to be executed on each core. Reactive scheduling involves periodically probing the progress and reacting to imbalances in progress across the cores by altering the schedule. It is shown that, when the tasks have high variance in run-times, this method results in smaller makespan compared to a non-reactive scheduler using plain heuristics. This method also performs better than the default Linux OS task scheduler for such tasks. 9% improvement in makespan over OS task scheduler is noticed for a workload comprising of 1100+ CPU intensive tasks with high standard deviations in run-times on a 20-core system.