An Efficient Scheduling Algorithm for the Multiprocessor Platform

Given a task set T, determining the number of processors leading to a feasible schedule for T is an important problem in the real-time embedded systems community. For periodic and independent task sets, the utilization rate represents a lower bound on the number of processors. A multiprocessor platform with fewer processors than the utilization rate of a given task set does not have a feasible schedule. To the best of our knowledge, there is no estimation on the lower bound of the number of processors for a single-instance task set. The contribution of this paper is two-fold. Firstly, given a single-instance, non-preemptive and independent task set, we provide a lower bound on the number of processors such that there exists no feasible schedules on a multiprocessor platform with fewer processors than this lower bound. Secondly, we provide an efficient algorithm that finds a feasible schedule of a single-instance non-preemptive and independent task set on a multiprocessor platform having the number of processors equal to the lower bound.