Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platforms

Given a collection of recurring tasks or processes that comprise a real-time system, and a collection of available processing units of different kinds upon which to execute them, the heterogeneous multiprocessor feasibility problem is concerned with determining whether the given tasks can be executed on the available processing units in such a manner that all timing constraints are met. A preemptive scheduling model is assumed. Under the partitioned scheduling paradigm - each task may execute on only one processor - this problem has previously been shown to be intractable. Under the global scheduling paradigm, however, a polynomial-time algorithm for heterogeneous multiprocessor feasibility analysis is presented here, and proved correct. An upper bound is derived upon the number of tasks that need to be executed upon multiple processors: even in the worst case, it is shown that this number is reasonable small (of the order of the number of processors), implying that the benefits of global scheduling are available without requiring that too many tasks be forced to execute on multiple processors.