RUN: Optimal Multiprocessor Real-Time Scheduling via Reduction to Uniprocessor
Paul Regnier, George Lima, Ernesto Massa, Greg Levin, Scott Brandt · 2011
Optimal multiprocessor real-time schedulers incur significant overhead for preemptions and migrations. We present RUN, an efficient scheduler that reduces the multiprocessor problem to a series of uniprocessor problems. RUN significantly outperforms existing optimal algorithms with an upper bound of O(log m) average preemptions per job on m processors (≤ than 3 per job in all of our simulated task sets) and reduces to Partitioned EDF whenever a proper partitioning is found.