Andrew Shewmaker, Carlos Maltzahn, Katia Obraczka, Scott Brandt
07/23/2014 10:29 AM
Computer Science
The RUN (Reduction to UNiprocessor) [18, 19, 13] algorithm was first described by Regnier, et al. as a novel and elegant solution to real-time multiprocessor scheduling. The first practical implementation of RUN [3] created by Compagnin, et. al., both verified the simulation results and showed that it can be efficiently implemented on top of standard operating system primitives. While RUN is now the proven best solution for scheduling fixed task sets with fixed rate on multiprocessors, further work remains to make it practical for common workloads and on resources other than CPUs.
This technical report briefly describes RUN, then out lines enhancements to enable it to support dynamic task sets, best-effort tasks, and sporadic tasks. It also examines how RUN might be adapted for use in situations involving an array of multiple resources where some form of preemptions and migrations are allowed (although must be minimized). It also describes how buffers can be sanity checked in a system where a RUN-scheduled resource is consuming data from another RUN-scheduled resource.
