Multiprocessor preprocessing algorithms for uniprocessor on-line scheduling

Chetto & Chetto [3] presented an algorithm for the online admission control and run-time scheduling of aperiodic real-time jobs in preemptive uniprocessor environments that are executing systems of periodic hard-real-time tasks. This algorithm requires a significant degree of preprocessing of the system of periodic tasks - in general, this preprocessing takes time exponential in the representation of the periodic task system. In this paper, we develop techniques for speeding up the preprocessing phase of the Chetto & Chetto algorithm, by adapting it for implementation in parallel environments. We validate the effectiveness of our parallelization both by theoretical results, and through is simulation experiments.