Co-scheduling real-time tasks and non real-time tasks using empirical probability distribution of execution time requirements

We present a novel co-scheduling algorithm for real-time (RT) and non real-time response time sensitive (TS) tasks. Previous co-scheduling algorithms focussed on providing isolation to the tasks without considering the impact of scheduling of the RT tasks on the response times of the TS tasks. To best utilize the available processing capacity, the number of jobs qualifying for acceptable performance should be maximized. A good scheduling algorithm would reduce the deadline overrun times for soft real-time tasks and the response times for the TS tasks, while meeting deadline guarantees for the RT tasks. We present a formulation of optimal co-scheduling algorithm and show that such an algorithm would minimize the expected processor share of RT tasks at any instant. We propose Stochastic Processor Sharing (SPS) algorithm that uses the empirical probability distribution of execution times of the RT tasks to schedule the RT tasks such that their maximum expected processor share at any instant is minimized. We show theoretically and empirically that SPS provideds significant performance benefits in terms of reducing response times of TS jobs over current co-scheduling algorithms.